Understanding the performance difference between CLI and grep crates

[lightjacket]

First off, this is a fantastic tool and I think it's amazing that you've pulled the core logic into their own crates so others can re-use it in tools they are making.

I'm trying to do just that and am hitting a stumbling block around the performance of using the crate in my own code vs using the rg cli tool.

I'm timing my own code via:

let matcher = RegexMatcher::new(format!(".*{}.*", search_term).as_str())?;
let start = Instant::now();
let mut result = 0;
Searcher::new().search_path(&matcher, i, Bytes(|lnum, line| {
    result += 1;
    Ok(true)
}))?;
println!("elapsed={}", start.elapsed().as_secs_f32());

On my machine, that reports 0.067671694s elapsed.

Running rg on my terminal on the same file with the same pattern results in:

21577

real	0m0.026s
user	0m0.026s
sys	0m0.000s

For my own tool, I set a bunch of release profile flags in case that was it:

[profile.release]
lto = "fat"
codegen-units = 1
panic = "abort"

3x difference seems pretty large to me so I'd imagine I am missing something obvious, but I was hoping someone might be able to point me in a direction to investigate.

[BurntSushi]

What happens when you run rg with --no-mmap?

[lightjacket]

A bit of a difference but not much:

time rg --no-mmap -c '.*070.*' <file> 
21577

real	0m0.030s
user	0m0.021s
sys	0m0.008s

[BurntSushi]

All right. Please provide the full source code of your program.

[lightjacket]

Here's a simplified program that performs the same:

use std::env;
use std::error::Error;
use std::time::Instant;
use grep::regex::RegexMatcher;
use grep::searcher::Searcher;
use grep::searcher::sinks::Bytes;

fn main() -> Result<(), Box<dyn Error>> {
    let args: Vec<String> = env::args().collect();
    let search_term = args.get(1).expect("need a search term");
    let filename = args.get(2).expect("need a file name");

    let matcher = RegexMatcher::new(format!(".*{}.*", search_term).as_str())?;
    println!("starting...");
    let start = Instant::now();
    let mut result = 0;
    Searcher::new().search_path(&matcher, filename, Bytes(|_lnum, _line| {
        result += 1;
        Ok(true)
    }))?;
    println!("elapsed={}", start.elapsed().as_millis());
    Ok(())
}

P.S. Thanks for the very fast replies!

[BurntSushi]

Ah okay, thanks for that. TL;DR: Use RegexMatcher::new_line_matcher instead of RegexMatcher::new, and that will fix most of the problem.

The issue here is subtle, and I missed the fact that your regex was .*foo.* instead of just plain foo. You also didn't show the actual ripgrep command you used. (In the future, it's best to include as much details as you can so that others can reproduce your experiment.) It's possible you're using .*foo.* intentionally, but in case you're not, foo will also report lines containing foo anywhere. The only difference with .*foo.* is that .*foo.* will match the entire line instead of just foo.

Anyway, that leading .* is key because it actually inhibits a class of prefix literal optimizations within the core regex engine. The only way to re-capture those is to tell grep-regex (the layer above the core regex engine) that you want to do a line oriented search. When you do that, grep-regex can sniff out inner literals that aren't just prefixes, and then do a very fast candidate search for those. Why does being line oriented matter? Well, it's because when a candidate is found, the bounds of that match are simple and quick to compute: just find the line terminators on either side. Then we can run the actual full regex to find the complete match. It sounds like a lot of work, but when matches are relatively rare (a pretty common case), it is much faster to look for literal matches than it is to run the full regex engine.

Once of the things that RegexMatcher::new_line_matcher does is check that your regex can never match across line boundaries. Because if it can, it screws up the optimization (never mind the regex no longer being line oriented). So for example, if you wrote the regex foo\sbar, new_line_matcher will automatically strip \n from \s. However, if you wrote foo\nbar, then new_line_matcher will actually return an error, since there is no obvious transformation to be made.

Now in your case, .*foo.* actually is already line oriented. It doesn't require any transformation. So why doesn't grep-regex just automatically perform this optimization? Welllll.... That's because the definition of a line itself isn't something that grep-regex assumes internally. You can actually change what the line terminator is. (Indeed, ripgrep's --null-data flag will switch the line terminator from \n to \x00, the NUL byte.)

RegexMatcherBuilder::line_terminator says a bit more.

And dipping down a level to the core matcher interface, grep-matcher::Matcher::line_terminator also says some things.

Ultimately, the grep family of crates is really really hard to use because of subtle details like this. I tried to do my best with API docs, but what it really needs is a solid high level treatment on how to fit all of the pieces together. Alas, I have not had the time to do that.

[BurntSushi]

Note however that, e.g., rg -c foo input will not count lines, and your program will. Counting lines is really fast, so you're not likely to notice a huge speed difference, but you might. In that case, you have to configure your Searcher to not count lines with SearcherBuilder::line_number. But if you do that, you'll have to implement Sink yourself, since all of the convenience Sink impls require line numbers:

The searcher must be configured to report line numbers. If it isn't, an error is reported at the first match and searching stops.

[BurntSushi]

And I asked about memory maps above since using them can sometimes result in a slightly faster program. They are disabled by default, but SearcherBuilder::memory_map can be used to enable them.

[lightjacket]

Thanks! Never imagined I'd get an answer so fast. Using new_line_matcher absolutely addressed the performance difference. Apologies for not including the rg command (it was time rg -c '.*070.*' <file> for the sake of completeness).

The explanations makes perfect sense, and the documentation links you added are very clear reading them now. I'm not sure I would have appreciated the nuances of those points in the documentation before your answer here, so I think you're right about the high-level documentation being helpful, but it does sound like a tricky bit of writing (and a big time investment) so more than understandable that it's not there.

Again, great tool and libraries!

[BurntSushi]

Aye, yeah, it is probably a multi-week project of dedicated focus to put together the high level docs. There are just so many corners, optimizations, features and abstractions that it's difficult. ripgrep was initially a larger pile of tightly coupled code; it did not start out with most of its logic separated into crates. Thus, a lot of the design of those crates kind of went like this: "Okay I have this optimization in existing ripgrep code, and now it needs to be bubbled up into the API of a crate (or worse, into something totally generic like the Matcher trait) as an option because it only applies under certain conditions that can't be assumed to be true all the time."

[BurntSushi]

One of the driving reasons to design ripgrep internals as a bunch of higher level APIs like this instead of keeping the code coupled (which I'm totally happy to do) was to make support for things like alternate regex engines plausible. This is how I satisfied some very highly sought-after features like look-around: I added PCRE2. The fact that one can use these crates to write your own grep was only a little more effort and a nice bonus. Alas, I don't think anyone has seriously used the grep family of crates, likely because they require some amount of domain expertise to wield effectively right now. So I consider that aspect of crate structure a failure.