Hacker News Reader

Comment by kolbe | Hacker News Reader

Well, the conundrum sits with the fact that this is the disassembly of the main loop:

        vmovdqu64       zmm3, zmmword ptr [rdi + rcx]
        vmovdqu64       zmm4, zmmword ptr [rdi + rcx + 64]
        vmovdqu64       zmm5, zmmword ptr [rdi + rcx + 128]
        vmovdqu64       zmm6, zmmword ptr [rdi + rcx + 192]
        vpaddb  zmm7, zmm3, zmm0
        vpaddb  zmm8, zmm4, zmm0
        vpaddb  zmm9, zmm5, zmm0
        vpaddb  zmm10, zmm6, zmm0
        vpcmpltub       k1, zmm7, zmm1
        vpcmpltub       k2, zmm8, zmm1
        vpcmpltub       k3, zmm9, zmm1
        vpcmpltub       k4, zmm10, zmm1
        vpaddb  zmm3 {k1}, zmm3, zmm2
        vpaddb  zmm4 {k2}, zmm4, zmm2
        vpaddb  zmm5 {k3}, zmm5, zmm2
        vpaddb  zmm6 {k4}, zmm6, zmm2
        vmovdqu64       zmmword ptr [rdi + rcx], zmm3
        vmovdqu64       zmmword ptr [rdi + rcx + 64], zmm4
        vmovdqu64       zmmword ptr [rdi + rcx + 128], zmm5
        vmovdqu64       zmmword ptr [rdi + rcx + 192], zmm6

...which is, upon first glance, is similar to yet better than the intrinsics version you wrote. Additionally it has cleaner tail handling.

View on HN

The tail handling is the main point of the post. The tolower1 line on the chart is very spiky because the autovectorizer doesn’t use masked loads and stores for tails, and instead does something slower that tanks performance. The tolower64 line is smoother and rises faster because masked loads and stores make it easier to handle strings shorter than the vector size.

There is something to be said for using masking load/stores instead of downgrading the SIMD register types. But to my eye, something is clearly wrong with your code in such a way that the "naive" autovectorized version should be blowing yours out of the water at 256B. Your code leaves a sparse instruction pipeline, and thus needs to run through the loop 4 times for every one of the autovectorized version. So, something is wrong here, as far as I know. I was just trying to make sure you'd covered the basics, like ensuring you were targeting the right architecture with your build and whatnot.

This is yours. Basically the same instructions, but taking up way more space:

        vmovdqu64       zmm3, zmmword ptr [rsi]
        vpaddb  zmm4, zmm3, zmm0
        vpcmpltub       k1, zmm4, zmm1
        vpaddb  zmm3 {k1}, zmm3, zmm2
        vmovdqu64       zmmword ptr [rdi], zmm3

Unrolling on AVX-512, especially on Zen 4 with its double-pumped almost-everything, isn't particularly significant; the 512-bit store alone has a reciprocal throughput of 2 cycles/zmm, which gives a pretty comfortable best possible target of 2 cycles/iteration. With Zen 4 being 6-wide out of the op cache, that's fine for up to 12 instructions in the loop (and with separate ports for scalar & SIMD, the per-iteration scalar op overhead is irrelevant).

Interestingly enough, clang 16 doesn't unroll the intrinsics version, but trunk does, which'd make the entire point moot.

The benchmark in question, as per the article, tests over 1MB in blocks, so it'll be at L2 or L3 speeds anyway.

