#video talk by Kulukundis on #Swiss-Tables at cppcon 2019. #toread
on 02025-09-09#ByteDance proposed that #Golang use #Swiss-Tables for #hashing, apparently accepted in Go 1.24
on 02025-09-07“We are extremely pleased to announce the availability of the new “Swiss Table” family of hashtables in Abseil and the absl::Hash #hashing framework that allows easy extensibility for user defined types. Last year at CppCon, We presented a talk on a new hashtable that we were rolling out across #Google’s codebase.” #C++ #Swiss-tables #performance
on 02025-09-07#video of a talk by Kulukundis at cppcon 2017. Kip says, “Presentation about the latest tricks in hash tables. Uses SSE instructions and man is it fast. Good benchmarks against the standard C routines.” Heh: “As with anything like this, benchmarks are the only source of truth you will ever get, and they are lies.” Called "Swiss tables" (because Alkis and Roman, its primary developers, “are in the Zurich office”, and it’s “closed hashing”), supposedly the fastest hash table in the world. “What did we gain? (...) the vague feeling of superiority when we force a difficult decision onto the user. And that is the #C++ way.” You put metadata about which array elements are full or deleted into a separate byte array, along with truncated-to-7-bits hash values, to avoid needing magic sentinel values for your key type. By using SSE matching to look for truncated-hash matches in a 16-bucket group, you can find the candidates in three instructions, which also means that your erase function can avoid inserting tombstones “if any other element in the group was empty”, which seems like a pretty big win actually. Also he mentions “other sizes [than power of 2] with fast modulus”. #algorithms #performance #hashing
on 02025-09-06