Engineered structures
Beside the classes of the book, which follow its pseudocode, a few
structures are written for speed, for the programs that need it, and
tested in test/engineered.cpp, the heaps in
test/heaps.cpp, the vectors in
test/sequences.cpp and, the hashing, in
test/hashing.cpp, the concurrent ones also on
real threads under ThreadSanitizer. FlatHashTable is the hash
tested in test/engineered.cpp and, the hashing,
in test/hashing.cpp and, those of the notes of
Ferragina, in test/engineered_pearls.cpp,
the concurrent ones also on real threads under ThreadSanitizer. FlatHashTable is the hash
table that bench/dictionaries.cpp compares with
boost::unordered_flat_map, while OpenHashTable stays the table of
section 7.2 of the book; bench/hashing.cpp compares
the hashing with Abseil, unordered_dense, robin-map, libcuckoo, XXH3,
wyhash, rapidhash, fastfilter_cpp, xor_singleheader, PTHash, BBHash and
RecSplit; bench/priority.cpp compares the heaps
with Boost.Heap, tlx and radix-heap, also in Dijkstra’s algorithm, and
bench/memory.cpp the arena and the pool with
std::pmr, Boost.Pool, mimalloc and jemalloc;
bench/graphs.cpp runs the algorithms of the book on
graphs, templates on their structures, on those of the standard library,
of Boost and of ADS, with the same counts of work on the three.
RecSplit, and the concurrent cuckoo table with libcuckoo,
boost::concurrent_flat_map and a std::unordered_map under a
std::shared_mutex.
RecSplit. The combinatorial ones are tested in
test/engineered_combinatorial.cpp
and compared by bench/combinatorial.cpp
and bench/backtrack.cpp with libpopcnt,
libmorton, Hinnant’s combinations and the programs DLX1, DLX2 and SSXCC
of Knuth.
std::pmr, Boost.Pool, mimalloc and jemalloc, and
bench/allocators.cpp the standard allocators in
the node containers, in std::allocate_shared and across two threads;
bench/positions.cpp,
bench/assembly.cpp and
bench/fingerprints.cpp measure the structures
of the rows of a model (the index of their positions, their assembly for
the solvers of linear programs and their fingerprints) against the
standard library, Boost and Eigen; their tests are in
test/engineered_memory.cpp and
test/engineered_sparse.cpp.
What |
Header |
Test |
|---|---|---|
two-level bucket queue for integer keys (Dial; Burns et al.) |
|
|
d-ary heap of plain items, no handles |
|
|
d-ary heap of the ids with decrease-key, the places in a vector, a PRIORITYQUEUE whose handles are the ids |
|
|
graph in compressed rows, each arc next to its weight, the rows sorted by head; transpose and relabelling |
|
|
union-find in one vector, by size or rank, the paths halved or compressed (Tarjan and van Leeuwen) |
|
|
radix heap, monotone integer keys in buckets by digits of B bits (Ahuja et al.) |
|
|
double-ended queues: min-max heap (Atkinson et al.) and interval heap (van Leeuwen and Wood) |
|
|
monotone bucket queue on a circular window, overflow to a radix heap (Dial) |
|
|
sequence heap, sorted sequences merged in batches by trees of losers (Sanders) |
|
|
pairing heap with decrease-key, two-pass or auxiliary two-pass (Fredman et al.; Stasko and Vitter) |
|
|
sort of a List by relinking its cells: radix sort of ( key , cell ) or merge of the natural runs |
|
|
tiered vector: access in O( 1 ), insertion and removal anywhere in O( sqrt n ) (Goodrich and Kloss) |
|
|
vector with room for N items inside itself |
|
|
hash table with control bytes in groups of 15 matched by SSE2, NEON or SWAR, the hash mixed on 128 bits, at most 7/8 full (Swiss tables; Boost’s |
|
|
hash table of pointers, linear probing, Fibonacci hashing |
|
|
arena of objects in blocks, stable addresses |
|
|
pool of objects in doubling blocks, the slot freed last made first |
|
|
allocator of small blocks by size classes, a free list and a page of 64 KB per class (mimalloc, TLSF) |
|
|
allocator of the large blocks on transparent huge pages |
|
|
standard allocator of size classes of 8 bytes, free lists by page, for the node containers and |
|
|
pool of size classes shared by threads, a heap per thread, the frees of the others sent back in batches (mimalloc; snmalloc) |
|
|
index of the positions of objects in a vector, renumbered in one pass after an erasure by rank (Jacobson) |
|
|
fingerprints of rows of doubles, dense and sparse, +0 equal to -0 and every NaN to every NaN |
|
|
compressed sparse columns or rows from triplets, repetitions summed, into the arrays of the caller (Gustavson; Davis) |
|
|
compressed sparse rows that grow by rows and shrink by sets of rows in one pass |
|
|
SplitMix64, Zobrist and simple tabulation hashing |
|
|
hashes of words and strings by folded products of 128 bits, stripes in AVX2 or AVX-512 past 256 bytes (wyhash, XXH3) |
|
|
filter of Bloom in blocks of 256 bits, one bit in each of 8 words (Putze et al.; Parquet) |
|
|
binary fuse filter, fingerprints of 8 or 16 bits (Graf and Lemire) |
|
|
cuckoo filter with removals, fingerprints of 8 or 16 bits, buckets of 4 places in one word (Fan et al.) |
|
|
prefix filter, bins of 25 fingerprints as pocket dictionaries of 32 bytes, the overflow in a blocked filter of Bloom (Even, Even and Morrison) |
|
|
standard Ribbon filter, Gauss elimination on the fly, solution by columns (Dillinger and Walzer) |
|
|
minimal perfect hash function by pilots, about 3 bits per key (PTHash) |
|
|
minimal perfect hash function by recursive splitting, about 1.8 bits per key, leaves by rotation fitting (RecSplit; Bez et al.) |
|
|
minimal perfect hash function by levels of fingerprints, ranks by blocks of 512 bits (Müller, Sanders, Schulze, Zhou; BBHash; FMPH) |
|
|
cuckoo table with buckets of 4 places, tags of 8 bits, search in breadth (Li et al.; libcuckoo) |
|
|
hash map with its pairs in a dense vector and an index of positions in groups of 12 control bytes, a removal by moving the last pair (the dictionaries of CPython 3.6; |
|
|
population count of arrays by the carry-save adders of Harley and Seal (AVX-512, AVX2), pdep, pext, select in a word (Mula, Kurz and Lemire) |
|
|
permutations by Heap’s method and in lexicographic order, combinations, with the innermost places in straight-line code |
|
|
exact cover with colors on sparse sets, the dancing cells of Knuth’s SSXCC |
|
|
lock-free queue from one producer to one consumer |
|
|
lock-free inbox of many producers |
|
|
wavelet matrix: access, rank, select, range quantiles (Claude, Navarro and Ordonez) |
|
|
code of Huffman of bytes, lengths of at most 11 bits by package-merge, four streams, up to three symbols a lookup |
|
|
rANS of order 0 with four interleaved states (Duda; Giesen) |
|
|
Stream VByte, the lengths apart, one shuffle per 4 integers (Lemire, Kurz and Rupp) |
|
|
rank and select in about 3.9% of the bits, one 128-bit entry per 4096 bits (Kurpicz; Zhou, Andersen and Kaminsky) |
|
|
rank and select with the counts inside the lines of the bits, rank in one access (SPIDER, Laws et al.) |
|
|
compressed vector of bits in m H0 + 0.175 m bits with rank and select (Raman, Raman and Rao; Claude and Navarro) |
|
|
tANS of order 0 with 2^11 states, two halves of four states each (Duda) |
|
|
directly addressable codes with the optimal widths (Brisaboa, Ladra and Navarro) |
|
|
parse of LZ77 with no window in O(n) time (Karkkainen, Kempa and Puglisi) |
|
|
tree of losers with the keys in its nodes, matches with no jump on the integers (Knuth; MCSTL, tlx) |
|
|
merge of k sorted ranges by a lazy funnel of binary mergers (Frigo et al.; Brodal et al.) |
|
|
cuckoo table shared by threads, buckets of 4 places, locks on 2048 stripes, paths searched in breadth without locks (Li et al.; libcuckoo) |
|
|
cuckoo table shared by threads, buckets of 4 places, one lock per region of buckets, lookups without locks under versions (seqlock), huge pages (Li et al.; libcuckoo) |
|
|
lock-free queue of many producers, a lane of recycled blocks each |
|
|
bounded queue of many producers and many consumers, a sequence in each place (Vyukov) |
|
|
event count, the sleep of a thread until a condition holds, with asymmetric fences |
|
|
sparse matrices in compressed rows and in SELL-C-sigma (Kreutzer et al.) |
|
|
generators xoshiro256++, xoshiro256**, wyrand and the counter-based Philox4x32 and Philox4x64 (Salmon et al.), the alias method, normal and exponential deviates by ziggurats (Marsaglia and Tsang) |
|
|
work-stealing deque (Chase and Lev; Lê et al.) |
|
|
wavelet tree shaped by the code of Huffman, n(H0+1) bits (Makinen and Navarro) |
|
|
FM-index on the wavelet tree of Huffman, the succinct suffix array (Makinen and Navarro) |
|
|
partitioned Elias-Fano, blocks full, as vectors or by Elias-Fano (Ottaviano and Venturini) |
|
|
binary packing SIMD-BP128 and its patched form PFor (Lemire and Boytsov; Zukowski et al.) |
|
|
r-index: count and locate in space proportional to the runs of the transform (Gagie, Navarro and Prezza) |
|
|
move structure, a permutation of shifted intervals in O(1) a step (Nishimoto and Tabei) |
|
|
r-index on move structures (Bertram, Fischer and Nalbach) |
|