2 ms·
Reads 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
by christophilus 3mo ago
Reads 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 https://abseil.io/about/design/swisstables
- Beretta_Vexee 3mo agoThis is one of the least clear explanations of what a hash map bucket and overflow are that I hav read.
- lalitmaganti 3mo agoHave to plug the original Swiss Table talk by Matt Kulukundis: https://youtu.be/ncHmEUmJZf4?si=YRl2pDvdGZgd2ROq https://youtu.be/ncHmEUmJZf4?si=YRl2pDvdGZgd2ROq Excellent talk which explains the concepts really clearly and concisely.
- denotational 3mo agoThe OP, or the Abseil docs?
- Beretta_Vexee 3mo agogaborkoos.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.
- tialaramex 3mo agoThe 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 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.