Component bdlcc_stripedunorderedmap [Package bdlcc]

Provide a bucket-group locking (i.e., striped) unordered map. More...

Namespaces
namespace	bdlcc

---

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Thread Safety
  • Runtime Complexity
  • Number of Stripes
  • Set vs. Insert Methods
  • Rehash
    • Concurrent Rehash
    • Rehash Control
  • Usage
    • Example 1: Basic Usage
    • Example 2: Track Stats
    • Example 3: Visiting all the Container Elements

Purpose:

Provide a bucket-group locking (i.e., striped) unordered map.

Classes:

bdlcc::StripedUnorderedMap

Striped hash map

See also:

Component bdlcc_stripedunorderedmultimap, Component bdlcc_stripedunorderedcontainerimpl

Description:

This component provides a single concurrent (fully thread-safe) associative container, bdlcc::StripedUnorderedMap, that partitions the underlying hash table into a (user defined) number of "bucket groups" and controls access to each bucket group by a separate read-write lock. This design allows greater concurrency (and improved performance) than a bsl::unordered_map object protected by a single lock.

The terms "bucket", "load factor", and "rehash" have the same meaning as they do in the bslstl_unorderedmap component (see bslstl_unorderedmap|Unordered Map Configuration). A general introduction to these ideas can be found at: https://en.wikipedia.org/wiki/Hash_table

bdlcc::StripedUnorderedMap (and concurrent containers in general) does not provide iterators that allow users to manipulate or traverse the values of elements in a map. Alternatively, this container provides the setComputedValue method that allows users to change the value for a given key via a user provided functor and the visit method that will apply a user provided functor the value of every key in the map.

The bdlcc::StripedUnorderedMap class is an irregular value-semantic type, even if KEY and VALUE are VSTs. This class does not implement equality comparison, assignment operator, or copy constructor.

Thread Safety:

The bdlcc::StripedUnorderedMap class template is fully thread-safe (see bsldoc_glossary|Fully Thread-Safe), assuming that the allocator is fully thread-safe. Each method is executed by the calling thread.

Runtime Complexity:

  +----------------------------------------------------+--------------------+
  | Operation                                          | Complexity         |
  +====================================================+====================+
  | insert, setValue, setComputedValue, update         | Average: O[1]      |
  |                                                    | Worst:   O[n]      |
  +----------------------------------------------------+--------------------+
  | erase, getValue                                    | Average: O[1]      |
  |                                                    | Worst:   O[n]      |
  +----------------------------------------------------+--------------------+
  | visit(key, visitor)                                | Average: O[1]      |
  | visitReadOnly(key, visitor)                        | Worst:   O[n]      |
  +----------------------------------------------------+--------------------+
  | insertBulk, k elements                             | Average: O[k]      |
  |                                                    | Worst:   O[n*k]    |
  +----------------------------------------------------+--------------------+
  | eraseBulk, k elements                              | Average: O[k]      |
  |                                                    | Worst:   O[n*k]    |
  +----------------------------------------------------+--------------------+
  | rehash                                             | O[n]               |
  +----------------------------------------------------+--------------------+
  | visit(visitor), visitReadOnly(visitor)             | O[n]               |
  +----------------------------------------------------+--------------------+

Number of Stripes:

Performance improves monotonically when the number of stripes increases. However, the rate of improvement decreases, and reaches a plateau. The plateau is reached roughly at four times the number of the threads concurrently using the hash map.

Set vs. Insert Methods:

This container provides several set* methods and analogously named insert* methods having semantics that are identical except for the meaning of the return value. The rationale is best explained in the context of the bdlcc::StripedUnorderedMultiMap class. See bdlcc_stripedunorderedmultimap|Set vs. Insert methods. The behavior as seen in this component is the degenerate case when the number of elements updated (or inserted) is limited to 0 or 1.

Rehash:

Concurrent Rehash:

A rehash operation is a re-organization of the hash map to a different number of buckets. This is a heavy operation that interferes with, but does not disallow, other operations on the container. Rehash is warranted when the current load factor exceeds the current maximum allowed load factor. Expressed explicitly:

  bucketCount() <= maxLoadFactor() * size();

This above condition is tested implicitly by several methods and if found true (and if rehash is enabled and rehash is not underway), a rehash is started. The methods that check the load factor are:

• All methods that insert elements (i.e., increase size()).
• The maxLoadFactor(newMaxLoadFactor) method.
• The rehash method.

Rehash Control:

enableRehash and disableRehash methods are provided to control the rehash enable flag. Note that disabling rehash does not impact a rehash in progress.

Usage:

In this section we show intended use of this component.

Example 1: Basic Usage:

This example shows some basic usage of bdlcc::StripedUnorderedMap.

First, we define a bdlcc::StripedUnorderedMap object, myFriends, that maps int to bsl::string:

  bdlcc::StripedUnorderedMap<int, bsl::string> myFriends;

Notice that we are using the default value number of buckets, number of stripes, and allocator.

Then, we insert three elements into the map and verify that the size is the expected value:

  assert(0 == myFriends.size());
  myFriends.insert(0, "Alex");
  myFriends.insert(1, "John");
  myFriends.insert(2, "Rob");
  assert(3 == myFriends.size());

Next, we demonstrate insertBulk by creating a vector of three key-value pairs and add them to the map using a single method call:

  typedef bsl::pair<int, bsl::string> PairType;
  bsl::vector<PairType> insertData;
  insertData.push_back(PairType(3, "Jim"));
  insertData.push_back(PairType(4, "Jeff"));
  insertData.push_back(PairType(5, "Ian" ));
  assert(3 == insertData.size())

  assert(3 == myFriends.size());
  myFriends.insertBulk(insertData.begin(), insertData.end());
  assert(6 == myFriends.size());

