Regex Performance in Rust and Avoiding Catastrophic Cases

Rust's regex crate guarantees linear-time matching, so there is no catastrophic backtracking. The real costs are compiling in a loop, unanchored scans and capture groups. Learn what to cache and when to use regex-lite.

4 min read

Summarize in AI

Quick Summary

The regex crate matches in time proportional to the input length times the pattern size, so patterns cannot cause catastrophic backtracking, which makes it safe on untrusted text. The usual performance mistakes are compiling a Regex inside a loop, asking for capture groups when is_match would do, and using many separate patterns instead of one RegexSet. Compile once, store it in a LazyLock, and use regex::bytes for non-UTF-8 input.

Key takeaways

Compiling a regex is expensive (microseconds to milliseconds); do it once and reuse the value, which is Send + Sync.
Matching is guaranteed linear in the haystack, so there is no ReDoS from backtracking, but features that need backtracking (look-around, backreferences) are not supported.
is_match is faster than find, which is faster than captures; ask only for what you use.
RegexSet matches many patterns in one pass over the text.
regex-lite trades speed and Unicode data for smaller binaries and faster compile times.

Rust's regex crate is built on a different design from the backtracking engines in most languages. That gives it a guarantee people rarely get: matching cannot blow up exponentially. It also means its performance traps are different, and mostly about construction. Everything here compiles on Rust 1.90 with edition 2024 and regex 1.11.

The guarantee and its price

A pattern like (a+)+$ against a long string of as followed by b takes exponential time in a backtracking engine such as Perl or Python's re. In Rust it finishes in time proportional to the text. The price is the feature set: no backreferences (\1) and no look-ahead or look-behind. If you need those, the fancy-regex crate adds them and brings back the backtracking risk for those patterns.

Mistake 1: compiling in a loop

rust

use regex::Regex;

fn count_slow(lines: &[&str]) -> usize {
    lines
        .iter()
        .filter(|l| Regex::new(r"^\d{4}-\d{2}-\d{2}").unwrap().is_match(l)) // compiled per line
        .count()
}

use std::sync::LazyLock;

static DATE: LazyLock<Regex> = LazyLock::new(|| Regex::new(r"^\d{4}-\d{2}-\d{2}").unwrap());

fn count_fast(lines: &[&str]) -> usize {
    lines.iter().filter(|l| DATE.is_match(l)).count()
}

Regex::new parses the pattern, builds automata and prepares literal searches. On a hot path that dominates the actual matching by a wide margin. A compiled Regex is cheap to share across threads; clone it or put it in a static. The standard library's LazyLock (Rust 1.80) removes the need for once_cell here (const and static).

Mistake 2: asking for more than you need

rust

use regex::Regex;

fn demo(re: &Regex, text: &str) {
    let yes = re.is_match(text);          // cheapest: no match positions
    let span = re.find(text);             // match start and end
    let caps = re.captures(text);         // capture groups, most work
    let _ = (yes, span, caps);
}

Capture groups need the engine to track submatch positions, which is slower than finding the overall span. Use is_match for filters, find for extraction of the whole match, and captures only when you need the groups. Use non-capturing groups (?:...) where you only need grouping.

Many patterns: RegexSet

rust

use regex::RegexSet;

fn main() {
    let set = RegexSet::new([r"^ERROR", r"timeout", r"\bpanic\b"]).unwrap();
    let hits: Vec<usize> = set.matches("ERROR: connection timeout").into_iter().collect();
    println!("{hits:?}");
}

Text

[0, 1]

A RegexSet scans the input once and reports which patterns matched, instead of one scan per pattern. It does not report positions; follow up with the individual regex only for the lines that matched. This is the shape of a log filter with a list of rules.

Anchoring and literals

An anchored pattern (^) lets the engine fail fast. A pattern that begins with a literal prefix or contains a required literal gets a fast substring search (the engine uses vectorized routines from the memchr crate). Leading wildcards such as .*foo hide the literal and force a full scan; foo alone finds the same line with a faster search when you only need to know whether it matches.

Bytes and Unicode

rust

use regex::bytes::Regex;

fn main() {
    let re = Regex::new(r"(?-u)\xFF[\x00-\x7F]+").unwrap();
    println!("{}", re.is_match(b"\xFFabc"));
}

Text

true

regex::bytes matches on &[u8], which avoids a UTF-8 validation pass for binary or mixed data. Unicode-aware classes like \w and \d match thousands of code points; if you only mean ASCII, write [0-9] or disable Unicode with (?-u) for smaller, faster automata.

Limits for untrusted patterns

rust

use regex::RegexBuilder;

fn compile_user_pattern(p: &str) -> Result<regex::Regex, regex::Error> {
    RegexBuilder::new(p).size_limit(1 << 20).dfa_size_limit(1 << 22).build()
}

When users supply patterns (a search box, a rules file), a huge counted repetition like (\w{100}){100} can use lots of memory to compile. Set size limits and fail with an error (resource limits).

regex-lite and benchmarks

For a CLI where binary size and build time matter more than peak speed, regex-lite offers the same API subset with a smaller footprint, with limited Unicode support. Measure with realistic data and a harness such as Criterion or Divan before changing anything (benchmarking with Criterion and Divan); regex performance depends heavily on the pattern and input shape. For a worked CLI example, see the log analyzer.

Also inPerformance

Taggedregex