Regular Expression Benchmark Corpus

There is no standard benchmark for regular expression engines. I have been looking for one since 2006, when the FIRE/J evaluation made do with a dump of regexlib.com, and the engines I have read about since were each measured on a workload of their own; a novel, a dozen patterns, random text, a rule set. This is my attempt at one. It keeps patterns that people actually wrote and generates the inputs, so that the thing a matcher's cost depends on (how far it walks) is set rather than left to chance.

The current version is rc-2026.10: 2,393 patterns and 15,534 inputs, and a small corpus of 281 patterns and 1,874 inputs that is a subset of it. It is not released yet, so this page describes the benchmark and the method behind it.

Why generate the inputs

The pattern collections in use come with one sample string per pattern, written for another purpose: the example a regexlib.com contributor attached to an entry, or the text a regex101.com user typed into the tester. The patterns are a fair sample of what people write. The strings are not a fair input, and the reason is mechanical; an automaton pays for every character it reads, so the length of its walk decides the time, and the sample string fixes that length by accident. Over every eligible pattern of the two dumps, matched from the first character:

The two are not even alike. regexlib.com's samples are short positive examples, and nine in ten match in full. regex101.com's are texts written to be searched, so a match that starts at the first character dies at once on almost a third of them, and a benchmark that times those rows times one transition and the cost of a call. I saw it in my own numbers before I measured it: in the ten-engine rerun of the FIRE/J benchmark, FIRE/J led dk.brics.automaton by 1.3 times on the 2007 dump and was level on regex101. When the walk is one character long, there is nothing left for the faster walker to win.

So the corpus keeps the found patterns and makes the inputs an instrument.

What is in it

The patterns come from three sources:

Each pattern gets up to nine inputs, and every input asks one question: does the whole of it match? In the full corpus:

• Accepted strings are drawn uniformly from the strings of the pattern's language that have that length, and all 6,734 of them match in full. Fewer patterns have the longer ones because 39% of the languages are finite and their strings run out; the generator then takes the nearest length the language has, and never the same length twice.
• Rejections are a prefix that can still be completed to a match, drawn uniformly among the prefixes of the target length, followed by a character the automaton has no transition for. A walk over one consumes exactly the target and stops, which holds for all 7,499 of them. A rejection after 0 characters is the cost of a call and nothing else.
• Found inputs are the sample the source supplied, truncated to 512 characters and labelled, so that the corpus also carries what earlier evaluations measured.

The rows come as two tab-separated files. patterns.tsv has one row per pattern: its stratum and weight, its sources (and for a production regex, the registries and number of modules that use it), the size of its minimal automaton, whether its language is finite, its anchors and syntactic features, and the pattern itself. inputs.tsv has one row per input: kind, target, length, how many characters a walk consumes, whether the whole input matches, the reference's verdict, the annotations described further down, and the input. A third file holds the same rows as pattern<TAB>input, ready for a harness.

How it is built

One program builds it in six stages, each reading the previous stage's file, so that any stage can be rerun and checked on its own.

1. Ingest. The three sources, deduplicated by exact text (894 duplicates) and capped at 1,000 characters (809 longer ones dropped).
2. Classify. java.util.regex is the reference dialect. A pattern is eligible if the JDK compiles it and its minimal DFA (deterministic finite automaton), built with dk.brics.automaton through FIRE/J's translation of the Java dialect, has at most 10,000 states and is built within five seconds. What falls out is mostly what an automaton cannot express: anchors in the middle of a pattern, lookaround and inline flags, word boundaries, backreferences. 451,127 of the 545,495 distinct patterns are eligible.
3. Select. The eligible patterns fall into fifteen strata, three sources by five automaton sizes (1–3, 4–15, 16–63, 64–255, and 256 or more states). Each stratum is shuffled with a fixed seed, and the order is the draw. The full corpus takes the first 200 patterns of each draw that survive the next two stages (or all of a smaller stratum), the small corpus the first 20, which is why one is a subset of the other. Stratifying puts large automata in on purpose, and each pattern carries a weight, its stratum's population over its sample, for anyone who wants the population back; a production pattern of 4 to 15 states stands for 1,131.
4. Generate. For accepted strings the generator counts, for every state and every remaining length, how many accepted strings there are, and walks the automaton choosing each transition in proportion, so every string of the target length is equally likely. Rejections draw their prefix the same way. The alphabet is kept readable: a transition offers the printable ASCII characters it allows, failing those tab, newline and carriage return, failing those one representative. Without that rule a . would draw from 65,535 characters, and almost no input would be printable.
5. Check. Every input goes to java.util.regex with a one-second deadline. An accepted string must match. A rejection must not, and its prefix must still be viable: it matches, or the matcher ran into the end of the input. One contradicted input drops the whole pattern, since its automaton is then not the reference's language, and the next pattern in the draw takes its place; 50 of the 2,443 drawn were dropped.
6. Annotate and export. Without regenerating anything, record what an engine that asks a different question would see (below), and for each pattern the size of the automaton a search has to walk.