Then, we getValue method to retrieve the previously inserted string associated with the value 1:

  bsl::string value;
  bsl::size_t rc = myFriends.getValue(&value, 1);
  assert(1      == rc);
  assert("John" == value);

Now, we change the value associated with 1 from "John" to "Jack" and confirm that the size of the map has not changed:

  rc = myFriends.setValue(1, "Jack");
  assert(1 == rc);
  assert(6 == myFriends.size());

  rc = myFriends.getValue(&value, 1);
  assert(1      == rc);
  assert("Jack" == value);

Finally, we erase the element (3, "Jim") from the map, confirm that the map size is decremented, and that element can no longer be found in the map:

  rc = myFriends.erase(3);
  assert(1 == rc);
  assert(5 == myFriends.size());

  rc = myFriends.getValue(&value, 3);
  assert(0 == rc);

Example 2: Track Stats:

This example uses the setComputedValue and update methods to keep track of user ID usage counts (stats). A striped unordered map has the user ID as the key, and the count as the value. There are 2 functors, one used to increase the count (and set it to 1 if the user ID has not been referenced yet), and the other is used to decrease the count.

  typedef bdlcc::StripedUnorderedMap<int, int> StatsMap;

First, define a functor, IncFunctor, that has parameters corresponding to the KEY and VALUE types of StatsMap and, when invoked, adds 1 to whatever existing value is associated with the given KEY value. As a new value is initialized with default (0), adding 1 to it works correctly:

  struct IncFunctor {
      bool operator()(int        *value,  // 'VALUE *'
                      const int&)         // 'const KEY&'
      {
          *value += 1;
          return true;
      }
  };

Next, define a functor, DecFunctor, that has parameters corresponding to the KEY and VALUE types of StatsMap and, when invoked, subtracts 1 from whatever existing value is associated with the given KEY value:

      struct DecFunctor {
          bool operator()(int        *value,  // 'VALUE *'
                          const int&  )       // 'const KEY&'
          {
              *value -= 1;
              return true;
          }
      };

Then, create myStats, a StatsMap object with (as we did in Example 1 default number of buckets, number of stripes, and allocator:

  StatsMap myStats;

Next, instantiate myIncFunctor and myDecFunctor from IncFunctor and DecFunctor, respectively:

  IncFunctor myIncFunctor;
  DecFunctor myDecFunctor;

Next, increase count for three user IDs:

  assert(0 == myStats.size());
  int rc = myStats.setComputedValue(1001, myIncFunctor);
  assert(0 == rc);
  rc = myStats.setComputedValue(1002, myIncFunctor);
  assert(0 == rc);
  rc = myStats.setComputedValue(1003, myIncFunctor);
  assert(0 == rc);
  assert(3 == myStats.size());
  int value = 0;
  rc = myStats.getValue(&value, 1001);
  assert(1 == rc);
  assert(1 == value);

Now, increase count for existing user IDs. Confirm that the values have been updated as expected.

  rc = myStats.setComputedValue(1001, myIncFunctor);
  assert(1 == rc);
  rc = myStats.setComputedValue(1002, myIncFunctor);
  assert(1 == rc);
  rc = myStats.setComputedValue(1001, myIncFunctor);
  assert(1 == rc);
  assert(3 == myStats.size());
  rc = myStats.getValue(&value, 1001);
  assert(1 == rc);
  assert(3 == value);
  rc = myStats.getValue(&value, 1002);
  assert(1 == rc);
  assert(2 == value);

Finally decrease count for existing user IDs. Confirm that the values have been updated as expected.

  int ret = myStats.update(1001, myDecFunctor);
  assert(1 == ret);
  ret = myStats.update(1003, myDecFunctor);
  assert(1 == ret);
  assert(3 == myStats.size());
  rc = myStats.getValue(&value, 1001);
  assert(1 == rc);
  assert(2 == value);
  rc = myStats.getValue(&value, 1003);
  assert(1 == rc);
  assert(0 == value);

Example 3: Visiting all the Container Elements:

This example uses the visit method to apply a transformation (as defined by a functor) to the value of every key-value pair in the map. This example will construct a map from names (type bsl::string) to some (arbitrary) measure of salary (type int):

  typedef bdlcc::StripedUnorderedMap<bsl::string, int> SalaryMap;

First, define a functor, mySalaryAdjustmentVisitor, that increases values above 1000 by 3% and lower values by 5%. The fractional part of increases are truncated to int values:

  struct mySalaryAdjustmentVisitor {
      bool operator()(int                *value,  // 'VALUE *'
                      const bsl::string&)         // 'const KEY&'
      {
          if (*value <= 1000) {
              *value = static_cast<int>(*value * 1.05);
          } else {
              *value = static_cast<int>(*value * 1.03);
          }
          return true;
      }
  };

Then, default create mySalaries, a SalaryMap object:

  SalaryMap mySalaries;

Next, load mySalaries with some representative elements:

  mySalaries.insert("Alex", 1000);
  mySalaries.insert("John",  800);
  mySalaries.insert("Rob",  1100);
  assert(3 == mySalaries.size());

Now, apply mySalaryAdjustmentVisitor to every element in the map:

  mySalaryAdjustmentVisitor func;
  mySalaries.visit(func);
  assert(3 == mySalaries.size());

Finally, confirm that the values have been adjusted as expected:

  int         value;
  bsl::size_t rc;

  rc = mySalaries.getValue(&value, "Alex");
  assert(1    == rc);
  assert(1050 == value);

  rc = mySalaries.getValue(&value, "John");
  assert(1    == rc);
  assert( 840 == value);

  rc = mySalaries.getValue(&value, "Rob");
  assert(1    == rc);
  assert(1133 == value);