Boost.Unordered

As more elements are added to an unordered associative container, the number of collisions will increase causing performance to degrade. To combat this the containers increase the bucket count as elements are inserted. You can also tell the container to change the bucket count (if required) by calling rehash.

The standard leaves a lot of freedom to the implementer to decide how the number of buckets is chosen, but it does make some requirements based on the container’s load factor, the number of elements divided by the number of buckets. Containers also have a maximum load factor which they should try to keep the load factor below.

You can’t control the bucket count directly but there are two ways to influence it:

max_load_factor doesn’t let you set the maximum load factor yourself, it just lets you give a hint. And even then, the standard doesn’t actually require the container to pay much attention to this value. The only time the load factor is required to be less than the maximum is following a call to rehash. But most implementations will try to keep the number of elements below the max load factor, and set the maximum load factor to be the same as or close to the hint - unless your hint is unreasonably small or large.

A note on max_load for open-addressing and concurrent containers: the maximum load will be (max_load_factor() * bucket_count()) right after rehash or on container creation, but may slightly decrease when erasing elements in high-load situations. For instance, if we have a boost::unordered_flat_map with size() almost at max_load() level and then erase 1,000 elements, max_load() may decrease by around a few dozen elements. This is done internally by Boost.Unordered in order to keep its performance stable, and must be taken into account when planning for rehash-free insertions.

Similarly, a custom hash function can be used for custom types:

Since the default hash function is Boost.Hash, we can extend it to support the type so that the hash function doesn’t need to be explicitly given:

See the Boost.Hash documentation for more detail on how to do this. Remember that it relies on extensions to the standard - so it won’t work for other implementations of the unordered associative containers, you’ll need to explicitly use Boost.Hash.

It is not specified how member functions other than rehash and reserve affect the bucket count, although insert can only invalidate iterators when the insertion causes the container’s load to be greater than the maximum allowed. For most implementations this means that insert will only change the number of buckets when this happens. Iterators can be invalidated by calls to insert, rehash and reserve.

As for pointers and references, they are never invalidated for node-based containers (boost::unordered_[multi]set, boost::unordered_[multi]map, boost::unordered_node_set, boost::unordered_node_map), but they will be when rehashing occurs for boost::unordered_flat_set and boost::unordered_flat_map: this is because these containers store elements directly into their holding buckets, so when allocating a new bucket array the elements must be transferred by means of move construction.

In a similar manner to using reserve for vectors, it can be a good idea to call reserve before inserting a large number of elements. This will get the expensive rehashing out of the way and let you store iterators, safe in the knowledge that they won’t be invalidated. If you are inserting n elements into container x, you could first call:

The first thing a new user of boost::concurrent_flat_set or boost::concurrent_flat_map will notice is that these classes do not provide iterators (which makes them technically not Containers in the C++ standard sense). The reason for this is that iterators are inherently thread-unsafe. Consider this hypothetical code:

In a multithreaded scenario, the iterator it may be invalid at point B if some other thread issues an m.erase(k) operation between A and B. There are designs that can remedy this by making iterators lock the element they point to, but this approach lends itself to high contention and can easily produce deadlocks in a program. operator[] has similar concurrency issues, and is not provided by boost::concurrent_flat_map either. Instead, element access is done through so-called visitation functions:

The visitation function passed by the user (in this case, a lambda function) is executed internally by Boost.Unordered in a thread-safe manner, so it can access the element without worrying about other threads interfering in the process.

On the other hand, a visitation function can not access the container itself:

Access to a different container is allowed, though:

But, in general, visitation functions should be as lightweight as possible to reduce contention and increase parallelization. In some cases, moving heavy work outside of visitation may be beneficial:

Visitation is prominent in the API provided by boost::concurrent_flat_set and boost::concurrent_flat_map, and many classical operations have visitation-enabled variations:

