Overview
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
Taught by
CppNow