Golang Maps: how Swiss Tables replaced the old bucket design
blog.gaborkoos.comReads like GPT. But, it was still interesting to me. I hadn’t heard of Swiss tables before. The article links to the primary sources, to those who want to avoid reading LLM output: https://abseil.io/about/design/swisstables
The Swiss Table is Google's preferred hash table design, it's what you get in the Abseil C++ library and for many years it is the implementation behind Rust's HashMap type too, and as you see, it's also now how Go's map works.
https://www.youtube.com/watch?v=JZE3_0qvrMg is the 2019 CppCon talk by Matt Kulukundis which gets into more depth of why this is a good idea if you're the sort of person who knows what SIMD is and how caches work.
This is one of the least clear explanations of what a hash map bucket and overflow are that I hav read.
Have to plug the original Swiss Table talk by Matt Kulukundis: https://youtu.be/ncHmEUmJZf4?si=YRl2pDvdGZgd2ROq
Excellent talk which explains the concepts really clearly and concisely.
The OP, or the Abseil docs?
gaborkoos.com blog post, It suggests that the overflow is a sort of extension of the primary bucket, when it is a entry par entry collisions resolution mechanism.
The abseil documentation is dense but clear. What I get is Swiss tables are a sort of SSE optimized upside down Merkle tree.
So, if engineers out there are not even interested in the most immediate layer of code in front of their eyes (e.g., the code that is now written by LLMs), I guess more and more the kind of stuff like the one in the article is becoming like software archeology, isn’t it?
I love to learn these stuff, and pre-llm era it gave me a plus career wise. Nowadays I guess knowing this stuff pays less off (besides increasing your curiosity)
Slop
LLMs write so badly