A Success Story in Implementing Understandable World Class Hash Tables
We present a success story about implementing one of the most important data structures, hash tables, with world class performance.
C++ allowed maintaining the Robin Hood hash table invariant (abbreviated RH) with the performance of parallel computation, even using only normal integer operations:
1. The execution costs of maintaining this invariant were minimized
2. The benefits are realized beyond other implementations
3. The actual code is easier to understand than alternatives in the performance S-tier
RH is a powerful invariant that allows implementations to unlock non-obvious and substantial benefits including cache locality.
Our solution for this challenge is to use parallel computation techniques that require only normal integer processor operations, and can be scaled up to "SIMD" operations (SIMD means "Single Instruction Multiple Data").
The parallel programming abstraction layer is composable, programmer understandable, and friendly to the optimizing compiler. We will prove these assertions with real source code, benchmarks and Compiler Explorer disassembly.
This will illustrate how specifics of RH and the scalable SIMD-based implementation gives not-seen-before improvements: using the bits devoted to "Probe Sequence Length" not just for cache locality but also reducing false matches exponentially.
These examples gives us confidence that fully realizing the powers of this invariant will outperform alternative schemes.
Eduardo Madrid
Tech Lead at Snap, Inc., helping performance on augmented reality of the Snapchat app. Author of open source libraries and components such as the Zoo type-erasure framework. Prior experience at Fintech, including automated trading. Several times presenter at CPPCon, C++ Now, C++ London
Scott Bruce
Scott has been writing software professionally for 20+ years.
He's been entranced by performance and efficiency at least 15 of those 20+ years.
He worked in distributed systems, Search, Adwords, Adsense and ML at Google for 13 years. He worked 4.5 years at Snapcht, on monetization systems, performance, and advanced mobile telemetry systems. He is currently an engineer at Rockset, working on distributed system performance and real time analytics. Presenter of a production software talk at Google, Snap, UCLA, USC, Caltech and others over the last ten plus years.