5 ms·

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 loo

by 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.
    - dzaima 4y ago
      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.
      - dragontamer 4y ago
        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).
        janwas 4y ago
        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/generic_ops-inl.h#L90 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?
        dragontamer 4y ago
        > 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.
  - dragontamer 4y ago
    > 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.
    - fanf2 4y ago
      For loading the rag end of a string, the branchiness looks like while (len-- > 0) { /* load */ } or switch (len) { /* 8 cases */ } https://en.wikipedia.org/wiki/Duff%27s_device https://en.wikipedia.org/wiki/Duff%27s_device
    - nwallin 4y ago
      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.
  - Const-me 4y ago
    > 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 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.
dzaima 4y ago
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)
adrian_b 4y ago
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.

by fanf2 4y ago

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.
  - dzaima 4y ago
    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.
    - dragontamer 4y ago
      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).
      - janwas 4y ago
        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/generic_ops-inl.h#L90 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?
        dragontamer 4y ago
        > 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.
- dragontamer 4y ago
  > 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.
  - fanf2 4y ago
    For loading the rag end of a string, the branchiness looks like while (len-- > 0) { /* load */ } or switch (len) { /* 8 cases */ } https://en.wikipedia.org/wiki/Duff%27s_device https://en.wikipedia.org/wiki/Duff%27s_device
  - nwallin 4y ago
    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.
- Const-me 4y ago
  > 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 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.

dzaima 4y ago

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)

adrian_b 4y ago

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.