3 ms·

In my example the table stores the hash codes themselves instead of the keys (because the hash function is invertible) Oh, I see, right. If determining the hom

In my example the table stores the hash codes themselves instead of the keys (because the hash function is invertible) Oh, I see, right. If determining the home bucket is trivial, then the back-shifting method is great. The issue is just that it’s not as much of a general-purpose solution as it may initially seem. In the bad cases, it's really bad. With a different algorithm (Robin Hood or bidirectional linear probing), the load factor can be kept well over 90% with good performance, as the benchmarks in the same repo demonstrate. I’ve seen the 90% claim made several times in literature on Robin Hood hash tables. In my experience, the claim is a bit exaggerated, although I suppose it depends on what our idea of “good performance” is. See these benchmarks, which again go up to a maximum load factor of 0.95 (although boost and Absl forcibly grow/rehash at 0.85-0.9): https://strong-starlight-4ea0ed.netlify.app/ https://strong-starlight-4ea0ed.netlify.app/ Tsl, Martinus, and CC are all Robin Hood tables (https://github.com/Tessil/robin-map https://github.com/Tessil/robin-map, https://github.com/martinus/robin-hood-hashing https://github.com/martinus/robin-hood-hashing, and https://github.com/JacksonAllan/CC https://github.com/JacksonAllan/CC, respectively). Absl (from Google) and Boost are well-known C++ SIMD-based hash tables. Khash (https://github.com/attractivechaos/klib/blob/master/khash.h https://github.com/attractivechaos/klib/blob/master/khash.h) is, I think, an ordinary open-addressing table using quadratic probing. Fastmap is a new, yet-to-be-published design that is fundamentally similar to bytell (https://www.youtube.com/watch?v=M2fKMP47slQ https://www.youtube.com/watch?v=M2fKMP47slQ) but also incorporates some aspects of the aforementioned SIMD maps (in particular, it stores a 4-bit fragment of the hash code to avoid most false key comparisons). As you can see, all the Robin Hood maps spike upwards dramatically as the load factor gets high, becoming as much as 5-6 times slower at 0.95 vs 0.5 in one of the benchmarks (uint64_t key, 256-bit struct value: Total time to erase 1000 existing elements with N elements in map). Only the SIMD maps (with Boost being the clear better performer of the two) and Fastmap appear mostly immune to load factor in all benchmarks, although the SIMD maps do - I believe - use tombstones for deletion in at least some cases. I’ve only read briefly about bi-directional linear probing – never experimented with it.

