4 ms·

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

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.

sedatk 4y ago
"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.)"
- dragontamer 4y ago
  DNS labels like "ycombina" (tor) you mean? :-)
  - fanf2 4y ago
    Two out of three ain’t bad :-) news.ycombinator.com
  - cratermoon 4y ago
    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.
fanf2 4y ago
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.
- dragontamer 4y ago
  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.
  - fanf2 4y ago
    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.
    - dragontamer 4y ago
      > 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.
moonchild 4y ago
> 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.
- dragontamer 4y ago
  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)
  - moonchild 4y ago
    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.
    - moonchild 4y ago
      (Unless you count an avx512-specific instruction operating on a 32- or 16-byte vector as an 'avx512 instruction'.)
    - mhh__ 4y ago
      Skylake is 7 years old
      - moonchild 4y ago
        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.
        mhh__ 4y ago
        throughput and latency did improve with alder lake (...), but i see your point.
dietrichepp 4y ago
Naive version to explore autovectorization: https://gcc.godbolt.org/z/bcefvznG3 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 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 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.
- dragontamer 4y ago
  > 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.
  - dietrichepp 4y ago
    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.)
  - zen_1 4y ago
    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.
nimish 4y ago
> 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
cratermoon 4y ago
> on today's systems BIND still supports critical internet infrastructure on less capable hardware.
Marat_Dukhan 4y ago
Linux-capable RISC-V cores often have 64-bit architecture and no SIMD/vector processing capabilities.
fulafel 4y ago
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.
adrian_b 4y ago
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.
kristianp 4y ago
Google and wikipedia tell me that SWAR is: SIMD within a register, also known by the name "packed SIMD".

sedatk 4y ago

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

dragontamer 4y ago
DNS labels like "ycombina" (tor) you mean? :-)
- fanf2 4y ago
  Two out of three ain’t bad :-) news.ycombinator.com
- cratermoon 4y ago
  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.

fanf2 4y ago

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.

dragontamer 4y ago
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.
- fanf2 4y ago
  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.
  - dragontamer 4y ago
    > 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.

moonchild 4y ago

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

dragontamer 4y ago
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)
- moonchild 4y ago
  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.
  - moonchild 4y ago
    (Unless you count an avx512-specific instruction operating on a 32- or 16-byte vector as an 'avx512 instruction'.)
  - mhh__ 4y ago
    Skylake is 7 years old
    - moonchild 4y ago
      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.
      - mhh__ 4y ago
        throughput and latency did improve with alder lake (...), but i see your point.

dietrichepp 4y ago

Naive version to explore autovectorization: https://gcc.godbolt.org/z/bcefvznG3 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 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 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.

dragontamer 4y ago
> 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.
- dietrichepp 4y ago
  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.)
- zen_1 4y ago
  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.

nimish 4y ago

> 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

cratermoon 4y ago

> on today's systems BIND still supports critical internet infrastructure on less capable hardware.

Marat_Dukhan 4y ago

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

fulafel 4y ago

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.

adrian_b 4y ago

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.

kristianp 4y ago

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