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
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
- Bryan Cantrill on Jails and Solaris Zones · PapersWeLove · 1:45:46
- Twitter and Visual Studio Rant · Molly Rocket · 38:19
- LibreSSL: The first 30 days, and what the Future Holds · Andrea Ross · 1:05:50
- Mock Interview with Shawn McGrath · Molly Rocket · 1:41:38
- Robocalypse Now: Using Deep Learning to Combat Cheating in Counter-Strike: Global Offensive · GDC Festival of Gaming · 1:05:25
- CppCon 2016: Chandler Carruth “Garbage In, Garbage Out: Arguing about Undefined Behavior..." · CppCon · 57:39
- CppCon 2015: Herb Sutter "Writing Good C++14... By Default" · CppCon · 1:29:05
- 3D Gaussian Splatting - Why Graphics Will Never Be The Same · IndividualKex · 2:12
- How Python was Shaped by leaky Internals, Armin Ronacher, Flask framework · Видео с мероприятий {speach! · 49:55
- CppCon 2015: Andrei Alexandrescu “std::allocator...” · CppCon · 1:12:27
- Lexical Scanning in Go - Rob Pike · GoogleFOSSSydney · 51:17
- Preventing the Collapse of Civilization / Jonathan Blow (Thekla, Inc) · DevGAMM · 1:02:41
- "Performance Matters" by Emery Berger · Strange Loop Conference · 42:15
- The Thirty Million Line Problem · Molly Rocket · 1:48:55
- RustConf 2018 - Closing Keynote - Using Rust For Game Development by Catherine West · Rust Programming Language · 42:29
- Erlang Factory 2014 - That's 'Billion' with a 'B': Scaling to the Next Level at WhatsApp · Erlang Solutions · 49:15