4 ms·

Have you compared to ska::flat_hash_map or khash? I’ve found the latter to be ideal if my keys/values were POD and the former otherwise. I’m not yet convinced t

Have you compared to ska::flat_hash_map or khash? I’ve found the latter to be ideal if my keys/values were POD and the former otherwise. I’m not yet convinced that it’s actually better based on their website. std::unordered_map is infamously slow.

usefulcat 7y ago
I did look at klib about a year ago. Honestly I don't recall whether I looked at khash in particular; I know I was also considering some of the other klib stuff for other uses. I did use Google's dense_hash_map for a time. For my application, the problem with implementations that use more traditional tombstone algorithms is that removing items from the table doesn't decrease the load, so that at some point the entire table has to be recreated. For my application, worst case performance is far more important than average performance. dense_hash_map definitely behaves as described above, and (from a quick look at the code) I believe khash does as well. I haven't looked at ska::flat_hash_map but thanks for the tip.
- ngbronson 7y ago
  Non-SIMD algorithms work better in some cases, for example if you look up the same key over and over (so the control flow is predictable) or when all of the data is in the L1. The SIMD approach tends to be more robust inside a larger program where there's less chance for branch prediction and caching to help you.
- attractivechaos 7y ago
  If I am right, if you delete all elements in F14, there will be no tombstone. However, if you delete some, there may still be some tombstones left. You may still need rehashing due to those remaining tombstones. In that sense, F14 is not eliminating the worst case; it makes the worst case happens less often. Then the question is how "less often". This probably depends on the access pattern. What is your access pattern? Are insertions and deletions frequently interleaved? Or do you insert a batch and then delete another batch? It will be interesting to have a micro-benchmark to measure how the F14 strategy works in practice. > I believe khash does as well. Yes, khash uses the traditional tombstone solution. It rehashes in the same space when there are too many tombstones.
  - ngbronson 7y ago
    It would be nice to have a deeper understanding of how/why this works, but in practice it seems fine. Under a continuous insert and erase workload the number of chunks with an overflow fluctuates a bit but stays low enough to keep probe lengths short, so F14 never needs to rehash to clean them up. Batched adds and then removes might let you bias a bit toward having longer probes for the remaining keys, but it never gets too bad. A truly adversarial workload could make things pretty bad, but they could also just insert lots of keys that all have the same hash code. See the steady_state_stats test at https://github.com/facebook/folly/blob/master/folly/container/test/F14MapTest.cpp#L797 https://github.com/facebook/folly/blob/master/folly/containe...
  - usefulcat 7y ago
    > What is your access pattern? Are insertions and deletions frequently interleaved? It's basically random, but generally they are very interleaved and most of the time the number of insertions and deletions are approximately equal over some period of time (~seconds). This is for keeping track of orders while processing a depth of book feed, in case you're familiar with that sort of thing. F14 is using some kind of reference counting scheme for tombstones, described in the article. I don't fully understand it, but it definitely seems different than the standard tombstone-based algorithm, which I do understand. In any case, when using something like dense_hash_map, I see huge spikes in processing time (due to rehashing) that I don't see when using F14. I also resize the hash tables up front to avoid having to do so later on, but of course for my use case that doesn't help with implementations that use a traditional tombstone algorithm unless I use ridiculously large initial sizes.
woadwarrior01 7y ago
Comparing to ska::flat_hash_map or khash wouldn't be fair, because the F14 hash tables use SIMD intrinsics to lookup 14 buckets at once (and thus the name) whilst the former two don't have that advantage. A fairer comparison would be against Swiss tables[1] from Google's abseil library, which uses the same trick. Also, std::unordered_map is slow because its interface requires a chaining based collision resolution strategy. [1]: https://abseil.io/blog/20180927-swisstables https://abseil.io/blog/20180927-swisstables
- greg7mdp 7y ago
  You may want to try my version of the Abseil hash tables (I updated the code to make them header-only) at https://github.com/greg7mdp/parallel-hashmap https://github.com/greg7mdp/parallel-hashmap.
