4 ms·

The reason why the single-lookup version works, the bytes being searched for have unique low 4 bits. So the lookup generates the vector with bytes equal to low_

The reason why the single-lookup version works, the bytes being searched for have unique low 4 bits. So the lookup generates the vector with bytes equal to low_nibble_mask[ source[i] & 0x0F ]. The table contains the bytes being searched for, in the elements which correspond to the low 4 bits of these bytes. The next instruction compares bytes in the source vector for equality with the results of that lookup. So, for each byte in the source vector, the first 3 instructions are computing the following expression, in parallel for each of the 16 bytes in the vector: bool eq = ( b == low_nibble_mask[ b & 0x0F ] ); The rest is trivial, identifying index of the first byte which compared true. And one more thing. > If you have an old SSE2 PC, only the simple SIMD approach is available That PSHUFB table lookup SSE instruction was introduced in SSSE3 extension. Now in 2024 it’s hard to find an old SSE2 PC which doesn’t also support SSSE3. You gonna need things like Pentium D launched in 2005, or AMD K10 launched in 2007.

ilrwbwrkhv 2y ago
Do you still use c++ or have you moved to rust?
- Const-me 2y ago
  I mostly use C++ and C#, and I’m not a fan of Rust.
  - victor106 2y ago
    I love C#. > I’m not a fan of Rust. I wonder why? Care to elaborate?
    - neonsunset 2y ago
      A little more on topic, if you like SIMD and C#, dotnet/runtime now has an introductory guide to Vector128/256/512<T> API: https://github.com/dotnet/runtime/blob/main/docs/coding-guidelines/vectorization-guidelines.md https://github.com/dotnet/runtime/blob/main/docs/coding-guid... Now, the default syntax can still be a bit more wordy with byref arithmetics than ideal, but you can add a few extension methods to make it look it closer to Rust's pointer arithmetics: https://github.com/U8String/U8String/blob/main/Sources/U8String/CaseConverters/U8AsciiCaseConverter.cs#L153-L171 https://github.com/U8String/U8String/blob/main/Sources/U8Str... (unrelated note but .NET lowers this to vpternlogd if AVX512VL is available) You can find more examples of SIMD use in dotnet/runtime if that interests you: https://grep.app/search?q=Vector%28128%7C256%7C512%29%3C%5Cw%2B%3E&regexp=true&filter[lang][0]=C%23&filter[repo][0]=dotnet/runtime https://grep.app/search?q=Vector%28128%7C256%7C512%29%3C%5Cw... Many paths are vectorized: to/from hexadecimal byte conversion, unicode encoding/decoding, various hash algorithms, counting and searching for elements, chunking text, there's a BLAS library now too and more.
    - Const-me 2y ago
      > I wonder why? The whole point of Rust is memory safety and security, but I don’t care too much about either of them. I mostly work on offline desktop apps. When I do work on network exposed servers, I use C# which delivers even better safety and security for a reasonable performance overhead. In pursue of that memory safety, Rust sacrificed pretty much everything else. The language is incredibly hard to learn. The compiler is even slower than C++. It’s hard to do R&D in Rust because memory safety forces minor changes into large refactors. The recent push to async/await is controversial, to say the least. It’s impossible to implement any non-trivial data structures in safe Rust. In my line of work designing data structures is more important than writing executable code, because the gap between RAM bandwidth and processor performance have been growing for decades now. Also, interesting post and discussion: https://news.ycombinator.com/item?id=40172033 https://news.ycombinator.com/item?id=40172033
      - jltsiren 2y ago
        I found Rust easy to learn after ~25 years of C/C++. It was definitely easier than learning to use Python properly. Maybe it was because I was often writing multi-threaded shared-memory code in C++, and that forces you to think in a very Rust-like way. Rust makes it difficult to implement data structures that rely on pointers. But in practice, you often want to minimize the use of actual pointers, even in data structures that use pointers on an abstract level. Pointers are large, following them is slow, and they encourage making many small allocations, which has a large space overhead. And if you define the interface in terms of pointers, you can't easily switch to an implementation where you can't point directly to any individual item stored in the structure.
        Const-me 2y ago
        > Maybe it was because I was often writing multi-threaded shared-memory code in C++ I’ve been writing C/C++ for living for about 25 years, also often writing multi-threaded shared-memory code in C++. However, seems I worked on very different projects, because I think in very Rust-incompatible way. Here’s an example. Quite often I need to compute long arrays of numbers, and the problem is parallel, like multiplication of large matrices. A good way to do that is slicing the output into blocks, and computing different blocks on different CPU cores, using OpenMP or some other thread pool. Different CPU cores need concurrent write access to the same vector, this is illegal in Rust. > But in practice, you often want to minimize the use of actual pointers In practice I often want actual pointers because graphs and trees are everywhere in computing. Many of them mutable, like DOM tree of this web page we’re visiting. Pointer chasing is generally slow compared to arithmetic instructions, but much faster than hash maps which can be used to implement the same thing. A hash map lookup is chasing at least 1 pointer usually multiple (depends on the implementation), and before that spends time computing the hash. > they encourage making many small allocations Pointer and allocations are orthogonal. It’s possible to design pointer-based data structure like tree or graph where the nodes are owned by containers, as opposed to other nodes.
