Loading…
C++Now 2018 has ended
Back To Schedule
Wednesday, May 9 • 11:00am - 12:30pm
You Can Do Better than std::unordered_map: New and Recent Improvements to Hash Table Performance

Log in to save this to your schedule, view media, leave feedback and see who's attending!

Feedback form is now closed.
The hash table is probably the most important data structure. Because of that importance, there is a large zoo of possible implementations with design trade-offs. The standard hash table, std::unordered_map, traded off performance in order to get backwards compatibility with std::map. Which was probably a good choice, but it does leave us with a lot of hash tables that are slower than necessary, while also using more memory than necessary.

This talk is about replacements for std::unordered_map. How they work, why they are faster, and when you should choose which. Topics include linear probing with Robin Hood Hashing, Google's new trick of using SIMD instructions to look at 16 elements at a time, and optimizations for node based containers, because they can actually be really fast.

I will also talk about recent improvements to hash table performance. Little tricks that shave nanoseconds from table lookup times. In an environment that's already had decades worth of micro-optimizations, it's fascinating to watch as people come up with inventive new ways to keep pushing performance.

Speakers
avatar for Malte Skarupke

Malte Skarupke

Malte is an AI programmer at Avalanche Studios in New York. In his free time he likes to optimize algorithms. He blogs at www.probablydance.com


Wednesday May 9, 2018 11:00am - 12:30pm MDT
Bethe
  presentation