The check earned its keep before the corpus existed. The first build rejected far more patterns than this one, and three of the causes were bugs in the translation, which I had taken from FIRE/J: the dot excluded only a newline, where Java's excludes every line terminator; an empty alternative, as in a||b or (|x), reached the automaton library as a literal bar; and a possessive quantifier was dropped as if it did not change the language, which it does (a*+a matches nothing in Java). The first two are fixed, the third is refused, and FIRE/J took the same corrections. The 50 patterns dropped now use constructs the translation still reads differently from Java: a class nested inside a class, a POSIX bracket class such as [[:digit:]], and one \x{…} escape.

The seed, the strata and the quotas are fixed in the build before anything is measured, and changing any of them makes a new version. The two large sources are fetched by a script that checks them against the checksums the corpus was built from, and a manifest lists the checksum of every corpus file. The build is Python with its standard library; the generator is Java 21 on dk.brics.automaton.

Measuring with it

• Ask whether the whole input matches. Earliest, leftmost-first and leftmost-longest engines give the same answer to that question, because a match of the whole input has only one span, so a backtracking engine, a DFA and a POSIX matcher can all take part in every row. That is matches() in Java, a full match in RE2, \A(?:p)\z in Go, and ^(p)$ with a match spanning the input for regexec.
• Report by kind and target, not as one median. The rejections after 0 characters give the cost of a call, the other rows give cost against walk length, and the found inputs give continuity with earlier benchmarks.
• An engine that asks something else reads the annotations. Each input records where the shortest, the leftmost-first and the longest match from the first character end, and where a search finds its first match. An engine that matches a prefix bins its rows by the end its semantics reports; one that searches finds a match in about one rejection in five.
• Another dialect sets some rows aside. The verdicts are Java's, and 18% of the rejections stop on a line terminator, which Java's dot excludes in five forms, RE2's in one, and a POSIX dot without REG_NEWLINE in none. Each input names the character its walk stops on and lists the line terminators it contains.
• Apply the weights for figures about the population of patterns rather than about the strata.
• Use the small corpus for development and for engines too slow for the full one. Since it is a subset, a result on it can be checked against the full corpus later.

My own harness, the one behind the ten-engine table on the FIRE/J page, reads the export as it is. It runs every engine in a process of its own, compiles each pattern five times and keeps the median, warms each pattern up until its per-call time is steady, and then times at least 20 ms of calls. A pattern whose first call takes longer than 20 ms is timed three times and flagged, so that a backtracking blow-up is recorded rather than dropped. Its report still gives one distribution per corpus, though; breaking it down by kind and target is the next thing it needs.

Where it stops

• It times recognition, not search. Every input is matched from its first character. The automaton a search needs is recorded but never walked, and it can be far bigger: 3[0-9]{9} has 11 states, and its search automaton 1,024. An engine built around a literal prefilter is measured here without its advantage.
• No submatches. Capture groups are where a POSIX matcher pays, and nothing here asks for them.
• Regular patterns only. Backreferences and lookaround are left out, although the engines that support them would want them measured. That needs a different generator.
• One translation, one reference. A defect the two share would pass. For 97 rejections (1.3%) Java agrees with the verdict but cannot confirm that no longer input would match, because the matcher looked at the end of the input, as a trailing $ makes it do; those rows are labelled. Eight inputs Java could not decide within a second are kept and labelled too, because the slow inputs of a backtracking engine belong in a benchmark.
• Readable, not realistic. The inputs are uniform over a readable alphabet, not drawn from the text an application sees. They control the walk at the price of realism, which is why the found inputs stay.
• The patterns are their sources'. regexlib.com in 2007, the drafts people typed into regex101.com, and the production regexes of 2019, all read as Java reads them. A pattern written for another dialect is kept only if Java accepts it, and then it means what Java says it means.

Status

The corpus, its generator and its build are in one repository, private while I finish it, so there is nothing to download yet.

Related

• FIRE/J, whose translation of the Java dialect builds the automata here, and whose 2008 benchmark the harness reproduces.
• The FIRE/J paper (Software: Practice and Experience, 2008), whose regexlib.com dump is one of the three sources.
• The 2006 benchmark utility, the first attempt.
• Regular Expression Complexity, the tool for the size and length measures the harness also reports for every pattern.