How Swiss tables work in Go built-in map

Posted by valyala 5 days ago

Counter103Comment17OpenOriginal

Comments

Comment by nasso_dev 2 days ago

swiss 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

Comment by EdSchouten 2 days ago

I guess it took a bit longer to get it adopted within Go because of some additional challenges:

https://go.dev/blog/swisstable#go-challenges

Comment by tialaramex 2 days ago

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.

Comment by jerf 2 days ago

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.

Comment by hazz 2 days ago

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.

Comment by tialaramex 2 days ago

Python's hash table type, dict, promises that it remembers insertion order. If you put the mapping 5 => "dog" in first, then when we ask what is in the dict we'd get told 5 => "dog" first, duh.

Historically Python had a more conventional but very, very badly implemented hash table type, the "I can't believe it can sort"† of hash tables. Somebody wanted a hash table type which remembers insertion order because Python programmers have a bad habit of writing "Golden tests" in which that order matters even though in a good modern hash table type it's not guaranteed, so they built one. But because the built-in hash table type was garbage, this new OrderedDict type was much faster and much smaller despite solving a more difficult problem.

For a little while it was unclear if Python would decide to rewrite their dict type to have decent performance or just embrace this new better alternative and then they decided that because it's beginner friendly they will just embrace the OrderedDict and require that this type has ordering.

However, a good hash table doesn't inherently have this property, and that goes for the Swiss Table the same as other common designs. So they can't swap dict out for a Swiss Table without breaking their own promise that the dict type preserves insertion order.

If you're used to a language where this doesn't happen such as Rust, or C++ or Java or any number of other programming languages, that insertion ordering rule seems crazy, but if you've never used a programming language at all before and have never even wondered how dict works it seems obvious that this is how it should work.

† https://hectorcorrea.com/blog/2022-08-30/i-can-t-believe-it-...

Comment by hazz 2 days ago

Yes, Ruby also has the same self-imposed constraint on insertion order. I agree it makes it more complicated to change the hash table implementation but it seems it wouldn’t be impossible to adapt Swiss Tables to support this. For example, by storing the “insertion number” (an incrementing integer) in each bucket, and possibly using table groups (as Go does) so that you only need to sort the buckets in a group, not the whole table, in order to yield entries in order. But this is just a naive sketch and I am not an expert on hash tables!

Comment by fweimer 2 days ago

ihtabs preserve iteration order and have performance competitive with swiss tables (while not requiring as high a load factor): https://github.com/vnmakarov/ihtab

Comment by tialaramex 2 days ago

That is what they claim but I'm very sceptical - not that they can preserve order but that they get similar performance.

Comment by bruce343434 2 days ago

I 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?

Comment by func25 1 day ago

Hi, author here. Thanks for the feedback.

At the table level, yes, it is an array of groups. The important part is that SIMD compares those small control bytes, not 8 complete keys.

Linear probing with a stride of 8 would work too. But when nearby groups are full, new keys keep moving to the same next empty group. As that group fills up too, the search gets longer. Triangular probing uses larger jumps to reduce this clustering, though it is not faster for every lookup. I added the explanation in the article.

The directory and multiple tables solve a separate problem, growth. A single large array would need all its entries redistributed when it grows. Go splits the storage into smaller tables so growth only rebuilds the affected table, reducing the delay that one insertion can cause. The Go blog explains this motivation.

I've added an overview near the beginning for the big picture, plus explanations of what the different parts help with at the end.

Comment by Surac 2 days ago

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

Comment by articulatepang 1 day ago

It’s important for you to hear that this kind of syntax thing really, really doesn’t matter that much. Having this kind of complaint about languages is a sign that you haven’t worked on compilers or learned about the field of programming language theory. Which is fine! But worth knowing that there are more interesting and important things to argue about.

Aspects of language design that are way more important are: the semantics, including type system, memory model, concurrency model, module system and so on; tooling; performance; FFI and OS interface; and lots of other things.

The reason these things matter more than surface-level syntax stuff is that they change what kinds of problems you can solve with the language, and what tradeoffs you’ll accept if you use it.

Of course, hyperpalatable syntax can be a factor in a language’s success, like Python. But at this point it’s Python’s ecosystem that perpetuates its dominance, and if they made some syntax changes it wouldn’t change that by much.

Comment by CyberDildonics 2 days ago

This article is about a map data structure.

Comment by pjmlp 1 day ago

I for one, love Pascal and ML's revenge on modern languages design.

Not that matters too much, given AI based programming tooling going forward.

Comment by michelleo11y 10 hours ago

[flagged]

Comment by lna_stub 2 days ago

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

Comment by donk8r 2 days ago

the 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