Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

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

CppNow via YouTube

Overview

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

Taught by

CppNow

Reviews

Start your review of You Can Do Better than std - unordered_map - New Improvements to Hash Table Performance

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.