rebar

A biased barometer for gauging the relative speed of some regex engines on a curated set of tasks.

Links

• METHODOLOGY describes the motivation, design, benchmark selection and evaluation protocol used by rebar.
• BUILD describes how to build rebar and the regex engines it measures.
• TUTORIAL provides a guided exploration of some of the most useful rebar sub-commands.
• CONTRIBUTING describes how to add new benchmarks and how to add a new regex engine to benchmark.
• MODELS describes the different types of workloads measured.
• FORMAT describes the directory hierarchy and TOML format for how benchmarks are defined.
• KLV describes the format of data given to regex engine runner programs for how to execute a benchmark.
• BIAS is a work-in-progress document describing the bias of this barometer.
• WANTED provides some ideas for other regex engines to add to rebar.
• BYOB discusses how to "bring your own benchmarks." That is, anyone can use rebar with their own engine and benchmark definitions.

Results

This section shows the results of a curated and biased set of benchmarks. These reflect only a small subset of the benchmarks defined in this repository, but were carefully crafted to attempt to represent a broad range of use cases and annotated where possible with analysis to aide in the interpretation of results.

The results begin with a summary, then a list of links to each benchmark group and then finally the results for each group. Results are shown one benchmark group at a time, where a single group is meant to combine related regexes or workloads, where it is intended to be useful to see how results change across regex engines. Analysis is provided, at minimum, for every group. Although, analysis is heavily biased towards Rust's regex crate, as it is what this author knows best. However, contributions that discuss other regex engines are very welcomed.

Below each group of results are the parameters for each individual benchmark within that group. An individual benchmark may contain some analysis specific to it, but it will at least contain a summary of the benchmark details. Some parameters, such as the haystack, are usually too big to show in this README. One can use rebar to look at the haystack directly. Just take the full name of the benchmark and give it to the rebar haystack command. For example:

$ rebar haystack unicode/compile/fifty-letters
ͱͳͷΐάέήίΰαβγδεζηθικλμνξοπρςστυφχψωϊϋόύώϙϛϝϟϡϸϻͱͳͷΐάέή

Similarly, the full benchmark execution details (including the haystack) can be seen with the rebar klv command:

$ rebar klv unicode/compile/fifty-letters
name:29:unicode/compile/fifty-letters
model:7:compile
pattern:7:\pL{50}
case-insensitive:5:false
unicode:4:true
haystack:106:ͱͳͷΐάέήίΰαβγδεζηθικλμνξοπρςστυφχψωϊϋόύώϙϛϝϟϡϸϻͱͳͷΐάέή
max-iters:1:0
max-warmup-iters:1:0
max-time:1:0
max-warmup-time:1:0

Finally, you can run the benchmark yourself and look at results on the command line:

$ rebar measure -f '^unicode/compile/fifty-letters$' | tee results.csv
$ rebar cmp results.csv

Summary

Below are two tables summarizing the results of regex engines benchmarked. Each regex engine includes its version at the time measurements were captured, a summary score that ranks it relative to other regex engines across all benchmarks and the total number of measurements collected.

The first table ranks regex engines based on search time. The second table ranks regex engines based on compile time.

The summary statistic used is the geometric mean of the speed ratios for each regex engine across all benchmarks that include it. The ratios within each benchmark are computed from the median of all timing samples taken, and dividing it by the best median of the regex engines that participated in the benchmark. For example, given two regex engines A and B with results 35 ns and 25 ns on a single benchmark, A has a speed ratio of 1.4 and B has a speed ratio of 1.0. The geometric mean reported here is then the "average" speed ratio for that regex engine across all benchmarks.

If you're looking to compare two regex engines specifically, then it is better to do so based only on the benchmarks that they both participate in. For example, to compared based on the results recorded on 2023-05-04, one can do:

$ rebar rank record/all/2023-05-04/*.csv -f '^curated/' -e '^(rust/regex|hyperscan)$' --intersection -M compile
Engine      Version           Geometric mean of speed ratios  Benchmark count
------      -------           ------------------------------  ---------------
hyperscan   5.4.1 2023-02-22  2.03                            25
rust/regex  1.8.1             2.13                            25

Caution: Using a single number to describe the overall performance of a regex engine is a fraught endeavor, and it is debatable whether it should be included here at all. It is included primarily because the number of benchmarks is quite large and overwhelming. It can be quite difficult to get a general sense of things without a summary statistic. In particular, a summary statistic is also useful to observe how the overall picture itself changes as changes are made to the barometer. (Whether it be by adding new regex engines or adding/removing/changing existing benchmarks.) One particular word of caution is that while geometric mean is more robust with respect to outliers than arithmetic mean, it is not unaffected by them. Therefore, it is still critical to examine individual benchmarks if one wants to better understand the performance profile of any specific regex engine or workload.

Summary of search-time benchmarks

Summary of compile-time benchmarks

Benchmark Groups

Below is a list of links to each benchmark group in this particular barometer. Each benchmark group contains 1 or more related benchmarks. The idea of each group is to tell some kind of story about related workloads, and to give a sense of how performance changes based on the variations between each benchmark.

This report was generated by rebar 0.0.1 (rev 8c6edf6843).

• literal
• literal-alternate
• date
• ruff-noqa
• lexer-veryl
• cloud-flare-redos
• unicode-character-data
• words
• aws-keys
• bounded-repeat
• unstructured-to-json
• dictionary
• noseyparker
• quadratic

literal

This group of benchmarks measures regex patterns that are simple literals. When possible, we also measure case insensitive versions of the same pattern. We do this across three languages: English, Russian and Chinese. For English, Unicode mode is disabled while it is enabled for Russian and Chinese. (Which mostly only matters for the case insensitive benchmarks.)

This group is mainly meant to demonstrate two things. Firstly is whether the regex engine does some of the most basic forms of optimization by recognizing that a pattern is just a literal, and that a full blown regex engine is probably not needed. Indeed, naively using a regex engine for this case is likely to produce measurements much worse than most regex engines. Secondly is how the performance of simple literal searches changes with respect to both case insensitivity and Unicode. Namely, substring search algorithms that work well on ASCII text don't necessarily also work well on UTF-8 that contains many non-ASCII codepoints. This is especially true for case insensitive searches.

Notice, for example, how RE2 seems to be faster in the sherlock-casei-ru benchmark than in the sherlock-ru benchmark, even though the latter is "just" a simple substring search where as the former is a multiple substring search. In the case of sherlock-ru, RE2 actually attempts a literal optimization that likely gets caught up in dealing with a high false positive rate of candidates. Where as in the case of sherlock-casei-ru, no literal optimization is attempted and instead its lazy DFA is used. The high false positive rate in the simpler literal case winds up making it overall slower than it likely would be if it would just use the DFA.

This is not in any way to pick on RE2. Every regex engine that does literal optimizations (and most do) will suffer from this kind of setback in one way or another.

literal-alternate

This group is like literal, but expands the complexity from a simple literal to a small alternation of simple literals, including case insensitive variants where applicable. Once again, we do this across three languages: English, Russian and Chinese. We disable Unicode mode for English but enable it for Russian and Chinese. Enabling Unicode here generally only means that case insensitivity takes Unicode case folding rules into account.

This benchmark ups the ante when it comes to literal optimizations. Namely, for a regex engine to optimize this case, it generally needs to be capable of reasoning about literal optimizations that require one or more literals from a set to match. Many regex engines don't deal with this case well, or at all. For example, after a quick scan at comparing the sherlock-en benchmark here and in the previous literal group, one thing that should stand out is the proportion of regex engines that now measure throughput in MB/s instead of GB/s.

One of the difficulties in optimizing for this case is that multiple substring search is difficult to do in a way that is fast. In particular, this benchmark carefully selected each alternation literal to start with a different character than the other alternation literals. This, for example, inhibits clever regex engines from noticing that all literals begin with the same byte (or small number of bytes). Consider an alternation like foo|far|fight. It is not hard to see that a regex engine could just scan for the letter f as a prefilter optimization. Here, we pick our regex such that this sort of shortcut isn't available. For the regex engine to optimize this case, it really needs to deal with the problem of multiple substring search.

Multiple substring search can be implemented via a DFA, and perhaps in some cases, quite quickly via a shift DFA. Beyond that though, multiple substring search can be implemented by other various algorithms such as Aho-Corasick or Rabin-Karp. (The standard Aho-Corasick formulation is an NFA, but it can also be converted to a DFA by pre-computing all failure transitions. This winds up with a similar result as using Thompson's construction to produce an NFA and then powerset construction to get a DFA, but the Aho-Corasick construction algorithm is usually quite a bit faster because it doesn't need to deal with a full NFA.)

The problem here is that DFA speeds may or may not help you. For example, in the case of RE2 and Rust's regex engine, it will already get DFA speeds by virtue of their lazy DFAs. Indeed, in this group, RE2 performs roughly the same across all benchmarks. So even if you, say build an Aho-Corasick DFA, it's not going to help much if at all. So it makes sense to avoid it.

But Rust's regex crate has quite a bit higher throughputs than RE2 on most of the benchmarks in this group. So how is it done? Currently, this is done via the Teddy algorithm, which was ported out of Hyperscan. It is an algorithm that makes use of SIMD to accelerate searching for a somewhat small set of literals. Most regex engines don't have this sort of optimization, and indeed, it seems like Teddy is not particularly well known. Alas, regex engines that want to move past typical DFA speeds for multiple substring search likely need some kind of vectorized algorithm to do so. (Teddy is also used by Rust's regex crate in the previous literal group of benchmarks for accelerating case insensitive searches. Namely, it enumerates some finite set of prefixes like she, SHE, ShE and so on, and then looks for matches of those as a prefilter.)

date

This is a monster regex for extracting dates from unstructured text from the datefinder project written in Python. The regex itself was taken from printing the DATES_PATTERN variable in the datefinder project. I then removed all names from the capture groups, unnecessary escapes and collapsed it to a single line (because not all regex engines support verbose mode).

The regex is more akin to a tokenizer, and the datefinder library attempts to combine these tokens into timestamps.

We measure an ASCII only version of it and a Unicode-aware version of it. Unicode is relevant here because of case insensitivity, and because the regex makes use of the character classes \s and \d, which are bigger when they're Unicode aware. We also measure the compilation time of each.

The results here can be a little tricky to interpret. Namely, it looks like backtrackers tend to do worse than automata oriented regex engines, but go/regexp uses automata and is itself quite slow here. Notice, though, that hyperscan, re2 and rust/regex do well here. While I'm less familiar with hyperscan, the explanation for re2 and rust/regex is obvious once you look at a profile: it's the lazy DFA. Both have implementations of a regex engine that build a DFA during search time, with at most one new transition (and one new state) being create per byte of haystack. In practice, most transitions get reused, which means that it tends to act like a real DFA most of the time for most regexes on most haystacks.

Compilation time of this monster regex is also all over the place. PCRE2 does the best, and Hyperscan winds up being quite slow. Once you enable Unicode mode, compilation time generally gets worse, and especially so for re2 and rust/regex. In particular, both compile byte oriented automata, which means the transitions are defined over bytes and not codepoints. That means large Unicode classes like \d tend to balloon in size, because they get converted into UTF-8 automata.

ruff-noqa

The regex benchmarked here comes from the Ruff project, which is a Python linter written in Rust. The project uses many regexes, but we pluck one out in particular that is likely to be run more frequently than the others:

(\s*)((?i:# noqa)(?::\s?(([A-Z]+[0-9]+(?:[,\s]+)?)+))?)

This is a regex that looks for # noqa annotations on each line. The noqa annotation generally causes the linter to ignore those lines with respect to warnings it emits. The regex also tries to extract annotations following the noqa that permit ignoring only specific rules in the linter.

This benchmark has a few interesting characteristics worth pointing out:

• It is line oriented, which means the haystacks it searches are likely to be small. This in turn means that the overhead of the regex engine is likely to matter more than in throughput oriented benchmarks.
• On this particular haystack (the CPython source code), the number of matches is quite small. Therefore, it is quite beneficial here to be able to have a fast path to say "there is no match" without doing any extra work. While the number of matches here is perhaps uncharacteristically small for a Python project, you would generally expect most lines to not have # noqa in them, and so the presumption of a fast rejection is probably a decent assumption for this particular regex.
• Ruff uses capturing groups to pick out parts of the match, so when a match is found, the regex engine needs to report additional information beyond just the overall match spans. The spans of each matching capture group also need to be reported.
• There are no prefix (or suffix) literals in the regex to enable any straight-forward prefilter optimizations.

With respect to the point about no prefix or suffix literals, we also include a tweaked version of the regex that removes the leading (\s*):

(?i:# noqa)(?::\s?(([A-Z]+[0-9]+(?:[,\s]+)?)+))?

In this case, the regex now starts with a literal, albeit one that is asked to match case insensitively. We can actually see pretty clearly the impact the tweaked version has on the speed for each regex engine. pcre2/jit, for example, improves its throughput from around 500 MB/s to 1.5 GB/s. go/regexp has an even more dramatic (relatively speaking) improvement.

rust/regex is a little different in that it's quite fast in both cases. The key optimization that applies for rust/regex is the "reverse inner" optimization. Even in the original regex, rust/regex will pluck out the # noqa literal and search for it case insensitively. When a candidate is found, it then searches for (\s*) in reverse to find the start position, and then finally does a standard forward search from that point to find the reverse position.

lexer-veryl

This group benchmarks a "lexer" where it combines a whole bunch of different patterns that identify tokens in a language into a single regex. It then uses capture groups to determine which branch of the alternation actually matched, and thus, which token matched. We also benchmark a variant of this that asks the regex engine to search for each pattern individually (most regex engines don't support this mode).

This is used by the Veryl project by way of the Parol parser generator. The regex was extracted by the Parol maintainers upon my request.

We use this regex to represent the "lexing" use case, where sometimes folks will build a pretty big regex with a bunch of small regexes for identifying tokens. Usually the idea is that the lexer matches literally everything in the haystack (indeed, the last branch in this regex is a . and the first is any newline), and thus these sorts of regexes tend to be quite latency sensitive. Namely, it really matters just how much overhead is involved in reporting matches. This is likely one of the reasons why most regex engines are overall pretty slow here.

The other aspect of this that's quite difficult is the sheer number of capturing groups. There's several dozen of them, which means regex engines have to keep track of a fair bit of state to handle it.

You might think this would be bad for backtrackers and good for automata engines, since automata engines are supposed to be able to handle large alternations better than backtrackers. But that's not the case here. Even for example Python's regex engine (backtracker) beats RE2 (automata). My hypothesis for why this is, is latency. Automata engines tend to have multiple engines internally and therefore tend to have higher latency, and sometimes multiple engines run to service one search. Backtrackers tend to have one engine that handles everything. But still, shouldn't the huge alternation be disastrous for the backtracker? Perhaps, unless many of the matches occur in an early branch, which is likely the case here. Namely, the second alternation matches a (single ASCII space), which is probably the most frequently occurring byte in the haystack. An automata engine that doesn't use a DFA (which might be the case here, because the regex is so big), will wind up spending a lot of time keeping track of all branches of the alternation, even if it doesn't need to explore all of them. In contrast, a backtracker will try one after the other, and if most cases match an early branch, the backtracker is likely to take less overall time.

Most regex engines are stuck in the 1 MB/s (or less) range. The regex crate and PCRE2's JIT get up to about 10 MB/s, with PCRE2 edging out the regex crate.

Note that the regex was lightly modified from the original to increase portability across different regex engines. For example, the [\s--\r\n] class was changed to [\t\v\f ].

As for the second benchmark, multiple, it uses the same patterns from each alternation in the single benchmark, but treats each one as a distinct pattern. Doing this requires explicit support for searching multiple regex patterns. (RE2's and Rust's regex crate "regex set" functionality is not enough for this, as it only reports which patterns match a haystack, and not where they match. That's partially why the rust/regex engine in this barometer actually just use the lower level meta::Regex APIs from the regex-automata crate.)

In the multiple case, the rust/regex does very well and the key reason is the abdication of capture groups as a necessary tool to determine which token matched. Namely, now we can simply use a pattern ID from the match to determine which "branch" in the original regex was taken. We no longer need to ask for or inspect capture groups. This gives a critical benefit to automata engines that support searching for multiple patterns, because it no longer requires them to use slower engines for resolving capturing groups.

cloud-flare-redos

This benchmark uses a regex that helped cause an outage at Cloudflare. This class of vulnerability is typically called a "regular expression denial of service," or "ReDoS" for short. It doesn't always require a malicious actor to trigger. Since it can be difficult to reason about the worst case performance of a regex when using an unbounded backtracking implementation, it might happen entirely accidentally on valid inputs.

The particular regex that contributed to the outage was:

(?:(?:"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|\-|\+)+[)]*;?((?:\s|-|~|!|\{\}|\|\||\+)*.*(?:.*=.*)))

As discussed in Cloudflare's post mortem, the specific problematic portion of the regex is:

.*(?:.*=.*)

Or more simply:

.*.*=.*;

We benchmark the original regex along with the simplified variant. We also split the simplified variant into one with a short haystack (about 100 bytes) and one with a long haystack (about 10,000 bytes). The benchmark results for the original and simplified short variant should be roughly similar, but the difference between the short and long variant is where things get interesting. The automata based engines generally maintain a similar throughput for both the short and long benchmarks, but the backtrackers slow way down. This is because the backtracking algorithm for this specific regex and haystack doesn't scale linearly with increases in the size of the haystack.

The purpose of this benchmark is to show a real world scenario where the use of a backtracking engine can bite you in production if you aren't careful.

We include Hyperscan in this benchmark, although it is questionable to do so. Hyperscan reports many overlapping matches from the regex used by Cloudflare because of the trailing .*, so it is probably not a great comparison. In particular, this regex was originally used in a firewall, so it seems likely that it would be used in a "is a match" or "not a match" scenario. But our benchmark here reproduces the analysis in the appendix of Cloudflare's port mortem. But the real utility in including Hyperscan here is that it demonstrates that it is not a backtracking engine. While its throughput is not as high as some other engines, it remains roughly invariant with respect to haystack length, just like other automata oriented engines.

Note that rust/regex has very high throughput here because the regex is small enough to get compiled into a full DFA. The compilation process also "accelerates" some states, particularly the final .*. This acceleration works by noticing that almost all of the state's transitions loop back on itself, and only a small number transition to another state. The final .* for example only leaves its state if it sees the end of the haystack or a \n. So the DFA will actually run memchr on \n and skip right to the end of the haystack.

unicode-character-data

This regex parses data from UnicodeData.txt, which is part of the Unicode Character Database. This regex was extracted from the ucd-parse crate, which is part of the ucd-generate project.

This benchmark works by iterating over every line in the haystack and then running the regex on each line. Every line matches the regex, so regex engines that attempt to do some extra work to reject non-matches quickly will get penalized. For example, rust/regex looks for a semi-colon first via its "reverse inner" optimization, since a semi-colon is a required part of the regex. But this optimization is just extra work here. Indeed, disabling it will improve the thoughput of rust/regex on this benchmark.

pcre2/jit does remarkably well here, and these types of regexes are one of the many things that pcre2/jit does quickly compared to most other regex engines.

We also include compilation time for this regex, where PCRE2 again does quite well.

words

This benchmark measures how long it takes for a regex engine to find words in a haystack. We compare one regex that finds all words, \b\w+\b and another regex that only looks for longer words, \b\w{12,}\b. We also compare ASCII regexes on English text with Unicode regexes on Russian text.

The split between finding all words and finding only long words tends to highlight the overhead of matching in each regex engine. Regex engines that are quicker to get in and out of its match routine do better at finding all words than regex engines that have higher overhead. For example, regress is faster than rust/regex on all-english, but substantially slower than rust/regex on long-english. This is likely because rust/regex is doing more work per search call than regress, which is in part rooted in the optimizations it performs to gain higher throughput.

Otherwise, pcre2/jit does quite well here across the board, but especially on the Unicode variants. When comparing it against rust/regex for example, it is substantially faster. In the case of rust/regex, its faster DFA oriented engines cannot handle the Unicode aware \b on non-ASCII haystacks, and this causes rust/regex to use a slower internal engine. It's so slow in fact that python/re and python/regex are both faster than rust/regex for the Unicode benchmarks. For the ASCII long-english benchmark, rust/regex and re2 both do well because most of the time is spent in its lazy DFA, which has pretty good throughput performance when compared to a pure backtracker.

Note that several regex engines can't be used in the Unicode variants because either they don't support a Unicode aware \w or because they don't support a Unicode aware \b (or both).

aws-keys

This measures a regex for detecting AWS keys in source codeaws-key-blog. In particular, to reduce false positives, it looks for both an access key and a secret key within a few lines of one another.

We also measure a "quick" version of the regex that is used to find possible candidates by searching for things that look like an AWS access key.

The measurements here demonstrate why the pypi-aws-secrets project splits this task into two pieces. First it uses the "quick" version to identify candidates, and then it uses the "full" version to lower the false positive rate of the "quick" version. The "quick" version of the regex runs around an order of magnitude faster than the "full" version across the board. To understand why, let's look at the "quick" regex:

((?:ASIA|AKIA|AROA|AIDA)([A-Z0-7]{16}))

Given this regex, every match starts with one of ASIA, AKIA, AROA or AIDA. This makes it quite amenable to prefilter optimizations where a regex engine can look for matches of one of those 4 literals, and only then use the regex engine to confirm whether there is a match at that position. Some regex engines will also notice that every match starts with an A and use memchr to look for occurrences of A as a fast prefilter.

We also include compilation times to give an idea of how long it takes to compile a moderately complex regex, and how that might vary with the compilation time of a much simpler version of the regex.

Note that in all of the measurements for this group, we search the CPython source code (concatenated into one file). We also lossily convert it to UTF-8 so that regex engines like regress can participate in this benchmark. (The CPython source code contains a very small amount of invalid UTF-8.)

bounded-repeat

This group of benchmarks measures how well regex engines do with bounded repeats. Bounded repeats are sub-expressions that are permitted to match up to some fixed number of times. For example, a{3,5} matches 3, 4 or 5 consecutive a characters. Unlike unbounded repetition operators, the regex engine needs some way to track when the bound has reached its limit. For this reason, many regex engines will translate a{3,5} to aaaa?a?. Given that the bounds may be much higher than 5 and that the sub-expression may be much more complicated than a single character, bounded repeats can quickly cause the underlying matcher to balloon in size.

We measure three different types of bounded repeats:

• A search for a number of consecutive letters, both ASCII only and Unicode aware.
• A search for certain types of words surrounding a Result type in Rust source code.
• A search for consecutive words, all beginning with a capital letter.

We also include measurements for the compilation time of the last two.

Hyperscan does unusually well here, particularly for an automata oriented engine. It's plausible that it has some specific optimizations in place for bounded repeats.

rust/regex slows down quite a bit on the context regex. Namely, the context regex is quite gnarly and its (?s:.) sub-expression coupled with the bounded repeat causes a large portion of its transition table to get filled out. This in turn results in more time than usual being spent actually building the lazy DFA's transition table during a search. Typically, the lazy DFA's transition table is built pretty quickly and then mostly reused on subsequent searches. But in this case, the transition table exceeds the lazy DFA's cache capacity and results in the cache getting cleared. However, the rate at which new transitions are created is still low enough that the lazy DFA is used instead of falling back to a slower engine.

unstructured-to-json

These benchmarks come from a task that converts unstructured log data to structured JSON data. It works by iterating over every line in the log file and parsing various parts of each line into different sections using capture groups. The regex matches every line, so any fast logic design to reject non-matches will generally penalize regex engines here.

The original regex looks like this:

(?x)
^
(?P<timestamp>[^\ ]+\ [^\ ]+)

[\ ](?P<level>[DIWEF])[1234]:[\ ]

(?P<header>
    (?:
        (?:
            \[ [^\]]*? \] | \( [^\)]*? \)
        ):[\ ]
    )*
)

(?P<body>.*?)

[\ ]\{(?P<location>[^\}]*)\}
$

(The actual regex is flattened since not all engines support verbose mode. We also remove the names from each capture group.)

pcre2/jit does really well here. I'm not personally familiar with how PCRE2's JIT works, but if I had to guess, I'd say there are some clever optimizations with respect to the [^ ]+ (and similar) sub-expressions in this regex.

Otherwise, the backtracking engines generally outperform the automata engines in this benchmark. Interestingly, all of re2, go/regexp and rust/regex principally use their own bounded backtracking algorithms. But it looks like "proper" backtrackers tend to be better optimized than the ones found in RE2 and its descendants. (Bounded backtracking does have to pay for checking that no combination of haystack position and NFA state is visited more than once, but even removing that check does not bring, e.g., rust/regex up to speeds similar to other backtrackers.)

dictionary

This benchmark highlights how well each regex engine does searching for a small dictionary of words. The dictionary is made up of about 2,500 words, where every word is at least 15 bytes in length. The number of words was chosen to be small enough that most regex engines can execute a search in reasonable time. The bigger minimum length of each word was chosen in order to make this a throughput benchmark. That is, there is only one match found here, so this benchmark is measuring the raw speed with which an engine can handle a big alternation of plain literals.

Most regex engines run quite slowly here. perl, re2 and rust/regex lead the pack with throughput measured in MB/s, while the rest are measured in KB/s. One might think that this is a benchmark that would manifest as a bright dividing line between finite automata engines and backtracking engines. Namely, finite automata engines should handle all of the alternations in "parallel," where as backtrackers will essentially try to match each alternate at each position in the haystack (owch). Indeed, this seems mostly true, but perl (a backtracker) does quite well while go/regexp (a finite automata engine) does quite poorly. Moreover, what explains the differences between perl, re2 and rust/regex?

There are several knots to untangle here.

First, we'll tackle the reason why go/regexp has a poor showing here. The answer lies in how the Thompson NFA construction works. A Thompson NFA can be built in worst case linear time (in the size of the pattern), but in exchange, it has epsilson transitions in its state graph. Epsilon transitions are transitions in a finite state machine that are followed without consuming any input. In a case like foo|bar|quux, you can think of the corresponding Thompson NFA (very loosely) as creating a single starting state with three epsilon transitions to each of foo, bar and quux. In a Thompson NFA simulation (i.e., a regex search using a Thompson NFA), all of these epsilon transitions have to be continually followed at every position in the haystack. With a large number of alternations, the amount of time spent shuffling through these epsilon transitions can be quite enormous. While the search time remains linear with respect to the size of the haystack, the "constant" factor here (i.e., the size of the regex pattern) can become quite large. In other words, a Thompson NFA scales poorly with respect to the size of the pattern. In this particular case, a Thompson NFA just doesn't do any better than a backtracker.

The second knot to untangle here is why perl does so well despite being a backtracker. While I'm not an expert on Perl internals, it appears to do well here because of something called a trie optimization. That is, Perl's regex engine will transform large alternations like this into an equivalent but much more efficient structure by essentially building a trie and encoding it into the regex itself. It turns out that rust/regex does the same thing, because the exact same optimization helps a backtracker in the same way it helps a Thompson NFA simulation. The optimization exploits the fact that the branches in the alternation are not truly independent and actually share a lot of overlap. Without the optimization, the branches are treated as completely independent and one must brute force their way through each one.

So what does this trie optimization look like? Consider a regex like zapper|z|zap. There is quite a bit of redundant structure. With some care, and making sure to preserve leftmost-first match semantics, it can be translated to the equivalent pattern z(apper||ap). Notice how in the pattern we started with, the alternation needs to be dealt with for every byte in the haystack, because you never know which branch is going to match, if any. But in the latter case, you now don't even need to consider the alternation until the byte z matches, which is likely to be quite rare.

Indeed, the algorithm for constructing such a pattern effectively proceeds by building a trie from the original alternation, and then converting the trie back to whatever intermediate representation the regex engine uses.

The last knot to untangle is to explain the differences between perl, re2 and rust/regex. Perl still uses a backtracking strategy, but with the trie optimization described above, it can try much fewer things for each position in the haystack. But what's going on with re2 and rust/regex? In this case, re2 uses the Thompson NFA simulation, but re2 does not use the trie optimization described above, so it gets stuck in a lot epsilon transition shuffling. Finally, rust/regex does the trie optimization and uses its lazy DFA internally for this case. re2 probably could too, but both libraries use various heuristics for deciding which engine to use. In this case, the regex might be too big for re2 to use its lazy DFA.

OK, that wraps up discussion of the single benchmark. But what is the multi benchmark? Where single represents combining all words in the dictionary into a single pattern, multi represents a strategy where each word is treated as its own distinct pattern. In the single case, Hyperscan actually rejects the pattern for being too large, but is happy to deal with it if each word is treated as its own pattern. The main semantic difference between these strategies is that the multi approach permits not only identifying where a match occurred, but which word in the dictionary matched. And this is done without using capture groups.

Hyperscan does really well here. While its source code is difficult to penetrate, my understanding is that Hyperscan uses its "FDR" algorithm here, which is essentially SIMD-ified variant of multi-substring Shift-Or. This benchmark represents Hyperscan's bread and butter: multi-pattern search.

rust/regex actually does worse in the multi case versus the single case. rust/regex's support for multi-pattern search is still young, and in particular, the multi-pattern case currently inhibits the trie optimization discussed above.

Finally, we also include compile-time benchmarks for each of the above cases in order to give an idea of how long it takes to build a regex from a dictionary like this. I don't have much to say here other than to call out the fact that the trie optimization does have a meaningful impact on regex compile times in the rust/regex case at least.

noseyparker

This benchmark measures how well regex engines do when asked to look for matches for many different patterns. The patterns come from the Nosey Parker project, which finds secrets and sensitive information in textual data and source repositories. Nosey Parker operates principally by defining a number of rules for detecting secrets (for example, AWS API keys), and then looking for matches of those rules in various corpora. The rules are, as you might have guessed, defined as regular expressions.

I went through each of its rules and extracted a total of 96 regular expressions, as of commit be8c26e8. These 96 regexes make up the single and multi benchmarks below, with single corresponding to joining all of patterns into one big alternation and multi corresponding to treating each pattern as its own regex. In the latter case, only the rust/regex and hyperscan engines are measured, since they are the only ones to support multi-regex matching.

This is a particularly brutal benchmark. Most regex engines can't deal with it at all, and will either reject it at compilation time for being too big or simply take longer than we're willing to wait. (rebar imposes a reasonable timeout for all benchmarks, and if the timeout is exceeded, no measurements are collected.)

Hyperscan is in its own class here. Hyperscan was purpose built to deal with the multi-pattern use case, and it deals with it very well here. The specific patterns also put this in its wheelhouse because they all have some kind of literal string in them. Hyperscan uses a literal searching and finite automata decomposition strategy to quickly identify candidate matches and avoids doing redundant work. Although how it all fits together and avoids pitfalls such as worst case quadratic search time doesn't appear to be written down anywhere.

rust/regex just barely does serviceably here. It uses its lazy DFA to handle this regex, but with the default cache sizes, profiling suggests that it is spending a lot of its time building the DFA. It's plausible that increasing the cache size for such a big regex would let it execute searches faster.

pcre2/jit doesn't do as well here, but one might expect that because it is a backtracking engine. With that said, no other backtracking engine could deal with this regex at all, so pcre2/jit is doing quite well relative to other backtracking engines.

Finally, we also include compile time benchmarks for each of the single and multi cases to give a general sense of how long this monster regex takes to build.

quadratic

This set of benchmarks is meant to convince you that, even if you use a regex engine that purports to guarantee worst case linear time searches, it is likely possible to use it in a way that results in worst case quadratic time!

The regex we use here is .*[^A-Z]|[A-Z] and the haystack we search is the letter A repeated 100, 200 and 1000 times. There are two key insights to understanding how this results in quadratic behavior:

1. It requires one to iterate over all matches in a haystack. Some regex engines (e.g., rust/regex and go/regexp) provide first class APIs for such an operation. They typically handle the pathological case of an empty match for you, which would result in an infinite loop in naively written code. Some regex engines (e.g., pcre2 and re2) do not provide any APIs for iterating over all matches. Callers have to write that code themselves. The point here is that a regex search is executed many times for a haystack.
2. Because of how leftmost-first match semantics work, a regex engine might scan all the way to the end of a haystack before reporting a match that starts and ends at the beginning of the haystack. The reason for this is that most regex engines will, by default, greedily consume as much as possible.

Quadratic behavior occurs by exploiting both of the insights above: by crafting a regex and a haystack where every search scans to the end of the haystack, but also that every search reports a match at the beginning of the search that is exactly one character long.

Indeed, this is exactly what the regex .*[^A-Z]|[A-Z] does on a haystack like AAAAA. Leftmost-first match semantics says that if there are multiple matches that occur at the same position, then the match generated "first" by the pattern should be preferred. In this case, .*[^A-Z] is preferred over [A-Z]. But since .* matches as much as possible, it is not actually known whether that branch matches until the regex engine reaches the end of the haystack and realizes that it cannot match. At that point, the match from the second branch, [A-Z] corresponding to the first A, is reported. Since we're iterating over every match, the search advances to immediately after the first A and repeats the same behavior: scanning all the way to the end of the haystack, only to discover there is no match, and then reporting the second A as the next match. This repeats itself, scanning the entire haystack a number of times proportional to n^2, where n is the length of the haystack.

It is important to note that in a finite automata oriented regex engine, the fact that [A-Z] matches at the beginning of the haystack is known after the regex engine scans that part of the haystack. That is, its internal state is aware of the fact that a match exists. It specifically continues searching because leftmost-first semantics demand it. Once it reaches the end of the haystack (or a point at which no other match could occur), then it stops and returns the most recent match that it found. Unlike a backtracker, it does not need to go back to the beginning of the haystack and start looking for a match of the second branch.

Given the semantics of leftmost-first matching, there is no way to avoid this. It is, unfortunately, just how the cookie crumbles.

With all of that said, hyperscan is the one regex engine that manages to maintain the same throughput for each of the 1x, 2x and 10x benchmarks. That is, it does not exhibit worst case quadratic behavior here. It retains its linear search time. How does it do it? The secret lay in the fact that Hyperscan doesn't implement leftmost-first match semantics. (Indeed, this is why some of its match counts differ throughout the benchmarks in rebar.) Instead, Hyperscan reports a match as soon as it is seen. Once a match is found, it doesn't continue on to try and greedily match the regex. For example, the regex \w+ will report 5 matches in the haystack aaaaa, where as for most other regex engines, only one match will be reported. This means hyperscan can zip through this benchmark in one pass of the haystack.

The rust/regex engine can also do this, but requires dropping down to the regex-automata crate and using Input::new(haystack).earliest(true) when running a search. This instructs the regex engine to report matches as they're seen, just like Hyperscan. Indeed, if the rust/regex runner program uses this approach, then its throughput remains constant for the 1x, 2x and 10x benchmarks, just like for Hyperscan.

Credit goes to this bug filed against the go/regexp engine for making me aware of this issue.

Note: We use [A-Z] in this example instead of A in an attempt to subvert any sort of literal optimizations done by the regex engine.