HashMap for a set that is known ahead of time

I have a set of 1 to 20 seemingly random and distinct integers that need to be mapped to another set of integers. I've been using the standard HashMap until now but I think it's probably possible to optimize the process.

I've done some research and I think what I need is a perfect hash function. I know there is phf crate, but it only seems to works for keys that are known at compile time. My keys are generated at runtime.

Is there a crate that allows creating hashmaps that are optimized for a precise set of values? Or do I need to implement it myself? If so, is there an obvious algorithm that I should implement?

Thanks!

1 Like

It's not obvious to me that it'd be worth doing a bunch of optimizing at runtime to figure out a PHF for whatever you happen to get.

If you're using the default HashMap, though, that comes with a DoS-resistent Hasher, which would be the easiest place to optimize things. The easiest speed improvement would probably just be to use fxhash - Rust by replacing HashMap with FxHashMap -- which is just a type alias of HashMap with a different hasher, so all the methods you're used to will still be there.

I'm currently using a custom Hasher implementation that does nothing other than assiging its input to its state. This works because I'm only receiving u64 keys.

My get operation is quite critical in term of performances, so would perfer spending a bit more time optimizing than losing a few cpu cycles each time I need to query a value.

It would be interesting to see a crate that JIT compiles simple functions like this to optimized machine code.

This may seem weird but if you only have 1-20 keys, a simple linear search may be the fastest. Especially if you can vectorize, for this you should have 2 separate arrays for the keys and values, search the keys (2-8 at a time depending on AVX and branchless), use the index for the value.

5 Likes

Here's a proof of concept JIT compiled map runnable on the playground. I would be interested in knowing how it compares to other alternatives in terms of performance.

  • It allocates 29 bytes of memory for each entry, but is rounded up to the page size, which is typically 4096 bytes. Memory management could be improved to pack multiple maps into a single page.
  • For simplicity, it does a linear search, but could be improved by striking a balance between binary search and linear search.
  • It only supports x64 Linux, but if it performs well and someone likes to make a crate out of it, support for more platforms should be added.
  • Having an enormous amount of entries in the map is undefined behavior, due to the four byte address of branches wrapping around. A crate with a safe interface would need to take care of this.
2 Likes

Unfortunately, I'm currently on Windows so I can't test it outiside the playground. It's pretty impressive nonetheless and I'd love to see how this performs compared to the other existing solutions.

EDIT: I've done some benchmarks this morning. For those who might end up need it later, here what I found on my machine. input is the number of key inserted (those are u64s), and it's mapped to the average time taken to find a random value of the set.

ahash, fxhash and nohash are hashing algoryhtm (well, nohash doesn't hash the values - and I guess it was a mistake on my part). linear is linear search in an array (not vectorized, I'm not sure how this can be done). binary is binary search in a sorted array.

I'm curious to see how the JIT map and a perfect hash function can perform for this special case and I might come back to edit this post if I find something that outperform those. For now I guess I will use fxhash, as proposed by scottmcm, which outperforms the other soltions.

1 Like

Can you share the benchmark code?

No problem, @Fredrik! It uses criterion so it's just cargo bench. Here's a pastbin link.

My results on x64 GNU/Linux are significantly different from yours. fxhash isn't that low, and is even higher than nohash. ahash doing far worse. JIT collections looking good. As I saw you're using a set rather than a map, I made a JIT set which generates fewer instructions than the JIT map.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.