- akira2501 2y ago
  Rust. Never mentioned. Shoehorned into every conversation anyways.
  - IntelMiner 2y ago
    It's the "btw I use Arch" of programming
  - intelVISA 2y ago
    The usurper must challenge the King.
adrian_b 2y ago
Not only the Pentium D (2004) did not have SSSE3, but also the later CPUs until the Core Solo, which was launched at the beginning of 2006. SSSE3 (a.k.a. Merom New Instructions), including PSHUFB, has been introduced first in Core Duo (mid 2006). AMD has launched its first CPUs with SSSE3 only in 2011 (Bobcat & Bulldozer).
mananaysiempre 2y ago
As a side note, the article and the simdjson paper don’t mention that it’s also possible to do an arbitrary set of bytes < 128 in two lookups (or one lookup and one variable shift), by vectorizing !!(bitset[b >> 3] & oneshl[b & 7]), where bitset[i] has its jth bit set iff i*8+j is in the set, and oneshl[i] is 1<<i. (I don’t remember where I saw this first, unfortunately, a pull request to a Rust something or other.) If you’re on x86 and thus using PSHUFB for the lookup, making the first shift an arithmetic one will also see you reject bytes ≥ 128 automatically.
- anonymoushn 2y ago
  I don't really know how this algorithm works because it doesn't seem to consume the input at all, but some techniques are here: http://0x80.pl/articles/simd-byte-lookup.html http://0x80.pl/articles/simd-byte-lookup.html
paulmd 2y ago
> You gonna need things like Pentium D launched in 2005, or AMD K10 launched in 2007. finally, my moment to shine https://i.imgur.com/WxmKuG8.jpeg https://i.imgur.com/WxmKuG8.jpeg
- intelVISA 2y ago
  Had one of those, it was stupidly expensive for the (low) performance - put me off AMD forever...
  - adrian_b 2y ago
    Perhaps you are confusing Athlon 64 with Athlon XP. The image shows an Athlon 64. Even Athlon XP was initially fast, but then Intel, after switching to an improved 130 nm CMOS process, has succeeded to increase very fast the clock frequencies of Pentium 4, from the low 2.0 GHz until 3.06 GHz in 2002 and eventually 3.2 GHz in 2003. The clock frequency advantage became so large for Intel that Athlon XP was no longer competitive. On the other hand, Athlon 64 was in a completely other class, at least when using a 64-bit operating system. I had a couple of Athlon 64, a 2.4 GHz single-core and a 2.2 GHz dual-core. The 3.2 GHz Pentium 4 CPUs were no match for them. With a 3.2 GHz Pentium 4 I needed 2-3 days of non-stop work (24/24) for the compilation of a Linux distribution, while with Athlon 64 that was reduced to only a half day's work. Before the introduction of Core Duo in mid 2006, for a couple of years all the available Intel CPUs that competed with Athlon 64 were not only extremely slow, but they were also extremely loud, suggesting an airplane takeoff (because the Intel 90 nm process was a failure, with huge leakage; the Core Duo that made Intel the best again was made in an improved 65 nm process). The various variants of Athlon 64 became worse than what Intel offered only after mid 2006, though even much later there were many cases when they were cheap enough to provide better performance per dollar than Intel. The image shown by the other poster is of an Athlon 64 made in 2005, at a time when it was the best CPU that could be obtained from any vendor.
    - intelVISA 2y ago
      Maybe I misremember, but the CPU I used was an Athlon 64 FX-62 I think and was around the time the Core2Duo was coming out. I wasn't quite a 2003 adopter so the gains were probably lost on me by then. :')
stabbles 2y ago
I blogged about this when I stumbled up on it the first time: https://stoppels.ch/2022/11/30/io-is-no-longer-the-bottleneck-part-2.html https://stoppels.ch/2022/11/30/io-is-no-longer-the-bottlenec... "Trick 2: Creating masks efficiently". It's pretty neat.
- anonymoushn 2y ago
  Great post! There was a contest for counting frequencies also in 2022, you may enjoy reading some of the submissions: https://easyperf.net/blog/2022/05/28/Performance-analysis-and-tuning-contest-6 https://easyperf.net/blog/2022/05/28/Performance-analysis-an...