usefulcat 7y ago
I know it's late, but I finally got around to trying ska::flat_hash_map. For my application (lots of insertions and deletions) it's not quite as fast as F14, but the difference is fairly small. It's also much easier to incorporate than folly, since the entire thing is in a single header file.

usefulcat 7y ago

I did look at klib about a year ago. Honestly I don't recall whether I looked at khash in particular; I know I was also considering some of the other klib stuff for other uses. I did use Google's dense_hash_map for a time. For my application, the problem with implementations that use more traditional tombstone algorithms is that removing items from the table doesn't decrease the load, so that at some point the entire table has to be recreated. For my application, worst case performance is far more important than average performance. dense_hash_map definitely behaves as described above, and (from a quick look at the code) I believe khash does as well. I haven't looked at ska::flat_hash_map but thanks for the tip.

ngbronson 7y ago
Non-SIMD algorithms work better in some cases, for example if you look up the same key over and over (so the control flow is predictable) or when all of the data is in the L1. The SIMD approach tends to be more robust inside a larger program where there's less chance for branch prediction and caching to help you.
attractivechaos 7y ago
If I am right, if you delete all elements in F14, there will be no tombstone. However, if you delete some, there may still be some tombstones left. You may still need rehashing due to those remaining tombstones. In that sense, F14 is not eliminating the worst case; it makes the worst case happens less often. Then the question is how "less often". This probably depends on the access pattern. What is your access pattern? Are insertions and deletions frequently interleaved? Or do you insert a batch and then delete another batch? It will be interesting to have a micro-benchmark to measure how the F14 strategy works in practice. > I believe khash does as well. Yes, khash uses the traditional tombstone solution. It rehashes in the same space when there are too many tombstones.
- ngbronson 7y ago
  It would be nice to have a deeper understanding of how/why this works, but in practice it seems fine. Under a continuous insert and erase workload the number of chunks with an overflow fluctuates a bit but stays low enough to keep probe lengths short, so F14 never needs to rehash to clean them up. Batched adds and then removes might let you bias a bit toward having longer probes for the remaining keys, but it never gets too bad. A truly adversarial workload could make things pretty bad, but they could also just insert lots of keys that all have the same hash code. See the steady_state_stats test at https://github.com/facebook/folly/blob/master/folly/container/test/F14MapTest.cpp#L797 https://github.com/facebook/folly/blob/master/folly/containe...
- usefulcat 7y ago
  > What is your access pattern? Are insertions and deletions frequently interleaved? It's basically random, but generally they are very interleaved and most of the time the number of insertions and deletions are approximately equal over some period of time (~seconds). This is for keeping track of orders while processing a depth of book feed, in case you're familiar with that sort of thing. F14 is using some kind of reference counting scheme for tombstones, described in the article. I don't fully understand it, but it definitely seems different than the standard tombstone-based algorithm, which I do understand. In any case, when using something like dense_hash_map, I see huge spikes in processing time (due to rehashing) that I don't see when using F14. I also resize the hash tables up front to avoid having to do so later on, but of course for my use case that doesn't help with implementations that use a traditional tombstone algorithm unless I use ridiculously large initial sizes.

woadwarrior01 7y ago

Comparing to ska::flat_hash_map or khash wouldn't be fair, because the F14 hash tables use SIMD intrinsics to lookup 14 buckets at once (and thus the name) whilst the former two don't have that advantage. A fairer comparison would be against Swiss tables[1] from Google's abseil library, which uses the same trick. Also, std::unordered_map is slow because its interface requires a chaining based collision resolution strategy. [1]: https://abseil.io/blog/20180927-swisstables https://abseil.io/blog/20180927-swisstables

greg7mdp 7y ago
You may want to try my version of the Abseil hash tables (I updated the code to make them header-only) at https://github.com/greg7mdp/parallel-hashmap https://github.com/greg7mdp/parallel-hashmap.

usefulcat 7y ago

I know it's late, but I finally got around to trying ska::flat_hash_map. For my application (lots of insertions and deletions) it's not quite as fast as F14, but the difference is fairly small. It's also much easier to incorporate than folly, since the entire thing is in a single header file.