4 ms·

Lessons from Hash Table Merging

willvarfar 9mo ago
Kudos, neat digging and writeup that makes us think :) If you merge linear probed tables by iterating in sorted hash order then you are matching the storage order and can congest particular parts of the table and cause the linear probing worse case behaviour. By changing the iteration order, or salting the hash, you can avoid this. Of course chained hash tables don't suffer from this particular problem. My quick thought is that hash tables ought keep an internal salt hidden away. This seems good to avoid 'attacks' as well as speeding up merging etc. The only downside I can think of is that the creation of the table needs to fetch a random salt that might not be quick, although that can alleviated by allowing it to be set externally in the table creation so people who don't care can set it to 0 or whatever. What am I missing?
- kzrdude 9mo ago
  Having a per-table key for the hash function is what siphash authors propose and what many do to combat dos attacks right? For example Rust's default HashMap. The keys are hidden/secret to the system external to the application.
oleggromov 9mo ago
There's a typo with 'ULL' string suffixes in the hexadecimal numbers in the first code example.
- rurban 9mo ago
  No, 0xd6e8feb86659fd93ULL is a valid unsigned long long number. With stdint.h you'd get portable suffix macros, which would help on non-Windows, but they do look worse.
  - oleggromov 9mo ago
    Oh wow, my apology - didn't know that and didn't notice the length of the hexademical number. TIL.
tialaramex 9mo ago
In Rust, don't do this, it's more work and it'll tend to be slower, often much slower. HashMap implements Extend, so just h0.extend(h1) and you're done, the people who made your HashMap type are much better equipped to optimize this common operation. In a new enough C++ in theory you might find the same functionality supported, but Quality of Implementation tends to be pretty frightful.
- OskarS 9mo ago
  > HashMap implements Extend, so just h0.extend(h1) and you're done, the people who made your HashMap type are much better equipped to optimize this common operation. Are you sure? I'm not very used to reading Rust stdlib, but this seems to be the implementation of the default HashMap extend [1]. It just calls self.base.extend. self.base seems to be hashbrown::hash_map, and this is the source for it's extend [2]. In other words, does exactly the same thing, just iterates through hash map and inserts it. Maybe I'm misreading something going through the online docs, or Rust does the "random seed" thing that abseil does, but just blinding assuming something doesn't happen "because Rust" is a bit silly. [1]: https://doc.rust-lang.org/src/std/collections/hash/map.rs.html#2817-2819 https://doc.rust-lang.org/src/std/collections/hash/map.rs.ht... [2]: https://docs.rs/hashbrown/latest/src/hashbrown/map.rs.html#4649 https://docs.rs/hashbrown/latest/src/hashbrown/map.rs.html#4...
  - tialaramex 9mo ago
    Yes, HashMap will by default be randomly seeded in Rust, but also the code you linked intelligently reserves capacity. If h0 is empty, it reserves enough space for all of h1, and if it isn't then it reserves enough extra space for half of h1, which turns out to be a good compromise. Note that the worst case is we ate a single unneeded growth, while the best case is that we avoided N - 1 grows where N may be quite large.
    - attractivechaos 9mo ago
      First of all, as khuey pointed out, the current implementation accumulates values. extend() replaces values instead. It wouldn't achieve the same functionality. I tried extend() anyway. It didn't work well. Based on your description, extend() implements a variation of preallocation (i.e. Solution II). However, because it doesn't always reserve enough space to hold the merged hash table, clustering still happens depending on N. I have updated the rust implementation (with the help of LLM as I am not a good rust programmer). You can try it yourself with "ht-merge-rust 1 -e -n14m" or point out if I made mistakes. > HashMap will by default be randomly seeded in Rust Yes, so it is with Abseil. The default rust hash functions, siphash in the standard library and foldhash in hashbrown, are ~3X as slow in comparison to simple hash functions on pure insertion load. When performance matters, we will use faster hash functions at least for small keys and will need a solution from my post. > In a new enough C++ in theory you might find the same functionality supported, but Quality of Implementation tends to be pretty frightful. This is not necessary. The rust libraries are a port of Abseil, a C++ library. Boost is as fast as Rust. Languages/libraries should learn from each other, not fight each other.