- Const-me 2y ago
  Nice post! A small tip, broadcasting from memory is often free. For lookup tables like that I typically define a global variable like that: static const __m128i g_lookup = _mm_setr_epi8( ... ); And then in the function, before the main loop, I use `_mm256_broadcastsi128_si256` to load + broadcast the 16-byte vector in 1 instruction.

ilrwbwrkhv 2y ago

Do you still use c++ or have you moved to rust?

Const-me 2y ago
I mostly use C++ and C#, and I’m not a fan of Rust.
- victor106 2y ago
  I love C#. > I’m not a fan of Rust. I wonder why? Care to elaborate?
  - neonsunset 2y ago
    A little more on topic, if you like SIMD and C#, dotnet/runtime now has an introductory guide to Vector128/256/512<T> API: https://github.com/dotnet/runtime/blob/main/docs/coding-guidelines/vectorization-guidelines.md https://github.com/dotnet/runtime/blob/main/docs/coding-guid... Now, the default syntax can still be a bit more wordy with byref arithmetics than ideal, but you can add a few extension methods to make it look it closer to Rust's pointer arithmetics: https://github.com/U8String/U8String/blob/main/Sources/U8String/CaseConverters/U8AsciiCaseConverter.cs#L153-L171 https://github.com/U8String/U8String/blob/main/Sources/U8Str... (unrelated note but .NET lowers this to vpternlogd if AVX512VL is available) You can find more examples of SIMD use in dotnet/runtime if that interests you: https://grep.app/search?q=Vector%28128%7C256%7C512%29%3C%5Cw%2B%3E&regexp=true&filter[lang][0]=C%23&filter[repo][0]=dotnet/runtime https://grep.app/search?q=Vector%28128%7C256%7C512%29%3C%5Cw... Many paths are vectorized: to/from hexadecimal byte conversion, unicode encoding/decoding, various hash algorithms, counting and searching for elements, chunking text, there's a BLAS library now too and more.
  - Const-me 2y ago
    > I wonder why? The whole point of Rust is memory safety and security, but I don’t care too much about either of them. I mostly work on offline desktop apps. When I do work on network exposed servers, I use C# which delivers even better safety and security for a reasonable performance overhead. In pursue of that memory safety, Rust sacrificed pretty much everything else. The language is incredibly hard to learn. The compiler is even slower than C++. It’s hard to do R&D in Rust because memory safety forces minor changes into large refactors. The recent push to async/await is controversial, to say the least. It’s impossible to implement any non-trivial data structures in safe Rust. In my line of work designing data structures is more important than writing executable code, because the gap between RAM bandwidth and processor performance have been growing for decades now. Also, interesting post and discussion: https://news.ycombinator.com/item?id=40172033 https://news.ycombinator.com/item?id=40172033
    - jltsiren 2y ago
      I found Rust easy to learn after ~25 years of C/C++. It was definitely easier than learning to use Python properly. Maybe it was because I was often writing multi-threaded shared-memory code in C++, and that forces you to think in a very Rust-like way. Rust makes it difficult to implement data structures that rely on pointers. But in practice, you often want to minimize the use of actual pointers, even in data structures that use pointers on an abstract level. Pointers are large, following them is slow, and they encourage making many small allocations, which has a large space overhead. And if you define the interface in terms of pointers, you can't easily switch to an implementation where you can't point directly to any individual item stored in the structure.
      - Const-me 2y ago
        > Maybe it was because I was often writing multi-threaded shared-memory code in C++ I’ve been writing C/C++ for living for about 25 years, also often writing multi-threaded shared-memory code in C++. However, seems I worked on very different projects, because I think in very Rust-incompatible way. Here’s an example. Quite often I need to compute long arrays of numbers, and the problem is parallel, like multiplication of large matrices. A good way to do that is slicing the output into blocks, and computing different blocks on different CPU cores, using OpenMP or some other thread pool. Different CPU cores need concurrent write access to the same vector, this is illegal in Rust. > But in practice, you often want to minimize the use of actual pointers In practice I often want actual pointers because graphs and trees are everywhere in computing. Many of them mutable, like DOM tree of this web page we’re visiting. Pointer chasing is generally slow compared to arithmetic instructions, but much faster than hash maps which can be used to implement the same thing. A hash map lookup is chasing at least 1 pointer usually multiple (depends on the implementation), and before that spends time computing the hash. > they encourage making many small allocations Pointer and allocations are orthogonal. It’s possible to design pointer-based data structure like tree or graph where the nodes are owned by containers, as opposed to other nodes.
