Swissing a table
35 points by carlana
35 points by carlana
This year I chose to investigate “Swiss tables”, the new hash table idea behind recent improvements to Go’s maps.
New idea? Hm, is this different from the old C++ swiss table? https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h (circa 2018)
It's not. This is acknowledged in the Go blogpost introducing the new Swiss Tables implementation.
Like sorting algorithms, hash table data structures continue to see improvements. In 2017, Sam Benzaquen, Alkis Evlogimenos, Matt Kulukundis, and Roman Perepelitsa at Google presented a new C++ hash table design, dubbed "Swiss Tables". In 2018, their implementation was open sourced in the Abseil C++ library.
Go 1.24 includes a completely new implementation of the built-in map type, based on the Swiss Table design.
Hash tables, when they work well, work very well and are kinda hard to beat in a decisive manner.
I think in general alternatives would probably do well to focus on the areas where hash tables are weak, which is mostly when you have to grow or resize the table.
I wonder if there's a no-copy way in which to change the type of the underlying table from hash to swiss when the threshold on which the later ones have improved performance gets reached.