bdlcc_stripedunorderedcontainerimpl

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Thread Safety
  • Runtime Complexity
  • Number of Stripes
  • Rehash
    • Concurrent Rehash
    • Rehash Control
  • Usage

Purpose

Provide common implementation of striped un-ordered map/multimap.

Classes

• bdlcc::StripedUnorderedContainerImpl: striped container for key-value types

See also

bdlcc_stripedunorderedmap, bdlcc_stripedunorderedmultimap

Description

This component provides bdlcc::StripedUnorderedContainerImpl, a common implementation for bdlcc::StripedUnorderedMap and bdlcc::StripedUnorderedMultiMap, that are concurrent (fully thread-safe) associative containers that partition their underlying hash tables into a (user-defined) number of "bucket groups" and control access to each part of their hash tables by separate read-write locks. For most methods, the "map" and "multimap" classes forward to the analogous method in this "impl" class with an additional argument that specifies if the calling class has unique keys or not.

Thread Safety

The bdlcc::StripedUnorderedContrainerImpl 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.

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

There is no usage example for this component since it is not meant for direct client use.