Note that in this last example the visitation function could actually modify the element: as a general rule, operations on a boost::concurrent_flat_map m will grant visitation functions const/non-const access to the element depending on whether m is const/non-const. Const access can be always be explicitly requested by using cvisit overloads (for instance, insert_or_cvisit) and may result in higher parallelization. For boost::concurrent_flat_set, on the other hand, visitation is always const access. Consult the references of boost::concurrent_flat_set and boost::concurrent_flat_map for the complete list of visitation-enabled operations.

In the absence of iterators, visit_all is provided as an alternative way to process all the elements in the container:

In C++17 compilers implementing standard parallel algorithms, whole-table visitation can be parallelized:

Traversal can be interrupted midway:

There is one last whole-table visitation operation, erase_if:

visit_while and erase_if can also be parallelized. Note that, in order to increase efficiency, whole-table visitation operations do not block the table during execution: this implies that elements may be inserted, modified or erased by other threads during visitation. It is advisable not to assume too much about the exact global state of a concurrent container at any point in your program.

Suppose you have an std::array of keys you want to look up for in a concurrent map:

Bulk visitation allows us to pass all the keys in one operation:

This functionality is not provided for mere syntactic convenience, though: by processing all the keys at once, some internal optimizations can be applied that increase performance over the regular, one-at-a-time case (consult the benchmarks). In fact, it may be beneficial to buffer incoming keys so that they can be bulk visited in chunks:

There’s a latency/throughput tradeoff here: it will take longer for incoming keys to be processed (since they are buffered), but the number of processed keys per second is higher. bulk_visit_size is the recommended chunk size —smaller buffers may yield worse performance.

boost::concurrent_flat_sets and boost::concurrent_flat_maps can be copied, assigned, cleared and merged just like any Boost.Unordered container. Unlike most other operations, these are blocking, that is, all other threads are prevented from accesing the tables involved while a copy, assignment, clear or merge operation is in progress. Blocking is taken care of automatically by the library and the user need not take any special precaution, but overall performance may be affected.

Another blocking operation is rehashing, which happens explicitly via rehash/reserve or during insertion when the table’s load hits max_load(). As with non-concurrent containers, reserving space in advance of bulk insertions will generally speed up the process.

As open-addressing and concurrent containers are based on the same internal data structure, boost::unordered_flat_set and boost::unordered_flat_map can be efficiently move-constructed from boost::concurrent_flat_set and boost::concurrent_flat_map, respectively, and vice versa. This interoperability comes handy in multistage scenarios where parts of the data processing happen in parallel whereas other steps are non-concurrent (or non-modifying). In the following example, we want to construct a histogram from a huge input vector of words: the population phase can be done in parallel with boost::concurrent_flat_map and results then transferred to the final container.

boost::unordered_[multi]set and boost::unordered_[multi]map provide a conformant implementation for C++11 (or later) compilers of the latest standard revision of C++ unordered associative containers, with very minor deviations as noted. The containers are fully AllocatorAware and support fancy pointers.

The C++ standard does not currently provide any open-addressing container specification to adhere to, so boost::unordered_flat_set/unordered_node_set and boost::unordered_flat_map/unordered_node_map take inspiration from std::unordered_set and std::unordered_map, respectively, and depart from their interface where convenient or as dictated by their internal data structure, which is radically different from that imposed by the standard (closed addressing).

Open-addressing containers provided by Boost.Unordered only work with reasonably compliant C++11 (or later) compilers. Language-level features such as move semantics and variadic template parameters are then not emulated. The containers are fully AllocatorAware and support fancy pointers.

The main differences with C++ unordered associative containers are:

There is currently no specification in the C++ standard for this or any other type of concurrent data structure. The APIs of boost::concurrent_flat_set and boost::concurrent_flat_map are modelled after std::unordered_flat_set and std::unordered_flat_map, respectively, with the crucial difference that iterators are not provided due to their inherent problems in concurrent scenarios (high contention, prone to deadlocking): so, Boost.Unordered concurrent containers are technically not models of Container, although they meet all the requirements of AllocatorAware containers (including fancy pointer support) except those implying iterators.

