RegexSet much slower than multiple single scans

[lukaslueg]

I have a set of ~20 very simple but not anchored regexes to run against a buffer. The chance of at least one match is on the order of a few percent. My idea was to use a RegexSet to scan the buffer once (in reality a stream of ~20gb) and rescan with individual regexes to find matches if there are in fact any.

As it turns out, the RegexSet-pass is much, much slower than scanning the buffer multiple times:

#![feature(test)]

extern crate test;
extern crate regex;

static PATTERNS: &'static [&'static str] = &[
         "ABC", "FOO", "BAR", "FOOBAR", "BARFOO",
        "foo", "haha", "asdfk", "safdkj", "sadhakjs", "345845hj",
        "^234jkl2$", "^ß0gjk2$", "^lkjsdf$", "^234rklj$", "2234sg$"
    ];

fn main() {
    println!("Hello, world!");
}

fn fixture() -> Vec<u8> {
    std::iter::repeat(32).take(10*1024).collect()
}

#[bench]
fn single(b: &mut test::Bencher) {
    let fix = fixture();
    let haystick = std::str::from_utf8(&fix).unwrap();
    let set: Vec<_> = PATTERNS.iter().map(|p| regex::Regex::new(p).unwrap()).collect();
    b.iter(move || {
        let m: Vec<_> = set.iter().map(|r| r.is_match(haystick)).collect();
        test::black_box(m);
    });
}

#[bench]
fn multiple(b: &mut test::Bencher) {
    let fix = fixture();
    let haystick = std::str::from_utf8(&fix).unwrap();
    let set = regex::RegexSet::new(PATTERNS).unwrap();
    b.iter(move || {
        //let m = set.is_match(haystick);
        let m: Vec<_> = set.matches(haystick).into_iter().collect();
        test::black_box(m);
    });
}

Running target/release/retest-ae36173f0b85f6dc

running 2 tests
test multiple ... bench:      22,619 ns/iter (+/- 384)
test single   ... bench:       3,057 ns/iter (+/- 114)

test result: ok. 0 passed; 0 failed; 0 ignor

The RegexSet being much, much slower than rescanning is very surprising.

[lukaslueg]

On 100mb of spaces the speeds are 233m ns/i for multi and 91m ns/i for single.
On 10mb of random utf8 chars the speeds are 122m ns/i for multi and 23m ns/i for single.

[BurntSushi]

Benchmarking regexes is hard, and the results can be surprising because optimizations can make it tricky to reason straight-forwardly about performance. In this particular benchmark, I'd like to note the following things:

1. There are a reasonably small number of regexes.
2. All of the regexes are just literals, with a few anchored to the beginning/end of text.
3. None of the regexes ever match anywhere in the haystack.
4. The haystack is quite small, and given the speeds involved, you very well could be benchmarking match overhead. (Indeed, your benchmark results on bigger haystacks suggest that is the case.)

The "naive" solution in this case is much faster precisely because of the above three criteria. The small number of regexes means that the constant factor improvement of RegexSet is pretty small. The fact that the regexes are mostly literals and the match infrequency means that a simple scan using Regex is going to be insanely fast because it essentially compiles down to a single memchr call that reports "nope, this byte doesn't match in this haystack of 0x32 bytes." On the other hand, a RegexSet doesn't know this optimization is possible, so it either tries Aho-Corasick or the full lazy DFA, both of which are going to be much slower than a call to memchr on a very small haystack.

The point of a RegexSet is to scale. Add more regexes, use larger haystacks, increase match frequency or change the regexes to something other than plain literals and you might see the gap close.

I think this is probably working as intended.

[yazaddaruvala]

@BurntSushi I've been running similar benches, and it seems like RegexSet is always less scalable than Vec<Regex>. What am I doing wrong?

