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.
Comments
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?
Hi, author here. Thanks for the feedback.
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.