tolower() with AVX-512

Note that the “unsafe read beyond of death” trick is considered undefined behavior in the Rust and LLVM memory model, even if it’s allowed by the underlying hardware. Like any undefined behavior, compilers are allowed to assume it doesn’t happen for the purpose of optimization, leading to results you don’t expect. The only way around this is to use inline assembly.

https://github.com/ogxd/gxhash/issues/82

Neat and performant code like the article makes me very curious how the competition will shake out between AMD's AVX512 implementation and Intel's upcoming AVX10. The entire point of AVX10 seems to be to resolve Intel's P vs E core situation, while AMD seems to have taken a better approach of using either full width (Zen5) or double-pumped 256bit (Zen4, Zen5 mobile) as appropriate to the situation, while making the API seamless.

The big gains delivered in the article are all on a double-pumped Zen4 core! AVX512 brings a lot to the table so its quite frustrating that Intel market-segmented support for it so heavily as to completely inhibit its adoption in broad-based client code.

just for giggles: http://www.unicode.org/Public/3.1-Update1/CaseFolding-4.txt

> Finally, we do a masked add. We pass c twice: bytes from the first c are copied to the result when is_uppper is false, and when is_upper is true the result is c + to_upper.

Is that an error in the post ? Shouldnt it do the addition when is_upper is false and copy the same when it is true ?

Unfortunately those SWAR optimizations are only useful for strings that are aligned on 8 bytes address.

If your SWAR algorithm is applied on a non-aligned string, it is often slower than the original algorithm.

And splitting the algorith in 3 parts (handling the beginning up to an aligned address, then the aligned part, and then the less-than-8-bytes tail) takes even more instructions.

Here is a similar case on a false claim of a faster utf8.IsValid in Go, with benchmarks: https://github.com/sugawarayuuta/charcoal/pull/1

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/, 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/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

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)

I'm lost, what is swar?

With the advent of Unicode, the concept of upper and lowercase is a quagmire. You need a whole bunch of data to do it right.

If your work involves some process whose timely completion depends on how fast ASCII tolower executes, you better shake things up somehow and change the ground rules.

In the past I have added a black border around an image to be able to completely avoid the read beyond buffer SIMD problem. It worked very well and allowed us to beat some opencv implementation in terms of speed. But you don't always have full control over the input like that.

Did you try something like this? The autovectorizer looks pretty clean to me.

https://godbolt.org/z/1c5joKK5n

See also, https://github.com/Daniel-Liu-c0deb0t/uwu

Using SIMD for making text into … uwu.

Now account for Unicode characters (ie, Â -> â) and I’ll be impressed.

Shame most programmers only care about ASCII. There is a whole world that exists outside of the standard [a-z,A-Z,0-9] character set

...you know, while I personally think that the RISC approach was an honest mistake, stuff like this makes me see why some people wanted to got rid of complex instructions.

Well, supposedly RISC-V implementations will have none of this malarkey while still rivaling x64/ARM64 in processing speed at comparable technology/clock rates/prices, just with plain old loads-and-xors-and-stores?