exDM69 9mo ago
Maybe this would be a suitable application for "Fibonacci hashing" [0][1], which is a trick to assign a hash table bucket from a hash value. Instead of just taking the modulo with the hash table size, it first multiplies the hash with a constant value 2^64/phi where phi is the golden ratio, and then takes the modulo. There may be better constants than 2^64/phi, perhaps some large prime number with roughly equal number of one and zero bits could also work. This will prevent bucket collisions on hash table resizing that may lead to "accidentally quadratic" behavior [2], while not requiring rehashing with a different salt. I didn't do detailed analysis on whether it helps on hash table merging too, but I think it would. [0] https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ https://probablydance.com/2018/06/16/fibonacci-hashing-the-o... [1] https://news.ycombinator.com/item?id=43677122 https://news.ycombinator.com/item?id=43677122 [2] https://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion https://accidentallyquadratic.tumblr.com/post/153545455987/r...
- SkiFire13 9mo ago
  > This will prevent bucket collisions on hash table resizing Fibonacci hashing is really adding another multiplicative hashing step followed by dropping the bottom bits using a shift operation instead of the top bits using an and operation. Since it still works by dropping bits, items that were near before the resize will still be near after the resize and it won't really change anything.
  - attractivechaos 9mo ago
    Exactly. And khashl uses Fibonacci hashing. Without salting, it has the same problem.
SkiFire13 9mo ago
> I evaluated the following hash table libraries, all based on linear probing. > Abseil > Rust standard > hashbrown These hash tables are not based on plain linear probing, they use something that's essentially quadratic probing done in chunks. Not sure about the others but they might be doing something similar.
- attractivechaos 9mo ago
  These three and boost are all based on swiss tables. They are indeed more robust than plain linear probing. khashl is the only one here using basic linear probing. Without salting, its curve is through the roof, much worse than swiss tables.
wehateclusters 9mo ago
[dead]
AlotOfReading 9mo ago
This easier to solve if you use a permutation instead of hash functions. Let h0 be the larger table, and h1 the smaller. N = len(h0), M = len(h1). Pretend the elements of the tables are sequentially indexed. Element[0] is h0[0], Element[N] is h1[0], etc. h0' = Resize(h0, (N+M)*capacity_factor) for x in 0...(range): y = permute(x, 0, (N+M)*capacity_factor) if(y >= N) move_to(h0'[y], element[x]) One allocation and you move the minimum number of elements needed to eliminate primary clustering. Elements in h0 that aren't moved would presumably remain correctly indexed. You have to move the remaining elements of h1 as well, but that cluttered things. Any randomish permutation works, from basic ones up to cryptographic. If your permutation only works on certain powers of two, iterate it until the result is in range.

Kudos, neat digging and writeup that makes us think :) If you merge linear probed tables by iterating in sorted hash order then you are matching the storage order and can congest particular parts of the table and cause the linear probing worse case behaviour. By changing the iteration order, or salting the hash, you can avoid this. Of course chained hash tables don't suffer from this particular problem. My quick thought is that hash tables ought keep an internal salt hidden away. This seems good to avoid 'attacks' as well as speeding up merging etc. The only downside I can think of is that the creation of the table needs to fetch a random salt that might not be quick, although that can alleviated by allowing it to be set externally in the table creation so people who don't care can set it to 0 or whatever. What am I missing?

kzrdude 9mo ago
Having a per-table key for the hash function is what siphash authors propose and what many do to combat dos attacks right? For example Rust's default HashMap. The keys are hidden/secret to the system external to the application.

oleggromov 9mo ago

There's a typo with 'ULL' string suffixes in the hexadecimal numbers in the first code example.

rurban 9mo ago
No, 0xd6e8feb86659fd93ULL is a valid unsigned long long number. With stdint.h you'd get portable suffix macros, which would help on non-Windows, but they do look worse.
- oleggromov 9mo ago
  Oh wow, my apology - didn't know that and didn't notice the length of the hexademical number. TIL.

tialaramex 9mo ago

In Rust, don't do this, it's more work and it'll tend to be slower, often much slower. HashMap implements Extend, so just h0.extend(h1) and you're done, the people who made your HashMap type are much better equipped to optimize this common operation. In a new enough C++ in theory you might find the same functionality supported, but Quality of Implementation tends to be pretty frightful.

