[lld] xxHash performance - XXH_X64 vs XXH3_X64

[PiotrZSL]

Currently for hashing (symbol names, ...) in lld we use llvm::xxHash64 that utilize https://github.com/Cyan4973/xxHash implementation.
In 2020 Yann Collet released stable version of XXH3 algorithm, and in 2021 it included additional performance optimizations.

This algorithm is described as:
XXH3 (since v0.8.0): generates 64 or 128-bit hashes, using vectorized arithmetic.

When linking debug version on clang binary on single thread we get:

 Time (mean ± σ):      7.715 s ±  0.143 s    [User: 5.685 s, System: 1.782 s]
 Range (min … max):    7.532 s …  8.375 s    50 runs

And xxHash64 according to perf takes around ~6.81%

When using XXH3_64 we get:

 Time (mean ± σ):      7.429 s ±  0.157 s    [User: 5.384 s, System: 1.810 s]
 Range (min … max):    7.256 s …  8.247 s    50 runs

and hash function according to perf takes ~1.32%.

This mean that there is +- cheap way to gain 4-5%.
Maybe it's time to switch ?

[MaskRay]

llvm/ mainly uses xxhash64 for StringMap.cpp. ld.lld uses xxhash64 for SHF_MERGE duplicate elimination (primarily for SHF_MERGE|STRINGS), --icf=, and --build-id=fast (uncommon).
SHF_MERGE|SHF_STRINGS duplicate elimination time is mostly spent on .debug_str and .rodata.str1.1 sections, but I think the time portion is very small.

We can hack llvm::xxhash64 to use an alternative hash implementation (if we do change, we need to fix 14 lld/test/ELF string merge tests).
I have tried https://github.com/Cyan4973/xxHash #define XXH_INLINE_ALL and with or without #define XXH_VECTOR XXH_SCALAR.
My results are the following on a Linux x86-64 machine, linking a debug build of clang 16, 234MiB .debug_str).

% hyperfine --warmup 2 --min-runs 25 "numactl -C 20-27 /t/lld"{0,1}" -flavor gnu @response.txt --threads=8"
Benchmark 1: numactl -C 20-27 /t/lld0 -flavor gnu @response.txt --threads=8
  Time (mean ± σ):      3.099 s ±  0.027 s    [User: 7.018 s, System: 3.056 s]
  Range (min … max):    3.059 s …  3.177 s    25 runs

Benchmark 2: numactl -C 20-27 /t/lld1 -flavor gnu @response.txt --threads=8
  Time (mean ± σ):      3.080 s ±  0.029 s    [User: 6.804 s, System: 3.047 s]
  Range (min … max):    3.045 s …  3.169 s    25 runs

Summary
  'numactl -C 20-27 /t/lld1 -flavor gnu @response.txt --threads=8' ran
    1.01 ± 0.01 times faster than 'numactl -C 20-27 /t/lld0 -flavor gnu @response.txt --threads=8'

In lld0, llvm::xxHash64 takes 3.51% of total time while in lld1, llvm::xxHash3 takes 1.28% of total time.
So there is some improvement on the hash performance.

(Technically SIMD doesn't really help as most strings are short. The reference implementation has lots of dirty optimizations I am not sure apply to modern compilers.)

I have compared XXH3_64bits with XXH64 and the former is slightly faster, albeit by a very small margin.

If we do find xxh3 beneficial, we may consider a clean implementation like
https://github.com/easyaspi314/xxhash-clean/blob/master/xxh3-64b-ref.c

Using this implementation, XXH3_64bits takes 1.74% of total time, slower than the reference implementation.

[MaskRay]

• https://reviews.llvm.org/D154812 ([Support] Add llvm::xxh3_64bits)
• https://reviews.llvm.org/D154813 Use it in ld.lld SHF_MERGE|SHF_STRINGS duplicate elimination

I tuned the simplified version to be on par with the reference implementation (which contains lots of workarounds for old compilers). Hope that it can be useful :) Cyan4973/xxHash#808

[MaskRay]

I migrated a few other use cases to xxh3_64bits. Going forward, xxHash64 should be considered deprecated and not used for new use cases.

Related, I also changed StringMap (StringSet) to use xxh3 (https://reviews.llvm.org/D155781). We had a similar hash change in Jan 2023 (https://reviews.llvm.org/D142862) and it would be nice if we had xxh3 at that time... The pain fixing ~20 places across llvm-project made me think we need some bot coverage for reversed iteration order: https://discourse.llvm.org/t/reverse-iteration-bots/72224