In a non-concurrent unordered container, iterators serve two main purposes:

In place of iterators, boost::concurrent_flat_set and boost::concurrent_flat_map use internal visitation facilities as a thread-safe substitute. Classical operations returning an iterator to an element already existing in the container, like for instance:

are transformed to accept a visitation function that is passed such element:

(In the second case f is only invoked if there’s an equivalent element to obj in the table, not if insertion is successful). Container traversal is served by:

of which there are parallelized versions in C++17 compilers with parallel algorithm support. In general, the interface of concurrent containers is derived from that of their non-concurrent counterparts by a fairly straightforward process of replacing iterators with visitation where applicable. If for regular maps iterator and const_iterator provide mutable and const access to elements, respectively, here visitation is granted mutable or const access depending on the constness of the member function used (there are also *cvisit overloads for explicit const visitation); In the case of boost::concurrent_flat_set, visitation is always const.

One notable operation not provided by boost::concurrent_flat_map is operator[]/at, which can be replaced, if in a more convoluted manner, by try_emplace_or_visit.

Boost.Unordered sports one of the fastest implementations of closed addressing, also commonly known as separate chaining. An example figure representing the data structure is below:

An array of "buckets" is allocated and each bucket in turn points to its own individual linked list. This makes meeting the standard requirements of bucket iteration straight-forward. Unfortunately, iteration of the entire container is often times slow using this layout as each bucket must be examined for occupancy, yielding a time complexity of O(bucket_count() + size()) when the standard requires complexity to be O(size()).

Canonical standard implementations will wind up looking like the diagram below:

It’s worth noting that this approach is only used by libc++ and libstdc++; the MSVC Dinkumware implementation uses a different one. A more detailed analysis of the standard containers can be found here.

This unusually laid out data structure is chosen to make iteration of the entire container efficient by inter-connecting all of the nodes into a singly-linked list. One might also notice that buckets point to the node before the start of the bucket’s elements. This is done so that removing elements from the list can be done efficiently without introducing the need for a doubly-linked list. Unfortunately, this data structure introduces a guaranteed extra indirection. For example, to access the first element of a bucket, something like this must be done:

With a simple bucket group layout, this is all that must be done:

In practice, the extra indirection can have a dramatic performance impact to common operations such as insert, find and erase. But to keep iteration of the container fast, Boost.Unordered introduces a novel data structure, a "bucket group". A bucket group is a fixed-width view of a subsection of the buckets array. It contains a bitmask (a std::size_t) which it uses to track occupancy of buckets and contains two pointers so that it can form a doubly-linked list with non-empty groups. An example diagram is below:

Thus container-wide iteration is turned into traversing the non-empty bucket groups (an operation with constant time complexity) which reduces the time complexity back to O(size()). In total, a bucket group is only 4 words in size and it views sizeof(std::size_t) * CHAR_BIT buckets meaning that for all common implementations, there’s only 4 bits of space overhead per bucket introduced by the bucket groups.

A more detailed description of Boost.Unordered’s closed-addressing implementation is given in an external article. For more information on implementation rationale, read the corresponding section.

The diagram shows the basic internal layout of boost::unordered_flat_set/unordered_node_set and boost:unordered_flat_map/unordered_node_map.

As with all open-addressing containers, elements (or pointers to the element nodes in the case of boost::unordered_node_set and boost::unordered_node_map) are stored directly in the bucket array. This array is logically divided into 2ⁿ groups of 15 elements each. In addition to the bucket array, there is an associated metadata array with 2ⁿ 16-byte words.

A metadata word is divided into 15 h_i bytes (one for each associated bucket), and an overflow byte (ofw in the diagram). The value of h_i is:

