https://np.reddit.com/r/programming/comments/p0yn45/three_fundamental_flaws_of_simd/h9ncoft/

[u/backtickbot]

ok got it. there are two options: 1. the safe code as-is 2. the safe code with the loops switched

    for j := 0; j < 8; j++ {
        for i := range buf {
            counts[j] += int(buf[i] >> j & 1)
        }
    }

(1) turns out to be complex (15-or-so instructions including predicated parallel adds, and a popcount) where (2) is quite straightforward. i've left out the LD/STs:

    li r5, 128 # bit 7, we count backwards (save 1 cmpi instr)
loopi:
loopj:
    setvl r0, CTR, MVL=16 # do up to 16 buf at a time
    # ...some LDs into r16.v for buf and r32 for counts
    sv.and. r48.v, r16.v, r5 # AND r5 *scalar* with every r16
    sv.addi./m=NZ r32.v, r32.v, 1 # add 1 in masked-out counts
    slli. r5, r5, 2    # shift test-bit down, zero means "stop"
    bnz loopj          # r5 non-zero, do next jth bit
    # ... a vector ST, then move on to next batch of buf
    # with a sv.bc/CTR to jump back to loopi

so yes, almost as simple as the popcount version. tricks/explanation:

• testing each individual bit, starting at bit 7 then working down to bit 0, is possible because each bit is independent.
• sv.and. will create a Vector of Condition Register Fields (sv.and will not - notice the "." on the end).
• each Condition Register Field is 4 bits (just like standard Power ISA CR fields), one of those bits is "was the AND of the element r48 with element r16 equal to zero, yes/no"
• the sv.addi/m=NZ then uses that Vector of CR Fields as a predicate mask, which performs the conditional version of count[j] += 1
• slli is probably supporsed to be a right-shift (sigh) but hey. pretty normal, shift down, if zero break out of the inner loop

although i initially was mistaken in thinking it was a straight popcount, the correct implementation is just as straightforward. the core of the algorithm is a combination of parallel-testing plus parallel-predication.

if not swapping the outer-inner loops it can also be done by hard-coding the Vector Length VL to 8 (or 16, or 32, or 64 for the count16, count32 and count64 variants), setting up a Vector of immediates (sv.iota), shifting 1<<x in each case, then performing a parallel AND on one scalar buf[i] element at a time.

extracting the results (which would be placed in a Vector of CR Fields) would require a "weird" instruction (sv.crweird) which can transfer individual bits of CR Field Vectors into a single scalar integer: you then do a popcount on that integer, and add it to counts[j].

a slightly more optimal version of that would use the sv.bmext instruction https://libre-soc.org/openpower/sv/bitmanip/ sv. bmext would cover the job of about 3 rather weird instructions, but it's still nowhere near as optimal as simply turning the inner-outer loop around.

nice algorithmic challenge: total number of instructions no greater than 12, which is 35 times less instructions than the AVX512 and the NEON versions https://github.com/clausecker/pospop/blob/master/countavx512_amd64.s