Closed ogxd closed 9 months ago
Results for first try at an hybrid approach
This is very encouraging. This is all done without using generics, which ended up making the code too complex for no good reason IMHO.
Note that this all remains stable with the full 128 bit version, which is AWESOME.
There are a few remaing things to tackle:
Some bench results on my Ryzen 5 PC: | no avx2 | with avx2 | |
---|---|---|---|
main branch | |||
hybrid-2 branch |
In 4th picture we use both 128-bit SIMD for small inputs and 256-bit SIMD for larger inputs. It has the benefit of being stable with the 128-bit only version |
s128 s256 hybird and the other hash maybe can draw it in the same picture so it looks clearer
I can't because they're all generated from different compilation targets but I have used a max y of 130000 for all so scalewise it is comparable.
As you can see with the hybrid+stable approach there is a small loss in throughput starting with 32-bytes long inputs compared to the full AVX2 algorithm. Maybe a small compromise is acceptable if stability is guaranteed but still I'd like to continue fiddling with the implementation to see if a little more throughput can be squeezed out of it
Share an article for reference only
https://deepmind.google/discover/blog/alphadev-discovers-faster-sorting-algorithms/
We applied AlphaDev to one of the most commonly used algorithms for hashing in data structures to try and discover a faster algorithm. And when we applied it to the 9-16 bytes range of the hashing function, the algorithm that AlphaDev discovered was 30% faster.
This year, AlphaDev’s new hashing algorithm was released into the open-source Abseil library, available to millions of developers around the world, and we estimate that it’s now being used trillions of times a day.
Interesting article but I doubt AI (at least AI as we know it currently) would help making gxhash more performant
Here is what it looks like after a few more optimizations (still passing SMHasher)
gxhash-2 is the current version on main, gxhash-3 is what is proposed in this PR
Takeaways:
Are all these hashes stable ?
Yes all hashes generated in v3 will be the same, independently from actual intrinsics used.
I did one more batch of optimizations yesterday but I am reaching the limits (or at least my limit 😅).
I am going to proceed to a cleanup and review this as a whole
I did (again 😅) one more batch of optimizations
Merging this by the end of the week.
Currently, the rust standard library uses hashbrown, and hashbrown uses ahash. I think you can try submitting a pull request to hashbrown first and replace ahash with gxhash.
https://github.com/rust-lang/hashbrown
Since Rust 1.36, this is now the HashMap implementation for the Rust standard library. However you may still want to use this crate instead since it works in environments without std, such as embedded systems and kernels.
Uses AHash as the default hasher, which is much faster than SipHash. However, AHash does not provide the same level of HashDoS resistance as SipHash, so if that is important to you, you might want to consider using a different hasher.
Yes I know I've already done that, and it was earlier today to be precise ;)
This has led to this first issue https://github.com/ogxd/gxhash/issues/40
Context
Currently, gxhash with a 128-bit state is much faster for small input sizes, while gxhash with a 256-bit state is faster for large input sizes. The idea is to study the possibilities of making an hybrid state version of gxhash, leveraring the advantages of 128-bit state with the advantages of the 256-bit state processing, for maximum throughput for all input sizes.
See the break-even point:
Challenges
There are two ways to achieve this:
Some challenges are:
Todo