4 ms·

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 thr

by dzaima 2y ago

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.

fanf2 2y ago
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.
kolbe 2y ago
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.
- dzaima 2y ago
  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 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.
  - fanf2 2y ago
    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!
  - kolbe 2y ago
    > 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).

by dzaima 2y ago

fanf2 2y ago

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.

kolbe 2y ago

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.

dzaima 2y ago
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 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.
- fanf2 2y ago
  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!
- kolbe 2y ago
  > 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).