running 18 tests
Build  2,500 RegexSet:   (".*0001.*", ".*0002.*", ..., ".*2500.*") - Build Throughput: 28379.11/s
Build  2,500 Regexes:    (".*0001.*", ".*0002.*", ..., ".*2500.*") - Build Throughput: 20942.27/s
Build 25,000 Regexes: (".*00001.*", ".*00002.*", ..., ".*25000.*") - Build Throughput: 19261.36/s
test contains::medium_needle::match_no::regex_set    ... bench: 151,573,011 ns/iter (+/- 6,969,733)
test contains::medium_needle::match_no::regexes      ... bench:   4,930,707 ns/iter (+/- 613,576)
test contains::medium_needle::match_no::regexes_10x  ... bench:  50,170,445 ns/iter (+/- 4,844,777)
test contains::medium_needle::match_yes::regex_set   ... bench: 152,474,252 ns/iter (+/- 5,832,912)
test contains::medium_needle::match_yes::regexes     ... bench:   4,954,995 ns/iter (+/- 679,333)
test contains::medium_needle::match_yes::regexes_10x ... bench:  50,405,913 ns/iter (+/- 5,722,213)
test contains::small_needle::match_no::regex_set     ... bench:   2,695,389 ns/iter (+/- 308,408)
test contains::small_needle::match_no::regexes       ... bench:     394,149 ns/iter (+/- 74,657)
test contains::small_needle::match_no::regexes_10x   ... bench:   7,589,178 ns/iter (+/- 555,109)
test contains::small_needle::match_yes::regex_set    ... bench:   2,590,789 ns/iter (+/- 293,424)
test contains::small_needle::match_yes::regexes      ... bench:     340,748 ns/iter (+/- 77,446)
test contains::small_needle::match_yes::regexes_10x  ... bench:   7,183,063 ns/iter (+/- 695,527)
Build  10,000 RegexSet:   ("00001", "00002", ..., "10000") - Build Throughput: 117828.35/s
Build  10,000 Regexes:    ("00001", "00002", ..., "10000") - Build Throughput:  27229.22/s
Build 100,000 Regexes: ("000001", "000002", ..., "100000") - Build Throughput:  24990.66/s
test exact::small_needle::match_no::regex_set        ... bench:   3,109,441 ns/iter (+/- 246,743)
test exact::small_needle::match_no::regexes          ... bench:     797,690 ns/iter (+/- 120,845)
test exact::small_needle::match_no::regexes_10x      ... bench:   8,570,098 ns/iter (+/- 727,307)
test exact::small_needle::match_yes::regex_set       ... bench:   2,809,886 ns/iter (+/- 258,279)
test exact::small_needle::match_yes::regexes         ... bench:     811,185 ns/iter (+/- 118,593)
test exact::small_needle::match_yes::regexes_10x     ... bench:   8,596,560 ns/iter (+/- 741,550)

test result: ok. 0 passed; 0 failed; 0 ignored; 18 measured; 0 filtered out

Code:

// License: https://en.wikipedia.org/wiki/WTFPL

#![allow(dead_code)]
#![feature(concat_idents)]
#![feature(test)]

#[macro_use] extern crate cached;
#[macro_use] extern crate lazy_static;

extern crate regex;
extern crate regex_syntax;
extern crate pbr;
extern crate test;

use test::Bencher;
use pbr::ProgressBar;
use regex::Regex;

macro_rules! compare_regex_set {
    ($id:ident, $matcher:expr, $format:tt, $needle:expr, $matches:expr) => {
        mod $id {
            use super::*;

            #[bench]
            fn regexes(b: &mut Bencher) {
                let set = build_stressor_regexes(test::black_box($matcher.max_inputs()), $matcher);
                let full_needle: &str = &format!($format, $needle);
                assert_eq!(set.matches(full_needle).len(), $matches);
                b.iter(|| set.matches(test::black_box(full_needle)));
            }
            #[bench]
            fn regexes_10x(b: &mut Bencher) {
                let set = build_stressor_regexes(test::black_box($matcher.max_inputs()*10), $matcher);
                let full_needle: &str = &format!($format, &("0".to_owned() + $needle));
                assert_eq!(set.matches(full_needle).len(), $matches);
                b.iter(|| set.matches(test::black_box(full_needle)));
            }

            #[bench]
            fn regex_set(b: &mut Bencher) {
                let set = build_stressor_regex_set(test::black_box($matcher.max_inputs()), $matcher);
                let full_needle: &str = &format!($format, $needle);
                assert_eq!(if set.matches(full_needle).matched_any() { 1 } else { 0 }, $matches);
                b.iter(|| set.matches(test::black_box(full_needle)));
            }
        }
    }
}

