How Swiss tables work in Go built-in map
victoriametrics.com
victoriametrics.com
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
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-...
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.
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.
>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.
D have pretty much all of aspects of your main concerns and being much better than Rust and Go [1].
[1] Language Plasticity is More Important Than Ever:
https://blog.dlang.org/2026/08/10/language-plasticity-is-mor...
Not that matters too much, given AI based programming tooling going forward.
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.