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

What Hacker News said

Recommends tialaramex · 2021-06 · on “Malloc broke Serenity's JPGLoader, or: how to win the lottery”

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: [this 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 of the examples are much like this story, you design this sophisticated, heavily optimised unordered container for millions of items, and then your users put three items into it, and they depend on the order of those items and you "broke" their code by not having this behaviour you never promised an

Recommends tialaramex · 2026-07 · on “Golang Maps: how Swiss Tables replaced the old bucket design”

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. [this 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 work.

Cites anonymoushn · 2022-08 · on “A quick and practical “MSI” hash table”

There's a talk about this data structure here: [this 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 low quality, some checks for equality of the full hash or equality of the value (the former probably just costs a cache miss and the latter might be very expensive) can be skipped, but under better conditions for the hash and load factor and known-pretty-bad conditions for randomness of consecutive l

Cites vitus · 2024-06 · on “Compilers are too smart”

> 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 asked for the users back in no particular order you get exactly: Carol, Alice, Bob. Ow :( This reminded me of Matt Kulukundis at cppcon talking about migrating away from std::unordered_map, wherein he brought up this point exactly: [this video] Matt then goes on to describe how Abseil adds a nondeterminis

Cites mizmar · 2025-07 · on “SIMD within a register: How I doubled hash table lookup performance”

It's one of the improvements they claimed in the 2019 presentation. [this 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) and without (_mm_loadu_si128). Both claim the same latency and throughput. Somewhere I've heard the slowdown of unaligned access comes from using more bandwidth to load two aligned 128-bit lines to compose the unaligned value. But no idea if this affects multiple loads of continuous memory.