mod exact { use super::*;
    mod small_needle { use super::*;
        compare_regex_set!(
            match_no,
            Matcher::Exact,
            "{}",
            "00_002",
            0
        );
        compare_regex_set!(
            match_yes,
            Matcher::Exact,
            "{}",
            "00002",
            1
        );
    }
}
mod contains { use super::*;
    mod small_needle { use super::*;
        compare_regex_set!(
            match_no,
            Matcher::Contains,
            "{}",
            "0_002",
            0
        );
        compare_regex_set!(
            match_yes,
            Matcher::Contains,
            "{}",
            "0002",
            1
        );
    }
    mod medium_needle { use super::*;

        compare_regex_set!(
            match_no,
            Matcher::Contains,
            "This ö article lists and discusses the usage and derivation of names of large numbers, together with their possible extensions. The following table lists those names of large numbers that are found in many English dictionaries and thus have a special claim to being \"real words.\" The \"Traditional British\" values shown are unused in American English and are becoming rare in British English, but their other-language variants are dominant in many non-English-speaking areas, including continental Europe and Spanish-speaking countries in Latin America; see Long and short scales. English also has many words, such as \"zillion\", used informally to mean large but unspecified amounts; {} see indefinite and fictitious numbers.",
            "",
            0
        );
        compare_regex_set!(
            match_yes,
            Matcher::Contains,
            "This ö article lists and discusses the usage and derivation of names of large numbers, together with their possible extensions. The following table lists those names of large numbers that are found in many English dictionaries and thus have a special claim to being \"real words.\" The \"Traditional British\" values shown are unused in American English and are becoming rare in British English, but their other-language variants are dominant in many non-English-speaking areas, including continental Europe and Spanish-speaking countries in Latin America; see Long and short scales. English also has many words, such as \"zillion\", used informally to mean large but unspecified amounts; {} see indefinite and fictitious numbers.",
            "0002",
            1
        );
    }
}
// TODO: Add strings which actually match multiple regexes

/**
  Builders
**/

#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub enum Matcher {
    Exact,
    Contains,
}

impl Matcher {
    fn format(self, s: String) -> String { match self {
        Matcher::Exact => format!("{}", s),
        Matcher::Contains => format!(".*?{}.*?", s),
    }}
    fn max_inputs(self) -> usize { match self {
        Matcher::Exact =>   10_000, // Note: RegexSet::CompiledTooBig @ 37_500
        Matcher::Contains => 2_500, // Note: RegexSet::CompiledTooBig @  3_200
    }}
}

pub struct RegexSet(Vec<Regex>);

impl RegexSet {
    fn new(res: impl Iterator<Item=String>) -> Result<RegexSet, ()> {
        let regexes = res.map(|p| Regex::new(&p).unwrap()).collect::<Vec<Regex>>();
        Ok(RegexSet(regexes))
    }
    fn matches(&self, needle: &str) -> Vec<usize> {
        self.0.iter().enumerate().filter(|(_, re)| re.is_match(needle)).map(|(i, _)| i).collect()
    }
}

