Component bdlcc_stripedunorderedcontainerimpl [Package bdlcc]

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

Namespaces
namespace	bdlcc

---

Detailed Description

Outline

• Purpose
• Classes
• DESCRIPTON: This component provides bdlcc::StripedUnorderedContainerImpl,
  • 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:

Component bdlcc_stripedunorderedmap, Component bdlcc_stripedunorderedmultimap

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