OskarS 9mo ago
> HashMap implements Extend, so just h0.extend(h1) and you're done, the people who made your HashMap type are much better equipped to optimize this common operation. Are you sure? I'm not very used to reading Rust stdlib, but this seems to be the implementation of the default HashMap extend [1]. It just calls self.base.extend. self.base seems to be hashbrown::hash_map, and this is the source for it's extend [2]. In other words, does exactly the same thing, just iterates through hash map and inserts it. Maybe I'm misreading something going through the online docs, or Rust does the "random seed" thing that abseil does, but just blinding assuming something doesn't happen "because Rust" is a bit silly. [1]: https://doc.rust-lang.org/src/std/collections/hash/map.rs.html#2817-2819 https://doc.rust-lang.org/src/std/collections/hash/map.rs.ht... [2]: https://docs.rs/hashbrown/latest/src/hashbrown/map.rs.html#4649 https://docs.rs/hashbrown/latest/src/hashbrown/map.rs.html#4...
- tialaramex 9mo ago
  Yes, HashMap will by default be randomly seeded in Rust, but also the code you linked intelligently reserves capacity. If h0 is empty, it reserves enough space for all of h1, and if it isn't then it reserves enough extra space for half of h1, which turns out to be a good compromise. Note that the worst case is we ate a single unneeded growth, while the best case is that we avoided N - 1 grows where N may be quite large.
  - attractivechaos 9mo ago
    First of all, as khuey pointed out, the current implementation accumulates values. extend() replaces values instead. It wouldn't achieve the same functionality. I tried extend() anyway. It didn't work well. Based on your description, extend() implements a variation of preallocation (i.e. Solution II). However, because it doesn't always reserve enough space to hold the merged hash table, clustering still happens depending on N. I have updated the rust implementation (with the help of LLM as I am not a good rust programmer). You can try it yourself with "ht-merge-rust 1 -e -n14m" or point out if I made mistakes. > HashMap will by default be randomly seeded in Rust Yes, so it is with Abseil. The default rust hash functions, siphash in the standard library and foldhash in hashbrown, are ~3X as slow in comparison to simple hash functions on pure insertion load. When performance matters, we will use faster hash functions at least for small keys and will need a solution from my post. > In a new enough C++ in theory you might find the same functionality supported, but Quality of Implementation tends to be pretty frightful. This is not necessary. The rust libraries are a port of Abseil, a C++ library. Boost is as fast as Rust. Languages/libraries should learn from each other, not fight each other.

exDM69 9mo ago

Maybe this would be a suitable application for "Fibonacci hashing" [0][1], which is a trick to assign a hash table bucket from a hash value. Instead of just taking the modulo with the hash table size, it first multiplies the hash with a constant value 2^64/phi where phi is the golden ratio, and then takes the modulo. There may be better constants than 2^64/phi, perhaps some large prime number with roughly equal number of one and zero bits could also work. This will prevent bucket collisions on hash table resizing that may lead to "accidentally quadratic" behavior [2], while not requiring rehashing with a different salt. I didn't do detailed analysis on whether it helps on hash table merging too, but I think it would. [0] https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ https://probablydance.com/2018/06/16/fibonacci-hashing-the-o... [1] https://news.ycombinator.com/item?id=43677122 https://news.ycombinator.com/item?id=43677122 [2] https://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion https://accidentallyquadratic.tumblr.com/post/153545455987/r...

SkiFire13 9mo ago
> This will prevent bucket collisions on hash table resizing Fibonacci hashing is really adding another multiplicative hashing step followed by dropping the bottom bits using a shift operation instead of the top bits using an and operation. Since it still works by dropping bits, items that were near before the resize will still be near after the resize and it won't really change anything.
- attractivechaos 9mo ago
  Exactly. And khashl uses Fibonacci hashing. Without salting, it has the same problem.

SkiFire13 9mo ago

> I evaluated the following hash table libraries, all based on linear probing. > Abseil > Rust standard > hashbrown These hash tables are not based on plain linear probing, they use something that's essentially quadratic probing done in chunks. Not sure about the others but they might be doing something similar.

attractivechaos 9mo ago
These three and boost are all based on swiss tables. They are indeed more robust than plain linear probing. khashl is the only one here using basic linear probing. Without salting, its curve is through the roof, much worse than swiss tables.

wehateclusters 9mo ago

[dead]

AlotOfReading 9mo ago

This easier to solve if you use a permutation instead of hash functions. Let h0 be the larger table, and h1 the smaller. N = len(h0), M = len(h1). Pretend the elements of the tables are sequentially indexed. Element[0] is h0[0], Element[N] is h1[0], etc. h0' = Resize(h0, (N+M)*capacity_factor) for x in 0...(range): y = permute(x, 0, (N+M)*capacity_factor) if(y >= N) move_to(h0'[y], element[x]) One allocation and you move the minimum number of elements needed to eliminate primary clustering. Elements in h0 that aren't moved would presumably remain correctly indexed. You have to move the remaining elements of h1 as well, but that cluttered things. Any randomish permutation works, from basic ones up to cryptographic. If your permutation only works on certain powers of two, iterate it until the result is in range.