Nice work. But your story is incomplete if you don't include comparison with icgrep (parabix.costar.sfu.ca). Although icgrep is still an active research project, it is faster in many cases and has broader Unicode support (full Unicode level 1 of UTS #18, plus many level 2 features). For example, try the '\N{SMIL(E|ING)}' search that finds lines containing emoji characters with SMILE or SMILING in their Unicode name. icgrep also correctly applies Unicode character class intersection with expressions such as [\p{Greek}&&\p{Lu}], while ripgrep fails to meet UTS 18 level 1 requirements by interpreting '&&' as literal characters.
Nevertheless, we appreciate the challenge that ripgrep presents to our performance story. We definitely see some cases in which rg achieves better performance taking advantage of fixed strings somewhere in the pattern. We'll have to work on that... But for patterns based on Unicode classes (e.g., \p{Greek}, icgrep can be much faster, especially on large files. (We are only focused on big data applications -- icgrep has significant dynamic compilation overhead). It also does very well in cases involving alternations and ambiguity.
The icgrep performance story is based primarily on a new bitwise data parallel regular expression algorithm working off the Parabix transform representation of text. See our ICA3PP 2015 or PACT 2014 papers.
It might be fair to say that icgrep is not yet polished enough for inclusion in your study. I just added our first implementation of -r/-R flags last night and we certainly haven't yet handled .gitignore, etc. But if you want to understand the truth about regular expression performance, I think that the data point represented by icgrep (and its continuing development) needs to be included.
Benchmarking aside, I think the icgrep approach is very interesting.
The appeal of this sort of bit parallel stuff is that you don't get performance variability. It's all fun and games with literal optimizations until you pick the wrong literal - all you have to do is stuff the file in the down-thread benchmark with a huge pile of "Holmes Holmes Holmes Lestrade Lestrade Lestrade" etc and suddenly both rg and Hyperscan will look a lot dumber and icgrep will keep going at the same speed.
Unfortunately, we've never figured out a way to dispense with literal-based matching for the large scale cases that we work with. When someone gives you a dozen regexes - or 12,000 - bit parallel approaches go into the weeds (as do most regex-oriented techniques; DFAs explode and bit-parallel NFAs - regardless of organization - become ponderous).
Speaking as the leader of the Hyperscan project (https://github.com/01org/hyperscan), I'd say you might not be the only project feeling a bit neglected in the performance comparison here.
It's nice to be mentioned - and even called out by name as the inventor of Teddy (!) - but we're always even more pleased when someone else measures Hyperscan, as it minimizes the prospect of us embarrassing ourselves by posting some self-serving and/or outlandish microbenchmark.
Also it saves everyone time reading the obligatory Intel legal disclaimers...
This sounds interesting. I suspect there are many alternate approaches to multiple regex.
Sadly, regex benchmarking is a sewer. There are two classes of multiple regex benchmarks: public ones and good ones, and not much intersection between the two. Synthetic pattern generation can be manipulated to say whatever you want it to say, Snort patterns aren't intended to be run simultaneously (so putting a big pile of them into a sack and running them is of arguable use), and most vendors guard proprietary signature sets closely (we have thousands, but all the good ones are customer confidential).
That being said, there are some paths forward here. Let's talk.
Certainly. I dropped an e-mail at the hyperscan account.
By the way, if you try out icgrep and use the -DumpASM option, you may notice a very unusual characteristic: the generated code is almost completely dominated by AVX2 instructions!
I did a brief performance comparison with icgrep here: https://github.com/BurntSushi/ripgrep/issues/63 --- Yes, it does a little better on things like \p{Greek} (and has even better Unicode support than ripgrep) but is missing literal optimizations, which are a ridiculously common case for search tools like this. (As you acknowledged.) Just about every single person who has come to me with a performance comparison of ripgrep has used a simple literal pattern, because that's what people search. You need to knock that case out of the park to be competitive. Even sift and pt do this to some extent.
Hyperscan is another top-notch regex implementation worth looking at too, for example. With that said, it does look like icgrep could be added to the single-file benchmark at least, but it is by far the hardest piece of software to actually get installed. (Your build instructions required me to compile llvm.)
> But your story is incomplete if you don't include comparison with icgrep
My story is incomplete for a very very large number of reasons. icgrep is only one of them. As I said in the blog post, the benchmarks are not only biased, but curated.
Of course, I agree icgrep is worth looking into. It's on my list to learn more about.
> It also does very well in cases involving alternations and ambiguity.
So does ripgrep. :-)
$ ls -hl OpenSubtitles2016.raw.en
-rw-r--r-- 1 andrew users 9.3G Sep 10 11:51 OpenSubtitles2016.raw.en
$ time rg '\w+ Holmes|\w+ Watson|\w+ Adler|\w+ Moriarty|\w+ Lestrade' OpenSubtitles2016.raw.en | wc -l
26464
real 0m30.606s
user 0m29.987s
sys 0m0.567s
$ time icgrep '\w+ Holmes|\w+ Watson|\w+ Adler|\w+ Moriarty|\w+ Lestrade' OpenSubtitles2016.raw.en | wc -l
26464
real 0m41.346s
user 0m40.770s
sys 0m0.513s
$ time rg -i '\w+ Holmes|\w+ Watson|\w+ Adler|\w+ Moriarty|\w+ Lestrade' OpenSubtitles2016.raw.en | wc -l
27370
real 0m17.611s
user 0m17.100s
sys 0m0.510s
$ time icgrep -i '\w+ Holmes|\w+ Watson|\w+ Adler|\w+ Moriarty|\w+ Lestrade' OpenSubtitles2016.raw.en | wc -l
27370
real 0m43.715s
user 0m43.193s
sys 0m0.523s
In the case insensitive search, ripgrep isn't actually doing any literal optimizations, but it is in the first case. Namely, it sees that ` ` is required in every alternate. Since ` ` is so common, this ends up slowing down the search. (This shows how literal optimizations aren't necessarily so simple, because it's easy to make a mistake like I've done and cause search to be slower.)
If we change ` ` to `\s+`, we can see ripgrep regain its performance precisely because it can't do any literal optimizations:
$ time rg '\w+\s+Holmes|\w+\s+Watson|\w+\s+Adler|\w+\s+Moriarty|\w+\s+Lestrade' OpenSubtitles2016.raw.en | wc -l
26464
real 0m17.607s
user 0m17.117s
sys 0m0.490s
$ time icgrep '\w+\s+Holmes|\w+\s+Watson|\w+\s+Adler|\w+\s+Moriarty|\w+\s+Lestrade' OpenSubtitles2016.raw.en | wc -l
26464
real 0m46.368s
user 0m45.883s
sys 0m0.483s
$ time rg -i '\w+\s+Holmes|\w+\s+Watson|\w+\s+Adler|\w+\s+Moriarty|\w+\s+Lestrade' OpenSubtitles2016.raw.en | wc -l
27370
real 0m17.583s
user 0m17.080s
sys 0m0.493s
$ time icgrep -i '\w+\s+Holmes|\w+\s+Watson|\w+\s+Adler|\w+\s+Moriarty|\w+\s+Lestrade' OpenSubtitles2016.raw.en | wc -l
27370
real 0m48.662s
user 0m48.127s
sys 0m0.503s
Nevertheless, ripgrep outperforms icgrep in every case.
Now, with all that said, I bet this is my bias showing. I'm confident you can find other cases (we don't already know about) where icgrep beats ripgrep. :-)
Running the same tests on our test machine, I am seeing dramatically different performance results. Our test machine has AVX2, but this can't be the whole story.
Strange. I'm not sure how to explain the results either. Is there something I'm supposed to do to enable icgrep to use AVX2? I followed the build instructions in the README verbatim. Here's my cpu info (which is quite new and does have AVX2):
If the file path is any indication, it looks like I'm using `icgrep1.0`. But the file path also has `icgrep-devel` in it. So I don't know. When I get a chance, I guess I'll try to figure out how to compile the devel version. (It seemed like that was what I was doing, by checking out the source, but maybe not.)
Yes, you have icgrep 1.0. The current development version has about the same build process, sorry that it is such a pain. It is available by svn checkout as follows.
svn co http://parabix.costar.sfu.ca/svn/icGREP/icgrep-devel
AVX2 is autodetected and used if available and enabled by the operating system/hypervisor (Although icgrep1.0 can be compiled to use AVX2, it had some issues).
Nevertheless, we appreciate the challenge that ripgrep presents to our performance story. We definitely see some cases in which rg achieves better performance taking advantage of fixed strings somewhere in the pattern. We'll have to work on that... But for patterns based on Unicode classes (e.g., \p{Greek}, icgrep can be much faster, especially on large files. (We are only focused on big data applications -- icgrep has significant dynamic compilation overhead). It also does very well in cases involving alternations and ambiguity.
The icgrep performance story is based primarily on a new bitwise data parallel regular expression algorithm working off the Parabix transform representation of text. See our ICA3PP 2015 or PACT 2014 papers.
It might be fair to say that icgrep is not yet polished enough for inclusion in your study. I just added our first implementation of -r/-R flags last night and we certainly haven't yet handled .gitignore, etc. But if you want to understand the truth about regular expression performance, I think that the data point represented by icgrep (and its continuing development) needs to be included.