When looking for an element with hash value h, SIMD technologies such as SSE2 and Neon allow us to very quickly inspect the full metadata word and look for the reduced value of h among all the 15 buckets with just a handful of CPU instructions: non-matching buckets can be readily discarded, and those whose reduced hash value matches need be inspected via full comparison with the corresponding element. If the looked-for element is not present, the overflow byte is inspected:

Insertion is algorithmically similar: empty buckets are located using SIMD, and when going past a full group its corresponding overflow bit is set to 1.

In architectures without SIMD support, the logical layout stays the same, but the metadata word is codified using a technique we call bit interleaving: this layout allows us to emulate SIMD with reasonably good performance using only standard arithmetic and logical operations.

A more detailed description of Boost.Unordered’s open-addressing implementation is given in an external article. For more information on implementation rationale, read the corresponding section.

boost::concurrent_flat_set and boost::concurrent_flat_map use the basic open-addressing layout described above augmented with synchronization mechanisms.

Two levels of synchronization are used:

By using atomic operations to access the group metadata, lookup is (group-level) lock-free up to the point where an actual comparison needs to be done with an element that has been previously SIMD-matched: only then is the group’s spinlock used.

Insertion uses the following optimistic algorithm:

This algorithm has very low contention both at the lookup and actual insertion phases in exchange for the possibility that computations have to be started over if some other thread interferes in the process by performing a succesful insertion beginning at the same group. In practice, the start-over frequency is extremely small, measured in the range of parts per million for some of our benchmarks.

For more information on implementation rationale, read the corresponding section.

All benchmarks were created using unordered_set<unsigned int> (non-duplicate) and unordered_multiset<unsigned int> (duplicate). The source code can be found here.

The insertion benchmarks insert n random values, where n is between 10,000 and 3 million. For the duplicated benchmarks, the same random values are repeated an average of 5 times.

The erasure benchmarks erase all n elements randomly until the container is empty. Erasure by key uses erase(const key_type&) to remove entire groups of equivalent elements in each operation.

The successful lookup benchmarks are done by looking up all n values, in their original insertion order.

The unsuccessful lookup benchmarks use n randomly generated integers but using a different seed value.

All benchmarks were created using:

The source code can be found here.

The insertion benchmarks insert n random values, where n is between 10,000 and 10 million.

The erasure benchmarks erase traverse the n elements and erase those with odd key (50% on average).

The successful lookup benchmarks are done by looking up all n values, in their original insertion order.

The unsuccessful lookup benchmarks use n randomly generated integers but using a different seed value.

All benchmarks were created using:

The source code can be found here.

The benchmarks exercise a number of threads T (between 1 and 16) concurrently performing operations randomly chosen among update, successful lookup and unsuccessful lookup. The keys used in the operations follow a Zipf distribution with different skew parameters: the higher the skew, the more concentrated are the keys in the lower values of the covered range.

boost::concurrent_flat_map is exercised using both regular and bulk visitation: in the latter case, lookup keys are buffered in a local array and then processed at once each time the buffer reaches bulk_visit_size.

boost::unordered_[multi]set and boost::unordered_[multi]map adhere to the standard requirements for unordered associative containers, so the interface was fixed. But there are still some implementation decisions to make. The priorities are conformance to the standard and portability.

The Wikipedia article on hash tables has a good summary of the implementation issues for hash tables in general.

The C++ standard specification of unordered associative containers impose severe limitations on permissible implementations, the most important being that closed addressing is implicitly assumed. Slightly relaxing this specification opens up the possibility of providing container variations taking full advantage of open-addressing techniques.

The design of boost::unordered_flat_set/unordered_node_set and boost::unordered_flat_map/unordered_node_map has been guided by Peter Dimov’s Development Plan for Boost.Unordered. We discuss here the most relevant principles.

The same data structure used by Boost.Unordered open-addressing containers has been chosen also as the foundation of boost::concurrent_flat_set and boost::concurrent_flat_map:

boost::unordered_map — An unordered associative container that associates unique keys with another value.