Exit Zen
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
35
:145
English
to the container. Typically, such access is in read mode (that is, concurrent) even for modifying operations, so for most practical purposes there is no thread contention at this level. Access is only in write mode (blocking) when rehashing or performing container-wide operations such as swapping or assignment.
96/3120 · 312
36
:149
English
Group level: Each 15-slot group is equipped with an 8-byte word containing:
30/750 · 75
37
:150
English
** A read-write spinlock for synchronized access to any element in the group. ** An atomic _insertion counter_ used for optimistic insertion as described below.
53/1600 · 160
38
:154
English
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.
66/2450 · 245
39
:158
English
Insertion uses the following _optimistic algorithm_:
16/520 · 52
40
:160
English
The value of the insertion counter for the initial group in the probe
12/690 · 69
41
:161
English
sequence is locally recorded (let's call this value `c0`).
22/580 · 58
42
:162
English
Lookup is as described above. If lookup finds no equivalent element,
21/680 · 68
43
:163
English
search for an available slot for insertion successively locks/unlocks each group in the probing sequence.
35/1050 · 105
44
:165
English
When an available slot is located, it is preemptively occupied (its
23/670 · 67
45
:166
English
reduced hash value is set) and the insertion counter is atomically incremented: if no other thread has incremented the counter during the whole operation (which is checked by comparing with `c0`), then we're good to go and complete the insertion, otherwise we roll back and start over.
86/2850 · 285
46
:172
English
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.
103/4000 · 400
47
:179
English
For more information on implementation rationale, read the xref:rationale.adoc#rationale_concurrent_containers[corresponding section].
77/1340 · 134
The translation has come to an end.