<?xml version="1.0" encoding="UTF-8"?>
<xliff xmlns="urn:oasis:names:tc:xliff:document:1.1" version="1.1">
  <file original="NoName" source-language="en" datatype="plaintext" target-language="en">
    <body>
      <trans-unit xml:space="preserve" approved="no" id="b55c7c56e11c975a" weblate-flags="read-only, safe-html, strict-same">
        <source>﻿[#structures] = Data Structures</source>
        <target state="translated">﻿[#structures] = Data Structures</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">1</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="4551d922fa721c55" weblate-flags="read-only, safe-html, strict-same">
        <source>:idprefix: structures_</source>
        <target state="translated">:idprefix: structures_</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">4</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="4ebc6f95b2d9f420" weblate-flags="read-only, safe-html, strict-same">
        <source>Closed-addressing Containers</source>
        <target state="translated">Closed-addressing Containers</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">6</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="b8da4a8c6405050c" weblate-flags="read-only, safe-html, strict-same">
        <source>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:</source>
        <target state="translated">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:</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">16</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="03b08d76b3206954" weblate-flags="read-only, safe-html, strict-same">
        <source>image::bucket-groups.png[align=center]</source>
        <target state="translated">image::bucket-groups.png[align=center]</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">20</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="8a675af587b1408f" weblate-flags="read-only, safe-html, strict-same">
        <source>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())`.</source>
        <target state="translated">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())`.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">22</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="43a724da5de16ae7" weblate-flags="read-only, safe-html, strict-same">
        <source>Canonical standard implementations will wind up looking like the diagram below:</source>
        <target state="translated">Canonical standard implementations will wind up looking like the diagram below:</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">24</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="a480561826a1dec0" weblate-flags="read-only, safe-html, strict-same">
        <source>image::singly-linked.png[align=center,link=_images/singly-linked.png,window=_blank]</source>
        <target state="translated">image::singly-linked.png[align=center,link=_images/singly-linked.png,window=_blank]</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">28</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="90389aa9286e3ca0" weblate-flags="read-only, safe-html, strict-same">
        <source>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].</source>
        <target state="translated">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].</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">30</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="6a3b14b48910b1d7" weblate-flags="read-only, safe-html, strict-same">
        <source>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:</source>
        <target state="translated">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:</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">32</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="346a28818996869b" weblate-flags="read-only, safe-html, strict-same">
        <source>```c++ auto const idx = get_bucket_idx(hash_function(key)); node* p = buckets[idx]; // first load node* n = p-&gt;next; // second load if (n &amp;&amp; is_in_bucket(n, idx)) { value_type const&amp; v = *n; // third load // ... } ```</source>
        <target state="translated">```c++ auto const idx = get_bucket_idx(hash_function(key)); node* p = buckets[idx]; // first load node* n = p-&gt;next; // second load if (n &amp;&amp; is_in_bucket(n, idx)) { value_type const&amp; v = *n; // third load // ... } ```</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">34</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="dfb291abd960dff6" weblate-flags="read-only, safe-html, strict-same">
        <source>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&amp; v = *n; // second load // ... } ```</source>
        <target state="translated">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&amp; v = *n; // second load // ... } ```</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">44</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="2997ad2e85268b15" weblate-flags="read-only, safe-html, strict-same">
        <source>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:</source>
        <target state="translated">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:</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">54</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="98d8bb432f0b3fce" weblate-flags="read-only, safe-html, strict-same">
        <source>image::fca.png[align=center]</source>
        <target state="translated">image::fca.png[align=center]</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">58</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="ff417a42e510b473" weblate-flags="read-only, safe-html, strict-same">
        <source>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.</source>
        <target state="translated">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.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">60</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="db22bbb76ccacc93" weblate-flags="read-only, safe-html, strict-same">
        <source>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].</source>
        <target state="translated">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].</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">62</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="2eb8cd9a422898be" weblate-flags="read-only, safe-html, strict-same">
        <source>Open-addressing Containers</source>
        <target state="translated">Open-addressing Containers</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">68</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="aafcd815015ff39d" weblate-flags="read-only, safe-html, strict-same">
        <source>The diagram shows the basic internal layout of `boost::unordered_flat_set`/`unordered_node_set` and `boost:unordered_flat_map`/`unordered_node_map`.</source>
        <target state="translated">The diagram shows the basic internal layout of `boost::unordered_flat_set`/`unordered_node_set` and `boost:unordered_flat_map`/`unordered_node_map`.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">70</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="23f264ee346874cc" weblate-flags="read-only, safe-html, strict-same">
        <source>image::foa.png[align=center]</source>
        <target state="translated">image::foa.png[align=center]</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">76</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="ec1b7ec0ba302a31" weblate-flags="read-only, safe-html, strict-same">
        <source>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.</source>
        <target state="translated">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.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">78</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="bb6f8e488c76e7ea" weblate-flags="read-only, safe-html, strict-same">
        <source>image::foa-metadata.png[align=center]</source>
        <target state="translated">image::foa-metadata.png[align=center]</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">86</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="71cd690d2c364748" weblate-flags="read-only, safe-html, strict-same">
        <source>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:</source>
        <target state="translated">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:</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">88</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="9fab6f89bf5240f0" weblate-flags="read-only, safe-html, strict-same">
        <source>- 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.</source>
        <target state="translated">- 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.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">91</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="902237450cf7ccdc" weblate-flags="read-only, safe-html, strict-same">
        <source>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:</source>
        <target state="translated">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:</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">97</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="9b1205c02aa9a51a" weblate-flags="read-only, safe-html, strict-same">
        <source>- 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.</source>
        <target state="translated">- 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.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">106</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="e2194af18f9f975a" weblate-flags="read-only, safe-html, strict-same">
        <source>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.</source>
        <target state="translated">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.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">112</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="09acdbf8fe6a4441" weblate-flags="read-only, safe-html, strict-same">
        <source>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.</source>
        <target state="translated">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.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">115</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="a35e02b25dd6ed8b" weblate-flags="read-only, safe-html, strict-same">
        <source>image::foa-metadata-interleaving.png[align=center]</source>
        <target state="translated">image::foa-metadata-interleaving.png[align=center]</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">122</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="5be69997735e19b3" weblate-flags="read-only, safe-html, strict-same">
        <source>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].</source>
        <target state="translated">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].</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">124</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="f8a981fd33bbaba5" weblate-flags="read-only, safe-html, strict-same">
        <source>Concurrent Containers</source>
        <target state="translated">Concurrent Containers</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">130</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="643882adba530112" weblate-flags="read-only, safe-html, strict-same">
        <source>`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.</source>
        <target state="translated">`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.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">132</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="6d25eae40cf33826" weblate-flags="read-only, safe-html, strict-same">
        <source>image::cfoa.png[align=center]</source>
        <target state="translated">image::cfoa.png[align=center]</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">140</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="3dbf065c126ffaf5" weblate-flags="read-only, safe-html, strict-same">
        <source>Two levels of synchronization are used:</source>
        <target state="translated">Two levels of synchronization are used:</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">142</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="8b476bf6e8f44dcb" weblate-flags="read-only, safe-html, strict-same">
        <source>Container level: A read-write mutex is used to control access from any operation</source>
        <target state="translated">Container level: A read-write mutex is used to control access from any operation</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">144</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="1ef5b75659d79d48" weblate-flags="read-only, safe-html, strict-same">
        <source>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.</source>
        <target state="translated">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.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">145</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="d0df710b6e12992a" weblate-flags="read-only, safe-html, strict-same">
        <source>Group level: Each 15-slot group is equipped with an 8-byte word containing:</source>
        <target state="translated">Group level: Each 15-slot group is equipped with an 8-byte word containing:</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">149</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="34aec80982868ae0" weblate-flags="read-only, safe-html, strict-same">
        <source>** A read-write spinlock for synchronized access to any element in the group. ** An atomic _insertion counter_ used for optimistic insertion as described below.</source>
        <target state="translated">** A read-write spinlock for synchronized access to any element in the group. ** An atomic _insertion counter_ used for optimistic insertion as described below.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">150</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="28810cfbf6fac044" weblate-flags="read-only, safe-html, strict-same">
        <source>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.</source>
        <target state="translated">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.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">154</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="c03badca97dde7cb" weblate-flags="read-only, safe-html, strict-same">
        <source>Insertion uses the following _optimistic algorithm_:</source>
        <target state="translated">Insertion uses the following _optimistic algorithm_:</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">158</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="cc3901ed4253b937" weblate-flags="read-only, safe-html, strict-same">
        <source>The value of the insertion counter for the initial group in the probe</source>
        <target state="translated">The value of the insertion counter for the initial group in the probe</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">160</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="b1d44cbda92a0f8c" weblate-flags="read-only, safe-html, strict-same">
        <source>sequence is locally recorded (let's call this value `c0`).</source>
        <target state="translated">sequence is locally recorded (let's call this value `c0`).</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">161</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="8b2746ded7d5452a" weblate-flags="read-only, safe-html, strict-same">
        <source>Lookup is as described above. If lookup finds no equivalent element,</source>
        <target state="translated">Lookup is as described above. If lookup finds no equivalent element,</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">162</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="bd9f8f1ef739bb10" weblate-flags="read-only, safe-html, strict-same">
        <source>search for an available slot for insertion successively locks/unlocks each group in the probing sequence.</source>
        <target state="translated">search for an available slot for insertion successively locks/unlocks each group in the probing sequence.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">163</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="71d96ac9659c35bc" weblate-flags="read-only, safe-html, strict-same">
        <source>When an available slot is located, it is preemptively occupied (its</source>
        <target state="translated">When an available slot is located, it is preemptively occupied (its</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">165</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="2cb01fa3d31461d3" weblate-flags="read-only, safe-html, strict-same">
        <source>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.</source>
        <target state="translated">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.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">166</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="e9e99ff6033e4ac3" weblate-flags="read-only, safe-html, strict-same">
        <source>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.</source>
        <target state="translated">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.</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">172</context>
        </context-group>
      </trans-unit>
      <trans-unit xml:space="preserve" approved="no" id="3620a190a58f490c" weblate-flags="read-only, safe-html, strict-same">
        <source>For more information on implementation rationale, read the xref:rationale.adoc#rationale_concurrent_containers[corresponding section].</source>
        <target state="translated">For more information on implementation rationale, read the xref:rationale.adoc#rationale_concurrent_containers[corresponding section].</target>
        <context-group name="" purpose="location">
          <context context-type="sourcefile"></context>
          <context context-type="linenumber">179</context>
        </context-group>
      </trans-unit>
    </body>
  </file>
</xliff>