fn build_stressor_input<'a>(max: usize, matcher: Matcher) -> impl Iterator<Item=String> {
    let padding: usize = max.to_string().len();
    (1..=max)
        .map(move |n|
            format!("{:0width$}", n, width = padding)
        )
        .map(move |s|
            matcher.format(s)
        )
}
cached!{
    BUILD_STRESSOR_REGEXES;
    fn build_stressor_regexes(max: usize, matcher: Matcher) -> std::sync::Arc<RegexSet> = {
        let stdout = std::io::stdout();
        let mut stdout = stdout.lock();

        let mut build_pb = ProgressBar::on(&mut stdout, max as u64);
        build_pb.message("Build: ");
        let mut skip_pb: u16 = 0;
        let set = RegexSet::new(build_stressor_input(max, matcher).inspect(|_| {
            skip_pb = skip_pb.wrapping_add(1);
            if skip_pb == 0 { build_pb.add(u16::max_value().into()); }
        })).unwrap();
        build_pb.finish();
        std::sync::Arc::new(set)
    }
}

cached!{
    BUILD_STRESSOR_REGEX_SET;
    fn build_stressor_regex_set(max: usize, matcher: Matcher) -> std::sync::Arc<regex::RegexSet> = {
        let stdout = std::io::stdout();
        let mut stdout = stdout.lock();

        let mut build_pb = ProgressBar::on(&mut stdout, max as u64);
        build_pb.message("Build: ");
        let mut skip_pb: u16 = 0;
        let set = regex::RegexSet::new(build_stressor_input(max, matcher).inspect(|_| {
            skip_pb = skip_pb.wrapping_add(1);
            if skip_pb == 0 { build_pb.add(u16::max_value().into()); }
        })).unwrap();
        build_pb.finish();
        std::sync::Arc::new(set)
    }
}

[BurntSushi]

@yazaddaruvala I don't have a lot of time available to me, and I'm not finding your benchmark particularly accessible. Please make it easier for others to help you. Here are some ideas:

• Show the regexes explicitly somewhere.
• Use as few external dependencies as possible. Ideally, just regex and probably lazy_static.
• Reduce or eliminate the use of macros.
• Focus on as few benchmarks are possible.
• Create a new issue.

[hce]

You claim RegexSet uses aho-corasick when applicable, yet this is documented nowhere. The docs simply state that the runtime is O(nm) where n is the size of the haystack and m is the size of the regex set, which kinda implies that aho-corasick is not used.

[BurntSushi]

which kinda implies that aho-corasick is not used

No it doesn't. Big-O notation describes worst case, and the use of Aho-Corasick is an implementation detail and is correctly not part of the public API documentation.

[hce]

Your comment is not helpful. If no regexes are used, then that isn't the worst case, but the worst case is much better. I am writing a wrapper currently that uses RegexSet only if regular expressions are used. If it was mentioned in the documentation, there'd be no need for me to implement this wrapper.

[BurntSushi]

If you're going to criticize me for being unhelpful, then you might consider starting with the problem you're trying to solve instead of trying to pick at technical nits. I don't know what you're doing, what you're working on or what problem you're trying to solve. From my perspective, you looked like a drive by pedant. If instead you started with the problem you're trying to solve, then I could have just told you that there is no guarantee that Aho-Corasick is used if a RegexSet is just an alternation of literals. It only might be used if the very primitive literal extraction optimizations kick in. There is no theoretical reason why this is true today; it is one of many problems that are a result of a sub-par implementation that I'm trying to fix, but doing so takes a lot of work.

I am writing a wrapper currently that uses RegexSet only if regular expressions are used. If it was mentioned in the documentation, there'd be no need for me to implement this wrapper.

If I were doing this, I'd go about this in the exact same way given today's current implementation. So no, there does not exist any documentation I could add that would change this. Indeed, my globset crate does something quite similar. Ideally, globset wouldn't need to do much if anything, and just let RegexSet pick the fastest path, but the implementation just isn't that good yet.

[hce]

I need to match a small to moderate sized list of patterns (~between 5 and 200 entries, partly regexes, partly not) defined by a user, against a potentially very large list (~10 mio entries) of small strings (between ~5 and 60 characters each), finding all entries that match.