The Holy Grail - A Hash Array Mapped Trie for C++
summary
A C++ reference implementation of a Hash Array Mapped Trie is proposed for Boost/standard, using Hash Array Mapped Trie layout with 32-way branching (peeling 5 bits per level) giving max depth ~6–7 and average depth ≈5 for large sets; benchmarks use clang/libc++ and microbenchmarks on 100k+ items. Lookup performance approaches or sometimes beats unordered_set for well‑distributed hashes (base64 strings), but persistent insert costs are high (≈4–5× slower than std::set, ≈20× vs unordered_set on monotonic ints). Implementation uses a bitmap + compact array and a popcount intrinsic, and offers an atomic shared_hash_tree for lock‑free update/commit.
AI-written summary · about
chapters (9)
- 0:00Introduction to HAMTs
- 3:27C++ associative containers
- 7:07Persistent data structures
- 10:06Persistent binary trees
- 13:36Designing the hash tree
- 18:11Array mapping implementation
- 21:18Performance benchmarks
- 29:30Code and concurrency
- 33:34Conclusion and resources
related talks
51mThe Holy Grail! A Hash Array Mapped Trie for C++
51m“Cache Optimized Hash Tables”
40mImmutable Data Structures in C++
30m“Esoteric Data Structures and Where to Find Them”
50mMastering the unordered_map in C++
01h 02m“Lightweight Object Persistence With Relocatable Heaps in Modern C++"
56m“High Performance Code 201: Hybrid Data Structures"
55m “High Performance C++ Concurrent Transactional Data Structures"