Faster substring search with SIMD in Zig

Good write-up. This is a very popular approach to substring search! It is still worst case `O(m*n)` though. Do you have a fallback implementation like the `memchr` crate has to guarantee `O(m+n)`?

I'll also push back on some bits in the end:

    > But if it’s so much better, then why haven’t I made a pull request to
    > change std.mem.indexOf to use SIMD? Well, the reason is that
    >
    > std.mem.indexOf is generic over element size, and having a size
    > larger than u8 makes the algorithm much slower
    >
    > The algorithm used in stdmem.indexOf is cross-platform, while the
    > SIMD code wouldn’t be. (not all platforms have SIMD registers at all,
    > Arm has only 128-bit)

Does Zig not have a way to specialize this for sequences of unsigned 8-bit integers? If not, and you're thereforce force to used a more generic algorithm, that seems pretty unfortunate.

    > Substring searching is rarely the bottleneck in programs,
    > especially ones written in a fast language like Zig. That’s why
    > I don’t personally think it would be worth it to add it to the
    > standard library.

Oh I'm not sure I buy this at all! Substring search is a primitive operation and easily can be a bottleneck. There's a reason why widely used substring search implementations tend to be highly optimized.

  if (comptime T == u8) {
    // code
  }

I like that more people are getting involved with SIMD, and there have been several posts lately on both memmem-like and memcpy-like operations implemented in SIMD in different programming languages.

In most cases, though, these still focus on AVX/NEON instructions from over 10 years ago, rather than newer and more powerful AVX-512 variations, SVE & SVE2, or RVV.

These newer ISAs can noticeably change how one would implement a state-of-the-art substring search or copy/move operation. In my projects, such as StringZilla, I often use mask K registers (https://github.com/ashvardanian/StringZilla/blob/2f4b1386ca2...) and an input-dependent mix of temporal and non-temporal loads and stores (https://github.com/ashvardanian/StringZilla/blob/2f4b1386ca2...).

In typical cases, the difference between the suggested SIMD kernels and the state-of-the-art can be as significant as 50% in throughput. As SIMD becomes more widespread, it would be beneficial to focus more on delivering software and bundling binaries, rather than just the kernels.

I really wish Zig decided to add SIMD intrisics. There are many SIMD algorithms that can be done, but you have to switch back to C for those, because they depend on operations outside of what LLVM provides for vectors.

What about the worst case? I.e. something like searching for 1000 'a's in a long string of 'a's interspersed with 'b's every 500-1000 steps? Seems accidentally quadradic unfortunately in the absence of some KMP-like fallback

Nice article!

Also, this might be a stupid question (I'm a Zig newbie) but… instead of calling std.mem.eql() in the while loop to look at each potential match individually, couldn't you repeat the same trick as before? That is, use SIMD to search for the second and second-to-last character of the needle, then third and third-to-last, and so on, and finally take a bitwise AND of all the resulting bit masks? This way, one would avoid looking at each potential match one by one, and instead look at all of them at the same time.

Even if that doesn't work for some reason and you still need to loop over all potential matches individually, couldn't you use SIMD inside the while loop to replace std.mem.eql and thereby speed up string comparison? My understanding was that std.mem.eql loops over bytes one by one and compares them?

Every language tries to implement the best in class memory set/search primitives. Maybe we should move them to something called libos, where they will be implemented by every host OS? Then, OS manufacturers can supply libos.so/libos.dll/libos.dylib as part of the official OS distributions.

If the wheels get reinvented again and again, it means that they should be readily available.

>The difference between 4μs vs 1μs is extremely small, but it’s slightly faster nonetheless.

Put that in a loop and its an enormous speed-up.

Nice!

But, does that work with non-ascii characters? (aka Unicode).

    $ printf "t\\u00E9st" > /tmp/a 
    $ xxd /tmp/a
    00000000: 74c3 a973 74                             t..st
    $ cat /tmp/a
    tést

    $ printf "te\\u0301st" > /tmp/b 
    $ xxd /tmp/b
    00000000: 7465 cc81 7374                           te..st
    $ cat /tmp/b
    tést

    $ printf "t\\u00E9st" | rg -f - /tmp/a
    1:tést
    $ printf "t\\u00E9st" | rg -f - /tmp/b
    # ed: no result

    $ printf "t\\u00E9st" | uconv -x any-nfc | xxd
    00000000: 74c3 a973 74                             t..st
    $ printf "te\\u0301st" | uconv -x any-nfc | xxd
    00000000: 74c3 a973 74                             t..st