bdlcc_stripedunorderedmultimap

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

Purpose

Provide a bucket-group locking (striped) unordered multimap.

Classes

• bdlcc::StripedUnorderedMultiMap: Striped hash multimap

See also

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();

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::StripedUnorderedMultiMap.

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

bdlcc::StripedUnorderedMultiMap<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 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);

Now, we insert two additional elements, each having key values that already appear in the hash map:

myFriends.insert(3, "Steve");
assert(7 == myFriends.size());
 
myFriends.insert(4, "Tim");
assert(8 == myFriends.size());

Finally, we use the getValueAll method to retrieve both values associated with the key 3:

bsl::vector<bsl::string> values;
rc = myFriends.getValueAll(&values, 3);
assert(2 == rc);
 
assert(2            == values.size());
assert(values.end() != bsl::find(values.begin(), values.end(), "Jim"));
assert(values.end() != bsl::find(values.begin(), values.end(), "Steve"));

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.