File FlatHashTable.h

↰ Parent directory (ADS/dictionary)

A hash table with open addressing and control bytes, beyond the book: the engineered DICTIONARY of Namespace ADS [see File ADT.h], the one that the benchmark of the dictionaries compares with boost::unordered_flat_map, while OpenHashTable [see File OpenHashTable.h] stays the table of section 7.2.2.

Definition (ADS/dictionary/FlatHashTable.h)

Detailed Description

The places come in groups of 15, after the Boost table: beside the vector of the pairs, each group has 16 bytes aligned to 16, one control byte per place, empty (0) or full, in which case the byte is a fingerprint of 8 bits of the hash of its key, never 0, and a 16th byte of overflow. The 15 control bytes are compared with the fingerprint of a key all at once: by one comparison of SSE2 on x86-64, by one of NEON on ARM64, and elsewhere by broadword operations (SWAR, SIMD within a register) on two words of 64 bits; ADS_FLAT_SIMD, defined as 0 before the header, selects the broadword operations on any machine. A key is compared only in the places whose fingerprint matches, a false match costing a comparison and nothing else. When some fingerprint matches, the first line of cache of the pairs of the group is prefetched, as in Boost: the address depends only on the group, so that the processor issues the prefetch on the predicted branch while the control bytes are still on their way, and the two misses of a search overlap in part.

The hash h( k ) is mixed as in Boost: the product of h( k ) by :math:` lfloor 2^{64} / phi rfloor ` on 128 bits, its two halves XORed, so that every bit of the result depends on every bit of h( k ) and even the identity hash of the integers of std::hash spreads over the table; a hash that declares the member type is_avalanching (the convention of Boost) is taken as it is, on 64 bits, as the default one, DefaultHash< K > [see File FastHash.h], is for the integers and the strings, whose hash by FastHash costs one product per 16 bytes. The top bits of the mixed hash give the first group of the key, its low 8 bits the fingerprint (1 in place of 0) and its bits 8 to 10 the bit of the key in the bytes of overflow. The number of groups is a power of 2 and the groups are inspected in the triangular order :math:` g_i = ( g_0 + i ( i + 1 ) / 2 ) bmod G `, a permutation of the G groups.

An insertion that goes past a full group sets in its byte of overflow the bit of its key, one of 8. A search stops at the first group whose overflow lacks the bit of its key, after the places of that group whose fingerprint matches: a search for an absent key reads one group of 16 bytes, one line of cache, in the common case and never touches the pairs. remove() empties the place, with no deleted marks; but a place emptied in a group whose overflow is not 0 still counts as full, since the bits stay set until the next rebuild and the searches keep going past the group. A removal in the first group of its key writes the 16 control bytes of the group whole, at an address that depends only on the hash: the store of the single byte would have an address known only once the control bytes arrive from memory, and the loads of the next operations could not pass it before then, so that the removals of random keys would pay their misses one after the other instead of overlapping them (on a Xeon Gold 5120, 55 ns against 33 ns per removal from 10^6 keys). For the same reason a removal counts the places it may leave counted by a bound d, one more per removal, with no load: when :math:` n + d ` reaches the bound of the full places, the places counted are counted exactly, in :math:` O( m / 15 ) ` time, and the table is rebuilt only if fewer than :math:` m / 16 ` places are left, so that the next count comes at least :math:` m / 16 ` operations later and costs O( 1 ) amortized. An insertion takes the first empty place of the inspection of its key. The full places and those still counted stay at most 7 / 8 of the places: past it the table is rebuilt, twice as large if the pairs exceed half of that bound, of the same size otherwise (only the bits of overflow and the places counted go away), which costs O( 1 ) amortized per insertion; the new pair is built in the new places before the old pairs move, so that a key or a value that lives in the table is still there to copy. When the hash of a key reads memory that the key points to, as for the strings, the rebuild lists the full places and prefetches the memory of the key 8 places ahead, so that the misses of the keys overlap instead of coming one at a time. The rebuild only fills the new places, each group in the order of its places, so that it keeps the count of the full places of each group in a byte apart and never reads the control bytes it has just written (a load of a group right after the store of one of its bytes waits for the store). So some place is always empty, and each inspection ends, since it visits each group at most once. The search of an insertion is the one of find(), whose first group gives the place of a new key when it has an empty one, the common case; the groups after the first, and the rebuild, are out of line.

The iterators visit the pairs in the order of the places, as constant pairs of references ( key , value ), a group at a time by the mask of its full places [see const_iterator]; find() gives a value to change in place. A removal moves no other pair and keeps the iterators valid but the one on the removed pair (erase( it ) returns the next one), an insertion of a new key that rebuilds the table invalidates all of them (one that does not rebuild it keeps them, the new pair visited or not), and an insertion of a key already there replaces its value in place.

The contracts [see File Contract.h]: after insert() the key is in the table and after remove() it is not; the invariant is that each full place is reached by the inspection of its key, the bit of the key set in the overflow of each group before it, that the control bytes match the count of the pairs, and that the full places and those still counted stay at most 7 / 8 of the places. On a table of more than 1024 places the invariant is checked on the inspection of the key of the operation only, up to its first group whose overflow lacks the bit of the key. The operations are defined in FlatHashTable.tpp.

    1. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, 2nd ed., Addison-Wesley, 1998, section 6.4 (open addressing, the multiplicative hashing)

    1. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, section 7.1.3 (the broadword computing)

  1. Kulukundis, Designing a fast, efficient, cache-friendly hash table, step by step, CppCon 2017 (the Swiss tables of Abseil, the control bytes and the groups)

    1. Lopez Munoz, Inside boost::unordered_flat_map, 2022 (the groups of 15 places with a byte of overflow, the mixing of the hash, the prefetch of the pairs), https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html

Intel Corporation, Intel 64 and IA-32 Architectures Optimization Reference Manual, order number 248966 (the memory disambiguation: the loads that may pass a store whose address is not known yet), https://www.intel.com/content/www/us/en/developer/articles/ technical/intel-sdm.html

  1. Chen, A. Ailamaki, P. B. Gibbons, T. C. Mowry, Improving hash join performance through prefetching, Proceedings of ICDE 2004, 116-127, 2004, doi:10.1109/ICDE.2004.1319989 (the prefetch of the memory of the keys some keys ahead, in the rebuild)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions

Defines

Unions