tolower() with AVX-512
dotat.at
dotat.at
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.
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".
Alternatively, a different API would be returning an optional of the loaded data, having the stdlib/language/backend convert that to the appropriate boundary check (or always returning a None if impossible).
Ideally there'd be languages that can be at least configured into providing more "unsafe" useful things, even if at the expense of not having the code be compilable targeting funky hardware that noone would run the software in question on anyway.
That said, clang's MemorySanitizer, and, similarly, valgrind, could still produce errors via tracking which bytes are undefined within registers; might be somewhat delayed between load and error, but still shouldn't allow such out-of-bound values to be used for much.
And, anyway, as this load would be a separate instruction/builtin (if so decided), UB of regular operations is unaffected. If the sanitizer in question doesn't track (partial) register definedness, it could just accept all of these explicitly-potentially-OoB loads; indeed not ideal, but the alternative is not being to write such performant code at all.
And there are already people doing this, just limited to doing so with data within a custom allocator. It would just be nice to have a mechanism to not be fully ruled out of using standard tooling at least for testing.
Not using sanitizers is, of course, an option, but, as should be obvious, is very much not optimal. Having a single "questionable" operation in one place does not mean that the programmer intends for the entire function or program to be all "programmed against the machine"; the rest of the code, and, to an extent, even the fancy operation in question, could still very much benefit from regular language tooling.
Such operations needn't even be machine-specific.
"try loading N bytes, accepting garbage out-of-bounds; return None if cannot be done without potentially faulting" says and requires nothing about the architecture, and is implementable everywhere (even if as always returning None).
Aligning pointers is another option, but is fundamentally in no way different from the memory-protection-boundary-based version in how much it relies on hardware specifics, and compiler/language builtins could still be made that allow for sanitizer-friendly usage. It might be more or less efficient depending on use-case, both are useful to have.
Of course, the best option would be that malloc, the linker, etc work together to guarantee at least N bytes of addressable memory past all user-accessible pointers, at which point architecture specifics completely stop mattering. This needn't change any behavior around sanitizers or regular loads; all it'd mean is that the "load N bytes with trailing garbage" operation can always succeed. Sanitizers could error on said op reading outside of the guaranteed readability size, and regular loads of course continue erroring on any out-of-bounds read. Compilers could even use this guarantee themselves to emit unmasked loads for loop tails.
The other option that I've seen discussed is adding a freezing load to LLVM that turns the undef bits into some unspecified but valid bit patterns.
As soon as the thing is packaged to run on an raspberry or something else that doesn't like it, it will start to generate CVEs and be a major pain.
Masked loads kinda suck, they are a tiny bit slower and you now need a mask and you need to compute the mask..
The one case it can be annoying is passing pointers to constant data to custom-heap-assuming functions - e.g. to get a pointer to [n,n-1,n-2,...,2,1,0] for, say, any n≤64, make a global of [64,63,...,2,1,0] and offset its pointer; but you end up needing to add padding to the global, and this materializes as avoidable binary size increase as the "padding" could just be other constants from anywhere else. Copying the constant to the custom heap would be extra startup time and more memory usage (not sharable between processes).
A trick to avoid reading beyond the end of the buffer is to make sure the end of the buffer lies on the same page. Typically, the OS will allocate memory in pages of 4KB, thus we can make a function that checks whether it is okay to read beyond or if we should fallback to the copy version.
-- https://ogxd.github.io/articles/unsafe-read-beyond-of-death/
But it sounds like the masking feature mentioned in a sibling comment takes care of it anyway.
It might not be the nicest thing to assume to be the case on all hardware, but it shouldn't be too unreasonable to put it under an "if (arch_has_a_minimum_page_size)". So many things already assume at least 4KB pages, Intel/AMD aren't gonna break like half the world. If anything, they'd want to make larger pages to make larger L1 caches more feasible.
I definitely see the conundrum since the dangerous code is such a huge performance gain.
No. First, undefined behavior is a term of art in the C standard, so the idea of generalizing it is nonsensical. Second, ANSI C explicitly does not allow this assumption, and ISO C—while more open ended—doesn't specifically justify this assumption. The entire "UB = assume it cannot happen" thing is grossly dishonest FUD.
"It's always been this way so it's impossible to address." Forgive me if I'm not convinced.
From https://highassurance.rs/chp3/undef.html:
> In other words, should a developer inadvertently trigger UB, the program can do absolutely anything.
Well, no. It is "behavior . . . for which this International Standard imposes no requirements." There are restraints and constraints beyond the ISO standard.
realloc(p, 0) is now undefined in C23. However, every mainstream OS and compiler specifies the correct behavior for that environment. It is simply not. true. that the program can do anything. What is true is that the range of behavior is not restricted by the ISO standard.
A very significant amount of their effort, time, focus went into understanding precisely what was, and was not "Undefined Behavior" - the instant you did anything that was "undefined" anything that happened after that was fair game.
They also did zero dynamic memory allocation after starting an application. All memory was allocated on startup based on initial config settings.
My sense in watching that extraordinarily skilled team was that the logic and features they were building (on a very complex FHSS MAC) were secondary to convincing the compiler and hardware to do something that the specifications and definitions should happen. The great firmware developers were also pretty solid language lawyers.
What I am saying is that a compiler that sees
int8_t x;
float x;
I am also saying that a compiler that offers -fwrapv and formats your hard drive on int x = INT_MAX; x++; rather than "behaving during translation or program execution in a documented manner characteristic of the environment" is pathological, violates the spirit of the ANSI and ISO standards, and violates the letter of the ANSI standard.
Note that one of the differences between C and Rust is that integer overflow is not UB in Rust (it panics in debug mode and wraps in release mode: https://doc.rust-lang.org/book/ch03-02-data-types.html#integ...). But there are other sources of UB in unsafe Rust, such reads through a pointer not allowed by the memory model.
No, they really don't. https://godbolt.org/z/M6hcTx3aY
Clang will not blow your computer up just because you use #pragma STDC FENV_ROUND <direction> in accordance with its documentation.
I don't know why it became popular to make UB into a bogeyman and act like it's an intractable problem, but it isn't. Compilers handle most UB just fine.* It's better for everyone if we can focus on the actual problems rather than blowing it out of proportion with sweeping generalizations.
* All undefined behavior is undefined, but some undefined behavior is more undefined than others.
It sounds like you agree that programmers should avoid relying on luck for UB safety. If you have a way to prove that this UB is actually safe and not just lucky, feel free to present it. Until then, I stand by everything I’ve said.
It isn't true to say that "any undefined behavior" can result in a parade of horribles. That is a sweeping generalization. Huge amounts of undefined behavior are in fact well-defined by the implementation and/or environment.
Indeed, the formal definition of "implementation-defined" is so narrow that most of what you'd think should be "implementation-defined" is actually "undefined." The example I gave of realloc(ptr, 0) is one such case. "Classifying a call to realloc with a size of 0 as undefined behavior would allow POSIX to define the otherwise undefined behavior however they please." WG14 n2464, available at https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2464.pdf
There’s nothing wrong or misleading in what I wrote. If, hypothetically, there were a second specification that constrained the Rust compiler’s translation of programs that over-read memory, then it would have been wrong to write that over-reading memory in Rust is undefined behavior, and misleading to suggest that a statement about “any undefined behavior” is applicable to it. But there is no such second specification (as confirmed by comments on the issue I linked from RalfJung, whose formal specification hat is much pointier than either of ours), and you aren’t even disputing that. Instead, you have deliberately misapplied a statement about “any undefined behavior” to other unrelated behavior that is in fact defined, in order to construct a pretense for calling someone else dishonest. Find better hobbies.
There's no such thing as "insofar as both specifications apply to it, that is defined behavior, not undefined behavior." Undefined behavior in C that is standardized by POSIX is still undefined behavior. Indeed, that is why "Possible undefined behavior [includes] behaving during translation or program execution in a documented manner characteristic of the environment." Behaving according to the POSIX specification on a POSIX system (or according to the specification of any system on that system) is explicitly accounted for in the definition of "undefined behavior."
These things are objectively, inarguably true, and recorded in black and white. I do not understand why you are so relentless in trying to gaslight HN about them. Just stop.
When the term “undefined behavior” appears in different context, we use our writing and reading comprehension skills to agree on what it means. If we’re programming in standard C, it refers to one class of behavior. If we’re programming in POSIX C, it refers to a smaller class of behavior (even according to the C standards committee: see the usage of “otherwise undefined behavior” in N2464). If we’re programming in Rust, it refers to a completely different class of behavior.
From my very first message, I did my part by providing the context explicitly: “undefined behavior in the Rust and LLVM memory model”. You complained that it’s nonsense to talk about “undefined behavior” in any context other than the C standard, but I provided references showing that it’s not. Yet you persist in intentionally misinterpreting what I wrote in order to accuse me of gaslighting. Does that make you feel superior?
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.
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.
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.
I’ve been shipping software that requires AVX2 and FMA3 because it is a professional CAM/CAE application. Our users typically don’t use sub-$100 Intel processors like Pentium and Celeron. The key is communication, you need to make sure users are aware of the hardware requirements before they buy.
Another example, in the server market, you can almost always count on having at least AVX2 support because most servers today are cloud-based. For people running these cloud services, power efficiency is crucial due to the high cost of electricity, so they tend to replace old hardware regularly.
On the other hand, for desktop software aimed at a broad audience, there are valid reasons to hesitate before shipping code that requires AVX1.
Modern GPUs include hardware accelerators for popular video codecs, these are typically way more power efficient than even AVX-512 software implementations.
Believe what you want but as soon as realtime is not a concern and quality matters you'll be using CPU-based encoders unless you have special hardware for your use case.
> Modern GPUs include hardware accelerators for popular video codecs
... with shit quality encoders because they are designed for speed first.
Decoding is a different matter but even there older hardware can easily end up not supporting codecs (or profiles of them) that you come accross.
For IO bandwidth-bound heavy lifting these things typically use AES algorithm. The hardware support for that algorithm is widely available inside CPU cores for more than a decade: https://en.wikipedia.org/wiki/AES_instruction_set#x86_archit... That hardware support is precisely what enabled widespread use of HTTPS or full disk encryption. Before AES-NI it was too slow, or it required specialized accelerator chips found in web servers in 2000-s who needed to encrypt/decrypt HTTPS traffic.
I don’t think people use AVX2 or AVX512 for AES because AES-NI is way faster. The runtime dispatch needs just a few implementations: hardware-based AES to use on 99% of the computers, and couple legacy SSE-only versions.
Later, 256-bit AES instructions were introduced, but significantly later than AVX2. Such 256-bit AES instructions, which double the AES throughput, are available in more recent CPUs, like AMD Zen 3 and Intel Alder Lake (the so-called VAES instructions).
Some of the more recent CPUs with AVX-512 support have added 512-bit AES instructions, for an extra doubling of the AES throughput.
Zen 5 (desktop and server) doubles the AES throughput in comparison with Zen 4, similarly with the double throughput for other vector operations.
In conclusion, on x86 CPUs there are many alternatives for AES, which have different throughputs: 128-bit SSE instructions since Westmere, 128-bit AVX instructions since Sandy Bridge, 256-bit VAES AVX instructions since Zen 3 and Alder Lake and 512-bit AVX-512 instructions since Ice Lake, but only in the CPUs with AVX-512 support.
What do you mean? At least numpy and pytorch (the only numeric libraries I'm familiar with) both use runtime dispatching.
RHEL just moved up to x86_64-v2, equivalent to 2009 level CPUs. And they’re an early mover, Fedora/Ubuntu/Arch have not done the same.
Glibc has used CPU dispatching for str* and mem* functions for over a decade.
Mask operations can be trivially emulated with vblend, it is one extra instruction..
Width can't be emulated, you just are stuck running half speed.
This take keeps getting repeated, but doesn't appear to be backed up by reality.
Intel hasn't even put AVX10 on their upcoming chips(skymont), so it appears to be going nowhere.
For unaligned loads where you can't guarantee that the entire vector is on a mapped page?
What I like to see (for desktop) is: better cores, more cores, well standardized instruction sets that unlock useful things (wide SIMD, float16, gather/scatter, ...). AMD is doing pretty well at this. What Intel is doing instead: put weak cores alongside decent cores, cripple the decent cores to keep up with the weak cores, release CPUs with the same amount of cores as before for many generations in a row, use the weak cores to make it sound like they have more cores than they have, bring out way too many variants of instructions sets to ever have a useful common set, drop support for their own promising sounding instructions
I just really dislike anything Intel has come out with or plans to come out with lately :p
My cycle of preference of manufacturer (for desktop computers) has been: 90s: Intel. Early 2000s: AMD (pentium 4 was so meh). late 2000's+2010s: Intel. Now: AMD again. What will Intel do to gain foothold again (that isn't sabotaging the other)? We need to keep the competition going, or the other side may get too comfortable.
This would render the shuffles unusable, because you'd unpredictably have them costing either 1 uop or cycle to taking 10-30 uops/cycles depending on which core you are on at the moment. A situation similar to PEXT/PDEP, which cost almost nothing on Intel and dozens of cycles on AMD until a couple generations ago.
Why does Zen 4 not have this problem? First, they're only double-pumping instead of quad-pumping. Secondly, while most of their AVX-512 implementation is double-pumped, there seems to be a full-length shuffle unit in there.
Those large shuffles are really powerful for things like lookup tables. Large tables are suddenly way more feasible in-register, letting you replace a costly gather with an in-register permute.
It simply decodes operations on ZMM registers into multiple uOPS and schedules them to free 256b units. In addition, Zen 4 has special handling of 512b full-width shuffles, with dedicated hardware to avoid doing very expensive emulation. As a result, Zen 4 with its 4 256b SIMD units still acts like a very strong 2x512b core. There is nothing cheap about this implementation and it is probably the best rendition for consumer hardware so far.
Or possibly u8::make_ascii_lowercase which is the same function but with in-place mutation.
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.
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.
Fun times when an upgrade of the Unicode library used by your compiler changes the semantics of you program.
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.
This is as of now not widely deployed and few fonts support it, but in theory it is there now.
# 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'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.
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.
It is an inherently destructive round trip, especially in a language that makes excessive use of upper case when comapred to english. When you have the word "wagen" did it originally refer to a "car" or did it refer to someone "trying"?
I agree though that this makes the round-trip inherently destructive.
I don't think it's particularly confusing, but it is a great addition. As of 2017 the rules allow both "SS" and "ẞ".
Moreover, the current version of DIN 5008 (Rules for Writing and Design in Text and Information Processing) actually recommends preferring "ẞ" over "SS".
Ostensibly, the reform only applied to officials in government agencies, but that also included both teachers and students in schools, and today using the old orthography in university exams is marked as errors (although many lecturers don‘t care and won‘t mark it up). Just went through it a few months ago.
Today, new orthography is not optional, at workplaces you will be corrected (and sometimes chastised) for using old orthography. Just recently a colleague went through a document I wrote and changed every "daß" to "dass". Nothing else was changed.
The ship has sailed, though, since many cohorts of students have gone through it now. I would just like people to be tolerant of what we older people learned in school. I don‘t want to re-learn everything. Just leave me in peace.
ẞ is not a good capital letter of ß, but if that one single book ever gets transcribed into digital text, a unicode character code is necessary for that to happen.
I doubt systems that can't deal with the ß -> SS transcription will be able to deal with ẞ in the first place.
Next you are going to ask Unicode to include all fancy stylized initials which are of course specific to the paragraph in a single book they are used in? At that point just embed SVGs directly in Unicode because the fight for any semantic meaning has been lost.
Pretty sure the actual question would be: what if there are multiple conflicting official specs?
Well, the problem with any kind of language spec change is that it can take decades until it gets accepted widely.
Young people are the first adopters as they get it force-fed by schools, but getting the age bracket 40+ to adopt is a real challenge. Germany's 1996 project led to years-long battles and partial reversals in 2004/06, and really old people to this day haven't accepted it.
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 ?
Capital a is 0x40, lowercase is 0x60.
The addition of 0x20 needs to happen when is_upper is true.
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
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.
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
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
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
(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
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 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.
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.
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 ; 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.
(x >= 'a' && x <= 'z')
(x - 'a') < <some constant>
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/scal...
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.
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
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], zmm3Interestingly 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.
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.
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;
}
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.
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!
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).
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).
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.
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.
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 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!
> 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.
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...
Autovectorization is great and improving.
Using SIMD for making text into … uwu.
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
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?
Though, granted, RVV is significantly more uniform than AVX-512 (albeit at the cost of not having some useful goodies).
The proposal originates with Andes, and one of their own ISAs. They have several RISC-V cores with an early draft of it.
All while being scalable, i.e. minimum vector register width (VLEN) is 128-bit for the 'v' extension, but hardware can implement up to 65536-bit vectors (and software can choose to either pretend they're 128-bit, or can be written such that it portably scales automatically); and if you want more than 128 bits portably there's LMUL, allowing grouping registers up to 8 in a group, giving up to at-least-1024-bit registers.
For shuffles it has vrgather, which supports all element width lookups and can move any element to any other element (yes, including at LMUL=8, though as you can imagine it can be expected to slow down quadratically with LMUL; and could even become a problem at LMUL=1 for hardware with large VLEN, whenever that becomes a thing).
The core of modern RISC thought is basically: "The laws of physics mean that no matter how much hardware you throw at it, only some kinds of instructions can be implemented in a performant way. We should only include these kinds of instructions in the instruction set." Then you build more complex operations out of these simple building blocks, but the fact that every instruction provided can be reasonably implemented to run really fast, the CPU itself can be fast.
Masked vector adds belong in the set of instructions that can be implemented to be fast, and that's why they are included in the RVV RISC-V extension. An example of an instruction that cannot be implemented to be fast would be the humble x86 load+add, where you first look up a value in memory, and then add it to a register. The only reasonable way to implement this to be fast is to just split it into two separate operations which are also dispatched separately, and that is precisely what modern x86 does.