Very interesting! I tried reproducing it, but unfortunately:
$ sneller -j -S "SELECT COUNT(Line) FROM 'en.json' WHERE Line ~ 'Sherlock [A-Z]\\w+'"
expr.Unescape: unexpected backslash escape of 'w' (0x77)
$ sneller -j -S "SELECT COUNT(Line) FROM 'en.json' WHERE Line ~ 'Sherlock [A-Z][a-z]+'"
CPU doesn't support AVX-512
And that is the primary reason why ripgrep doesn't bother with AVX-512. Not because of some lack of skill as this blog suggests:
> Additionally, ripgrep uses AVX2 and does not take advantage of AVX-512 instruction sets, but this can be forgiven given the specialized skills required for handcrafting for SkylakeX and Icelake/Zen4 processors.
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. At least, it's not obvious to me that it's worth doing. And certainly, the skill argument isn't entirely wrong. I'd have to invest developer time to make it work.
I think there are two other things worth highlighting from this blog.
First is that sneller seems to do quite well with compressed data. This is definitely not ripgrep's strong suit. When you use ripgrep's -z/--search-zip flag, all it's doing is shelling out to your gzip/xz/whatever executable to do the decompression work, which is then streamed into ripgrep for searching. So if your search speed tanks when using -z/--search-zip, it's likely because your decompression tools are slow, not because of ripgrep. But it's a fair comparison from sneller's perspective, because it seems to integrate the two.
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. 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. :-)
And finally some corrections:
> However, when using a single thread, ripgrep appears to be slightly faster.
Not just slightly faster, over 2x faster!
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?
> The reason for this is that ripgrep uses the Boyer-Moore string search algorithm, which is a pattern matching algorithm that is often used for searching for substrings within larger strings. It is particularly efficient when the pattern being searched for is relatively long and the alphabet of characters being searched over is relatively small. Sneller does not use this substring search algorithm and as a result is slower than ripgrep with substrings. However, when long substrings are not present, Sneller outperforms ripgrep.
ripgrep has never used Boyer-Moore. (Okay, some years ago, ripgrep could use Boyer-Moore in certain niche cases. But that hasn't been the case for a while and it was never the thing most commonly used). What ripgrep uses today is succinctly described here: htt...
> 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.
> but considering that regex handling is a common task, it would be a missed opportunity not to consider AVX-512.
Just to be really clear here, it's less about "not considering it" and more about "not prioritizing it." I don't have any telemetry on where ripgrep is running, but I would guess that 99% of its uses are on consumer hardware. And consumer hardware is heading in a direction that doesn't include AVX-512. That lowers the priority for using it, especially when AVX-2 is available nearly everywhere. And indeed, ripgrep uses AVX-2.
> 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?
I don't really have an approach. ripgrep's decompression support isn't really about performance or improving throughput. It's just about the user experience. It's about making it easier to search stuff without having to decompress it explicitly first. You have a `foo.txt.gz` on your system? Great, ripgrep can search it using the standard tools available to you.
The separate question of making that faster (`gzip -d` is usually not the fastest way to decompress gzipped data for example) is something I'd like to explore in the future.
The other separate question of how to integrate compression and searching such that the holistic result unlocks interesting use cases and potentially even makes the overall search faster is not a use case that ripgrep really cares about. The important thing with ripgrep is about being able to search existing compressed data using standard tools.
What I'm trying to say here is that Sneller has a much more specialized and interesting target audience than ripgrep. :-)
> Can you explain how you calculated that. In our calculation we accounted for the time needed to do the decompression.
I'm looking at `Regex1` in your table. ripgrep has a reported timing of 3.899s and Sneller with one thread has a reported timing of 10.024s.
> Could you give some of those questions?
I tried to include those scattered around in my original comment. Otherwise I don't know what was on my mind when I wrote that. It was a while ago.
> 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?
How are you getting 12 states for \pL?
DFAs with Unicode aware \w are about a couple orders of magnitude bigger than DFAs with an ASCII-only \w:
3 comments
[ 3.4 ms ] story [ 18.8 ms ] threadVery interesting! I tried reproducing it, but unfortunately:
And that is the primary reason why ripgrep doesn't bother with AVX-512. Not because of some lack of skill as this blog suggests:> Additionally, ripgrep uses AVX2 and does not take advantage of AVX-512 instruction sets, but this can be forgiven given the specialized skills required for handcrafting for SkylakeX and Icelake/Zen4 processors.
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. At least, it's not obvious to me that it's worth doing. And certainly, the skill argument isn't entirely wrong. I'd have to invest developer time to make it work.
I think there are two other things worth highlighting from this blog.
First is that sneller seems to do quite well with compressed data. This is definitely not ripgrep's strong suit. When you use ripgrep's -z/--search-zip flag, all it's doing is shelling out to your gzip/xz/whatever executable to do the decompression work, which is then streamed into ripgrep for searching. So if your search speed tanks when using -z/--search-zip, it's likely because your decompression tools are slow, not because of ripgrep. But it's a fair comparison from sneller's perspective, because it seems to integrate the two.
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. 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. :-)
And finally some corrections:
> However, when using a single thread, ripgrep appears to be slightly faster.
Not just slightly faster, over 2x faster!
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?
> The reason for this is that ripgrep uses the Boyer-Moore string search algorithm, which is a pattern matching algorithm that is often used for searching for substrings within larger strings. It is particularly efficient when the pattern being searched for is relatively long and the alphabet of characters being searched over is relatively small. Sneller does not use this substring search algorithm and as a result is slower than ripgrep with substrings. However, when long substrings are not present, Sneller outperforms ripgrep.
ripgrep has never used Boyer-Moore. (Okay, some years ago, ripgrep could use Boyer-Moore in certain niche cases. But that hasn't been the case for a while and it was never the thing most commonly used). What ripgrep uses today is succinctly described here: htt...
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 rege...
> but considering that regex handling is a common task, it would be a missed opportunity not to consider AVX-512.
Just to be really clear here, it's less about "not considering it" and more about "not prioritizing it." I don't have any telemetry on where ripgrep is running, but I would guess that 99% of its uses are on consumer hardware. And consumer hardware is heading in a direction that doesn't include AVX-512. That lowers the priority for using it, especially when AVX-2 is available nearly everywhere. And indeed, ripgrep uses AVX-2.
> 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?
I don't really have an approach. ripgrep's decompression support isn't really about performance or improving throughput. It's just about the user experience. It's about making it easier to search stuff without having to decompress it explicitly first. You have a `foo.txt.gz` on your system? Great, ripgrep can search it using the standard tools available to you.
The separate question of making that faster (`gzip -d` is usually not the fastest way to decompress gzipped data for example) is something I'd like to explore in the future.
The other separate question of how to integrate compression and searching such that the holistic result unlocks interesting use cases and potentially even makes the overall search faster is not a use case that ripgrep really cares about. The important thing with ripgrep is about being able to search existing compressed data using standard tools.
What I'm trying to say here is that Sneller has a much more specialized and interesting target audience than ripgrep. :-)
> Can you explain how you calculated that. In our calculation we accounted for the time needed to do the decompression.
I'm looking at `Regex1` in your table. ripgrep has a reported timing of 3.899s and Sneller with one thread has a reported timing of 10.024s.
> Could you give some of those questions?
I tried to include those scattered around in my original comment. Otherwise I don't know what was on my mind when I wrote that. It was a while ago.
> 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?
How are you getting 12 states for \pL?
DFAs with Unicode aware \w are about a couple orders of magnitude bigger than DFAs with an ASCII-only \w:
That's with DFA minimization. Also, '\w' has 311 states while '(?-u)\w' has 5 states.I don't have a precise definition of enormous or impractical. Does it matter? I suppose one obvious...