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

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.

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.

> 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 nondeterministic iteration offset to each hash table to prevent anyone from relying on this moving forward.

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 lookups, it can be better to avoid the cost of doing one load in the small array of markers and another load in the large array of hash table entries. In the talk the presenter also says that they've changed the first load in such a way that it sometimes spans two cache lines, which makes it a bit more expensive, but that this was nonetheless a win for them.

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 and it made no sense to depend on. And the defence mentioned in this thread (randomise things which aren't guaranteed to have stability) is introduced because these are Google employees, they know about Hyrum, it just isn't enough. Sure the code failed when I tried to store 40 items due to your randomisation, but I found it worked OK with ten items as then the randomisation was defeated, so now I store ten items, and then your latest change broke that... The pathological use of data structure is why stuff like making the constructor for empty strings very cheap has a big effect on some codebases. Rust const-ified String::new() because an empty string doesn't need any heap store. So this means code which loops over a large array setting all the members to the empty string is only about as exp