Hacker News Reader

Comment by dragontamer | Hacker News Reader

Seems a bit odd to stop at SWAR on today's systems.

Every system I'm aware of has 128-bit SIMD implemented: either SSE (x86), NEON (ARM), or AltiVec (POWERPC). As such, 128-bit SIMD is the "reliably portable" SIMD operation.

Of course, for fastest speeds, you need to go to the largest SIMD-register size for your platform: 512-bit for some Intel processors, rumored AMD Zen4 and Centaur chips. 256-bit for most Intel / AMD Zen3 chips. 128-bit for Apple ARMs, 512-bit for Fujitsu A64 ARMs, etc. etc.

> And these are the fastest kinds of instructions :-)

And it should be noted that modern SIMD instructions execute at one-per-clock-tick. So the 64-bit instructions certainly are fast, but the SIMD instructions tie if you're using simple XOR or comparison operations.

--------

This style of code might even be "reliably auto-vectorizable" on GCC and CLANG actually. I wonder if I could get portable auto-vectorizing C from these examples.

View on HN

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.

> 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...

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.

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.

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”.)

-O2 doesn't have any usage of SIMD/vectorization though. Of course it'd be simpler.

...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.

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

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.

> 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.

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.)

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.

"labels are frequently less than 8 bytes long, and therefore fit inside a 64-bit register. So it probably isn’t worth dealing with the portability issues of working with wide vector registers (Especially since I could not find a quick way to load an arbitrary number of bytes into a vector register with AVX2 nor with NEON.)"

DNS labels like "ycombina" (tor) you mean? :-)

Two out of three ain’t bad :-)

news.ycombinator.com

Just off the top of my head, I'm betting that 9 out 10 of the most visited internet domains are 8 bytes or less. google, facebook, twitter, youtube, baidu, yahoo. I think instagram might be one of the few that isn't 8 bytes. That's not counting URL shorteners, either.

Actually most modern SIMD instructions have a throughput of more than one per clock cycle.

Simple SIMD instructions, like integer addition, comparison, XOR, have a throughput of 2 per cycle (many ARM cores), 3 per cycle (most Intel CPUs) or even 4 per cycle (AMD Zen 3).

Similar simple 64-bit instructions have a higher throughput in instructions per cycle, from 3 per cycle up to 5 per cycle (Alder Lake), but when considering the register size the total throughput of the SIMD instructions is always higher.

> Every system I'm aware of has 128-bit SIMD implemented

These still come in handy on embedded systems where there isn't a vector unit

Is there a good way to load an arbitrary number of bytes (up to the vector size) into a vector register? As I said in the article, I could not find one when looking at AVX2 or NEON reference manuals. Getting the data from RAM is the main bottleneck for short strings, which DNS names usually are.

You're not thinking in terms of SIMD.

If you load 5 bytes into a 128-bit register (16-bytes) you'll have 5-bytes of data + 11-bytes of garbage.

Perform the calculation over all 16-bytes. Yes, this makes 11-bytes of garbage at the end. Once you're done, just write back the first 5 bytes and you're set.

The 11-bytes of garbage are "free". They didn't cost you anything.

> Getting the data from RAM is the main bottleneck for short strings

Your L1 and L2 cache-lines are 64-byte minimum read / write anyway (actually, some systems were 128-byte minimum IIRC). A 16-byte read is literally smaller than what your cache does on the path into your registers.

EDIT: More importantly, modern CPUs only have 2x or 3x load/store units. Meaning a modern CPU can only perform ~2ish load/stores per clock tick. The SSE (16-byte / 128-bit) read / write to L1 cache will perform the same speed as a 8-byte /64-bit read/write to L1 cache in practice.

In fact the code that I left out of the blog post does almost exactly what you suggest :-) It’s the “load 5 bytes” and “store 5 bytes” that I don’t have a good solution for. At the moment I am using memmove() and relying on the compiler developers to have better ideas about optimizing it than I do… The bottleneck comes from the number of instructions and the branchiness, not the data bandwidth.

I briefly considered playing games with overlong reads, but then asan gave me a slap and I reconsidered the path to wisdom.

> branchiness

Memorize the following concept / pattern.

    int select(int choice, int A, int B){
        return (A & (~choice)) | (B & (choice)); 
    }

You can convert any "if(bool)" statement into the above 4 assembly instructions: two ands, an or, and a not.

This performs a 32-bit way parallel "choice" operation. For example, "choice = 0x00000000" will choose all bits from A. "choice = 0xFFFFFFFF" will choose all bits from B.

SIMD because "choice = 0xFFFF0000" will choose the first 16-bits from B, and the last-16 bits from A.

------

Any data-operation can be "simulated" with enough code operations, and vice versa. Obviously, use code when code is needed, and data when data is needed. But sometimes, you need to perform a "code/data" switcheroo and the above pattern helps.

EDIT: It doesn't always work. The combinational explosion of data may prevent such a technique from working in the general case. But still, its a good first step and "most if statements" are simple enough to work with the above pattern.

For loading the rag end of a string, the branchiness looks like

  while (len-- > 0) { /* load */ }

  switch (len) { /* 8 cases */ }

https://en.wikipedia.org/wiki/Duff%27s_device

SSE4.1 added `blend` which does this for most data types. The lone exception is 32 bit integers for whatever reason, which wasn't added until AVX2.

> It’s the “load 5 bytes” and “store 5 bytes” that I don’t have a good solution for.

