On Tue, 3 Nov 2026 06:30:31 GMT, Larry <[email protected]> wrote:
>> ### Description
>>
>> The AVX2 loop in generate_updateBytesAdler32() processed 16 bytes per
>> iteration using two vpshufb and four vpaddd instructions, and reduced the
>> accumulators with vpmulld followed by a vphaddd chain.
>>
>> VPHADDD is not a cheap single-µop operation: it decodes to three µops on
>> Intel P-cores — two in-lane shuffle µops plus one add — and those shuffle
>> µops contend for the shuffle pipes; the AVX forms are also microcoded on AMD
>> Zen and Intel E-cores
>> ([uops.info](https://uops.info/html-instr/VPHADDD_YMM_YMM_YMM.html)). In a
>> hot reduction loop this makes the vphaddd chain throughput-limited by the
>> shuffle pipes, hence relatively costly.
>>
>> This change rewrites the AVX2 loop as a dot product:
>> - vpsadbw computes the byte sum for a;
>> - vpmaddubsw/vpmaddwd compute the weighted byte sums for b, using two new
>> weight tables;
>> - the loop processes 64 bytes per iteration with two independent
>> accumulators to shorten the dependency chain;
>> - the AVX2 horizontal reduction uses 128-bit adds and shuffles instead of
>> the vphaddd chain;
>> - the 16/32-byte tails are handled with SIMD blocks.
>> - the reduction mod BASE (65521) uses the gcc magic multiply (q = (x *
>> 2147975281) >> 47) instead of two divl instructions.
>>
>> ### TEST
>>
>> - env: Intel Xeon 6980P (Granite Rapids), single socket, 128 cores / 256
>> threads (SMT2), 3 NUMA nodes, 755 GiB RAM, Ubuntu 22.04.4 LTS, glibc 2.35
>> - JMH: test/micro/org/openjdk/bench/java/util/TestAdler32.java;
>> - jvmArgs: "-Xms4g -Xmx4g -XX:UseAVX=2"
>> - results (ops/ms, mean):
>> | size | baseline | patched | delta |
>> | ---: | ---: | ---: | ---: |
>> | 1 | 104097.5 | 167073.8 | +60.5% |
>> | 2 | 101692.6 | 159382.4 | +56.7% |
>> | 4 | 94645.6 | 145376.2 | +53.6% |
>> | 8 | 84128.9 | 122917.0 | +46.1% |
>> | 15 | 69304.3 | 91653.2 | +32.2% |
>> | 16 | 66870.0 | 161618.9 | +141.7% |
>> | 24 | 56286.5 | 111292.6 | +97.7% |
>> | 31 | 50346.7 | 84490.9 | +67.8% |
>> | 32 | 56756.3 | 71429.1 | +25.9% |
>> | 64 | 52268 | 70605 | +35% |
>> | 256 | 30809 | 59958 | +95% |
>> | 1024 | 14318 | 33684 | +135% |
>> | 4096 | 4475 | 10687 | +139% |
>> | 8192 | 2268 | 5487 | +142% |
>> | 65536 | 291.3 | 564.9 | +94% |
>>
>> Sizes below 16 bytes use the scalar loop in both versions; the only relevant
>> difference is the final reduction modulo BASE, which baseline performs with
>> two divl instructions and the patched version with the magic multiply (q =
>> (x * 2147975281) >> 47). These rows therefore isolate the magic-mul...
>
> Larry has updated the pull request incrementally with one additional commit
> since the last revision:
>
> 8394260: Refine Adler32 AVX2 loop
>
> Reduce the AVX2 hot loop to one conditional backedge and remove the
> redundant yprev_a copy by accumulating ya before updating it.
>
> Factor the modulo BASE sequence into a helper and extend the Adler32 JMH
> parameters to cover the small sizes.
I wrote my own fuzzing test, independent from existing; everything passing
after days of running.
Also went into the asm for correctness. Everything looks correct. My biggest
complaint is variable names (and maybe a few more comments/pseudocode on the
actual algorithm..). It was mostly like this when you found it, but some
cleanup would be nice..
src/hotspot/cpu/x86/stubGenerator_x86_64_adler.cpp line 89:
> 87: const int BASE = 65521;
> 88: const int DIV_BASE_MAGIC_SHIFT = 47;
> 89: const juint DIV_BASE_MAGIC = 2147975281U; // gcc magic for unsigned
> divide by 65521
- uint32_t I think instead of juint
- its not "gcc magic".. `// ceil(2^47 / 65521) `
I got tripped up by this, it looks deceptively like barett reduction.. but
barett does floor() instead of ceil().. and barett usually leaves result off by
a prime or three; your reduction is 'final' within the given inputs.
Not sure if you considered it, but this prime is a pseudo-mersenne prime so
reduction could had been `low + 15*high`.. but you are left again with not
quite complete reduction (off by one prime).. two operations, probably just
fine for the intermediate reductions. meh, this algorithm isn't 'reduction
bound', so don't feel you have to spend time on mersenne reduction.
src/hotspot/cpu/x86/stubGenerator_x86_64_adler.cpp line 95:
> 93: auto reduce_mod_base = [&](const Register reg) {
> 94: __ movl(rax, reg);
> 95: __ imulq(rax, rcx);
`// rcx = DIV_BASE_MAGIC`
src/hotspot/cpu/x86/stubGenerator_x86_64_adler.cpp line 114:
> 112: const XMMRegister ya = xmm0;
> 113: const XMMRegister yb = xmm1;
> 114: const XMMRegister yb_0 = xmm2;
This is a bit nitpicky, but variable names really threw me for a loop. "Is `_0`
from a summation operation?", "Is x, y prefix for column vs row operations?".
There are overlaps/overloads in registers that are not 'trivial' to see that
they are just fine..
To convince myself, I rearranged some lines, ydot2v, ydot2v_0 -> ydot2v0,
ydot2v1, yb_0 -> yb1
Much of this was like it before you, but some cleanup is deserved I think
const XMMRegister ya = xmm0;
const XMMRegister yb0 = xmm1;
const XMMRegister yb1 = xmm2;
const XMMRegister ysum_a = xmm4;
const XMMRegister yzero = xmm5;
const XMMRegister yones = xmm6;
const XMMRegister ydot2v0 = xmm11; // weights 64..33
const XMMRegister ydot2v1 = xmm12; // weights 32..1
const XMMRegister ydata0 = xmm13;
const XMMRegister ydata1 = xmm14;
const XMMRegister ytmp0 = xmm7;
const XMMRegister ytmp1 = xmm15;
// GPR save area
const XMMRegister xtmp3 = xmm8;
const XMMRegister xtmp4 = xmm9;
const XMMRegister xtmp5 = xmm10;
// 128-bit views of registers
const XMMRegister xa = ya;
const XMMRegister xb = yb0;
// AVX512 only
const XMMRegister xsa = xmm3; // vphaddd needs xmm0-15
const XMMRegister ysa = xmm16;
const XMMRegister xtmp0 = xmm17;
const XMMRegister xtmp1 = xmm18;
const XMMRegister xtmp2 = xmm19;
src/hotspot/cpu/x86/stubGenerator_x86_64_adler.cpp line 241:
> 239: __ vphaddd(xa, xa, xa, Assembler::AVX_128bit);
> 240: __ vphaddd(xb, xb, xb, Assembler::AVX_128bit);
> 241: __ vphaddd(xsa, xsa, xsa, Assembler::AVX_128bit);
Did you try your optimization idea on these as well, on the 512 path? I guess
there is enough independent work here..
src/hotspot/cpu/x86/stubGenerator_x86_64_adler.cpp line 300:
> 298: __ subl(s, 64);
> 299:
> 300: __ vpsadbw(ytmp0, ydata0, yzero, Assembler::AVX_256bit);
This could use a comment... feel free to adapt from mine (I annotate when get
stuck/confused)
// ysum_a += ya // "clever": accumulate the accumulator gives rest of yb
scale
// ya += sum bytes into quadwords across ydata0 and ydata1
// ydata(01) = multiply and sum bytes into words (ydata(01) * [64..1])
// yb(01) += sum words into doublewords across ydata(01)
-------------
PR Review: https://git.openjdk.org/jdk/pull/33338#pullrequestreview-5756146905
PR Review Comment: https://git.openjdk.org/jdk/pull/33338#discussion_r4458343461
PR Review Comment: https://git.openjdk.org/jdk/pull/33338#discussion_r4458582819
PR Review Comment: https://git.openjdk.org/jdk/pull/33338#discussion_r4459610378
PR Review Comment: https://git.openjdk.org/jdk/pull/33338#discussion_r4459715897
PR Review Comment: https://git.openjdk.org/jdk/pull/33338#discussion_r4459769712
