search

Cyan4973 / xxHash

Extremely fast non-cryptographic hash algorithm
http://www.xxhash.com/
Other
9.2k stars 777 forks source link

Optimize xxh32 and xxh64 with ARM SVE instructions #737

Open hzhuang1 opened 2 years ago

hzhuang1 commented 2 years ago

With pull request #713 , XXH3 is optimized by ARM SVE instructions. Since data is divided in blocks in XXH3, and vector instructions could handle data in parallel.

For XXH32 & XXH64, data is fetched with stream. So a new method (multi-buffer) could be used to adopt vector instructions. The implementation is in https://github.com/hzhuang1/isa-l_crypto/tree/debug_xxh32. Multi-buffer also means multiple jobs. With multiple jobs running in parallel, vector instructions could be used to accelerate. Screenshot from 2022-09-07 14-22-59

The performance data fetched from two machines is above. One is SVE512 (fujitsu), and the other is SVE256 (AWS).

Cyan4973 commented 2 years ago

High level question : does the multi-buffer method generate the same final hash value as the regular one ?

hzhuang1 commented 2 years ago

High level question : does the multi-buffer method generate the same final hash value as the regular one ?

Only a part of code could be vectorized in multi-buffer, just like the block operation in XXH3. The left calculation is handled in each job. The final hash value must be same as the regular one.

Cyan4973 commented 2 years ago

The final hash value must be same as the regular one.

XXH3 was designed with parallel blocks in mind, so it works there, but XXH32 and XXH64 were not, so it's a bit less obvious to me that multi-buffer can generate the same final hash value as single stream.

Has it been already validated ? I assume xxhash_mb_rand_test.c's role is to do that, but I would welcome a confirmation.

A high level explanation would also be welcome, as currently the implementation is in assembly format, and the high-level logic is not self-obvious nor documented.

hzhuang1 commented 2 years ago

Has it been already validated ? I assume xxhash_mb_rand_test.c's role is to do that, but I would welcome a confirmation.

Yes, xxhash_mb_rand_test.c compare hash value with the result from regular xxhash.

A high level explanation would also be welcome, as currently the implementation is in assembly format, and the high-level logic is not self-obvious nor documented.

I'll try to add more explanation while I re-organize the patches.

Cyan4973 commented 1 year ago

This issue is primarily focused on a target implementation of XXH32 and XXH64 using SVE,

but a generic important claim made here is that it's possible to process large inputs with XXH32 and XXH64 by breaking them into multiple buffers, and processing them in parallel (employing multiple threads), and still generate the same result as if they were processed as a single stream.

If that's confirmed, this would be a fairly important property, that could be applied beyond SVE across multiple instruction sets. So a description of how to achieve this objective would be greatly appreciated.