You build that out of "load 16 bytes" and "store 16 bytes" operations.

    register = [news.YCOMBINATOR]
    isValid  = [00000FFFFFFFFFFF]; // "F" is really 0xFF, but you get the gist
    // isValid was generated because you were focusing on the YCOMBINATOR part
    // of the DNS entry: news . YCOMBINATOR . com. YCOMBINATOR there to focus
    // upon the current data being considered, while "news." and "com" should
    // remain untouched

    register = (register | ((register >= 'A' & register <='Z')  << 5));
    register = register & isValid;

    toWrite = writeLocation & (~isValid);
    toWrite = toWrite | register;
    writeLocation = toWrite;

If you're doing things in-place, then writeLocation could be a copy of "register" from the 1st step.

Doesn't work if you don't have read access past (or before) the segment you want. And, as GP says, asan won't like reading/writing out-of-bounds (even if temporarily) either. Probably very unlikely to happen, but that's not really something you want to be betting on.

I get it now. Thanks for explaining. That particular problem is solved by rounding up to the SIMD-width for all SIMD-allocations.

Ex: 13-size gets rounded up to 16-sized alloc. 25-size gets rounded up to a 32-sized alloc.

This, in combination of "processing of garbage" and "Valid" flags, should cover all the cases.

EDIT: At least, for the "dynamic" strings that are loaded into memory. Someone elsewhere has brought up compiler strings, which seem complicated to me (I'm not sure if we have any alignment guarantees, and therefore are forced to process strings sequentially, one byte at a time if they're from the compiler).

I agree padding is a good solution when you can arrange it.

In Highway we also use the blending/bit-select you mention: https://github.com/google/highway/blob/master/hwy/ops/generi... If HWY_MEM_OPS_MIGHT_FAULT, which is true if using ASAN or AVX2 (because AMD reserves the right to fault even if mask=0), we actually use a scalar loop.

I'm curious if anyone has data indicating that a jump table is faster, enough to make a difference?

> I'm curious if anyone has data indicating that a jump table is faster, enough to make a difference?

Anything that touches the branch predictors on these modern, crazy CPUs, is going to be too complicated to really understand from a performance perspective!

I'm pretty sure that jump tables / if statements all touch the branch predictor. Things will be high performance if the branch is consistently predicted correctly, but good luck figuring that out without just running the darn program on a CPU.

Between a jump table and a scalar loop, the loop will screw with the branch predictor more.

A jump table has the potential to be faster by doing SIMD, at the cost of taking more icache.

> It’s the “load 5 bytes” and “store 5 bytes” that I don’t have a good solution for

Strings in C are null terminated. You can avoiding loading exactly 5 bytes. For a string of length 4 load 4 bytes, for a string of length 5 load 6 bytes, you’ll read 5 characters of the payload + the terminating '\0'.

If you code C++, the standard library was fortunately designed with C interop in mind, strings form the standard library have c_str() method.

About how to do that efficiently, a good way is a jump table. Not all compilers are smart enough to compile switch into a table, but many of them are. Modern GCC usually does the right thing, take a look: https://godbolt.org/z/sK7jcoooa (untested)

Partial stores are pretty similar. Compare the vector of bytes for b == `\0`, use _mm_movemask_epi8(), then _tzcnt_u32() or _BitScanForward() to find the length, then in the switch use various extract instructions: _mm_cvtsi128_si32, _mm_cvtsi128_si64, _mm_extract_epi16, and/or _mm_extract_epi32.

That is possible in better SIMD instruction sets, like Intel/AMD AVX-512 or Armv9 SVE2.

In such instruction sets not only load and store but also most of the other instructions can operate on a subset of bytes/words/dwords/qwords of the registers, by using bit masks to specify which parts of a vector register are used in an operation.

It is possible to specify whether the unused parts should retain their previous value or they should be set to zero.

Moreover, for load and store, it is possible to load or store some number of bytes or of larger data from non-sequential locations, using the so-called gather and scatter instructions.

Doesn't seem to be for SSE & AVX at least (only 32-bit and 64-bit groups in AVX, and nothing for SSE). AVX-512 has _mm512_maskz_loadu_epi8, but not much has AVX-512.

It's a shame that there aren't guarantees on being able to overread some number of garbage bytes. (for a SIMD-heavy project, I've just went with a custom allocator that guarantees the ability to read past the end of allocations, and storing by either maskstore for 32/64-bit, and blending with what's already there for 8/16-bit)

> on today's systems

BIND still supports critical internet infrastructure on less capable hardware.

There's some uncovered ground between the processors having SIMD support and being able to use it portably from C. Also a compiler could compile this code to use SIMD instructions.

> modern SIMD instructions execute at one-per-clock-tick

Or even two, or four on apple arm, plus load and store which can be done in parallel.

Yeah, good point. SIMD is also superscalar on most systems.

For x86, Intel can do 3x AVX512 instructions per clock tick as long as each instruction is simple enough (add, AND, OR, NOT, XOR, maybe even multiply if you're not counting the latency issue)

Only port 5 and port 0/1 can do avx512 instructions on skylake/icelake, so I don't think you can get better throughput than 0.5 on current parts. Unless you count load & store as well, like I mentioned.

(Unless you count an avx512-specific instruction operating on a 32- or 16-byte vector as an 'avx512 instruction'.)

Skylake is 7 years old

And icelake is 3 years old. If you have a newer avx512-supported chip which can do more than two 512-bit alu ops per cycle, I would love to take a look at it.

throughput and latency did improve with alder lake (...), but i see your point.

Google and wikipedia tell me that SWAR is: SIMD within a register, also known by the name "packed SIMD".

Linux-capable RISC-V cores often have 64-bit architecture and no SIMD/vector processing capabilities.

Reply on news.ycombinator.com