Sneller Regex vs Ripgrep

Thank you for taking the time to review this.

> Namely, I tried running sneller on my CPU, which is a pretty recent i9-12900K, and not even it supports AVX-512. That's because Intel has been dropping support for AVX-512 from its more recent consumer grade CPUs. ripgrep is running far more frequently on consumer grade CPUs, so supporting AVX-512 is probably not particularly advantageous.

This regex engine is designed to leverage two powerful instructions that are available in Icelake/Zen 4 architectures. It is annoying that despite having recent hardware, many do not have these instructions. We are not suggesting that all software should necessarily use AVX-512 vectorization, but considering that regex handling is a common task, it would be a missed opportunity not to consider AVX-512.

> I think there are two other things worth highlighting from this blog. > > First is that sneller seems to do quite well with compressed data.

It is unfortunate that the sneller tools do not offer a meaningful way to disable compression, which complicates this comparison. Decompression can slow down performance on smaller files; However, on larger workloads, decompression can actually improve speed (when considering disk and networking factors). We never considered you would want to disable compression.

While ripgrep delegates compression to other tools, I'm curious about your approach to decompression if you really needed it. I'm interested in exploring ways in which people do use ripgrep with compression. Do you use transparent disk compression?

> Second is the issue of multi-threaded search. In ripgrep, the fundamental unit of work is "search a file." ripgrep has no support for more granular parallelism. That is, if you give it one file, it's limited to doing a single threaded search. ripgrep could do more granular parallelism, but it hasn't been obviously worth it to me. If most searches are on a directory tree, then parallelizing at the level of each file is almost certainly good enough. Making ripgrep's parallelism more fine grained is a fair bit of work too, and there would be a lot of fiddly stuff to get right.

The single-threadedness makes perfect sense: if you can avoid it, because you don't need it, don't use it. Debugging that stuff is no fun.

> If I could run sneller easily, I'd probably try to see how it does in a more varied workload than what is presented in this blog. :-)

If you do see an opportunity to run sneller, please let us know. But do not expect that much variation in speeds. Due to the branchlessness nature of the code, large sets of regexes have approximately the same performance. If two very different regexes compile to a DFA that can be run with the same branchless implementation, only the length of matching data makes a minor impact on speed.

> And finally some corrections: > > However, when using a single thread, ripgrep appears to be slightly faster. > Not just slightly faster, over 2x faster!

Can you explain how you calculated that. In our calculation we accounted for the time needed to do the decompression.

> The single threaded results for Regex2 and Regex3 for Sneller are quite nice! I'd be interested in hearing more about what you're doing in the Regex2 case, since Sneller and ripgrep are about on par with the Regex3 case. Maybe a fail fast optimization?

That's a good question. We chose this example because it emphasizes a crucial memory access pattern that we are specifically interested in. We gather 16x 4bytes with an expensive `vpgatherd`, but the high cost is offset by the regex engine's ability to determine, based on the first 4 characters, that a lane can be made inactive, resulting in no match. This feature is not exactly an optimization on its own; rather, it is an inherent aspect of how this setup with 16 lanes operates. Ripgrep loads 32bytes and concludes that a characters is not present and moves on.

For regex2, if the needle you are looking for is scarce, ripgrep loads number of lines N times 32 bytes, while sneller loads N times 4 bytes.

For regex3, both sneller and ripgrep need to load all bytes. They both have to scan until the end of the data, which leads to comparable speeds.

> I think I would also contest the claim that "long substrings" are the key here. ripgrep is plenty fast with short substrings too. You're correct that if you have no literals then ripgrep will get slower because it has to fall back to the regex engine. But I'd like to see more robust benchmarks there. Your Regex2 and Regex3 benchmarks raise more questions than it answers. :-)

Could you give some of those questions?

> So this is talking about the DFA graph for the regex `Sherlock [A-Z]\w+`. It's important to point out that, in ripgrep, `\w` is Unicode aware by default. Which makes it absolutely enormous. So I think the state graph you linked is probably only for the ASCII version of that regex.

That is unfortunate, because in Go `\w` is the Perl word character class `[0-9A-Za-z_]` (https://pkg.go.dev/regexp/syntax) and not what you use, which I assume is `\p{L}`. The state of the DFA with `\p{L}` has 12 states and 1291 edges, compared to 12 states and 132 edges with `\w`. When would you call a DFA enormous or impractical?

I ran

`sneller -j -S "SELECT COUNT(Line) FROM 'c:/en.iguana.zion' WHERE Line ~ 'Sherlock [A-Z]\\p{L}+'"`

which gave:

`{"count": 7880} 10.7GiB/s (scanned 14078181376 B (13.11 GB) in 1.2835706s)`

But this specific regex with an ASCII substring is handled differently, it uses an optimization similarly to ripgrep with a substring search. A fair question would be how Sneller behaves when it needs to handle a DFA with 12 states and 1291 edges.

Additionally, the results are not the same: the number of matches is not equal to 7882. How could I make `\w` conform to other regex implementations in ripgrep?

I will need to study this more thoroughly, and I will update the blog post accordingly.

> So I would also try to poke it to see what happens when handed a particularly a not-so-small regex. (Building a DFA can take quite some time.)

Fair question how regex compilers handle nefarious regexes. Go does not handle NFA with more than 1000 states, and, as you observed, we added some more restrictions when processing the NFA. It can be an interesting academic exercise to find monstrous regexes, but we haven't encountered useful regexes that hit these limits. But I guess you know some...