Compiling some unicode regexes is 2.5x slower

[jrmuizel]

What version of regex are you using?

v1.12.2

Describe the bug at a high level.

Compiling r"^[^/]+/foo/[^/]+$" takes 2.5x as long with unicode turned on then with it turned off

What are the steps to reproduce the behavior?

fn main() {
    for i in 0..100000 {

        let re = regex::bytes::RegexBuilder::new(r"^[^/]+/foo/[^/]+$")
            .unicode(true)
            .build().unwrap();
        assert!(re.is_match(b"bar/foo/baz"));
        
    }
}

Here's a profile with unicode(false) 931ms:
https://share.firefox.dev/47GnkMp
and a profile with unicode(true) 2.4s:
https://share.firefox.dev/4i6f5wO

The difference that stands out most is in regex_automata::nfa::thompson::compiler::Utf8Compiler::new
where I believe we're initializing a 10,000 element Vec.

This difference was discovered when investigating https://bugzilla.mozilla.org/show_bug.cgi?id=1983632

[BurntSushi]

Yes, Unicode regexes sometimes take longer. In this case, [^/] is a class representing every Unicode scalar value other than /. So compiling the regex requires building a UTF-8 automaton for that set of codepoints. So a Unicode regex taking longer is a generally expected thing. And yes, that might even be 2.5x slower. So the framing here is a little off. This should instead be framed as "is there a way to optimize this particular case that is important to us."

The most obvious optimization here, to me, is to use thread locals to reuse memory. But I've generally shied away from such things in libraries because they tend to lead to problems. And the memory used can be difficult reclaim in the future. In today's word, that memory is freed once you're done with it.

The specific 10,000 element vec you're referring to comes from here:

regex/regex-automata/src/nfa/thompson/map.rs

Lines 124 to 140 in 5ea3eb1

	/// Clear this map of all entries, but permit the reuse of allocation
	/// if possible.
	///
	/// This must be called before the map can be used.
	pub fn clear(&mut self) {
	if self.map.is_empty() {
	self.map = vec![Utf8BoundedEntry::default(); self.capacity];
	} else {
	self.version = self.version.wrapping_add(1);
	// If we loop back to version 0, then we forcefully clear the
	// entire map. Otherwise, it might be possible to incorrectly
	// match entries used to generate other NFAs.
	if self.version == 0 {
	self.map = vec![Utf8BoundedEntry::default(); self.capacity];
	}
	}
	}

With the 10000 number coming from here:

regex/regex-automata/src/nfa/thompson/compiler.rs

Line 1774 in 5ea3eb1

Utf8State { compiled: Utf8BoundedMap::new(10_000), uncompiled: vec![] }

The other approach that occurs to me is to find a way to avoid allocating 10,000 slots right away and up-front. This is a bit trickier and I'm not clear exactly on how to do it. In particular, the capacity is a variable influencing compression quality and not correctness.

[BurntSushi]

You could also consider whether you need Unicode mode for this regex.