The Holy Grail! A Hash Array Mapped Trie for C++
summary
Proposes a Hash Array Mapped Trie (HAMT) that gives persistent structural sharing so copies cost two integers and depth for 15M items drops from ~24 (red‑black) to ~5–6, enabling cheap immutable snapshots and atomic root swaps for readers. Provides a C++ reference implementation benchmarked with nonius microbenchmark on libc++; insertion pays full persistence cost (one run shows ~4× slower than std::set and ~20× slower than unordered_set), lookup matches or beats std::set and approaches unordered_set (strings even beat unordered_set). Uses popcount optimization, intrusive ref‑counting, and notes sensitivity to hash distribution, missing deletes and allocator tuning remain to finish.
AI-written summary · about
chapters (13)
- 0:00Introduction to HAMT
- 1:04What is a trie?
- 2:30Associative containers overview
- 6:29Persistence in data structures
- 13:38Hash tables vs red-black trees
- 15:27Introducing hash-array mapped trie
- 21:53Performance benchmarks
- 28:43Optimizing hash distribution
- 31:38Bit manipulation in HAMT
- 35:45Node structure details
- 36:52Shared hash trie concurrency
- 39:46Summary and claims
- 41:38Q&A session
related talks
36mThe Holy Grail - A Hash Array Mapped Trie for C++
51m“Cache Optimized Hash Tables”
40mImmutable Data Structures in C++
01h 02m“Lightweight Object Persistence With Relocatable Heaps in Modern C++"
01h 03mFunctional C++ for Fun & Profit
01h 26mLow-Latency Trading Systems in C++: Templated Meta-State Machines in HFT
58mFrozen data structures in C++14
54mAbseil's Open Source Hashtables: 2 Years In