Implementing Understandable World Class Hash Tables in C++

on YouTube ↗01h 05m

" summary

Claims world‑class performance backed by open source code, microbenchmarks and Compiler Explorer disassembly: a Robin Hood probing invariant implemented with SIMD/SWAR metadata comparisons and hoisted hash + probe‑sequence bits yields very small false positive rates and deterministic probing (max PSL ≈ log2 N). Results show sustained high load factors (reported 99.9% load factor) and dramatic lookup speedups (better than 10× versus std::unordered_map on their benchmarks). Implementation details include aligned/unaligned SWAR finds, journaled evictions, and pragmatic cost‑model tuning; code and numbers are available to inspect.

AI-written summary · about

" chapters (35)

1. 0:00High-performance hash tables intro
2. 1:52Fast hash table requirements
3. 2:55Open addressing vs chaining
4. 4:19Robin Hood probing hash tables
5. 6:06Robin Hood fundamentals
6. 8:59Find and delete in Robin Hood tables
7. 11:05Robin Hood advantages
8. 12:10Existing Robin Hood implementations
9. 13:56High-performance design strategies
10. 17:28SWAR parallelism in hash ops
11. 20:38SIMD register experiments
12. 21:00Generic programming abstractions
13. 23:26Instruction cost models revision
14. 26:14High load factor design
15. 27:20Metadata and data layouts
16. 29:04Dynamic config goals
17. 29:26Metadata packing and SWAR
18. 32:33Aligned find with SWAR needles
19. 35:45Hash functions scatter and hoist
20. 36:51Reducing branches for predictability
21. 40:48Insertion with SWAR causality
22. 42:57Eviction chains in insertions
23. 44:24Journaling key moves
24. 45:29Avoiding division in hot paths
25. 46:13Deletion shifting and tombstones
26. 46:35Resizing without full rehash
27. 48:02Benchmark results metrics
28. 50:13Complex key comparisons perf
29. 51:35Insertion perf across configs
30. 52:429% load factor benchmarks
31. 53:25Compiler challenges optimizations
32. 56:39Autistic code branch-free
33. 58:03Find termination conditions
34. 58:45Future work production
35. 59:47Q&A on Robin Hood ops

" related talks

• 56mWhat we know about hashesAndrey Aksenov · Backend Conf 2018
• 14mSEPH: Scalable, Efficient, and Predictable Hashing on Persistent MemoryChao Wang, Junliang Hu, Tsun-Yu Yang, Yuhong Liang, Ming-Chang Yang · OSDI 2023
• 01h 03m#Hashing (Hashing Values)Dietmar Kühl · ACCU 2019
• 55mSort vs Hash A DualityPeter V Geoghegan · PGConf Silicon Valley 2016
• 59mA Hash Map for Graph Processing Workloads & a Methodology for Transactional Data StructuresChristina Peterson, Kenneth Lamar · CppCon 2021
• 40m"Gaining Constant time Lookup over Unorganized Data"Ghadi Shayban, Jeb Beich · Clojure/conj 2023
• 24mWrite-Optimized Dynamic Hashing for Persistent MemoryMoohyeon Nam · FAST '19
• 01h 13mC++ Memory Model Meets High-Update-Rate Data StructuresPaul E. McKenney · CppCon 2014