11 ms·
tolower() with AVX-512
- h2odragon 2y agojust for giggles: http://www.unicode.org/Public/3.1-Update1/CaseFolding-4.txt http://www.unicode.org/Public/3.1-Update1/CaseFolding-4.txt
- fanf2 2y agoHeh, thank goodness I don’t have to deal with all that! This code is ascii-only because it arose from working on the DNS. There are other protocols that are ascii-case-insensitive so it turns up a lot in the hot path of many servers.
- tialaramex 2y agoThis is presumably Rust's u8::to_ascii_lowercase rather than C's tolower since tolower is locale sensitive (which you don't care about) and has Undefined Behaviour (because of course it does it's a C function and who cares about correctness) Or possibly u8::make_ascii_lowercase which is the same function but with in-place mutation.
- Asooka 2y agoThere is a difference between strings used internally, usually as IDs, and text entered by a human. For the former you'd always use straight ASCII in 8-bit encoding, for the latter ... things get difficult. A straightforward example are DNS addresses - they can technically contain almost any Unicode, but that is always converted to a very limited subset of ASCII for actual DNS resolution, which in turn is case-insensitive. There are of course things like programming languages with case-insensitive identifiers that support all human writing systems in Unicode. If that's what you're dealing with, you have my condolences.
- mananaysiempre 2y agoFor what it’s worth, with IDNs you’re still going to do a kind of case folding using stringprep before doing the query, and that isn’t really better than the table GP linked. ASCII-only case-insensitive matching is indeed a thing, but it’s usually mutually exclusive with (non-programmer) user-entered data.
- tialaramex 2y agoOn the wire DNS questions and answers are case preserving but not case sensitive which is important for correctness. DNS was designed a long time ago and doesn't have enough places to hide randomness (~30 bits at most are available) to protect it against a realistic attacker, so, for most names we do a terrible trick in the real world - we randomize the case during querying. This is called DNS-0x20 for obvious reasons. Suppose a web browser wants to know news.ycombinator.com AAAA? but bad guys know it's about to ask this (e.g. they use JS to force that lookup when they wanted), they can shove a billion bogus answers (one for every possible random value) onto the wire and have a great chance to trick the browser into accepting one of these answers which seemingly is to the question it just asked. But, if we instead pick random cases we're asking about, say, NeWS.yCOmbinAtOR.cOM and we can ignore answers for nEWS.yCOMBINATOR.cOM or news.ycombinator.com or NEWS.YCOMBINATOR.COM or any other spelling. Bad guys now need to do many orders of magnitude more expensive work for the same results.
- deleted 2y ago[deleted]
- account42 2y ago> There are of course things like programming languages with case-insensitive identifiers that support all human writing systems in Unicode. If that's what you're dealing with, you have my condolences. Fun times when an upgrade of the Unicode library used by your compiler changes the semantics of you program.
- hnben 2y ago> For the former you'd always use straight ASCII in 8-bit encoding why is that? IMO internal strings should be treated as black-box byte-arrays, i.e. the specific content does not matter to the software, except for checking equality between to strings. In this case it should not matter to the software if it is unicode or whatever.
- atoav 2y agoNote for the first example which transforms the German maße to MASSE that the German language has an uppercase Eszett as well: ẞ This is as of now not widely deployed and few fonts support it, but in theory it is there now.
- pdpi 2y agoWhile we're having fun with that: # Capitalising an eszett changes the string length. >>> "straße".upper() 'STRASSE' # If you don't specify the locale, round-trip upper/lower case # messes up the dotless i used in turkic languages. >>> 'ı'.upper().lower() 'i'
- kleiba 2y agoUp until a few years ago, the first conversion would have been the official way to write a German word that contains the ligature ß (a lower-case letter) in all caps, because there was no corresponding upper-case letter. However, in 2017, an upper-case variant [1] was introduced into the official German orthography, so the conversion cited here should no longer be necessary. [1] https://en.wikipedia.org/wiki/Capital_%E1%BA%9E https://en.wikipedia.org/wiki/Capital_%E1%BA%9E
- Tomte 2y agoIt is extremely unusual, and the addition to Unicode was very controversial. Basically, some type designers liked to play with capital ß and thought it cool to have it included into Unicode. There was a whole campaign for inclusion, and it was a big mistake. Because even though existing use must be shown to merit inclusion, they only managed to find a single book (a dictionary) printed in more than a few copies. From East Germany. And that book only used the capital ß for a single edition (out of dozens of editions) and reverted straight back to double s. Somehow, that still was enough for Unicode. Capital ß is a shit show, and it only confuses native speakers, because close to none of them have ever seen that glyph before. It has no real historic lineage (like the long s, for example, that pretty much nobody under 80 knows, either), it is a faux-retro modern design, an idle plaything.
- kleiba 2y agoWell, what can you do... amtlich is amtlich. And the behavior of a function that converts ß to double upper-case S can certainly be discussed too, if only for the fact that a round-trip toUpper().toLower() will not give you back the original word.
- kolbe 2y agoDid you try something like this? The autovectorizer looks pretty clean to me. https://godbolt.org/z/1c5joKK5n https://godbolt.org/z/1c5joKK5n
- fanf2 2y agoThat’s basically the same as `tolower1` - see the bullet points below the graph
- kolbe 2y agoWell, 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.
- fanf2 2y agoThe 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.
- kolbe 2y ago
- neonsunset 2y agoMask 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)
- ipunchghosts 2y agoI'm lost, what is swar?
- paulryanrogers 2y agoSIMD within a register
- jhart 2y ago[dead]
- singron 2y ago"SIMD Within A Register" I think the implication is that you can pack multiple items into an ordinary register and effectively get SIMD even if you aren't using explicit SIMD instructions. E.g. if you pack a 31 and 32 bit number into a 64 bit register (you need 1 spare for a carry bit), you can do 2 adds with a single 64-bit add. Games have used these tricks for graphics to pack RGB(A) values into 32 bit integers. E.g. this code from scummvm interpolates 2 16-bit RGB pixels (6 total components) packed into a 32-bit value. https://github.com/scummvm/scummvm/blob/master/graphics/scaler/intern.h https://github.com/scummvm/scummvm/blob/master/graphics/scal...
- LelouBil 2y ago> 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 ?
- jmalicki 2y agoThe operation is `tolower` Capital a is 0x40, lowercase is 0x60. The addition of 0x20 needs to happen when is_upper is true.
- fanf2 2y agoD'oh, I must have seen your comment 10 times before I realised the to_upper variable is named backwards and should be called to_lower. Thanks for pointing out that it was confusing! I've fixed the post and the code.
- Joker_vD 2y ago...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?
- dzaima 2y agoRISC-V does have RVV, which similarly can do SIMD, has masking, but also has a vector length separate from masks: https://godbolt.org/z/rrEW85snh https://godbolt.org/z/rrEW85snh. Complete with its own set of ~40000 C intrinsics (https://dzaima.github.io/intrinsics-viewer https://dzaima.github.io/intrinsics-viewer). Though, granted, RVV is significantly more uniform than AVX-512 (albeit at the cost of not having some useful goodies).
- pca006132 2y agoRISC-V has SIMD extension as well. Even when there is no SIMD, prefetching or instruction selection/scheduling will have a big impact on the performance, so it is unlikely one can easily write a few lines of assembly and get to a similar level of performance.
- Narishma 2y agoI don't think RISC-V's SIMD extension is very popular. At least I can't think of any available core implementing it. The vector extension is much more common.
- Findecanor 2y agoThe "P" (Packed SIMD) extension is still under development. It uses GPRs and is intended for smaller cores for which V would be too heavyweight. The proposal originates with Andes, and one of their own ISAs. They have several RISC-V cores with an early draft of it.
- fanf2 2y ago
- xyst 2y agoNow 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
- rurban 2y agoHe wrote about tolower(), not towlower()/wcslwr().
- deleted 2y ago[deleted]
- Brananarchy 2y agoC tolower() is locale aware and handles utf-8 as well as many other encodings
- fanf2 2y agoIt can only handle single-byte character sets, not UTF-8
- bonyt 2y agoSee also, https://github.com/Daniel-Liu-c0deb0t/uwu https://github.com/Daniel-Liu-c0deb0t/uwu Using SIMD for making text into … uwu.
- anderskaseorg 2y agoNote 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 https://github.com/ogxd/gxhash/issues/82
- dzaima 2y agoIt would be neat to have non-assembly options for things like this. A "load with unspecified elements for any values past the end of the allocation, UB only if the hardware doesn't like it" thing shouldn't be hard to support, even if just as an alias for the respective assembly invocations. Additional neatness would be being able to request a guarantee that all allocations - malloc, stack, constants - have at least, say, 64 bytes of non-faulting addresses after them, though that is significantly more complex, requiring cooperation between a bunch of parts. Annoying thing is that this is trivial with a custom allocator (as long as the compiler isn't told to consider the custom sub-allocations as separate), but then you're stuck not being able to use your SIMD stuff on anything outside your custom heap due to the very tiny chance of segfaulting. Sanitizers/valgrind don't necessarily become pointless with this even - the past-the-end values are still undefined, can be tracked as such, and error on use.
- tomsmeding 2y ago> A "load with unspecified elements for any values past the end of the allocation, UB only if the hardware doesn't like it" thing shouldn't be hard to support Not an expert, but to me this sounds like you want an alternative where behaviour for a read beyond the end of an allocation is merely implementation-defined, not undefined. That means the implementation (e.g. LLVM) has to document what they do — which may be platform-dependent — and the choice of whether it becomes undefined is up to the implementation. The natural thing to do here for the implementation is of course to say "I'm just going to emit the load instruction, it may crash your program, better be prepared".
- Remnant44 2y agoNeat 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.
- Tuna-Fish 2y agoIf Intel actually implements AVX10/256 on every CPU they ship going forwards, it will eventually win simply by availability. The market has repeatedly and thoroughly rejected dispatching to different code paths based on CPU, so the only SIMD implementation that actually matters is the lowest common denominator. And since AVX10.1/256 and AVX512VL have a shared subset, that will be what people will eventually target once enough time has passed and nearly everyone has a CPU that can support it. AVX512 will continue to give AMD some easy wins on the few benchmarking apps that were actually updated to support it, but if Intel sticks with the AVX10 plan I expect that AMD will eventually just use the double-pumped SIMD pipes for everything, just because they are the more efficient way to support AVX10/256 while retaining AVX512 compatibility. Intel did a lot of bad choices in the past decade, but segmenting the market based on instruction set has to be one of the worst. They just chose to kill all the momentum and interest in their newest and best innovations. Hopefully they actually add AVX10/256 support to the whole lineup, because the width is the least interesting part about AVX512, the masked operations especially are a lot more important.
- Remnant44 2y agoI agree. I still hesitate to ship code that requires even AVX1, even though it was first introduced in 2011(!). AVX512 really improves the instruction set. Not just from masking but from some really big holes filled in terms of instructions available that AVX2 doesn't have a good solution for. At the same time I also DO have plenty of code that could definitely use the compute throughput improvement of 512 bit vectors. But it's definitely a more niche usage. You have to at least nominally satisfy that you: 1) Benefit from 2x the ALU throughput 2) Live mostly in the cache 3) Are not worth running on the GPU instead.
- dolmen 2y agoUnfortunately 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 https://github.com/sugawarayuuta/charcoal/pull/1
- Findecanor 2y agoMasked SIMD operations, which are in AVX-512 and ARM SVE were intended to solve that problem. Then memory operations could still be aligned and of full vectors all the time, but masked to only those elements that are valid. Even if a masked vector-memory operation is unaligned and crosses into an unmapped or protected page, that will not cause a fault if those lanes are masked off. There are even special load instructions that will reduce the vector length to end at the first element that would have caused a fault, for operations such as strlen() where the length is not known beforehand.
- rowanG077 2y agoIn 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.
- kazinator 2y agoWith 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.