You Can Do Better than std - unordered_map - New Improvements to Hash Table Performance

Explore advanced hash table implementations and performance optimizations beyond std::unordered_map in this comprehensive conference talk from C++Now 2018. Dive into topics such as linear probing with Robin Hood Hashing, Google's SIMD-based optimization techniques, and node-based container improvements. Learn about recent micro-optimizations that enhance lookup times and compare the performance of various hash table implementations. Gain insights into when to choose specific hash table variants and understand the trade-offs between speed and memory usage. Discover how innovative approaches continue to push the boundaries of hash table performance, even in a field with decades of optimization history.

Syllabus

Intro
Why talk about hash tables?
Performance of standard containers
Vs linear search
Why are hash tables slow?
Talk Preview
What should we measure?
Optimization 1/7: Integer Modulo
Adding ska unordered_map
Cache Miss Lookup
Optimization 2/7: Cache Misses
A simple unordered_map
Open Addressing
dense_hash_map performance
Optimization 3/7: Back to Linked Lists
ptr_hash_map performance
Optimization 4/7: Robin Hood Hashing
Robin Hood Hashing Performance
A different perspective
The memory overhead of ska::flat_hash_map
Effect of max_load_factor
Optimization 5/7: Google's New flat_hash_map
How do we make it faster?
How many bits does Robin Hood Hashing need?
Optimization 6/7: Robin Hood Hashing +SIMD
Robin Hood SIMD Performance
Chaining hash table lookups
Reminder: What ptr_hash_map looks like