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 • 94 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/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

utopcellon Hacker News • Mentions

On “Swiss Tables and absl::Hash”

I believe the design is similar because Google presented the SwissTable design more than a year ago in CppCon 1. If I'm reading the link you sent correctly, then there was an initial bias in the benchmarks that favored F14, but after adjusting for that, the results are similar (not surprising since the basic idea is the same.) 1 link to this video
View on Hacker News

gopher_protocolon Hacker News • Mentions

On “Why Hashbrown Does a Double Lookup”

Open addressing has better cache performance, and for most workloads is much faster than chaining implementations. Hashbrown's implementation is based on Google's SwissTable, and they explained the reasoning behind their choices in this CppCon talk: link to this video
View on Hacker News