3 ms·

It was a lot of work to get these simd implementations done. If anybody is interested in integrating them into other libc implementations, please let me know.

It was a lot of work to get these simd implementations done. If anybody is interested in integrating them into other libc implementations, please let me know. I can help you. I'm also looking for anybody willing to sponsor a port of this work to other architectures or x86-64-v3/v4 (i.e. AVX2/AVX-512).

janwas 3y ago
Great to see SIMD used in string algorithms :) For porting, have you considered using github.com/google/highway? This allows you to write the code once using 'portable' intrinsics, and run on >20 instruction sets. Disclosure: I am the main author of this library, happy to discuss.
- clausecker 3y ago
  Generic libraries are not very useful as the code makes very atypical use of SIMD instructions. For example: * about half the code deals with reading the beginning and end of strings by doing elaborate, careful unaligned loads and masking * the other half is straightforward byte-wise comparison following by pmovmskb to inspect where matches were found. This is very performance sensitive and different strategies have to be used on different platforms. For example, NEON doesn't have an instruction like that, so you need to work around the shortcoming in various painful ways. * some functions currently use the x86-only pcmpistrm instruction and would need a complete redesign for other platforms I have so far not had any good experience with SIMD libraries for this kind of code. Even C++ + instrinsics delivers poor performance in this sort of setup. For example, when we ported our UTF-8 <-> UTF-16 kernels (AVX-512) from assembly to C++ with intrinsics, performance dropped by 25%. Also there are two other important constraints: * we're working far outside the rules of the C language, overreading buffers here and there. It is unknown if the C compiler would miscompile our code. * similarly, we don't want any C++ in libc, so using a C++-based library is out.
  - janwas 3y ago
    Ah, Highway is C++ so that won't work for you then. And indeed CMPISTR is quite nonportable. I'm curious whether you are getting good performance from CMPISTR relative to AVX2 or even AVX-512, for those who have it? Wider vectors might reduce the advantage of specialized instructions. I'm also curious if you looked into the difference of asm vs intrinsics, where the compiler was going wrong, and/or how long ago that was? As to careful loads and movmskb, Highway does have LoadN and Find(Known)FirstTrue which is still quite decent on Arm. You might find it useful if/when porting?
    - clausecker 3y ago
      > Ah, Highway is C++ so that won't work for you then. And indeed CMPISTR is quite nonportable. I'm curious whether you are getting good performance from CMPISTR relative to AVX2 or even AVX-512, for those who have it? Wider vectors might reduce the advantage of specialized instructions. The main advantage of pcmpistrm is that it doesn't need preprocessing. You can beat its raw speed just fine, e.g. using the Muła/Langdale algorithm (http://0x80.pl/articles/simd-byte-lookup.html http://0x80.pl/articles/simd-byte-lookup.html), but that algorithm requires costly preprocessing of the set to be matched. For string functions, input strings are usually very short and algorithms have to be optimised for that case; the steady state of a tight main loop is rarely reached and not the primary goal of optimisation. So as a result, any preprocessing before we can get started walking down the string gets really expensive. In fact, the benchmarks I wrote and whose results the Phoronox page has shamelessly ripped off use strings of just 64 bytes on average, which I believe is more representative for real-world cases than the very long strings other implementations seemed to have been optimised for. This is also the reason why I ended up using just SSE: not only do the instructions provided by SSE2 largely suffice for the job, but also is the advantage of longer vectors severely reduced when your input is unlikely to be longer than one or two of them. Plus for AVX and later, we have to do a VZEROUPPER before return (to ensure other SSE code in the user's program is not impacted), further reducing performance for such short-running string functions. > I'm also curious if you looked into the difference of asm vs intrinsics, where the compiler was going wrong, and/or how long ago that was? That was last year. Mainly, the code in question does unusually complex things with mask registers, constantly shuffling data back and forth between general purpose and mask registers. Gcc and clang do a really poor job deciding which operations to do in GPRs and which to do in mask registers. They also fail hard at hoisting constant loads out of hot loops. Finally, register allocation fails to find a solution that keeps everything in registers (which the asm code does just fine with 2 GPRs to spare), instead spilling to the stack. > As to careful loads and movmskb, Highway does have LoadN and Find(Known)FirstTrue which is still quite decent on Arm. You might find it useful if/when porting? Maybe, but keep in mind that strings are nul-terminated. So each loop trying to find something in a string must at the same time look for the nul terminator and be careful not to cross page boundaries while doing so. These aspects cannot be separated unless you want to sacrifice performance by reading the string twice at prohibitive cost. And we don't actually want to do masked loads. Instead, I load with junk before the beginning of the string and mask this junk out off the bitmask when testing if the mask has the desired contents. This moves the µops for computing the mask down the dependency chain to after comparison, improving ILP. I recommend you try and implement some of these functions yourself. strchr() and strcpy() are good starting points. You can use my benchmark framework (https://github.com/clausecker/strperf https://github.com/clausecker/strperf) to check the performance. I'm interested in seeing what you come up with.

janwas 3y ago

Great to see SIMD used in string algorithms :) For porting, have you considered using github.com/google/highway? This allows you to write the code once using 'portable' intrinsics, and run on >20 instruction sets. Disclosure: I am the main author of this library, happy to discuss.

