Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lessons from Hash Table Merging

gist.github.com

Post reply on HN
Print view View original

11–20 of 23 posts

Re: Lessons from Hash Table Merging

#11

Post by SkiFire13 »

exDM69 wrote: post #9

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 numbe…

> 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.

Re: Lessons from Hash Table Merging

#13

Post by attractivechaos »

SkiFire13 wrote: post #11
exDM69 wrote: post #9

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 numbe…

> 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.

Exactly. And khashl uses Fibonacci hashing. Without salting, it has the same problem.

Re: Lessons from Hash Table Merging

#14

Post by attractivechaos »

SkiFire13 wrote: post #10

> 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.

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.

Re: Lessons from Hash Table Merging

#15

Post by khuey »

tialaramex wrote: post #4

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.

From skimming the source code it looks like the merge operation here adds the values for duplicated keys rather than replacing the first value with the second value so using HashMaps's Extend impl won't work.

Re: Lessons from Hash Table Merging

#16

Post by attractivechaos »

tialaramex wrote: post #7
OskarS wrote: post #5

Earlier quoted context omitted.

> 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 o…

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 lar…

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.

Re: Lessons from Hash Table Merging

#17

Post by oleggromov »

rurban wrote: post #6
oleggromov wrote: post #3

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

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.

Oh wow, my apology - didn't know that and didn't notice the length of the hexademical number. TIL.

Re: Lessons from Hash Table Merging

#18

Post by jesse__ »

tialaramex wrote: post #4

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.

> the people who made your HashMap type are much better equipped to optimize ...

Who's to say I'm not the one making the hashtable? There are plenty of real-world reasons the standard library hashtable may be either inaccessible or unsuitable.

Furthermore, the idea that "oh, honey, it's too hard, smart people did it for you" is insufferable and needs to die. When I'm the one making something, I have dramatically more information about the problem I'm trying to solve than the author of a hashtable library, and am therefore much better equipped to make design decision tradeoffs.

Please stop perpetuating the idea that 'just use a library' is unilaterally the best option. Sometimes, it's not.

Re: Lessons from Hash Table Merging

#19

Post by tialaramex »

attractivechaos wrote: post #16
tialaramex wrote: post #7

Earlier quoted context omitted.

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 lar…

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 depen…

> First of all, as khuey pointed out, the current implementation accumulates values. extend() replaces values instead. It wouldn't achieve the same functionality.

Ah! Yes, I apologise. I missed the + in += and I'm not used to a hash table which defaults initialization for unseen entries (as the C++ hash tables all tend to because its native container types behave that way) so I wasn't looking for it.

The SipHash will be noticeably slower, no question about it, and so if you need to and know what you're paying you can replace the hash, including with integer_hasher which gives you what you'd likely know from many C++ stdlib implementations - an identity function presented as a hash.

> This is not necessary. The rust libraries are a port of Abseil, a C++ library.

More specifically HashBrown is a port [edited: actually a re-implementation I think, design->Rust not C++->Rust] of Abseil's Swiss Tables, and these days Rust's HashMap (and HashSet of course) use HashBrown but that's not what I was getting at here

I was thinking about analogues of Extend (because as I wrote above, I didn't notice that you're accumulating not overwriting) and modern C++ has this kind of feature in Ranges::to however it doesn't quite have Extend and as I said QoI is poor, there are often trivial optimisations that Rust does but the C++ means the same but isn't optimised.

I am interested in a quite different benchmark for hash tables, rather than merging I'm interested in very small hash tables. Clearly for two items it will be faster to try them both, and clearly for a million items trying them all is awful, so I measure a VecMap type (same API as a hash table but actually just the growable array of unordered key->value pairs, searched linearly) against HashMap and other implementations of this API.

For N=25 VecMap is still competitive, but even at N=5 if we use a very fast hash (such as that identity function) instead of SipHash we can beat VecMap for most operations. I suspect this sort of benchmark would fare very differently on older hardware (faster memory relative to ALU operations) and the direction of travel is likely to stay the same for the foreseeable future. In 1975 if you have six key->value pairs you don't want a hash table because it's too slow but in 2025 you probably do.

Re: Lessons from Hash Table Merging

#20

Post by tialaramex »

jesse__ wrote: post #18
tialaramex wrote: post #4

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.

> the people who made your HashMap type are much better equipped to optimize ... Who's to say I'm not the one making the hashtable? There are plenty of real-world reasons the standard library hashtable may be either inaccessible or unsuitable. Furthermore, the idea that "oh, honey, it's too hard, smart people did it for you" is insufferable and needs to die. When I'm the one making something, I have dramatically more…

If you made your own type, you should implement Extend. It seems you agree that in this case you are best placed to do a good job.

And indeed if you have your own custom operation you want, it may well make sense for you to implement it on both your own types and stdlib types.

Post reply on HN