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: [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] [VIDEO]

Related: this talk [VIDEO] about the making of absl::flat_hash_map (a "competitor" to boost::unordered_flat_map) is one of my favorites.

Have to plug the original Swiss Table talk by Matt Kulukundis: [VIDEO] Excellent talk which explains the concepts really clearly and concisely.

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: [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: [VIDEO]

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] [VIDEO] [1] [LINK] [2] [LINK]

STL has a lot of weird pitfalls. There was std::vector<bool> . Here you can see some pitfalls of std::unordered_map : < [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] >.