News for hackers. Stuff that matters.
Re:tolower() in bulk at speed by dietrichepp on Monday June 27, 2022 @06:28PM (#31901712)
Naive version to explore autovectorization:

https://gcc.godbolt.org/z/bcefvznG3

Yes, there's some amount of autovectorization here. Seems like a mess of a function. Here's something more like tolower8():

https://gcc.godbolt.org/z/h8GTanodd

The generated code definitely looks funny to me. Here is a manual vectorization, which is shorter:

https://gcc.godbolt.org/z/1e4odEsKq

The issue of loading into your vector register... well, there are some dirty tricks for that. The 16-byte slice containing the first byte, and the 16-byte slice containing the last byte, can both be loaded into registers and then shifted around in order to construct the desired value. Note the careful wording here... these slices might be the same slice. Or you can iterate over the 16-byte slices containing the array, and shift as you go, if you're storing into a different location. Or you can use various masked load/store operations on various architectures.

Re:tolower() in bulk at speed by nimish on Monday June 27, 2022 @07:30PM (#31902287)
> Seems like a mess of a function

It has to deal with an arbitrary n, so it's going to have some messy bits to deal with the "fringe": https://www.sigarch.org/simd-instructions-considered-harmful...

Re:tolower() in bulk at speed by janwas on Tuesday June 28, 2022 @02:12AM (#31904648)
It's often possible to avoid fringes via padding/overallocation. And if not, it may be possible to use unaligned loads/stores to handle the fringe in a single (final) iteration: https://github.com/google/highway#strip-mining-loops

It is actually feasible to write vector-style code using SIMD instructions. Yes, the SIMD ISA is more complicated because of the various accumulated extensions, but this is what we currently have. And a bit larger code size (for one final loop iteration) doesn't seem to be a big deal.

Re:tolower() in bulk at speed by tialaramex on Tuesday June 28, 2022 @05:44AM (#31905861)
This sort of stuff is where Iterate Loops are good:

https://github.com/google/wuffs/blob/main/doc/note/iterate-l...

WUFFS wants this because it demands all the checking at compile time (WUFFS code with a potential buffer overflow just won't compile), so if you need bounds checks you'll be writing them out by hand and the iterate loop often allows you to express a correct solution with no actual checks.

Re:tolower() in bulk at speed by dietrichepp on Monday June 27, 2022 @08:57PM (#31902875)
It’s more of a comment on how messy that code gets at -O3… it looks a lot messer than the -O2 code.

(I think, it’s time, to say that “‘X considered harmful’ considered harmful”.)

Re:tolower() in bulk at speed by dzaima on Tuesday June 28, 2022 @07:57AM (#31906562)
-O2 doesn't have any usage of SIMD/vectorization though. Of course it'd be simpler.
Re:tolower() in bulk at speed by dietrichepp on Tuesday June 28, 2022 @08:45AM (#31906937)
...Have you looked at the -O3 assembly that I'm talking about?

There's a short SIMD loop, which is simple, and fairly easy to understand. At -O2, you get a short scalar loop, which is simple, and fairly easy to understand.

If you were writing this function by hand, you might combine the SIMD loop with the scalar loop. That's not what happens, though. Instead, you get two versions of the SIMD loop which handle different alignments (unnecessary) and then, what appears to be an unrolled version of the scalar loop.

What’s going on here is that there are a bunch of transformations enabled at -O3 that come along with autovectorization. You don’t just get autovectorization by itself, you also get transformation passes that are designed to put your code into a state where vectorization is easier. You also sometimes get a number of transformations which are (empirically) dubious, in the sense that the resulting code is both larger and slower.

Re:tolower() in bulk at speed by dzaima on Tuesday June 28, 2022 @09:21AM (#31907337)
There's only one SIMD loop - a 128-bit one. There's a 64-bit SIMD segment for handling handling when the tail has ≥8 items (which is gonna be a pretty decent speedup for 8≤n≤15 byte inputs). If you're gonna operate on only very large inputs, it's quite unnecessary, yeah, but for a lowercasing function small inputs will be very common.

The unrolling of the scalar tail is quite unnecessary though (gcc does so even with -fno-unroll-loops). clang doesn't[0], though it does unroll the main loop (though that can be disabled with -fno-unroll-loops).

[0]: https://gcc.godbolt.org/z/n85aavnEo

Re:tolower() in bulk at speed by dietrichepp on Tuesday June 28, 2022 @10:28AM (#31908120)
You're right, only two loops.

It is still messy, though. And "it has SIMD" is not really a sufficient explanation for the messiness. I think of -O3 as a kind of "throw everything at the wall and see what sticks". You're pressing a button that makes your code big, messy, and fast (although not always big, not always messy, and not always fast).

You can spend as much time as you like explaining the reasoning behind these code transformations, but in the end, there are very good reasons why people don't use -O3 as the default optimization level.

Re:tolower() in bulk at speed by dragontamer on Monday June 27, 2022 @06:46PM (#31901905)
> The issue of loading into your vector register... well, there are some dirty tricks for that.

Good discussion. I think the only method you haven't talked about is the simple "unaligned load" instructions (which might be the simplest, and most portable way, to do this). I know that ARM and x86 both can do unaligned loads no problem, but at a possible performance penalty.

Re:tolower() in bulk at speed by dietrichepp on Monday June 27, 2022 @08:01PM (#31902497)
The reason I didn’t mention unaligned load is because it can cross a page boundary and fault. With aligned loads, you can avoid this.

(Edit: The idea is that with an aligned load, you only load 16-byte blocks that contain valid data. This can’t page fault, but you can load data you didn’t want, which is ok. Writing is trickier because the write may have to be atomic and can’t spill.)

Re:tolower() in bulk at speed by zen_1 on Monday June 27, 2022 @09:45PM (#31903196)
Another (admittedly quite niche) gotcha I've experienced with aarch64 unaligned SIMD loads specifically is that they will fail (raising a data abort exception) if they access memory that isn't specifically designated as "normal ram" by the MMU.

This can happen if you're writing code for an embedded system, or even if you're calling memcpy with a too-smart-for-it's-own-good libc (such as Newlib, that ships with the aarch64-none-elf toolchain ARM provides...) implementation without first setting the MMU up.