senderista 3y ago
Thanks for the benchmark references. I would be curious what you think of my benchmarks of RH and BLP: https://github.com/senderista/hashtable-benchmarks/wiki/64-bit-benchmarks https://github.com/senderista/hashtable-benchmarks/wiki/64-b.... BLP performance seems much more stable than RH in general. I haven't directly compared BLP to SIMD designs (since the impl is in Java), but would like to do so at some point. At any rate, I haven't yet found any reason to use RH rather than BLP (note that a BLP impl could store preferred bucket index, truncated hash code, distance from preferred bucket, etc., just like RH).
- JacksonAllan 3y ago
  As I’m sure you know, benchmarking hash tables is pretty difficult because there’s many variables that affect their performance and it’s hard to cover all use cases. Let me start by explaining the benchmarks I linked you to earlier. Eventually they will be open-sourced and published as part of a comprehensive review of C (and some C++) hash tables, but that’s potentially months away now that there is a war in Gaza keeping me very busy in my day job. The "uint32_t key, uint32_t value" benchmarks test how the hash tables perform when the hash function and key comparison function are inexpensive, traversing buckets is inexpensive (i.e. does not cause many cache misses), and moving elements is cheap. These benchmarks disadvantage tables that store metadata in a separate array (which here are Absl, Boost, Martinus, and Fastmap) because doing so necessarily causes at least one extra cache miss per lookup. The "uint64_t key, 256-bit struct" value benchmarks test how the tables perform when the hash function and key comparison function are inexpensive, traversing buckets is expensive (a cache miss per bucket), and moving elements is expensive. These benchmarks disadvantage tables that don’t store metadata in a separate array (or do but access the buckets array with every probe anyway to check the key) and that move elements around a lot (e.g. Robin Hood). The "16-char NULL-terminated string key, uint64_t value" benchmarks test how tables perform when the hash function and key comparison function are expensive. These benchmarks disadvantage hash tables that lack a (metadata) mechanism to avoid most key comparisons or do a lot of rehashing (this is where the performance of the liner-probing/back-shift-deletion tables goes nuclear if they’re not storing hash codes or home bucket indices). As I mentioned earlier, in these benchmarks the max load factor is set to 95% (although the SIMD tables rehash early even after we modify the fixed max load factors hard-coded into the libraries). Measurements are taken at intervals of 50k. Each data point is the average of five runs. We can make the lines smoother, and therefore make the benchmarks more readable, by upping the runs to ten or more (although adding more runs hides the variability of the maps that suffer from this problem – e.g. notice how Khash’s plots are usually much more squiggly than those of the other tables?). This approach allows us to see the performance of each map across the whole spectrum of load factors from about 0.48 (the troughs) to 0.95 (the peaks). Of course, these benchmarks don’t cover all cases and combinations – just a hopefully representative sample. They also don’t show memory usage (in general, the SIMD maps have one or one-and-a-fraction of a byte of overhead per bucket, Fastmap has two bytes, and the Robin Hood maps should have anywhere from two to eight bytes). They also don’t show the effect of tombstones when we do lots of deletions (e.g. the “erasure” benchmarks don’t show why the tombstoneless Fastmap may be superior to Boost in this regard). Now, on to your benchmarks, which I had a quick look at earlier and again just now: The first thing that jumps out at me is that it looks like you’re only testing longs as keys. In other words, you appear to only be covering the first scenario - perhaps the ideal scenario for an open-addressing table - that I described above: the hash function and key comparison function are inexpensive, traversing buckets is inexpensive, and moving elements is cheap. Your results may well vary when you change any of these variables. The second thing I’m concerned about is the way you handle load factor and measurement intervals. Take your “Average time for successful lookup (90% load factor)” benchmark, for example. Are you just setting the max load factor to 90% and then measuring at 10k, 100k, 1m, 10m, and 100m elements? If so, then you’re not measuring the tables at a 90% load factor – you’re measuring them at whatever their load factors happen to be at those intervals. This might explain, for example, why the measurement of the Robin Hood map at 1m is so radically different from its measurement at 10m in that benchmark, or why your plots look like bell curves in your “Average time for successful lookup (99% load factor)” benchmark. If I’m right, then I think you need to either use a much smaller measurement interval so that you actually capture the performance near the target load or benchmark the tables not at element-count intervals but when they approach the target load factor. If you do the former (as I do), then there might not be any need for the separate lower-max-load-factor benchmarks because the highest-max-load-factor benchmarks will – as I mentioned earlier – also show the performance at lower load factors. Of course, it’s nice that your horizontal scale is exponential, not linear like mine. For my benchmarks, I’m basically assuming that the trends we can clearly see for the 0-20m range will continue at higher element counts (I can’t see why they wouldn’t, and the difference made by slightly more cache misses as the element count grows should become less and less apparent at higher counts). Anyway, that's my 2c - hope it's helpful. Let me know if you have any suggestions regarding my benchmarks. I followed you on GitHub so that I can share some more comprehensive (i.e. many more C and C++ hash tables) benchmarks with you once I have time to run the full suite again (it takes a few hours, and I only have one computer).

senderista 3y ago

Thanks for the benchmark references. I would be curious what you think of my benchmarks of RH and BLP: https://github.com/senderista/hashtable-benchmarks/wiki/64-bit-benchmarks https://github.com/senderista/hashtable-benchmarks/wiki/64-b.... BLP performance seems much more stable than RH in general. I haven't directly compared BLP to SIMD designs (since the impl is in Java), but would like to do so at some point. At any rate, I haven't yet found any reason to use RH rather than BLP (note that a BLP impl could store preferred bucket index, truncated hash code, distance from preferred bucket, etc., just like RH).

