CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”
CppConYouTube ↗
Further reading 3
When does an implementation detail become a promise? →Callers can depend on observable behavior that was never documented. Changing an interpreter or a library then becomes a compatibility decision.When does an implementation detail become a promise? →Interpreter behavior, hash tables and public APIs illustrate how callers come to rely on what they can observe. Observable behavior need not have been formally guaranteed.What does a repeated microbenchmark leave out? →Compare the costs visible in an isolated hash-table operation with the effect of workload and cache behavior. Microbenchmarks help answer a narrower question than end-to-end measurements.
Caption notes
Swiss Tables replace pointer chains with open addressing, compact control bytes and SIMD scans. The performance tradeoffs depend on keys, loads and cache behavior.
Original passages · 6
this "what do
we gain", "what do we lose"?You get 16 probe length
in three instructions. It's amazing.But without running the data once, how do you know what
dimensions are inconsequential?they will rely upon
it, given enough users.We eliminate a memory interaction, on "find" and "insert".You get 16 probe length in three instructions