Birbla

Join the discussion

Write your take first — we'll ask for email only when you're ready to publish.

Sign in
  • Hacker News
  • the part that got me: eight control bytes packed into one uint64, so a single SIMD compare of H2 against the group spits out a bitmap of candidate slots before you've read a single key. old map just walked buckets, touching keys the whole way. that's where the lookup cost actually dropped for me
    by donk8r
  • Nice writeup, the group and control-word mechanics are the clearest I have seen. One thing it does not cover, and it matters in production: what the Swiss table map does to GC and real-workload memory at high cardinality.

    In data-heavy Go services with maps in the millions of keys, my bottleneck was rarely lookup speed. It was memory footprint and GC cost, because the collector has to scan every pointer in the map on each mark, and a map with pointer-heavy keys or values is a lot to walk. More than once I ended up restructuring the data to be pointer-free, or moving it off-heap, just to take it off the GC's radar.

    So the number I would want is not lookup throughput on a microbenchmark, but GC CPU and tail latency on a real workload at a high load factor. Has anyone measured the new map there? That is what would change my design decisions.

    by lna_stub
  • 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.
    by Surac
  • 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?
    by bruce343434
  • 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

    by nasso_dev

Explore Birbla archives