How Swiss tables work in Go built-in map
victoriametrics.com
How Swiss tables work in Go built-in map
1–10 of 18 posts
Re: How Swiss tables work in Go built-in map
#2swiss tables were invented by engineers working at google's zurich office, hence the name
im surprised that go, a programming language also from google, wasn't using them!
for an excellent talk on the development of swiss tables i highly recommend this talk by Matt Kulukundis at CppCon 2017: "Designing a fast, efficient, cache-friendly hash table, step by step" https://youtu.be/ncHmEUmJZf4
Re: How Swiss tables work in Go built-in map
#3swiss tables were invented by engineers working at google's zurich office, hence the name im surprised that go, a programming language also from google, wasn't using them! for an excellent talk on the development of swiss tables i highly recommend this talk by Matt Kulukundis at CppCon 2017: "Designing a fast, efficient, cache-friendly hash table, step by step" https://youtu.be/ncHmEUmJZf4
Go is much older than Swiss Tables. Since the hash table is a widely used container type and Go aspires to having a sort of "kitchen sink" stdlib I assume Go 1.0 had a hash table, and it can't be a Swiss Table because those weren't invented yet.
Re: How Swiss tables work in Go built-in map
#4swiss tables were invented by engineers working at google's zurich office, hence the name im surprised that go, a programming language also from google, wasn't using them! for an excellent talk on the development of swiss tables i highly recommend this talk by Matt Kulukundis at CppCon 2017: "Designing a fast, efficient, cache-friendly hash table, step by step" https://youtu.be/ncHmEUmJZf4
Go is much older than Swiss Tables. Since the hash table is a widely used container type and Go aspires to having a sort of "kitchen sink" stdlib I assume Go 1.0 had a hash table, and it can't be a Swiss Table because those weren't invented yet.
It's the "map" builtin. Go has a scripting-language-esque attitude of "you can build most things with arrays and hash tables". It doesn't completely preclude getting deeper but that's the general starting point.
Re: How Swiss tables work in Go built-in map
#5swiss tables were invented by engineers working at google's zurich office, hence the name im surprised that go, a programming language also from google, wasn't using them! for an excellent talk on the development of swiss tables i highly recommend this talk by Matt Kulukundis at CppCon 2017: "Designing a fast, efficient, cache-friendly hash table, step by step" https://youtu.be/ncHmEUmJZf4
I guess it took a bit longer to get it adopted within Go because of some additional challenges:
Re: How Swiss tables work in Go built-in map
#6swiss tables were invented by engineers working at google's zurich office, hence the name im surprised that go, a programming language also from google, wasn't using them! for an excellent talk on the development of swiss tables i highly recommend this talk by Matt Kulukundis at CppCon 2017: "Designing a fast, efficient, cache-friendly hash table, step by step" https://youtu.be/ncHmEUmJZf4
The Rust std lib HashMap is powered by the hashbrown crate which is also a port of Swiss Tables. At a brief glance Ruby/Python don’t use this approach but I don’t see any reason why they couldn’t.
Re: How Swiss tables work in Go built-in map
#7the part that got me: eight control bytes packed into one uint64, so a single SIMD compare of H2 against the group spits out a bitmap of candidate slots before you've read a single key. old map just walked buckets, touching keys the whole way. that's where the lookup cost actually dropped for me
Re: How Swiss tables work in Go built-in map
#8I feel like this article does a depth first search on what swiss tables are, jumping head first into the tiniest implementation details, but I'm missing the breadth first search. What is the top level `struct` of a swiss table? An array of groups? Why not simplify all of it into linear open addressing, with a stride of 8 for simd? Why the triangular jumps? What problems does this design solve?
Re: How Swiss tables work in Go built-in map
#9Nice writeup, the group and control-word mechanics are the clearest I have seen. One thing it does not cover, and it matters in production: what the Swiss table map does to GC and real-workload memory at high cardinality.
In data-heavy Go services with maps in the millions of keys, my bottleneck was rarely lookup speed. It was memory footprint and GC cost, because the collector has to scan every pointer in the map on each mark, and a map with pointer-heavy keys or values is a lot to walk. More than once I ended up restructuring the data to be pointer-free, or moving it off-heap, just to take it off the GC's radar.
So the number I would want is not lookup throughput on a microbenchmark, but GC CPU and tail latency on a real workload at a high load factor. Has anyone measured the new map there? That is what would change my design decisions.
Re: How Swiss tables work in Go built-in map
#10Go has the same illness like rust. First var name then type. We had that back in basic and i hate it. Some argument it would be better if you declare more than one var in the same line. I never di that. Why cant we have nice things.