Clang downgrades to ymm, which'll handle a 32-byte tail, but after that it does a plain scalar loop, up to a massive 31 iterations. Whereas masking appears to be approximately free on Zen 4, so I'd be surprised if the scalar tail would be better at even, like, 4 bytes (perhaps there could be some minor throughput gained by splitting up into optional unmasked ymm and then a masked ymm, but even that's probably questionable just from the extra logic/decode overhead).

Also worth considering that in real-world usage the masking version could be significantly better just from being branchless for up to 64-byte inputs.

Yeah the spikes in the “tolower1” line illustrate the 32 byte tail pretty nicely.

I should maybe draw a version of the chart covering just small strings, but it’s an SVG so you can zoom right in. The “tolower1” line shows relatively poor performance compared to “tolower64”, tho it is hard to see for strings less than 8 bytes.

L2 speeds are ~180GB/s on Zen 4. That's also a part of my confusion. This should be line speed.

I do not have the same experience as you with unrolling AVX512 loops on Zen 4. I recall even with double pumping, you can do 2.5 per cycle. As you noted with the stores, it takes two cycles, so you can put 4 into a 3.25 cycle pipeline, instead of 8 cycles. With 5 dependent ops covering 4.5 cycles, this should be a significant win.

I'm not defending the 31 length loop to clean up the mod32 leftover section. That is bad. But it doesn't answer why 256B is 4x slower than line speed and not significantly faster than the unrolled intrinsic version.

In my experience, I never used the masked load store because some platforms did an actual read over the masked-away parts, and could segfault. I recall hearing from a reliable source that Zen 4 doesn't do that, but didn't see official documentation for it. Clang may actually be avoiding the masked cleanup for that reason.

To top it off, I also always found it faster to just stagger the index back instead of a masked load/store whenever it's longer than 64 on calculations like this. That is, if it's size=80, do 0-63, and then 15-79 (which is an optimization Clang doesn't do either for some reason).

Finally, what really really confuses me is that whenever I write a benchmark like this:

         for(size_t i = 0; i < sizeof(src); i++) {
                 src[i] = (uint8_t)(i & 63) + 32;
         }

-O3 will do something absurd like just return the answer, since the inputs are constexpr. I can understand why the intrinsic version might confuse the compiler, but the clearly written one should totally have broken the benchmark and overwritten it with a constexpr answer.

Also of concern is that the input, and thus the loads & stores here, are intentionally bumped to cycle through all possible alignments, thus ending up unaligned most of the time, in which case it should be 3 cycles per store (I think?).

I don't understand your point about pipelining - OoO should mean that, as long as there's enough decode bandwidth and per-iteration scalar overhead doesn't overwhelm scalar execution resources, all SIMD ops can run at full force up to the most contended resource (store here), no?

That said, yeah, ~44GB/s is actually still pretty slow here, even for L3.

Masked load/store faulting was problematic on AVX2 (in addition to being pretty slow on AMD (which actually continues into Zen 4, despite it having fast AVX-512 versions)); AVX-512's should always be fine, and compilers already output them: https://godbolt.org/z/98sY57TE1

Intrinsics shouldn't "confuse" clang - clang lowers them, where possible, to the same LLVM instructions that the autovectorizer would generate. Both clang and gcc can even convert an intrinsics-based memcpy/memset impl to a libc call (as annoying may that be)!

If you want a compiler to not optimize out computation, you can add something like `__asm__ volatile(""::"r"(src):"memory");` after the loop to make it operate as if the contents of src were modified/read.

Clang rewrites my tolower64() into something rather more clever, and it adds a 2x unrolled version. (gcc keeps the object code much closer to what I wrote.) But from my point of view the important thing is that Clang retains the masked load and store for short string fragments. Its autovectorizer is not able to generate masked loads and stores.

I used Clang 11 for copybytes64() because it is unable to recognize the memcpy() idiom, whereas Clang 16 does turn it into memcpy() - which is slower!

> I don't understand your point about pipelining - OoO should mean that, as long as there's enough decode bandwidth and per-iteration scalar overhead doesn't overwhelm scalar execution resources, all SIMD ops can run at full force up to the most contended resource (store here), no?

You are reaching the limits of my understanding, but my level of knowledge is that store may have reciprocal throughput of 2, but it only occupies two ops (from double pumping a single one) over those two cycles, while the CPU pipeline can handle doing 10. For store in particular, nothing is dependent on it completing, so it can be "thrown into the wind" so to speak. But here's my approximation of the pipeline of a single thread, where dashes separate ops

LOADU.0 - LOADU.1 - _ - _ - _ - _ - ADD.0 - ADD.1 - _ - _ - CMP.0 - CMP.1 - _ - _ - _ - _ - ADD.0 - ADD.1 - _ - _ - STORE.0 - STORE.1 - [start again, because nothing is dependent on STORE completing]

So, that's 10 ops and 12 empty spots that can be filled by simultaneously doing 1.2 more loops simultaneously.

I do want to know why clang isn't using the masked load/store. If it's willing to do it on a dot-product, it should do it here as well. It makes me want to figure out what is blocking it (usually some guarantee that 99.9% of developers don't know they're making).

The store will still take up throughput even if nothing depends on it right now - there is limited hardware available for copying data from the register file to the cache, and its limit is two 32-byte stores per cycle, which you'll have to pay one way or another at some point.

With out-of-order execution, the layout of instructions in the source just doesn't matter at all - the CPU will hold multiple iterations of the loop in the reorder buffer, and assign execution units from multiple iterations.

e.g. see: https://uica.uops.info/?code=vmovdqu64%20zmm3%2C%20zmmword%2...

(click run, then Open Trace); That's Tiger Lake, not Zen 4, but still displays how instructions from multiple iterations execute in parallel. Zen 4's double-pumping doesn't change the big picture, only essentially meaning that each zmm instr is split into two ymm ones (they might not even need to be on the same port, i.e. double-pumping is really the wrong term, but whatever).

> The store will still take up throughput even if nothing depends on it right now - there is limited hardware available for copying data from the register file to the cache, and its limit is two 32-byte stores per cycle, which you'll have to pay one way or another at some point.

Sure. But that limit is one cycle--not two. This is getting pretty above my pay grade.

That tool is nifty, but I couldn't really figure out why it supports your assertion. I plugged in the two loop bodies and got these predicted throughput results:

Unrolled 4x: uiCA 6.00 llvm-mca 6.20

Regular: uiCA 2.00 llvm-mca 2.40

LLVM pretty strongly supports my experience that unrolling/reordering should be a substantial gain here, no? uiCA still has a meaningful gain as well.

Sorry, mixed things up - store has a limit of one 32-byte store per cycle (load is what has two 32-byte/cycle). Of additional note is Zen 4's tiny store queue of 64 32-byte entries, which could be at play (esp. with it pointing at L3; or it might not be important, I don't know how exactly it interacts with things).

The uiCA link was just to show how out-of-order execution works; the exact timings don't apply as they're for Tiger Lake, not Zen 4. My assertion being that your diagram of spaces between instructions is completely meaningless with OoO execution, as those empty spaces will be filled with instructions from another iteration of the loop or other surrounding code.

Clang is extremely unroll-happy in general; from its perspective, it's ~free to do, has basically zero downsides (other than code size, but noone's benchmarking that too much) and can indeed maybe sometimes improve things slightly.

