Performance regression in case-insensitive regexes

[RReverser]

This sample benchmark show ~24% regression between versions 1.1.2 and 1.1.3 on my machine:

#[bench]
fn bench(b: &mut test::Bencher) {
    lazy_static::lazy_static! {
        static ref RE: Regex = Regex::new(r#"(?i)googlebot/\d+\.\d+"#).unwrap();
    }

    let re = black_box(&*RE);
    let input = black_box("Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.103 Safari/537.36");

    b.iter(move || {
        black_box(re.is_match(input));
    });
}

According to the changelog, this corresponds to aho-corasick upgrade in #566, which might be the reason.

Note that I've also tried removing \d+\.\d+ part, keeping just (?i)googlebot - still same regression.

However, removing (?i) makes both almost equally fast, so I suspect this is something specific to case-insensitive handling.

[BurntSushi]

Thanks for the report. Unfortunately, this is probably within my acceptable range personally, especially at these scales. This is kind of the game we play with literal optimizations, which are a black art. It will in general not always be possible to never regress when playing with literal optimizations, so I think it would be good to adjust expectations on that front.

Roughly half of the regression can be fixed, at least for me, by re-enabling Aho-Corasick's prefilter. This was enabled when using aho-corasick 0.6 simply because there was no way to disable it. But since the Teddy searcher only uses Aho-Corasick for very short parts of the string, it seemed sensible to just disable it completely, with the assumption that a prefilter would, on average, be a net negative. It isn't in this case though. So I'm not quite sure whether to re-enable it or not.

The other half of the regression is more of a mystery to me. The new Aho-Corasick crate might have slightly higher constant factors than the old one.

I have some other ideas on how to speed up Teddy's verification step itself, which might help regain some of the loss here.

[RReverser]

Thanks for your thoughts! I agree that it's not critical at this particular level of absolute timings, but was mostly worried about it having more generic impact.

From what you're saying it sounds like it affects only short strings by design, so shouldn't be a problem.

I have some other ideas on how to speed up Teddy's verification step itself, which might help regain some of the loss here.

Should this be kept open for tracking potential improvements then?

[BurntSushi]

I tried to reproduce this again to see how this looks today. The first group is 1.1.2, the second is 1.1.3 and the last is 1.5.5:

[andrew@duff i572]$ for ((i=0; i<10; i++)); do cargo bench 2>&1 | grep ns/iter; done
test bench ... bench:          18 ns/iter (+/- 0)
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          19 ns/iter (+/- 1)
test bench ... bench:          20 ns/iter (+/- 1)
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          19 ns/iter (+/- 1)
test bench ... bench:          19 ns/iter (+/- 0)
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          19 ns/iter (+/- 0)
[andrew@duff i572]$ for ((i=0; i<10; i++)); do cargo bench 2>&1 | grep ns/iter; done
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          20 ns/iter (+/- 2)
test bench ... bench:          21 ns/iter (+/- 1)
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          17 ns/iter (+/- 1)
test bench ... bench:          17 ns/iter (+/- 1)
test bench ... bench:          20 ns/iter (+/- 0)
test bench ... bench:          20 ns/iter (+/- 2)
[andrew@duff i572]$ for ((i=0; i<10; i++)); do cargo bench 2>&1 | grep ns/iter; done
test bench ... bench:          16 ns/iter (+/- 2)
test bench ... bench:          17 ns/iter (+/- 1)
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          13 ns/iter (+/- 0)
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          15 ns/iter (+/- 2)
test bench ... bench:          17 ns/iter (+/- 0)
test bench ... bench:          17 ns/iter (+/- 0)

Eyeballing it, it looks like we're a hair faster than we were before. From looking at the profiles of each, it looks like in 1.1.3 I had introduced Aho-Corasick into the verification step for Teddy. But a while later, when I rewrote Teddy, I used a different verification scheme because I couldn't make the use of Aho-Corasick fast. (The details have faded from my memory.) So overall, I'd say that some improvements were made here.

Normally I would have converted this to a Criterion benchmark, but Criterion uses regex as a dependency which makes it a little annoying to get it setup to benchmark older versions of regex. Lol. So as a sanity check, I rewrote the benchmark as a simple program that executes the regex many times:

use regex::Regex;

fn main() {
    let re = Regex::new(r#"(?i)googlebot/\d+\.\d+"#).unwrap();
    let input = "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.103 Safari/537.36";

    let mut count = 0;
    for _ in 0..200_000_000 {
        if re.is_match(input) {
            count += 1;
        }
    }
    println!("{}", count);
}

The first below is 1.1.2. The second is 1.1.3. And the last is 1.5.5. It seems to roughly match the micro-benchmark above: 1.1.3 got a little slower and 1.5.5 got a bit faster.

[andrew@duff i572]$ time ./target/release/i572
0

real    3.535
user    3.531
sys     0.003
maxmem  4 MB
faults  0
[andrew@duff i572]$ time ./target/release/i572
0

real    3.659
user    3.658
sys     0.000
maxmem  4 MB
faults  0
[andrew@duff i572]$ time ./target/release/i572
0

real    3.441
user    3.437
sys     0.003
maxmem  4 MB
faults  0

So overall I'm going to close this. And in general, I think I stand by what I said before: literal optimizations are a black art and perf is likely to change over time as changes are made to the prefilter optimizations. It is difficult to impossible to get universal wins in all cases.