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

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.)

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]

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.

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]

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

> 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]

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]