2 ms·

I had similar results exploring hash tables for a nearly identical task here[0]. It seems like swiss tables are tuned for workloads of mostly gets of keys that

I had similar results exploring hash tables for a nearly identical task here[0]. It seems like swiss tables are tuned for workloads of mostly gets of keys that are not present. Otherwise the two-level lookup is an extra cost with not much benefit. IIRC Joad Nacer says he is using a hash table for this (again, essentially identical) task on highload.fun[1]. This was sort if surprising for the other competitors because the top couple solutions below that one use some variety of bloom filter instead. 0: https://easyperf.net/blog/2022/05/28/Performance-analysis-and-tuning-contest-6 https://easyperf.net/blog/2022/05/28/Performance-analysis-an... 1: https://highload.fun/tasks/2/leaderboard https://highload.fun/tasks/2/leaderboard

ww520 2y ago
Yes. Swiss is good for non-duplicate lookups. For highly duplicate data the extra memory fetch for the metadata byte really kills the performance. For this contest, there’re a billion lookups with only couple hundreds distinct keys. That means for most lookups, the full path of locating the key is executed - hashing, metadata comparison, hashed value comparison, and full key comparison. It’s actually quite expensive. Removing any part from the execution path really helps.