Does RipGrep optimize queries sharing a common prefix?

[zachriggle]

Just curious whether this is something I need to optimize on the input query, or whether RipGrep is smart enough to automatically optimize.

Let's assume I want to search for:

• FooBar
• FooBarBaz
• FooFoo

And my argument to rg looks like Foo(Bar|BarBaz|Foo).

Is rg smart enough to realize that any matches for FooBarBaz are already satisfied by FooBar (e.g. in -l mode)?

I expect that due to the ordering of the query, it will be satisfied by FooBar first in -l mode, but that's only due to the ordering of the expression (which I'm not sure is relevant).

For files WITHOUT matches, it will search the entire file for any matches of FooBar as well as FooBarBaz, or is it smart enough internally to know not to search for FooBarBaz as a match for FooBar (which was already tried) would be required for any matches?

I can optimize the query on the input-side to use the shortest prefix, I'm just curious whether I need to.

[BurntSushi]

Have you read my blog post introducing ripgrep? Literal optimizations of this sort are a central part of what makes ripgrep fast.

Also, by the way you're speaking, it kind of seems like you're assuming that the execution engine has backtracking semantics. I can't say for sure, but that's what it sounds like. Of course, if you use -P/--pcre2, this is a true. But the default engine uses finite automata, so matching an alternation doesn't try Bar and then BarBaz and then Foo one after another. They are all matched simultaneously. Of course, that only occurs when the actual regex engine is used.

Of course, for a simple query like Foo(Bar|BarBaz|Foo), the regex engine shouldn't be used at all. There aren't great introspection mechanisms currently, but the --debug output will sometime tip you off:

DEBUG|grep_regex::literal|crates/regex/src/literal.rs:58: literal prefixes detected: Literals { lits: [Complete(FooBar), Complete(FooBarBaz), Complete(FooFoo)], limit_size: 250, limit_class: 10 }

You can see that the literal detector pulled out three complete literals from the regex. The easiest way to "confirm" this is to profile a ripgrep execution and look at where time is being spent. It helps to run it on a big file. So running perf on rg 'Foo(Bar|BarBaz|Foo)' OpenSubtitles2018.raw.en gave me this:

In this case, the literals are passed to the aho-corasick crate, and from there, it detects that all matches begin with a common byte: F. So memchr is used there. A more complex case might use a different strategy. e.g., Running perf on rg 'FooBar|BarFoo|QuuxFoo|GooQuux' OpenSubtitles2018.raw.en where there is no common leading byte gives you:

In this case, the aho-corasick crate still isn't even using the Aho-Corasick algorithm, but rather a specialized vectorized algorithm called Teddy that tends to only work well for some small number of literals.

If you give ripgrep enough literals, then it will indeed ultimately just use Aho-Corasick and still bypass the regex engine entirely. Although other than construction time (with Aho-Corasick being much faster), the execution properties of Aho-Corasick and ripgrep's default regex engine are rather similar since they are both instantiations of finite automata.

[zachriggle]

Wow, huge reply to my question! I thought I had read something about RipGrep doing this, but wasn't sure. Thanks for the extended reply, you definitely went above and beyond. I'll have to revisit your blog post for sure!

I'm not super familiar with Rust development (or profiling) so the pointers to perf are useful and impressive language / ecosystem utilities!

As always, thanks for such a great tool @BurntSushi

[BurntSushi]

Note that perf is a Linux-specific tool and generally works with any executable that produces DWARF debug info. The Rust compiler does this on Linux, so it turns out that perf works quite nicely. :-)