Exit Zen
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
21
:86
English
image::foa-metadata.png[align=center]
37/370 · 37
22
:88
English
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:
85/1560 · 156
23
:91
English
- 0 if the corresponding bucket is empty. - 1 to encode a special empty bucket called a _sentinel_, which is used internally to stop iteration when the container has been fully traversed. - If the bucket is occupied, a _reduced hash value_ obtained from the hash value of the element.
89/2840 · 284
24
:97
English
When looking for an element with hash value _h_, SIMD technologies such as https://en.wikipedia.org/wiki/SSE2[SSE2] and https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[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:
271/5940 · 594
25
:106
English
- If the bit in the position _h_ mod 8 is zero, lookup terminates (and the element is not present). - If the bit is set to 1 (the group has been _overflowed_), further groups are checked using https://en.wikipedia.org/wiki/Quadratic_probing[_quadratic probing_], and the process is repeated.
144/2910 · 291
26
:112
English
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.
52/1520 · 152
27
:115
English
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.
88/2790 · 279
28
:122
English
image::foa-metadata-interleaving.png[align=center]
50/500 · 50
29
:124
English
A more detailed description of Boost.Unordered's open-addressing implementation is given in an https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[external article]. For more information on implementation rationale, read the xref:rationale.adoc#rationale_open_addresing_containers[corresponding section].
192/3240 · 324
30
:130
English
Concurrent Containers
4/210 · 21
31
:132
English
`boost::concurrent_flat_set`/`boost::concurrent_node_set` and `boost::concurrent_flat_map`/`boost::concurrent_node_map` use the basic xref:structures.adoc#structures_open_addressing_containers[open-addressing layout] described above augmented with synchronization mechanisms.
203/2750 · 275
32
:140
English
image::cfoa.png[align=center]
29/290 · 29
33
:142
English
Two levels of synchronization are used:
9/390 · 39
34
:144
English
Container level: A read-write mutex is used to control access from any operation
25/800 · 80