Skip to content
Hallway
0:00 / 0:00

#abseil#swisstable#hashtable

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

CppCon

189K subscribers • 101 videos on Hallway • Conference channel

YouTube
  • Recommended by 1 person: 1 on Hacker News.
  • A classic. People kept recommending it from 2021 to 2026.
  • Presented by Matt Kulukundis, senior software engineer at Google
  • Linked in the descriptionCppCon/CppCon2019

Advanced. Deep dive for people who know the field.

22K views7 years ago1 recommendation

Systems programmingComputer scienceData structuresC++Performance and optimization

Matt Kulukundis reviews the design, optimizations, and rollout lessons of Google's Abseil Swiss Table hash tables.

CppCon.org Discussion & Comments: reddit.com/r/cpp/ Presentation Materials: github.com/CppCon/CppCon2019 — Abseil's Open Source Hashtables: 2 Years In Two years ago we announced a new hashtable we were pushing out across Google. One year ago, we open sourced it as part of Abseil. This talk is a retrospective about those efforts. We will cover: - optimizations after the initial release - lessons from rollout across google - design choices that paid dividends - global monitoring of hashtables - discoveries made from monitoring — Matt Kulukundis Matt is a senior software engineer on the C++ libraries team at Google. Prior to Google he has worked on compilers, machine learning, and underwater robotics. In his free time, he scuba dives in warm places. — Videos Filmed & Edited by Bash Films: BashFilms.com Work at Hudson River Trading (HRT): tinyurl.com/safxfctf

Why it's here

1 person recommends this

What people say. Recommended for its deep dive into high-performance hash table design using SIMD and cache-friendly layouts.

tialaramexon Hacker News • Recommends

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: link to 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…
View on Hacker News

tialaramexon Hacker News • Recommends

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. link to 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.
View on Hacker News

anonymoushnon Hacker News • Mentions

On “A quick and practical “MSI” hash table”

There's a talk about this data structure here: link to 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…
View on Hacker News

vituson Hacker News • Mentions

On “Compilers are too smart”

…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: link to 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.…
View on Hacker News

mizmaron Hacker News • Mentions

On “SIMD within a register: How I doubled hash table lookup performance”

It's one of the improvements they claimed in the 2019 presentation. link to 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.
View on Hacker News

u/jacksaccountonredditin r/C_Programming • Mentions

On “If this isn't the perfect data structure, why?”

This thread has obviously been a real rollercoaster. I responded to one of your other comments, but let me just add some general observations here. From your other comments, it seems like your knowledge of hash tables might be limited to closed-addressing/separate-chaining hash tables. The current frontrunners in high-performance, memory-efficient hash table design all use some form of open addressing, largely to avoid pointer chasing and limit cache misses. In this regard, you want to check our SSE-powered hash tables (such as Abseil, Boost, and Folly/F14), Robin Hood hash tables (such as Martinus and Tessil), or Skarupke (I've recently had a lot of success with a similar design that…
2View on Reddit