How Swiss tables work in Go built-in map(victoriametrics.com) |
How Swiss tables work in Go built-in map(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-...
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.
Not that matters too much, given AI based programming tooling going forward.