11–18 of 18 posts
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.
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
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.
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-...
Earlier quoted context omitted.
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.
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…
Earlier quoted context omitted.
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…
ihtabs preserve iteration order and have performance competitive with swiss tables (while not requiring as high a load factor): https://github.com/vnmakarov/ihtab
Earlier quoted context omitted.
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.
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…
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.
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.
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.
Not that matters too much, given AI based programming tooling going forward.
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?
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.