JacksonAllan 3y ago
As I’m sure you know, benchmarking hash tables is pretty difficult because there’s many variables that affect their performance and it’s hard to cover all use cases. Let me start by explaining the benchmarks I linked you to earlier. Eventually they will be open-sourced and published as part of a comprehensive review of C (and some C++) hash tables, but that’s potentially months away now that there is a war in Gaza keeping me very busy in my day job. The "uint32_t key, uint32_t value" benchmarks test how the hash tables perform when the hash function and key comparison function are inexpensive, traversing buckets is inexpensive (i.e. does not cause many cache misses), and moving elements is cheap. These benchmarks disadvantage tables that store metadata in a separate array (which here are Absl, Boost, Martinus, and Fastmap) because doing so necessarily causes at least one extra cache miss per lookup. The "uint64_t key, 256-bit struct" value benchmarks test how the tables perform when the hash function and key comparison function are inexpensive, traversing buckets is expensive (a cache miss per bucket), and moving elements is expensive. These benchmarks disadvantage tables that don’t store metadata in a separate array (or do but access the buckets array with every probe anyway to check the key) and that move elements around a lot (e.g. Robin Hood). The "16-char NULL-terminated string key, uint64_t value" benchmarks test how tables perform when the hash function and key comparison function are expensive. These benchmarks disadvantage hash tables that lack a (metadata) mechanism to avoid most key comparisons or do a lot of rehashing (this is where the performance of the liner-probing/back-shift-deletion tables goes nuclear if they’re not storing hash codes or home bucket indices). As I mentioned earlier, in these benchmarks the max load factor is set to 95% (although the SIMD tables rehash early even after we modify the fixed max load factors hard-coded into the libraries). Measurements are taken at intervals of 50k. Each data point is the average of five runs. We can make the lines smoother, and therefore make the benchmarks more readable, by upping the runs to ten or more (although adding more runs hides the variability of the maps that suffer from this problem – e.g. notice how Khash’s plots are usually much more squiggly than those of the other tables?). This approach allows us to see the performance of each map across the whole spectrum of load factors from about 0.48 (the troughs) to 0.95 (the peaks). Of course, these benchmarks don’t cover all cases and combinations – just a hopefully representative sample. They also don’t show memory usage (in general, the SIMD maps have one or one-and-a-fraction of a byte of overhead per bucket, Fastmap has two bytes, and the Robin Hood maps should have anywhere from two to eight bytes). They also don’t show the effect of tombstones when we do lots of deletions (e.g. the “erasure” benchmarks don’t show why the tombstoneless Fastmap may be superior to Boost in this regard). Now, on to your benchmarks, which I had a quick look at earlier and again just now: The first thing that jumps out at me is that it looks like you’re only testing longs as keys. In other words, you appear to only be covering the first scenario - perhaps the ideal scenario for an open-addressing table - that I described above: the hash function and key comparison function are inexpensive, traversing buckets is inexpensive, and moving elements is cheap. Your results may well vary when you change any of these variables. The second thing I’m concerned about is the way you handle load factor and measurement intervals. Take your “Average time for successful lookup (90% load factor)” benchmark, for example. Are you just setting the max load factor to 90% and then measuring at 10k, 100k, 1m, 10m, and 100m elements? If so, then you’re not measuring the tables at a 90% load factor – you’re measuring them at whatever their load factors happen to be at those intervals. This might explain, for example, why the measurement of the Robin Hood map at 1m is so radically different from its measurement at 10m in that benchmark, or why your plots look like bell curves in your “Average time for successful lookup (99% load factor)” benchmark. If I’m right, then I think you need to either use a much smaller measurement interval so that you actually capture the performance near the target load or benchmark the tables not at element-count intervals but when they approach the target load factor. If you do the former (as I do), then there might not be any need for the separate lower-max-load-factor benchmarks because the highest-max-load-factor benchmarks will – as I mentioned earlier – also show the performance at lower load factors. Of course, it’s nice that your horizontal scale is exponential, not linear like mine. For my benchmarks, I’m basically assuming that the trends we can clearly see for the 0-20m range will continue at higher element counts (I can’t see why they wouldn’t, and the difference made by slightly more cache misses as the element count grows should become less and less apparent at higher counts). Anyway, that's my 2c - hope it's helpful. Let me know if you have any suggestions regarding my benchmarks. I followed you on GitHub so that I can share some more comprehensive (i.e. many more C and C++ hash tables) benchmarks with you once I have time to run the full suite again (it takes a few hours, and I only have one computer).