Provide a bucket-group locking (striped) unordered multimap.
More...
Namespaces |
| namespace | bdlcc |
Detailed Description
- Outline
-
-
- Purpose:
- Provide a bucket-group locking (striped) unordered multimap.
-
- Classes:
-
- See also:
- Component bdlcc_stripedunorderedmap, bdlcc_stripedunorderedimpl
-
- Description:
- This component provides a single concurrent (fully thread-safe) associative container,
bdlcc::StripedUnorderedMultiMap, 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_multimap object protected by a single lock.
bdlcc::StripedUnorderedMultiMap differs from bdlcc::StripedUnorderedMap in that the former allows multiple elements to have the same key value but the later requires that each element have a unique key value. Methods of the two classes have similar names and semantics differing only where the different key policy pertains.
- The terms "bucket", "load factor", and "rehash" have the same meaning as they do in the
bslstl_unorderedmultimap component (see bslstl_unorderedmultimap|Unordered Multimap Configuration). A general introduction to these ideas can be found at: https://en.wikipedia.org/wiki/Hash_table
bdlcc::StripedUnorderedMultiMap (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* methods 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::StripedUnorderedMultiMap 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::StripedUnorderedMultiMap 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, setValueFirst, setValueAll, | Average: O[1] |
| setComputedValueAll, setComputedValueFirst, update| Worst: O[n] |
+----------------------------------------------------+--------------------+
| eraseFirst, eraseAll, getValueFirst, getValueAll | 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] |
+----------------------------------------------------+--------------------+
| examine | Average: O[1] |
| | Worst: O[n] |
+----------------------------------------------------+--------------------+
| eraseBulkAll, 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 similarly named insert* methods that have nearly identical semantics. Both update the value of an existing element and both add a new element if the element sought is not present. Conceptually, the emphasis of the set* methods is the former, so its return value is the number of elements updated, and the intent of insert* methods is to add elements, so its return value is the number of new elements.
-
- 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();
-
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::StripedUnorderedMultiMap.
- First, we define a
bdlcc::StripedUnorderedMultiMap object, myFriends, that maps int to bsl::string: 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());
insertBulk by creating a vector of three key-value pairs and add them to the map using a single method call: Then, we use getValueFirst method to retrieve the previously inserted string associated with the value 1: bsl::string value;
bsl::size_t rc = myFriends.getValueFirst(&value, 1);
assert(1 == rc);
assert("John" == value);
myFriends.insert(3, "Steve");
assert(7 == myFriends.size());
myFriends.insert(4, "Tim");
assert(8 == myFriends.size());
getValueAll method to retrieve both values associated with the key 3: Notice that the results have the expected number and values. Also notice that we must search the results for the expected values because the order in which values are retrieved is not specified.
