3 ms·

Mask add looks neat! I wish there was a way to directly manipulate AVX512's mask registers in .NET intrinsics but for now we have to live with "recognized idiom

Mask add looks neat! I wish there was a way to directly manipulate AVX512's mask registers in .NET intrinsics but for now we have to live with "recognized idioms". For anyone interested, the author's core loop in ASM is as compiled by GCC .L3: vmovdqu8 zmm0, ZMMWORD PTR [rcx+rax] vmovdqa64 zmm1, zmm0 vpcmpb k1, zmm0, zmm4, 5 vpcmpb k0, zmm0, zmm3, 2 kandq k1, k1, k0 vpaddb zmm1{k1}, zmm0, zmm2 vmovdqu8 ZMMWORD PTR [rdi+rax], zmm1 add rax, 64 cmp rax, r8 jne .L3 uiCA (CQA/MAQAO) (https://uica.uops.info/ https://uica.uops.info/, make sure to pick CQA + Ice Lake) says it achieves nice 32B/cycle on Ice Lake. If you multiply by say 3 to match 3 GHz, this gives us almost 96 GiB/s assuming memory access is not a bottleneck (it always is in such algorithms). But this seems not as close to optimal utilization as it could be. Using Clang instead yields much better, nicely unrolled result with better instruction selection. .LBB0_9: vmovdqu64 zmm3, zmmword ptr [rsi] vmovdqu64 zmm5, zmmword ptr [rsi + 64] vmovdqu64 zmm6, zmmword ptr [rsi + 128] add rdx, -512 vpaddb zmm4, zmm3, zmm0 vpcmpltub k1, zmm4, zmm1 vpaddb zmm4, zmm5, zmm0 vpaddb zmm3 {k1}, zmm3, zmm2 vpcmpltub k1, zmm4, zmm1 vpaddb zmm4, zmm6, zmm0 vpaddb zmm5 {k1}, zmm5, zmm2 vmovdqu64 zmmword ptr [rcx], zmm3 vpcmpltub k1, zmm4, zmm1 vmovdqu64 zmmword ptr [rcx + 64], zmm5 vmovdqu64 zmm5, zmmword ptr [rsi + 192] vpaddb zmm6 {k1}, zmm6, zmm2 vmovdqu64 zmmword ptr [rcx + 128], zmm6 vmovdqu64 zmm6, zmmword ptr [rsi + 256] vpaddb zmm4, zmm5, zmm0 vpcmpltub k1, zmm4, zmm1 vpaddb zmm4, zmm6, zmm0 vpaddb zmm5 {k1}, zmm5, zmm2 vpcmpltub k1, zmm4, zmm1 vmovdqu64 zmmword ptr [rcx + 192], zmm5 vmovdqu64 zmm5, zmmword ptr [rsi + 320] vpaddb zmm6 {k1}, zmm6, zmm2 vmovdqu64 zmmword ptr [rcx + 256], zmm6 vmovdqu64 zmm6, zmmword ptr [rsi + 384] vpaddb zmm4, zmm5, zmm0 vpcmpltub k1, zmm4, zmm1 vpaddb zmm4, zmm6, zmm0 vpaddb zmm5 {k1}, zmm5, zmm2 vpcmpltub k1, zmm4, zmm1 vmovdqu64 zmmword ptr [rcx + 320], zmm5 vmovdqu64 zmm5, zmmword ptr [rsi + 448] vpaddb zmm6 {k1}, zmm6, zmm2 add rsi, 512 vmovdqu64 zmmword ptr [rcx + 384], zmm6 vpaddb zmm4, zmm5, zmm0 vpcmpltub k1, zmm4, zmm1 vpaddb zmm5 {k1}, zmm5, zmm2 vmovdqu64 zmmword ptr [rcx + 448], zmm5 add rcx, 512 cmp rdx, 63 ja .LBB0_9 This extracts more impressive 42.67B/c, I don't think even L2 cache can sustain such a throughput, but it's nice to know that medium length strings get up/downcased in about the same time it takes light from your screen to reach your cornea. The core for short lengths there is one instruction less: .LBB0_5: vmovdqu64 zmm3, zmmword ptr [rsi + rcx] vpaddb zmm4, zmm3, zmm0 vpcmpltub k1, zmm4, zmm1 vpaddb zmm3 {k1}, zmm3, zmm2 vmovdqu64 zmmword ptr [rax + rcx], zmm3 add rcx, 64 cmp r8, rcx jne .LBB0_5 Some months ago I wrote a similar ASCII in UTF-8 upcase/downcase implementation in C#: https://github.com/U8String/U8String/blob/main/Sources/U8String/CaseConverters/U8AsciiCaseConverter.cs#L158-L171 https://github.com/U8String/U8String/blob/main/Sources/U8Str... (the unrolled conversion for below vectorization lengths is required as short strings dominate most codebases so handling it fast is important - the switch compiles to jump table and then branchless fall-through to return) For now it goes as wide as 256b as it already saturates e.g. Zen 3 or 4 which have only 256x4 SIMD units (even though Zen 4 can do fancy 512b shuffles natively and has very good 512b implementation). The core loop compiles to compact G_M48884_IG05: vmovups ymm3, ymmword ptr [rdi+rax] vpaddb ymm4, ymm3, ymm1 vpcmpgtb ymm4, ymm2, ymm4 vpand ymm4, ymm4, ymm0 vpor ymm3, ymm4, ymm3 vmovups ymmword ptr [rsi+rax], ymm3 add rax, 32 cmp rax, rdx jbe SHORT G_M48884_IG05 Side by side with C ones: https://godbolt.org/z/eTGYhTPan https://godbolt.org/z/eTGYhTPan I believe you can also achieve similar with 3-instruction conversion with AVX512 with vpternlogd, as when I had access to AVX512 hardware, this is what .NET optimized it to for 256b width + AVX512VL, but strangely enough I can't make it do so for 512b width right now. You may notice failed SWAR attempt for switch dispatch case and I was wondering what kind of license your posts are distributed under? (gave up on it back then because per-element fall-through was already fast enough, but if yours passes the test suite, I'd love to use it haha)

fanf2 2y ago
Thanks for that analysis, very informative! I have not tried to get the best possible performance: at first I wanted to see if it would work at all, and the fact that my first attempt performed really well was a bonus! My main point of interest is strings less than the size of a vector register, and getting rid of the troughs in the throughput chart. You can click through the link to the code at the end of the blog post, which has all the licence details. It is 0BSD or MIT-0 except for the parts written originally for BIND which are MPL-2.0.
- neonsunset 2y ago
  Just to clarify - this was about SWAR version as my interest, similar to what you mentioned in a sibling comment, is in mainly below-vector-width strings, because these are most frequently passed to these kinds of functions by developers. I was going to try to see if it can further "amortize" the jump table with fallthrough for variable lengths below 16 in my C# UTF-8 string implementation that is going to use it. In any case, thanks for writing the article, for some reason there is quite a bit of negativity among users and developers towards AVX512 - it is seen as "AVX2 but twice as wide", which it of course isn't, but most do not know that. Also, you may want to simply do the overlapping conversion for the tail instead of masking out the elements, which is usually faster on the benchmarks (at least give it a try), and also align the source and destination for the loop to avoid split loads/stores.
inopinatus 2y ago
Clang and GCC have a differing approach to Intrinsics, and Clang is more likely than GCC to deviate from the Intel guide's specified opcodes & algorithms, and this is particularly noticeable with AVX-512 instructions. It's understandable given their respective architectures. Sometimes the result is an improvement, sometimes it is a detriment. A couple of years ago I worked on a heavily vectorized project that was intended to compile with either, and wound up maintaining inline asm and .S in the repository for specific targets alongside the C reference version. That made for some ugly Makefile shenanigans, and also meant including benchmarking as part of the test suite. It adds up to considerable maintenance burden, so the takeaway for me was that using Intrinsics as a low-level means to improve on the autovectorizer should be only very sparingly considered. Edit to add: quick example, from my notes during that project, https://godbolt.org/z/T4Pjhrz5d https://godbolt.org/z/T4Pjhrz5d ; the GCC output is what was expected, the Clang output was a surprise, and noticeably slower in practice, even when inlined. When looped (or similarly if unrolled), uiCA clocks it at 7 cycles to GCC's 4, and this was borne out by their benchmark performance in application code, in which this function was performed a few billion times in the course of a brute-forcing algorithm (which is to say, it mattered). I recall finding other issues where a dive into the LLVM codebase suggested that Clang 16 might be entirely unable to issue some masked AVX-512 instructions due to internal refactorings.

fanf2 2y ago

Thanks for that analysis, very informative! I have not tried to get the best possible performance: at first I wanted to see if it would work at all, and the fact that my first attempt performed really well was a bonus! My main point of interest is strings less than the size of a vector register, and getting rid of the troughs in the throughput chart. You can click through the link to the code at the end of the blog post, which has all the licence details. It is 0BSD or MIT-0 except for the parts written originally for BIND which are MPL-2.0.

neonsunset 2y ago
Just to clarify - this was about SWAR version as my interest, similar to what you mentioned in a sibling comment, is in mainly below-vector-width strings, because these are most frequently passed to these kinds of functions by developers. I was going to try to see if it can further "amortize" the jump table with fallthrough for variable lengths below 16 in my C# UTF-8 string implementation that is going to use it. In any case, thanks for writing the article, for some reason there is quite a bit of negativity among users and developers towards AVX512 - it is seen as "AVX2 but twice as wide", which it of course isn't, but most do not know that. Also, you may want to simply do the overlapping conversion for the tail instead of masking out the elements, which is usually faster on the benchmarks (at least give it a try), and also align the source and destination for the loop to avoid split loads/stores.

inopinatus 2y ago

Clang and GCC have a differing approach to Intrinsics, and Clang is more likely than GCC to deviate from the Intel guide's specified opcodes & algorithms, and this is particularly noticeable with AVX-512 instructions. It's understandable given their respective architectures. Sometimes the result is an improvement, sometimes it is a detriment. A couple of years ago I worked on a heavily vectorized project that was intended to compile with either, and wound up maintaining inline asm and .S in the repository for specific targets alongside the C reference version. That made for some ugly Makefile shenanigans, and also meant including benchmarking as part of the test suite. It adds up to considerable maintenance burden, so the takeaway for me was that using Intrinsics as a low-level means to improve on the autovectorizer should be only very sparingly considered. Edit to add: quick example, from my notes during that project, https://godbolt.org/z/T4Pjhrz5d https://godbolt.org/z/T4Pjhrz5d ; the GCC output is what was expected, the Clang output was a surprise, and noticeably slower in practice, even when inlined. When looped (or similarly if unrolled), uiCA clocks it at 7 cycles to GCC's 4, and this was borne out by their benchmark performance in application code, in which this function was performed a few billion times in the course of a brute-forcing algorithm (which is to say, it mattered). I recall finding other issues where a dive into the LLVM codebase suggested that Clang 16 might be entirely unable to issue some masked AVX-512 instructions due to internal refactorings.