akira2501 2y ago
Rust. Never mentioned. Shoehorned into every conversation anyways.
- IntelMiner 2y ago
  It's the "btw I use Arch" of programming
- intelVISA 2y ago
  The usurper must challenge the King.

adrian_b 2y ago

Not only the Pentium D (2004) did not have SSSE3, but also the later CPUs until the Core Solo, which was launched at the beginning of 2006. SSSE3 (a.k.a. Merom New Instructions), including PSHUFB, has been introduced first in Core Duo (mid 2006). AMD has launched its first CPUs with SSSE3 only in 2011 (Bobcat & Bulldozer).

mananaysiempre 2y ago

As a side note, the article and the simdjson paper don’t mention that it’s also possible to do an arbitrary set of bytes < 128 in two lookups (or one lookup and one variable shift), by vectorizing !!(bitset[b >> 3] & oneshl[b & 7]), where bitset[i] has its jth bit set iff i*8+j is in the set, and oneshl[i] is 1<<i. (I don’t remember where I saw this first, unfortunately, a pull request to a Rust something or other.) If you’re on x86 and thus using PSHUFB for the lookup, making the first shift an arithmetic one will also see you reject bytes ≥ 128 automatically.

anonymoushn 2y ago
I don't really know how this algorithm works because it doesn't seem to consume the input at all, but some techniques are here: http://0x80.pl/articles/simd-byte-lookup.html http://0x80.pl/articles/simd-byte-lookup.html

paulmd 2y ago

> You gonna need things like Pentium D launched in 2005, or AMD K10 launched in 2007. finally, my moment to shine https://i.imgur.com/WxmKuG8.jpeg https://i.imgur.com/WxmKuG8.jpeg

intelVISA 2y ago
Had one of those, it was stupidly expensive for the (low) performance - put me off AMD forever...
- adrian_b 2y ago
  Perhaps you are confusing Athlon 64 with Athlon XP. The image shows an Athlon 64. Even Athlon XP was initially fast, but then Intel, after switching to an improved 130 nm CMOS process, has succeeded to increase very fast the clock frequencies of Pentium 4, from the low 2.0 GHz until 3.06 GHz in 2002 and eventually 3.2 GHz in 2003. The clock frequency advantage became so large for Intel that Athlon XP was no longer competitive. On the other hand, Athlon 64 was in a completely other class, at least when using a 64-bit operating system. I had a couple of Athlon 64, a 2.4 GHz single-core and a 2.2 GHz dual-core. The 3.2 GHz Pentium 4 CPUs were no match for them. With a 3.2 GHz Pentium 4 I needed 2-3 days of non-stop work (24/24) for the compilation of a Linux distribution, while with Athlon 64 that was reduced to only a half day's work. Before the introduction of Core Duo in mid 2006, for a couple of years all the available Intel CPUs that competed with Athlon 64 were not only extremely slow, but they were also extremely loud, suggesting an airplane takeoff (because the Intel 90 nm process was a failure, with huge leakage; the Core Duo that made Intel the best again was made in an improved 65 nm process). The various variants of Athlon 64 became worse than what Intel offered only after mid 2006, though even much later there were many cases when they were cheap enough to provide better performance per dollar than Intel. The image shown by the other poster is of an Athlon 64 made in 2005, at a time when it was the best CPU that could be obtained from any vendor.
  - intelVISA 2y ago
    Maybe I misremember, but the CPU I used was an Athlon 64 FX-62 I think and was around the time the Core2Duo was coming out. I wasn't quite a 2003 adopter so the gains were probably lost on me by then. :')

stabbles 2y ago

I blogged about this when I stumbled up on it the first time: https://stoppels.ch/2022/11/30/io-is-no-longer-the-bottleneck-part-2.html https://stoppels.ch/2022/11/30/io-is-no-longer-the-bottlenec... "Trick 2: Creating masks efficiently". It's pretty neat.

anonymoushn 2y ago
Great post! There was a contest for counting frequencies also in 2022, you may enjoy reading some of the submissions: https://easyperf.net/blog/2022/05/28/Performance-analysis-and-tuning-contest-6 https://easyperf.net/blog/2022/05/28/Performance-analysis-an...
Const-me 2y ago
Nice post! A small tip, broadcasting from memory is often free. For lookup tables like that I typically define a global variable like that: static const __m128i g_lookup = _mm_setr_epi8( ... ); And then in the function, before the main loop, I use `_mm256_broadcastsi128_si256` to load + broadcast the 16-byte vector in 1 instruction.