Exit Zen
1
:1
English
[#structures] = Data Structures
19/320 · 32
2
:4
English
:idprefix: structures_
22/220 · 22
3
:6
English
Closed-addressing Containers
5/280 · 28
4
:16
English
Boost.Unordered sports one of the fastest implementations of closed addressing, also commonly known as https://en.wikipedia.org/wiki/Hash_table#Separate_chaining[separate chaining]. An example figure representing the data structure is below:
118/2410 · 241
5
:20
English
image::bucket-groups.png[align=center]
38/380 · 38
6
:22
English
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())`.
151/4330 · 433
7
:24
English
Canonical standard implementations will wind up looking like the diagram below:
22/790 · 79
8
:28
English
image::singly-linked.png[align=center,link=_images/singly-linked.png,window=_blank]
83/830 · 83
9
:30
English
It's worth noting that this approach is only used by pass:[libc++] and pass:[libstdc++]; the MSVC Dinkumware implementation uses a different one. A more detailed analysis of the standard containers can be found http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html[here].
173/2890 · 289
10
:32
English
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:
138/5600 · 560
11
:34
English
```c++ auto const idx = get_bucket_idx(hash_function(key)); node* p = buckets[idx]; // first load node* n = p->next; // second load if (n && is_in_bucket(n, idx)) { value_type const& v = *n; // third load // ... } ```
232/2170 · 217
12
:44
English
With a simple bucket group layout, this is all that must be done: ```c++ auto const idx = get_bucket_idx(hash_function(key)); node* n = buckets[idx]; // first load if (n) { value_type const& v = *n; // second load // ... } ```
173/2260 · 226
13
:54
English
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:
194/5240 · 524
14
:58
English
image::fca.png[align=center]
28/280 · 28
15
:60
English
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.
156/4130 · 413
16
:62
English
A more detailed description of Boost.Unordered's closed-addressing implementation is given in an https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html[external article]. For more information on implementation rationale, read the xref:rationale.adoc#rationale_closed_addressing_containers[corresponding section].
192/3270 · 327
17
:68
English
Open-addressing Containers
6/260 · 26
18
:70
English
The diagram shows the basic internal layout of `boost::unordered_flat_set`/`unordered_node_set` and `boost:unordered_flat_map`/`unordered_node_map`.
114/1480 · 148
19
:76
English
image::foa.png[align=center]
28/280 · 28
20
:78
English
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^_n_^ _groups_ of 15 elements each. In addition to the bucket array, there is an associated _metadata array_ with 2^_n_^ 16-byte words.
191/3730 · 373