why does RegexSet go slower as more patterns are added?

[Guillermogsjc]

Hi, excellent crate, just asking a concrete thing, as it is stunning me.

regex::RegexSet is a powerful type that allows to scale matches going only one time through the text for several patterns, as it is in the documentation is designed for scaling

If one has hundreds or thousands of regexes to match repeatedly (like a URL router for a complex web application or a user agent matcher), then a regex set can realize huge performance gains.

I write because I find a behaviour where there is a gain of performance until a number of regex in the regexset, then it drops, I am chunking a list of patterns and applying regexset of the chunks size, and find that:

• Time elapsed on regexset match stage by chunks of 200 is: 27.010525187s
• Time elapsed on regexset match stage by chunks of 100 is: 17.614525466s
• Time elapsed on regexset match stage by chunks of 50 is: 13.699502796s
• Time elapsed on regexset match stage by chunks of 30 is: 9.618671721s
• Time elapsed on regexset match stage by chunks of 20 is: 6.447414222s
• Time elapsed on regexset match stage by chunks of 10 is: 10.882996328s
• Time elapsed on regexset match stage by chunks of 5 is: 19.779958877s

This has no sense for me, it is a process with:

• Regex: 256
• Texts: 87770

I was expecting to have better performance on larger chunk sizes at the cost of more memory used.

It could be some design being doing wrong? Here is the method implemented

fn regexset_match(&self, regexset_chunk_size: usize) -> BTreeMap<usize, HashSet<usize>> {
        let start = Instant::now();
        let texts_len: u64 = self.texts.len() as u64;
        let regex_vec_slices: Vec<&[String]> = self
            .regex_operator
            .preprocessed_valid_patterns
            .chunks(regexset_chunk_size)
            .collect();
        let mut n_total_matches = 0;
        let mut chunk_iteration = 0;

        let mut regex_matches_set: BTreeMap<usize, HashSet<usize>> = BTreeMap::new();
        for regex_list in regex_vec_slices {
            let my_regex_set = self.regex_config.build_regexset(regex_list);

            let pb = ProgressBar::new(texts_len);
            let mut n_matches: usize = 0;
            for (text_index, transcript) in self.texts.iter().enumerate() {
                pb.inc(1);

                let matches = my_regex_set.matches(&transcript);
                n_matches += matches.len();
                if matches.len() > 0 {
                    for match_key in matches {
                        let truly_regex_index = chunk_iteration + match_key;
                        let elt = regex_matches_set
                            .entry(truly_regex_index)
                            .or_insert(HashSet::new());
                        elt.insert(text_index);
                    }
                }
            }
            pb.finish_with_message("done");
            n_total_matches += n_matches;
            chunk_iteration += regexset_chunk_size;
        }
        info!("Total number of matches in regex set: {}", n_total_matches);
        let match_duration = start.elapsed();
        info!(
            "Time elapsed on regexset match stage by chunks of {regexset_chunk_size} is: {match_duration:?}"            
        );
        regex_matches_set
    }
    ```
Version is `regex = "1.6"`.

Kind regards.

[BurntSushi]

Without a reproduction I can't really answer your question. :-/

If you search the issue tracker for RegexSet, you'll likely see that its performance can be somewhat variable.

Without a reproduction, all I can do is say something very generic. Namely, like virtually anything that does optimizations, there are thresholds everywhere. Thresholds, for example, might dictate when one regex engine is used in place of another. Those thresholds are often determined through a combination of "what makes sense" and what has been empirically observed in at least some cases. But those thresholds may not be correct in all cases. Sometimes they can be tweaked, but it will often just make some other case slower.

Now, some thresholds are actually configurable in the public API. You haven't shared the code you're using to build the regex set and didn't mention them, so I assume you don't know about them. The most important one is RegexSetBuilder::dfa_size_limit. I'd crank that to as much as you're willing to spend. If you aren't already doing that, it's very possible that you're running up against that limit after 20 regexes and getting thrown over to a slower regex engine internally. There is also RegexSetBuilder::size_limit, but this just impacts whether your regex is buildable at all or not, and doesn't have any impact on runtime performance.

[Guillermogsjc]

thanks @BurntSushi , it was just RegexSetBuilder::dfa_size_limit, I did not tweak this parameter yet... everything is now on 3 seconds an less through one RegexSet.

Maybe it could be interesting to warn about the importance of letting enough bytes to the DFA size on RegexSet, as if it is not enough, the performance is far from the expected when it is tweaked.

Congrats again for the astonishing lib, it is my main reason to learn Rust :)

[BurntSushi]

Glad that worked! Good luck.