Is there a limit to how much the OoO execution buffer can handle? I don't want to dig up the benchmarks again, but I remember for very long calculations (like computing a bunch of exp(x[i]), which boil down to about 40 AVX512 instructions), the unrolling+reordering was very effective.

Zen 4 has two 32-entry schedulers for SIMD, which I think is the relevant buffer here (many of my numbers in this thread, including these, are coming from https://chipsandcheese.com/2022/11/05/amds-zen-4-part-1-fron...), which would get mostly exhausted by one iteration of a 40-instruction loop. Whereas the 5-instruction body here should easily manage many iterations.

I think, at least. Now I'm at the limit of my knowledge, it took me a bit to figure out whether the reorder buffer or scheduler is the relevant thing here, and I'm still not too sure. Though, either way, 32 is the smallest number of all for Zen 4, and still fits 6 iterations of the 5-instruction loop and should happily reorder them. (and the per-iteration-overhead scalar code goes to separate schedulers)

On clang masked load/store tail - there are some flags to change its behavior, but seems like nothing does just a masked tail, and what does exist still has work to do, e.g. here's a magic incantation that I found looking through LLVM's source code to make it do a single body for the entire loop: https://godbolt.org/z/1Kb6qTx31. It's hilariously inefficient though, and likely meant for SVE which is intentionally designed for things like this.

The benchmark measures the time to copy about 1 MiByte, in chunks of various lengths from 1 byte to 1 kilobyte. I wanted to take into account differences in alignment in the source and destination strings, so there are a few bytes between each source and destination string, which are not counted as part of the megabyte.

On my Zen 4 CPU the L2 cache is 1 MiB per core, so because the working set is over 2 MB I think the relevant speed limit is the L3 cache.

To be sure I was measuring what I thought I was, I compiled each function separately to avoid interference from inlining, code motion, loop fusion, etc. Of course in real code it's more likely that you would want to encourage inlining, not prevent it!

Never heard about reading the masked area. Source?

AMD64 manual volume 4 (https://www.amd.com/content/dam/amd/en/documents/processor-t...):

> Exception and trap behavior for elements not selected for loading or storing from/to memory is implementation dependent. For instance, a given implementation may signal a data breakpoint or a page fault for doublewords that are zero-masked and not actually written.

I wonder if it ever happens IRL, as this would severely restrict the usefulness.

EDIT: does not seem to be applicable to AVX-512, only to AVX 1.

According to this PDF by intel, AVX-512 suppresses faults for masked access.

https://gcc.gnu.org/wiki/cauldron2014?action=AttachFile&do=g...

According to Intel document https://gcc.gnu.org/wiki/cauldron2014?action=AttachFile&do=g..., AVX-512 should suppress faults during masked access or otherwise it is not AVX-512.

The autovectorizer can, at times, when you check it produce reasonable simd code with a given compiler based on simple, clear C code. Is gcc as good in this case? Are previous versions of clang (that may be employed by users) going to work out as well. How do you check in your build that the compiler did the right thing? If you touch the C code in any way will it silently do something you don't want?

Autovectorization is great and improving.

Reply on news.ycombinator.com