Xxhash: custom secrets of XXH3 blocks loop unrolling
In discussion of #347, we found that the runtime size of custom secret seems to be the main issue of benchmark results of _withSecret() variants, which blocks the internal loop unrolling. Now there are 2 known workarounds:
switch table
Use switch table to convert some known length as compile time constants. This works for multiple targets including scalar, sse2, avx2 and avx512, but may bloat the executable size.
XXH_NO_INLINE XXH64_hash_t
XXH3_hashLong_64b_withSecret(const xxh_u8* XXH_RESTRICT input, size_t len,
const xxh_u8* XXH_RESTRICT secret, size_t secretSize)
{
switch (secretSize) {
case XXH3_SECRET_SIZE_MIN + 0 * 8: return XXH3_hashLong_64b_internal(input, len, secret, XXH3_SECRET_SIZE_MIN + 0 * 8);
case XXH3_SECRET_SIZE_MIN + 1 * 8: return XXH3_hashLong_64b_internal(input, len, secret, XXH3_SECRET_SIZE_MIN + 1 * 8);
case XXH3_SECRET_SIZE_MIN + 2 * 8: return XXH3_hashLong_64b_internal(input, len, secret, XXH3_SECRET_SIZE_MIN + 2 * 8);
case XXH3_SECRET_SIZE_MIN + 3 * 8: return XXH3_hashLong_64b_internal(input, len, secret, XXH3_SECRET_SIZE_MIN + 3 * 8);
case XXH3_SECRET_SIZE_MIN + 4 * 8: return XXH3_hashLong_64b_internal(input, len, secret, XXH3_SECRET_SIZE_MIN + 4 * 8);
case XXH3_SECRET_SIZE_MIN + 5 * 8: return XXH3_hashLong_64b_internal(input, len, secret, XXH3_SECRET_SIZE_MIN + 5 * 8);
case XXH3_SECRET_SIZE_MIN + 6 * 8: return XXH3_hashLong_64b_internal(input, len, secret, XXH3_SECRET_SIZE_MIN + 6 * 8);
case XXH3_SECRET_SIZE_MIN + 7 * 8: return XXH3_hashLong_64b_internal(input, len, secret, XXH3_SECRET_SIZE_MIN + 7 * 8);
......
}
return XXH3_hashLong_64b_internal(input, len, secret, secretSize);
}
manually unrolling
WIP, Need benchmark test. @easyaspi314 I think this issue is generic, and we should test on all optimized targets, not only avx512. The previous switch-table way does improve much for sse2 and avx2. The same thing should happen for this method. I will try it on x86 arch CPUs, but I have no NEON and VSX CPUs.
#if XXH_VECTOR == XXH_AVX512 && !XXH_REROLL
if (XXH_likely(nbStripes % 4 == 0)) {
for (n = 0; n < nbStripes; n+=4 ) {
const xxh_u8* const in = input + n*STRIPE_LEN;
if (accWidth == XXH3_acc_64bits) XXH_PREFETCH(in + XXH_PREFETCH_DIST_AVX512_64);
else XXH_PREFETCH(in + XXH_PREFETCH_DIST_AVX512_128);
XXH3_accumulate_512(acc,
in,
secret + n*XXH_SECRET_CONSUME_RATE,
accWidth);
XXH3_accumulate_512(acc,
in + 1 * STRIPE_LEN,
secret + (n+1)*XXH_SECRET_CONSUME_RATE,
accWidth);
XXH3_accumulate_512(acc,
in + 2 * STRIPE_LEN,
secret + (n+2)*XXH_SECRET_CONSUME_RATE,
accWidth);
XXH3_accumulate_512(acc,
in + 3 * STRIPE_LEN,
secret + (n+3)*XXH_SECRET_CONSUME_RATE,
accWidth);
}
} else
#endif
for (n = 0; n < nbStripes; n++) {
...
gzm55
All 12 comments
I will try it on x86 arch CPUs, but I have no NEON and VSX CPUs
Well there is very likely a NEON CPU in your pocket. I do all of my NEON testing on my phone. :).
And at least for aarch64 clang, this code strikes gold:
/* TODO: improve */
#ifdef __ARM_ARCH
# define XXH_PREFETCH_DIST 128 /* ARM prefers short prefetches */
#else
# define XXH_PREFETCH_DIST 384
#endif
...
#if !XXH_REROLL
# ifndef XXH3_UNROLL_COUNT
# define XXH3_UNROLL_COUNT 4
# endif
/* Attempt to unroll on iterations that are an even multiple. */
if (XXH_likely(nbStripes % XXH3_UNROLL_COUNT == 0)) {
for (n = 0; n < nbStripes; n += XXH3_UNROLL_COUNT) {
size_t m;
/* Don't prefetch too often */
XXH_PREFETCH(input + n * STRIPE_LEN + XXH_PREFETCH_DIST);
/* Don't physically unroll, just hint to the compiler */
for (m = 0; m < XXH3_UNROLL_COUNT; m++) {
const xxh_u8* const in = input + (n+m)*STRIPE_LEN;
XXH3_accumulate_512(acc,
in,
secret + (n+m)*XXH_SECRET_CONSUME_RATE,
accWidth);
}
}
}
else
#endif /* !XXH_REROLL */
{
for (n = 0; n < nbStripes; n++) {
...
}
}
Before:
./xxhsum 0.7.4 (64-bit aarch64 + NEON little endian), Clang 9.0.1 , by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 28194 it/s ( 2753.3 MB/s)
XXH32 unaligned : 102400 -> 23001 it/s ( 2246.2 MB/s)
XXH64 : 102400 -> 31655 it/s ( 3091.3 MB/s)
XXH64 unaligned : 102400 -> 31639 it/s ( 3089.7 MB/s)
XXH3_64b : 102400 -> 61794 it/s ( 6034.5 MB/s)
XXH3_64b unaligned : 102400 -> 57326 it/s ( 5598.2 MB/s)
XXH3_64b w/seed : 102400 -> 61718 it/s ( 6027.2 MB/s)
XXH3_64b w/seed unaligned : 102400 -> 57693 it/s ( 5634.1 MB/s)
XXH3_64b w/secret : 102400 -> 58522 it/s ( 5715.0 MB/s)
XXH3_64b w/secret unaligned : 102400 -> 54122 it/s ( 5285.4 MB/s)
XXH128 : 102400 -> 50873 it/s ( 4968.1 MB/s)
XXH128 unaligned : 102400 -> 50591 it/s ( 4940.6 MB/s)
XXH128 w/seed : 102400 -> 52321 it/s ( 5109.4 MB/s)
XXH128 w/seed unaligned : 102400 -> 49946 it/s ( 4877.5 MB/s)
XXH128 w/secret : 102400 -> 49623 it/s ( 4846.0 MB/s)
XXH128 w/secret unaligned : 102400 -> 46839 it/s ( 4574.1 MB/s)
After:
./xxhsum 0.7.4 (64-bit aarch64 + NEON little endian), Clang 9.0.1 , by Yann Collet
Sample of 100 KB...
XXH32 : 102400 -> 27992 it/s ( 2733.6 MB/s)
XXH32 unaligned : 102400 -> 23043 it/s ( 2250.3 MB/s)
XXH64 : 102400 -> 31633 it/s ( 3089.1 MB/s)
XXH64 unaligned : 102400 -> 31492 it/s ( 3075.4 MB/s)
XXH3_64b : 102400 -> 65217 it/s ( 6368.9 MB/s)
XXH3_64b unaligned : 102400 -> 61028 it/s ( 5959.8 MB/s)
XXH3_64b w/seed : 102400 -> 66373 it/s ( 6481.8 MB/s)
XXH3_64b w/seed unaligned : 102400 -> 60987 it/s ( 5955.8 MB/s)
XXH3_64b w/secret : 102400 -> 58118 it/s ( 5675.6 MB/s)
XXH3_64b w/secret unaligned : 102400 -> 53760 it/s ( 5250.0 MB/s)
XXH128 : 102400 -> 59891 it/s ( 5848.7 MB/s)
XXH128 unaligned : 102400 -> 55346 it/s ( 5404.9 MB/s)
XXH128 w/seed : 102400 -> 60097 it/s ( 5868.8 MB/s)
XXH128 w/seed unaligned : 102400 -> 54854 it/s ( 5356.9 MB/s)
XXH128 w/secret : 102400 -> 48962 it/s ( 4781.5 MB/s)
XXH128 w/secret unaligned : 102400 -> 46313 it/s ( 4522.7 MB/s)
This code might be a keeper of it also improved x86/plays well with GCC/MSVC. The only place where this is slower is XXH128 w/secret, and only negligibly.
easyaspi314
on 7 Apr 2020
And at least for aarch64 clang, this code strikes gold:
how about this template:
#define XXH3_UNROLL_COUNT 4
for (n = 0; n < nbStripes & (~(XXH3_UNROLL_COUNT - 1)); n += XXH3_UNROLL_COUNT) {
...
}
if (XXH_unlikely(n < nbStripes)) {
for (; n < nbStripes; n++) {
...
}
}
This is still able to be config by XXH_REROLL macro, but according to previous results, we should always close XXH_REROLL.
gzm55
on 7 Apr 2020
/* Don't prefetch too often */ XXH_PREFETCH(input + n * STRIPE_LEN + XXH_PREFETCH_DIST);
Each prefetch will only load one cache line, i.e. on most machines load one STRIPE_LEN bytes. Why is prefetching every 4 STRIPE_LEN bytes better?
gzm55
on 7 Apr 2020
I asked in a previous thread, but I don't think I've seen an answer :
Is this investigation targeting XXH_INLINE_ALL ? or non-inlined xxhash ? both ?
Cyan4973
on 7 Apr 2020
Btw, I can't test AVX512 directly, but I can benchmark AVX2.
In my tests, the _withSecret() variant is ~10% slower than "default" secret, which is measurable and within original expectation, but nowhere near as dramatic as suggested for the AVX512 variant, where a ~50% difference is reported (see this table).
Cyan4973
on 7 Apr 2020
I asked in a previous thread, but I don't think I've seen an answer :
Is this investigation targeting
XXH_INLINE_ALL? or non-inlined xxhash ? both ?
My benchmark results are compiled as default xxhsum.c, which is only define XXH_STATIC_LINKING_ONLY, so only non-inlined xxhash are benmarked.
gzm55
on 8 Apr 2020
OK, in which case, it makes sense that the _withSecret() variant doesn't know at compile time the length of the secret, hence cannot know at compile time the nb of rounds, which can explain the conservative code generation.
Manual unrolling may likely save the day.
Cyan4973
on 8 Apr 2020
XXH_INLINE_ALL gives the same results, it cannot hint the compiler to unroll the loop~
gzm55
on 8 Apr 2020
but nowhere near as dramatic as suggested for the
AVX512variant, where a ~50% difference is reported
In the original version, with the default secret (or compile time secret size), the whole 16 stripes of one block are all unrolled since avx512 has 32 registers.
Meanwhile, the runtime secret will not unroll at all. This is the internal loop with runtime secret size:
for (n = 0; n < nb_blocks; n++) {
40ad6a: 4d 39 ca cmp %r9,%r10
40ad6d: 0f 87 09 01 00 00 ja 40ae7c <XXH3_hashLong_64b_withSecret+0x13c>
40ad73: 48 85 f6 test %rsi,%rsi
40ad76: 0f 84 a5 00 00 00 je 40ae21 <XXH3_hashLong_64b_withSecret+0xe1>
40ad7c: 45 31 db xor %r11d,%r11d
40ad7f: 62 f2 fd 48 59 0d d7 vpbroadcastq 0x41d7(%rip),%zmm1 # 40ef60 <kSecret+0x160>
40ad86: 41 00 00
40ad89: 49 89 fe mov %rdi,%r14
40ad8c: 0f 1f 40 00 nopl 0x0(%rax)
40ad90: 4c 89 f3 mov %r14,%rbx
40ad93: 31 d2 xor %edx,%edx
40ad95: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
40ad9c: 00 00 00
40ad9f: 90 nop
40ada0: 0f 18 8b 40 01 00 00 prefetcht0 0x140(%rbx)
__m512i const data_vec = _mm512_loadu_si512 (input);
40ada7: 62 f1 fe 48 6f 13 vmovdqu64 (%rbx),%zmm2
__m512i const data_key = _mm512_xor_si512 (data_vec, key_vec);
40adad: 62 d1 ed 48 ef 1c d0 vpxorq (%r8,%rdx,8),%zmm2,%zmm3
__m512i const data_key_lo = _mm512_shuffle_epi32 (data_key, _MM_SHUFFLE(0, 3, 0, 1));
40adb4: 62 f1 7d 48 70 e3 f5 vpshufd $0xf5,%zmm3,%zmm4
__m512i const product = _mm512_mul_epu32 (data_key, data_key_lo);
40adbb: 62 f1 dd 48 f4 db vpmuludq %zmm3,%zmm4,%zmm3
__m512i const sum = _mm512_add_epi64(*xacc, data_vec);
40adc1: 62 f1 ed 48 d4 c0 vpaddq %zmm0,%zmm2,%zmm0
40adc7: 62 f1 fd 48 d4 c3 vpaddq %zmm3,%zmm0,%zmm0
for (n = 0; n < nbStripes; n++ ) {
40adcd: 48 83 c2 01 add $0x1,%rdx
40add1: 48 83 c3 40 add $0x40,%rbx
40add5: 48 39 d6 cmp %rdx,%rsi
40add8: 75 c6 jne 40ada0 <XXH3_hashLong_64b_withSecret+0x60>
__m512i const shifted = _mm512_srli_epi64 (acc_vec, 47);
Coming back to this issue, see if there's something that needs to and can be fixed before the release.
My understanding of this issue is that the _withSecret() variant is slower, because the compiler cannot guess how many rounds will be needed before a scramble.
That being said, as also mentioned previously, I'm not shocked by the speed difference in my tests.
Here are some results for SSE2 :
5#XXH3_64b : 102400 -> 236838 it/s (23128.7 MB/s)
9#XXH3_64b w/secret : 102400 -> 224560 it/s (21929.7 MB/s)
11#XXH128 : 102400 -> 205959 it/s (20113.2 MB/s)
15#XXH128 w/secret : 102400 -> 205928 it/s (20110.1 MB/s)
and then for AVX2 :
5#XXH3_64b : 102400 -> 313003 it/s (30566.7 MB/s)
9#XXH3_64b w/secret : 102400 -> 300500 it/s (29345.7 MB/s)
11#XXH128 : 102400 -> 268991 it/s (26268.6 MB/s)
15#XXH128 w/secret : 102400 -> 268972 it/s (26266.8 MB/s)
and then same thing with the auto-dispatcher (effectively dispatching towards AVX2) :
5#XXH3_64b : 102400 -> 338038 it/s (33011.5 MB/s)
9#XXH3_64b w/secret : 102400 -> 298914 it/s (29190.8 MB/s)
11#XXH128 : 102400 -> 269140 it/s (26283.2 MB/s)
15#XXH128 w/secret : 102400 -> 260954 it/s (25483.7 MB/s)
The difference may seem a bit more sensible, but the actually surprising part is the improved speed of XXH3_64bits() when using the DISPATCH=1 mode compared to direct -mavx2 compilation, which doesn't really make sense, until one considers the random impact of instruction alignment in the equation.
Anyway, even here, there is no big impact.
So, do I have to understand that the issue is present solely on AVX512 ?
In which case, I should try to get access to an avx512 laptop for testing.
Cyan4973
on 16 Jun 2020
In which case, I should try to get access to an
avx512laptop for testing.
If no avx512 laptop at hand, it could be still convenient to apply a cloud based hourly billing avx512 node for testing.
In the previous discussion, this could be a common issue for all arch, but the impact varies very much. If avx512 and other arch have different branches of looping, is it too complex?
It is ideal to find a common unrolling pattern in XXH3_accumulate for better performance. For the nb_rounds of XXH3_accumulate, we can distinguish three use case: a) full block with default secret, b) full block with custom secret, c) runtime dynamic rounds. If hinting by a new enum switch parameter, XXH3_accumulate can select better loop pattern for each case.
a) full block with default secret, one for- loop with compile time conditions, compilers will do it best.
b) full block with custom secret, we can first use a compile time for- loop with to deal with XXH3_SECRET_SIZE_MIN length secret, then fall through to case c).
c) runtime dynamic rounds, use XXH3_UNROLL_COUNT to do a partial manually loop unrolling.
gzm55
on 16 Jun 2020
I actually have an avx512 IceLake laptop around, which makes it possible to measure something.
Here are some results, using -mavx512f :
xxhsum.exe 0.7.4 by Yann Collet, compiled as 64-bit x86_64 + AVX512 little endian with GCC 10.1.0
Sample of 100 KB...
5#XXH3_64b : 102400 -> 376471 it/s (36764.7 MB/s)
7#XXH3_64b w/seed : 102400 -> 461522 it/s (45070.5 MB/s)
9#XXH3_64b w/secret : 102400 -> 315840 it/s (30843.8 MB/s)
11#XXH128 : 102400 -> 378861 it/s (36998.1 MB/s)
13#XXH128 w/seed : 102400 -> 356625 it/s (34826.7 MB/s)
15#XXH128 w/secret : 102400 -> 378412 it/s (36954.3 MB/s)
There is a drop of performance for the secret 64-bit variant, _but_...
It's nowhere near as bad as the performance drop when comparing the default variant with the secret one, with default losing badly (36 GB/s < 45 GB/s) vs seed.
And once again, it doesn't make sense for the seed variant to win this competition. I suspect the issue is related to random instruction alignment.
To complete the picture, look how results are so different with the 128-bit variant :
default and secret variants have virtually identical speed,
while seed is now losing compared to default, reversing the trend witnessed in the 64-bit variant.
What I mean is that, while there _might_ be a negative impact associated to the secret variant, it's nowhere near as bad as the impact of random instruction alignment.
Consequently, we should rather concentrate on this problem first.
Only after impact of instruction alignment cease to be "random" does it make sense to move to less impactful stuff such as unrolling the secret variant.
Completing the picture, here is a benchmark of the DISPATCH=1 variant, which effectively selects avx512 on this laptop :
xxhsum.exe 0.7.4 by Yann Collet, compiled as 64-bit x86_64 autoVec little endian with GCC 10.1.0
Sample of 100 KB...
5#XXH3_64b : 102400 -> 469008 it/s (45801.5 MB/s)
7#XXH3_64b w/seed : 102400 -> 429815 it/s (41974.1 MB/s)
9#XXH3_64b w/secret : 102400 -> 291818 it/s (28497.9 MB/s)
11#XXH128 : 102400 -> 350369 it/s (34215.7 MB/s)
13#XXH128 w/seed : 102400 -> 344618 it/s (33654.1 MB/s)
15#XXH128 w/secret : 102400 -> 309190 it/s (30194.3 MB/s)
In this setup, secret variants loses more comprehensively, but as stated before, it would be better if such a performance difference was consistent and not just randomly impacted by some incontrolable instruction alignment effect. Look also how XXH3_64bits get much faster in the dispatch variant, leading now compared to the seed variant, but also leading compared to direct avx512 compilation, which should not make sense. It mostly proves how fragile is benchmark comparison currently.
_note_ : the impact of instruction alignment seems way more pronounced for avx512 than for narrower vector instruction sets.
Cyan4973
on 16 Jun 2020
Related issues
WayneD
路
7Comments
make-github-pseudonymous-again
路
3Comments
easyaspi314
路
6Comments
xinglin
路
6Comments
gitmko0
路
7Comments
Most helpful comment
Well there is very likely a NEON CPU in your pocket. I do all of my NEON testing on my phone. :).
And at least for aarch64 clang, this code strikes gold:
Before:
After:
This code might be a keeper of it also improved x86/plays well with GCC/MSVC. The only place where this is slower is XXH128 w/secret, and only negligibly.