clausecker 3y ago
Generic libraries are not very useful as the code makes very atypical use of SIMD instructions. For example: * about half the code deals with reading the beginning and end of strings by doing elaborate, careful unaligned loads and masking * the other half is straightforward byte-wise comparison following by pmovmskb to inspect where matches were found. This is very performance sensitive and different strategies have to be used on different platforms. For example, NEON doesn't have an instruction like that, so you need to work around the shortcoming in various painful ways. * some functions currently use the x86-only pcmpistrm instruction and would need a complete redesign for other platforms I have so far not had any good experience with SIMD libraries for this kind of code. Even C++ + instrinsics delivers poor performance in this sort of setup. For example, when we ported our UTF-8 <-> UTF-16 kernels (AVX-512) from assembly to C++ with intrinsics, performance dropped by 25%. Also there are two other important constraints: * we're working far outside the rules of the C language, overreading buffers here and there. It is unknown if the C compiler would miscompile our code. * similarly, we don't want any C++ in libc, so using a C++-based library is out.
- janwas 3y ago
  Ah, Highway is C++ so that won't work for you then. And indeed CMPISTR is quite nonportable. I'm curious whether you are getting good performance from CMPISTR relative to AVX2 or even AVX-512, for those who have it? Wider vectors might reduce the advantage of specialized instructions. I'm also curious if you looked into the difference of asm vs intrinsics, where the compiler was going wrong, and/or how long ago that was? As to careful loads and movmskb, Highway does have LoadN and Find(Known)FirstTrue which is still quite decent on Arm. You might find it useful if/when porting?
  - clausecker 3y ago
    > Ah, Highway is C++ so that won't work for you then. And indeed CMPISTR is quite nonportable. I'm curious whether you are getting good performance from CMPISTR relative to AVX2 or even AVX-512, for those who have it? Wider vectors might reduce the advantage of specialized instructions. The main advantage of pcmpistrm is that it doesn't need preprocessing. You can beat its raw speed just fine, e.g. using the Muła/Langdale algorithm (http://0x80.pl/articles/simd-byte-lookup.html http://0x80.pl/articles/simd-byte-lookup.html), but that algorithm requires costly preprocessing of the set to be matched. For string functions, input strings are usually very short and algorithms have to be optimised for that case; the steady state of a tight main loop is rarely reached and not the primary goal of optimisation. So as a result, any preprocessing before we can get started walking down the string gets really expensive. In fact, the benchmarks I wrote and whose results the Phoronox page has shamelessly ripped off use strings of just 64 bytes on average, which I believe is more representative for real-world cases than the very long strings other implementations seemed to have been optimised for. This is also the reason why I ended up using just SSE: not only do the instructions provided by SSE2 largely suffice for the job, but also is the advantage of longer vectors severely reduced when your input is unlikely to be longer than one or two of them. Plus for AVX and later, we have to do a VZEROUPPER before return (to ensure other SSE code in the user's program is not impacted), further reducing performance for such short-running string functions. > I'm also curious if you looked into the difference of asm vs intrinsics, where the compiler was going wrong, and/or how long ago that was? That was last year. Mainly, the code in question does unusually complex things with mask registers, constantly shuffling data back and forth between general purpose and mask registers. Gcc and clang do a really poor job deciding which operations to do in GPRs and which to do in mask registers. They also fail hard at hoisting constant loads out of hot loops. Finally, register allocation fails to find a solution that keeps everything in registers (which the asm code does just fine with 2 GPRs to spare), instead spilling to the stack. > As to careful loads and movmskb, Highway does have LoadN and Find(Known)FirstTrue which is still quite decent on Arm. You might find it useful if/when porting? Maybe, but keep in mind that strings are nul-terminated. So each loop trying to find something in a string must at the same time look for the nul terminator and be careful not to cross page boundaries while doing so. These aspects cannot be separated unless you want to sacrifice performance by reading the string twice at prohibitive cost. And we don't actually want to do masked loads. Instead, I load with junk before the beginning of the string and mask this junk out off the bitmask when testing if the mask has the desired contents. This moves the µops for computing the mask down the dependency chain to after comparison, improving ILP. I recommend you try and implement some of these functions yourself. strchr() and strcpy() are good starting points. You can use my benchmark framework (https://github.com/clausecker/strperf https://github.com/clausecker/strperf) to check the performance. I'm interested in seeing what you come up with.