CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step” on HackerTube: recommended by 9 Hacker News commenters across 10 separate months, 2018–2026.
talk · advanced · evergreen
Matt Kulukundis explains how Google designed SwissTable, a fast, cache-friendly hash table, step by step from std::unordered_map. The talk covers open addressing, SIMD probing and the tradeoffs of changing a fundamental data structure.
HN repeatedly cites it as the definitive explanation of SwissTable, the design behind Abseil, Rust's hash map and Go's maps.
“Excellent talk which explains the concepts really clearly and concisely.”
19 Hacker News comments link this video. Each one links back to its thread.
Have to plug the original Swiss Table talk by Matt Kulukundis: ▶ this video Excellent talk which explains the concepts really clearly and concisely.
in “Golang Maps: how Swiss Tables replaced the old bucket design” · View on HN
Related: this talk ▶ this video about the making of absl::flat_hash_map (a "competitor" to boost::unordered_flat_map) is one of my favorites.
in “Inside boost::unordered_flat_map” · View on HN
Very cool! Independent of the cool use of `aesenc` and `aesdec`, the features for skipping ahead in the random stream and forking a separate stream are awesome. > My current home project is bump-allocator + semi-space garbage collection in SIMD for GPUs. As far as I can tell, both bump-allocation and semi-space garbage collection are easily SIMDified in an obvious manner. And since cudamalloc is fully synchronous, I wanted a more scalable, parallel solution to the GPU memory allocation problem. This is a great idea. 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] ▶ this video
in “MIPS Becomes RISC-V” · View on HN
I think you're underestimating the number of memory redirections that are necessary for chaining. It's more than one. That's the killer. It's important to be wary of assuming your data will be in cache. It usually isn't. The problem isn't making lots of high density searches in a hash map, the problem is making a search every now and then. A hash map that makes three DRAM accesses will always be worse that one that makes one, regardless 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: ▶ this video (warning, it's an hour. Takes a while to build up, too. Still worth it.)
in “Hash tables” · View on HN
In addition to this comment's siblings resources, I also suggest this really good Cppcon presentation on Swisstable ▶ this video
in “How we tracked down a Go 1.24 memory regression” · View on HN
▶ 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
in “Hash Ordering and Hyrum's Law” · View on HN
STL has a lot of weird pitfalls. There was std::vector<bool> . Here you can see some pitfalls of std::unordered_map : < ▶ 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] >.
in “Transmission torrent client ported to C++” · View on HN
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] ▶ this video [1] [link] [2] [link]
in “When Bloom filters don't bloom” · View on HN
This is where we get into O(1) != fast territory. Algorithmic complexity has a weak relationship to CPU performance, not a strong one. If you want to find something in a set storing it as an array and doing a linear scan will beat a std::unordered_set up to a shockingly large number of items due to how CPU's work. In particular it's the pointer chasing aspect of std::unordered_set that becomes a problem (an issue shared with _most_ hash set implementations). Remember an unordered_set is not an array of items, it's an array of buckets of items (this is how hash collision is handled). Worse still, those buckets are usually linked lists. It typically can't be speculated effectively and it can't be prefetched effectively, so you become memory latency bound during an un-cached lookup. And memory latency is just shy of absolutely terrible. If you're expecting L1/L2/L3 cache hits on lookups then you're not dealing with vary 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: ▶ this video
in “Bulk Data Structures C++” · View on HN
They are very, very similar. The hashes are two level: one is fairly traditional. You take the first k bits from the hash and look that up in a table. The second layer is 128 bit blocks. (one SSE/NEON register) This block contains 14 8 bit blocks, where the top bit is a tombstone marker, and the bottom 7 bits are the k+1 though k+7 bit from the hash. (or the top 7 bits? not sure. it's 7 bits from the hash that aren't used in the top layer) It uses SSE instructions to identify which of the 14 blocks to do a full key compare with. Both of them have two variants, 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: ▶ this video It's super interesting.
in “Open-sourcing F14 for memory-efficient hash tables” · View on HN
The dataset they use is <14GB of parquet [1] so the "cold start" seems to be intended to also measure having a dataset that doesn't fit in memory in a way. I don't think this is an oversight but it is just what they found to be feasible. This is explicitly written in [1]. Also the guy who setup this benchmark is very serious about benchmarking under difficult conditions [2] My personal opinion is that you need a massive amount of data and massive number of different variables to test for separately. For example you might want to monitor how many cache misses/hits there were, p99 latency etc. And you want to do it under full load, expected load etc. And you want to compare the different versions of the same database because comparing different databases makes things combinatorially more difficult, unless you have a real production use case that you are optimizing for ofc. The swisstable talk on cppcon is a good example of a useful benchmark and optimization that shows how difficult it is to really asses performance effects of even "small" changes. [3] [1] [link] [2] [link] [3] ▶ this video
in “Lies, Damn Lies and Database Benchmarks” · View on HN
Not a couple of sentences CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step” : ▶ this video
in “Swiss Tables” · View on HN
> I've implemented a hash map in my code. I loved the experience, and I know more about computers and hash maps now that I've done it. Yep, everyone at least once should implement a hash map. Hash maps are so fundamental and so often used that it really pays off to understand what makes them tick. > And my hash map was faster than the one in the C++ STL last I checked. I haven't benchmarked it against the Rust one, though. The one in C++ is very famous for being really slow, so this is a low bar to clear. (: Not sure if someone directly compared Rust's hash map to C++'s, but Rust's hash map is based on Google's SwissTable, so you can probably assume it performs roughly the same. Here are some graphs: ▶ this video
in “Why I Use C When I Believe in Memory Safety” · View on HN
Could someone explain to me in a clear and high level fashion what exactly pointer stability (or pointer instability for that regards) entails? I've watched some of the cppcon talks on the google hashtable implementation [0] and in that talk Matt Kulukundis also mentioned it affecting the adoption rate, but I always failed to really grasp the concept and its implications. Google searches also ended up rather fruitless to be honest. [0]: ▶ this video
in “A Tale of Java Hash Tables” · View on HN
Author here. A few weeks ago, we wrote about how we implemented SIMD instructions to aggregate a billion rows in milliseconds [1] thanks in great part to Agner Fog’s VCL library [2]. Although the initial scope was limited to table-wide aggregates into a unique scalar value, this was a first step towards very promising results on more complex aggregations. With the latest release of QuestDB, we are extending this level of performance to key-based aggregations. To do this, we implemented Google’s fast hash table aka “Swisstable” [3] which can be found in the Abseil library [4]. In all modesty, we also found room to slightly accelerate it for our use case. Our version of Swisstable is dubbed “rosti”, after the traditional Swiss dish [5]. There were also a number of improvements thanks to techniques suggested by the community such as prefetch (which interestingly turned out to have no effect in the map code itself) [6]. Besides C++, we used our very own queue system written in Java to parallelise the execution [7]. The results are remarkable: millisecond latency on keyed aggregations that span over billions of rows. We thought it could be a good occasion to show our progress by making this latest release available to try online with a pre-loaded dataset. It runs on an AWS instance using 23 threads. The data is stored on disk and includes a 1.6billion row NYC taxi dataset, 10 years of weather data with around 30-minute resolution and weekly gas prices over the last decade. The ins
in “Show HN: Query 1.6B rows in milliseconds, live” · View on HN
Apparently the standard imposes a set of requirements that the implementation must abide by thus making it a lot slower. [0] : [link] [1] : [link] [2] : ▶ this video
in “Why databases use ordered indexes but programming uses hash tables” · View on HN
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: ▶ this video
in “Why Hashbrown Does a Double Lookup” · View on HN
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] ▶ this video
in “Swiss Tables and absl::Hash” · View on HN
> ▶ 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#).
in “Transmission torrent client ported to C++” · View on HN