Skip to content
Hallway
0:00 / 0:00

#swisstable#hashtable#abseil

CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”

CppCon

189K subscribers • 103 videos on Hallway • Conference channel

YouTube
  • Recommended by 11 people: 9 on Hacker News, 1 on Lobsters and 1 curated list.
  • A classic. People kept recommending it from 2019 to 2026.
  • Presented by Matt Kulukundis, Software Engineer at Google
  • Linked in the descriptionCppCon/CppCon2017

Advanced. Deep dive for people who know the field.

137K views9 years ago11 recommendations

Systems programmingComputer scienceData structuresPerformance and optimizationC++

Matt Kulukundis explains the step-by-step design of SwissTable, Google's high-performance, SIMD-accelerated hash table.

CppCon.org — Presentation Slides, PDFs, Source Code and other presenter materials are available at: github.com/CppCon/CppCon2017 — Hash tables consume a large volume of both compute resources and memory across Google's production system. The design for hash tables in C++ traces its origins to the SGI STL implementation from 20 years ago. Over these years, computer architecture and performance has changed dramatically and we need to evolve this fundamental data structure to follow those changes. This talk describes the process of design and optimization that starts with std::unordered_map and ends with a new design we call "SwissTable", a 2-level N-way associative hash table. Our implementation of this new design gets 2-3x better performance with significant memory reductions (compared to unordered_map) and is being broadly deployed across Google. — Matt Kulukundis: Google, Senior Software Engineer 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 --- Videos Filmed & Edited by Bash Films: BashFilms.com

Why it's here

11 people recommend this, 1 disputes it

What people say. Highly recommended as an exceptional explanation of modern cache-friendly hash table design and SIMD optimization.

nwallinon Hacker News • Recommends

On “Hash tables”

…less of how much work it needs to do, and this is for two reasons. First is there obvious: RAM is slow as balls, we get it. Second is more insidious. You just evicted two cache lines. It's not just the lookup itself that's slower, you also made the consumer of your data structure slower. Here's a look at what open addressing looks like these days: link to this video (warning, it's an hour. Takes a while to build up, too. Still worth it.)…
View on Hacker News

sujayakaron Hacker News • Recommends

On “MIPS Becomes RISC-V”

…dea. I wonder if we could speed up LuaJIT even more by SIMD accelerating the GC's mark and/or sweep phases... If you're interested in more work in this area, a former coworker wrote a neat SPMD implementation of librsync 1. And, if you haven't seen it, the talk on SwissTable 2 (Google's SIMD accelerated hash table) is excellent. 1 link 2 link to this video…
View on Hacker News

KerrickStaleyon Hacker News • Recommends

On “Inside boost::unordered_flat_map”

Related: this talk link to this video about the making of absl::flat_hash_map (a "competitor" to boost::unordered_flat_map) is one of my favorites.
View on Hacker News

lalitmagantion Hacker News • Recommends

On “Golang Maps: how Swiss Tables replaced the old bucket design”

Have to plug the original Swiss Table talk by Matt Kulukundis: link to this video Excellent talk which explains the concepts really clearly and concisely.
View on Hacker News

dbremneron Lobsters • Recommends

Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step (2017)
10View on Lobsters

programming-talkscurated list on GitHubRecommends

Under “Data Structures & Algorithms”

Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step 00:59:33 by **Matt Kulukundis** (2017)
View the list

nwallinon Hacker News • Recommends

On “Open-sourcing F14 for memory-efficient hash tables”

…one which guarantees that references to keys and values will remain valid even if iterators are invalidated, and another which is faster but iterator invalidation invalidates references to keys or values. IMHO it looks like the Folly team saw the Abseil presentation last year and said, "That's a good idea, we should do that." abseil presentation: link to this video It's super interesting.…
View on Hacker News

kllrnohjon Hacker News • Recommends

On “Bulk Data Structures C++”

…large sizes probably and you're going to get much better cache density with the flat array than the array-of-buckets. There are alternative hashsets that are flat and avoid this, but they are less common and as far as I know no standard implementation on any language uses such a hash set. There's a good talk about such a dense, flat hash set here: link to this video…
View on Hacker News

vthrilleron Hacker News • Recommends

On “When Bloom filters don't bloom”

May I suggest you to have a look at Swiss Tables? There's a good talk from CppCon 0 that explains its design decisions, and implementations available as part of Abseil 1 and Rust stdlib 2. 0 link to this video 1 link 2 link
View on Hacker News

yakubinon Hacker News • Recommends

On “Transmission torrent client ported to C++”

STL has a lot of weird pitfalls. There was std::vector<bool> . Here you can see some pitfalls of std::unordered_map : < link to this video >. The whole talk is interesting to watch. In the beginning you can also see the puzzling design of std::unordered_map (puzzling because of the number of indirections). I'd reach for abseil first: < link >.
View on Hacker News

jbandela1on Hacker News • Recommends

On “Hash Ordering and Hyrum's Law”

link to this video Is a fun presentation by Matthew Kulukundis (designer of Google's Hash Table) with Hyrum Wright offering objections from the crowd (Hyrum's law) about the design and rollout of it at Google
View on Hacker News

SkiFire13on Hacker News • Recommends

On “How we tracked down a Go 1.24 memory regression”

In addition to this comment's siblings resources, I also suggest this really good Cppcon presentation on Swisstable link to this video
View on Hacker News

josefxon Hacker News • Disputes

On “Transmission torrent client ported to C++”

> link to this video Some good points, but also "calling find with C strings is slow", you are using C strings, don't expect speed from code worshiping strlen of all things. Also the issue with integer hash being its identity? That is the case for every language I checked (Python, Java, C#).
View on Hacker News

u/pigeon768in r/C_Programming • Mentions

On “Is it big brain to skip the hash function for 64-bit keys?”

Depends on the hash table. In C++, the hash function for integers *is* the identity function. `std::hash<int>{}(x)` is just `x`. It does basically exactly what you said. High performance hash tables tend to rely heavily on *all* of the bits of the hash being good. They will use a two level--sort of--hash table, where the top 54 bits do one thing and the bottom 8 bits do a second thing. You can reduce the expected number of false/collided checks to zero using SIMD instructions. But this only works if *every single bit* of your hash function is good. Here's a video about a Google engineer developing a very fast hash table in C++. I believe it's used in the entirety of Google right now. The…
8View on Reddit

u/skeetoin r/C_Programming • Mentions

On “Why is there no C conference?”

Every year you can think of a subset of CppCon as being like a C conference. There are a bunch of presentations that are entirely or mostly relevant to C, and not just in a broader sense of being relevant to *any* language. I plucked out a bunch from CppCon 2017 for you. These are *roughly* ordered from best to worst: * [Matt Godbolt “What Has My Compiler Done for Me Lately? Unbolting the Compiler's Lid”] * Chandler Carruth “Going Nowhere Faster” * James McNellis “Everything You Ever Wanted to Know about DLLs” * John Regehr “Undefined Behavior in 2017 (part 1 of 2)” * John Regehr “Undefined Behavior in 2017 (part 2 of 2)” * Piotr Padlewski “Undefined Behaviour is awesome!” * [Tob…
7View on Reddit

u/Fluid-Being-3515in r/C_Programming • Mentions

I made an STB style swiss table implementation https://github.com/vanelk/stb\_swiss\_tbl This is basically roughly based on this talk link to this video I really wanted to experiment with this idea, and when I decided to re-design it in C as an STB-style library. I also use external dependencies for hashing, and my array implementation is nothing's stb.h
5View on Reddit