Abseil's Open Source Hashtables: 2 Years In - Matt Kulukundis - CppCon 2019

Channel:CppCon · Length:54:00 · Published:2019-10-02 · Views:22120

Watch on YouTube

Summary

Matt Kulukundis reviews two years of Abseil's Swiss table hashtable, covering post-release optimizations, lessons from rolling it out across Google, design choices, and what global monitoring revealed.

Why HN recommends it

HN points to it as the authoritative talk on Swiss tables, their design rationale, and real-world effects like Hyrum's law.

gets into more depth of why this is a good idea — HN, 2026

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

Subtitles (excerpt)

all right hello everyone I'm Matt Kula Kondos this is my second major talk at cpp con and two years ago I presented about the opens for the hash table that is now open sourced but before I begin I want to really clearly state this is the work of many people many of the people on the slides did the initial work many did the open sourcing work primarily schandle actually did the open sourcing work the slides I'm about to present are very heavily the work of Sam Benz akin who has done a lot of the optimizations in here but by no way am I the primary or even the major effort in any of this so I'm gonna start giving you a little overview of where we're going because this talk jumps in pretty fast I marked it in on the menu as intermediate-advanced but that's in the new zealand hiking leveling system not in the american hiking leveling system so we're going to explore a few internet interconnected big questions around our hash tables what have we learned while deploying them across Google can we improve them for CPU efficiency can we approve can we improve their memory for small tables and can we automatically identify tables that are misbehaving at scale in a way that's useful so that's sort of roughly where we're going but I'm gonna start with background there's a huge

On Hacker News

The Swiss Table is Google's preferred hash table design, it's what you get in the Abseil C++ library and for many years it is the implementation behind Rust's HashMap type too, and as you see, it's also now how Go's map works. [VIDEO] is the 2019 CppCon talk by Matt Kulukundis which gets into more depth of why this is a good idea if you're the sort of person who knows what SIMD is and how caches … — tialaramex, 2026-07
There's even a CPPCon talk about Google's "Swiss" tables with interruptions by Hyrum each time the new code's observable behaviour changes because, at Google, they internally have enough users for Hyrum's law to kick in all the time: [VIDEO] The talk was presumably better live because Hyrum doesn't have a microphone, so his interjections are hard to follow, but it's a good way to illustrate. Some… — tialaramex, 2021-06
It's one of the improvements they claimed in the 2019 presentation. [VIDEO] Reporting 10% speedup on find, but 15% slowdown on insert. The speedup probably comes from using 4 more bits of hash, which leads to fewer collisions. And slowdown from more complicated code for the mirroring. I'm still confused on the SIMD alignment. There are load instructs with alignment requirements (_mm_load_si128) a… — mizmar, 2025-07
> Abseil, Boost and Folly all provide types which lose some performance to get this back if it's all you need to be "drop-in". Indeed, Google's initial migration from std::unordered_map to swisstables moved everyone to absl::node_hash_map since it was safer, even though flat_hash_map generally offers better performance. > after adding fake users Alice, Bob and Carol to your user hash table, when … — vitus, 2024-06
There's a talk about this data structure here: [VIDEO] Basically it stores one array of 1-byte markers that contain a full-or-empty bit and a 7-bit prefix of the hash, then a separate array of buckets. The lookup first loads a neighborhood of bytes in the former array to find entries that match in the first hash byte or empty entries. If the table is very highly loaded or if the hash function is … — anonymoushn, 2022-08

Related videos