CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”

Channel:CppCon · Length:59:33 · Published:2017-10-26 · Views:137843

Watch on YouTube

Summary

Matt Kulukundis explains how Google designed SwissTable, a fast, cache-friendly hash table, step by step from std::unordered_map. The talk covers open addressing, SIMD probing and the tradeoffs of changing a fundamental data structure.

Why HN recommends it

HN repeatedly cites it as the definitive explanation of SwissTable, the design behind Abseil, Rust's hash map and Go's maps.

Excellent talk which explains the concepts really clearly and concisely. — HN, 2026

C, C++, Rust, Go & systems languages · Software performance & optimization · Algorithms & data structures

Subtitles (excerpt)

Hello. Welcome, I am Matt Kulukundis. This is "Designing A Fast, Efficient, Cache-friendly Hash Table, Step by Step". If you thought it was something else, stay, this is better then what you thought it would be. Trust me. But before I start, I just wanna give credit, 'cause this is the work of a lot of people. I am not the primary author of many of this, I'm more the primary evangelist. I convince people to do things and they listen to me 'cause they're fools. In alphabetical order, I wanna thank Elcus Evlogimanos, who is probably the most primary author for all of this. He's done the lion's share of the coding and much of the deep thought involved. Jeff Dean, from Google, came in with some brilliant insights at a very opportune moment. Jeffrey Limb, also, well everyone's at Google. Jeffrey Limb did a bit of the very micro-optimization of assembly. None of his work is actually gonna be covered 'cause it's way too low level. Roman Periplitza is responsible for all of the crazy template hackery. Sam Benza also did a huge volume of the code reviews, the template hackery, some of the optimization work, and is just sorta generally spread himself across all of it effectively. Sanjay Ghemawat, came in with Jeff Dean, at the same moment.

On Hacker News

Have to plug the original Swiss Table talk by Matt Kulukundis: [VIDEO] Excellent talk which explains the concepts really clearly and concisely. — lalitmaganti, 2026-07
Related: this talk [VIDEO] about the making of absl::flat_hash_map (a "competitor" to boost::unordered_flat_map) is one of my favorites. — KerrickStaley, 2022-11
Very cool! Independent of the cool use of `aesenc` and `aesdec`, the features for skipping ahead in the random stream and forking a separate stream are awesome. > My current home project is bump-allocator + semi-space garbage collection in SIMD for GPUs. As far as I can tell, both bump-allocation and semi-space garbage collection are easily SIMDified in an obvious manner. And since cudamalloc is … — sujayakar, 2021-03
I think you're underestimating the number of memory redirections that are necessary for chaining. It's more than one. That's the killer. It's important to be wary of assuming your data will be in cache. It usually isn't. The problem isn't making lots of high density searches in a hash map, the problem is making a search every now and then. A hash map that makes three DRAM accesses will always be … — nwallin, 2019-10
In addition to this comment's siblings resources, I also suggest this really good Cppcon presentation on Swisstable [VIDEO] — SkiFire13, 2025-07

Related videos