C++Now 2018: You Can Do Better than std::unordered_map: New Improvements to Hash Table Performance

Malte Skarupke explains why std::unordered_map is slow and presents faster hash table designs, including Robin Hood hashing and SIMD optimizations.

cppnow.org — Presentation Slides, PDFs, Source Code and other presenter materials are available at: cppnow.org/history/2018/talks/ — 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. — 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 — Videos Filmed & Edited by Bash Films: BashFilms.com --- *--* ---