https://github.com/BurntSushi/rebar Skip to content Toggle navigation Sign up * Product + Actions Automate any workflow + Packages Host and manage packages + Security Find and fix vulnerabilities + Codespaces Instant dev environments + Copilot Write better code with AI + Code review Manage code changes + Issues Plan and track work + Discussions Collaborate outside of code Explore + All features + Documentation + GitHub Skills + Blog * Solutions For + Enterprise + Teams + Startups + Education By Solution + CI/CD & Automation + DevOps + DevSecOps Case Studies + Customer Stories + Resources * Open Source + GitHub Sponsors Fund open source developers + The ReadME Project GitHub community articles Repositories + Topics + Trending + Collections * Pricing [ ] * # In this repository All GitHub | Jump to | * No suggested jump to results * # In this repository All GitHub | Jump to | * # In this user All GitHub | Jump to | * # In this repository All GitHub | Jump to | Sign in Sign up You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. {{ message }} BurntSushi / rebar Public * Notifications * Fork 0 * Star 62 A biased barometer for gauging the relative speed of some regex engines on a curated set of tasks. License Unlicense license 62 stars 0 forks Star Notifications * Code * Issues 0 * Pull requests 2 * Discussions * Actions * Security * Insights More * Code * Issues * Pull requests * Discussions * Actions * Security * Insights BurntSushi/rebar This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. master Switch branches/tags [ ] Branches Tags Could not load branches Nothing to show {{ refName }} default View all branches Could not load tags Nothing to show {{ refName }} default View all tags Name already in use A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch? Cancel Create 3 branches 0 tags Code * Local * Codespaces * Clone HTTPS GitHub CLI [https://github.com/B] Use Git or checkout with SVN using the web URL. [gh repo clone BurntS] Work fast with our official CLI. Learn more about the CLI. * Open with GitHub Desktop * Download ZIP Sign In Required Please sign in to use Codespaces. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching Xcode If nothing happens, download Xcode and try again. Launching Visual Studio Code Your codespace will open once ready. There was a problem preparing your codespace, please try again. Latest commit @BurntSushi BurntSushi readme: update regex crate version ... 0203f1a Jul 5, 2023 readme: update regex crate version This modifies the version of the regex crate benchmarked from 1.8.4 to 1.9.0. When data was collected, the purported version was indeed 1.8.4, but the actual code being measured was effectively 1.9.0. It's just that 1.9.0 hadn't actually been released yet. But now it has. 0203f1a Git stats * 173 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time .vim engines: add rust/regex/lite engine April 29, 2023 08:48 benchmarks benchmarks/opt: add new nfa-sparse optimization July 1, 2023 14:22 byob byob: remove temporary csv measurements April 17, 2023 10:37 engines engines: remove crates.io patches July 5, 2023 08:56 record readme: update regex crate version July 5, 2023 08:58 scripts scripts: add clarifying comment July 1, 2023 14:31 shared shared/klv: tweak KLV output April 16, 2023 22:43 src report: add note about pairwise comparisons May 5, 2023 08:18 .gitignore main: initial version of rebar March 7, 2023 09:57 BIAS.md doc: note repetitive execution in BIAS April 6, 2023 21:06 BUILD.md doc: make some parts of BUILD instructions clearer April 15, 2023 14:38 BYOB.md doc: touchups for BYOB April 17, 2023 10:39 CONTRIBUTING.md doc: various fixups to CONTRIBUTING.md April 12, 2023 08:31 Cargo.lock deps: update everything March 20, 2023 12:01 Cargo.toml engines: add rust/regex/lite engine April 29, 2023 08:48 FORMAT.md doc: small clarification on format July 5, 2023 08:46 KLV.md main: initial version of rebar March 7, 2023 09:57 METHODOLOGY.md doc: touchups to METHODOLOGY April 6, 2023 21:59 MODELS.md doc: updates to MODELs and .NET README March 25, 2023 20:46 README.md readme: update regex crate version July 5, 2023 08:58 TUTORIAL.md doc: fix table of contents link in TUTORIAL April 16, 2023 22:42 UNLICENSE initial commit January 27, 2023 07:50 WANTED.md doc: a variety of other touchups April 6, 2023 08:07 build.rs cli: add 'rebar version' command and record it in measurements April 11, 2023 14:33 rustfmt.toml initial commit January 27, 2023 07:50 View code [ ] rebar Links Results Summary Summary of search-time benchmarks Summary of compile-time benchmarks Benchmark Groups 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 README.md 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 [?][?][?]Iaeeiuabgdezethiklmnxoprsstuphkhpsoiuouo[?]stwqsp[?][?][?][?][?]Iaee 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:[?][?][?]Iaeeiuabgdezethiklmnxoprsstuphkhpsoiuouo[?]stwqsp[?][?][?][?][?]Iaee 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 Engine Version Geometric mean of speed Benchmark ratios count hyperscan 5.4.2 2.03 28 2023-04-22 rust/regex 1.9.0 2.70 38 pcre2/jit 10.42 5.26 34 2022-12-11 dotnet/compiled 7.0.7 6.24 34 re2 2023-07-01 9.03 31 dotnet/ 7.0.7 10.13 29 nobacktrack javascript/v8 20.3.0 12.27 30 regress 0.6.0 30.48 30 python/regex 2023.6.3 36.43 34 java/hotspot 20.0.1+9-29 37.07 34 python/re 3.11.3 37.08 33 perl 5.36.1 44.47 33 icu 72.1.0 46.06 34 go/regexp 1.20.5 69.36 31 pcre2 10.42 102.16 33 2022-12-11 rust/regex/lite 0.1.0 134.78 28 Summary of compile-time benchmarks Engine Version Geometric mean of speed Benchmark ratios count pcre2 10.42 1.40 10 2022-12-11 rust/regex/lite 0.1.0 2.17 10 icu 72.1.0 2.92 11 regress 0.6.0 3.03 8 go/regexp 1.20.5 5.06 10 pcre2/jit 10.42 5.50 11 2022-12-11 re2 2023-07-01 10.84 10 rust/regex 1.9.0 10.97 14 dotnet/compiled 7.0.7 19.40 10 python/re 3.11.3 32.63 11 python/regex 2023.6.3 90.04 11 dotnet/ 7.0.7 131.50 6 nobacktrack hyperscan 5.4.2 441.82 7 2023-04-22 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. Engine sherlock-en sherlock-casei-en sherlock-ru sherlock-casei-ru sherlock-zh dotnet/ 14.2 GB/s 6.1 GB/s 22.9 GB/s 5.0 GB/s 35.2 GB/s compiled dotnet/ 7.8 GB/s 4.1 GB/s 7.3 GB/s 2.5 GB/s 24.8 GB/s nobacktrack go/regexp 4.1 GB/s 47.7 MB/s 2.1 GB/s 34.2 MB/s 2.0 GB/s hyperscan 29.9 GB/s 29.0 GB/s 4.3 GB/s 7.4 GB/s 50.3 GB/s icu 1597.2 MB/s 451.4 MB/s 3.0 GB/s 282.1 MB/s 4.2 GB/s java/ 2.4 GB/s 282.1 MB/s 3.5 GB/s 224.6 MB/s 5.2 GB/s hotspot javascript/ 6.1 GB/s 2.9 GB/s 40.6 GB/s 3.3 GB/s 10.5 GB/s v8 pcre2 6.9 GB/s 745.7 MB/s 2.1 MB/s 2027.2 KB/s 56.8 MB/s pcre2/jit 26.0 GB/s 16.8 GB/s 32.0 GB/s 18.9 GB/s 36.2 GB/s perl 2.9 GB/s 560.5 MB/s 3.4 GB/s 102.6 MB/s 7.2 GB/s python/re 3.7 GB/s 345.8 MB/s 6.5 GB/s 507.7 MB/s 9.0 GB/s python/ 3.1 GB/s 2.8 GB/s 4.5 GB/s 3.9 GB/s 6.8 GB/s regex re2 12.2 GB/s 2.5 GB/s 768.1 MB/s 948.0 MB/s 2.8 GB/s regress 3.3 GB/s 1163.4 MB/s 3.4 GB/s 316.7 MB/s 3.4 GB/s rust/regex 31.5 GB/s 10.0 GB/s 31.3 GB/s 8.7 GB/s 40.3 GB/s rust/regex/ 76.0 MB/s 55.9 MB/s 119.6 MB/s - 166.5 MB/s lite rust/ 32.4 GB/s 8.0 GB/s 33.4 GB/s 6.6 GB/s 39.9 GB/s regexold Show individual benchmark parameters. sherlock-en Parameter Value full name curated/01-literal/sherlock-en model count regex Sherlock Holmes case-insensitive false unicode false haystack-path opensubtitles/en-sampled.txt count(.*) 513 sherlock-casei-en Parameter Value full name curated/01-literal/sherlock-casei-en model count regex Sherlock Holmes case-insensitive true unicode false haystack-path opensubtitles/en-sampled.txt count(.*) 522 sherlock-ru Parameter Value full name curated/01-literal/sherlock-ru model count regex Sherlok Kholms case-insensitive false unicode true haystack-path opensubtitles/ru-sampled.txt count(.*) 724 sherlock-casei-ru Parameter Value full name curated/01-literal/sherlock-casei-ru model count regex Sherlok Kholms case-insensitive true unicode true haystack-path opensubtitles/ru-sampled.txt count(.*) 746 rust/regex/lite is not included because it doesn't support Unicode-aware case insensitive matching. sherlock-zh Parameter Value full name curated/01-literal/sherlock-zh model count regex Xia Luo Ke *Fu Er Mo Si case-insensitive false unicode true haystack-path opensubtitles/zh-sampled.txt count(.*) 30 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.) Engine sherlock-en sherlock-casei-en sherlock-ru sherlock-casei-ru sherlock-zh dotnet/ 3.7 GB/s 453.7 MB/s 2.2 GB/s 780.1 MB/s 16.9 GB/s compiled dotnet/ 2.6 GB/s 374.5 MB/s 1012.0 MB/s 299.6 MB/s 12.1 GB/s nobacktrack go/regexp 24.7 MB/s 15.5 MB/s 32.7 MB/s 9.1 MB/s 45.9 MB/s hyperscan 13.9 GB/s 13.4 GB/s 4.6 GB/s 4.0 GB/s 19.8 GB/s icu 630.6 MB/s 113.3 MB/s 168.1 MB/s 106.7 MB/s 337.3 MB/s java/ 69.3 MB/s 64.0 MB/s 120.1 MB/s 55.4 MB/s 175.1 MB/s hotspot javascript/ 691.6 MB/s 670.0 MB/s 942.0 MB/s 596.7 MB/s 6.7 GB/s v8 pcre2 840.8 MB/s 154.8 MB/s 1737.5 KB/s 1621.4 KB/s 8.6 MB/s pcre2/jit 1510.3 MB/s 654.6 MB/s 1188.7 MB/s 296.6 MB/s 2.5 GB/s perl 1090.6 MB/s 114.8 MB/s 135.4 MB/s 75.3 MB/s 220.4 MB/s python/re 420.4 MB/s 42.8 MB/s 315.3 MB/s 57.6 MB/s 635.9 MB/s python/ 304.1 MB/s 67.8 MB/s 305.1 MB/s 91.5 MB/s 872.6 MB/s regex re2 926.4 MB/s 925.2 MB/s 936.1 MB/s 924.6 MB/s 966.5 MB/s regress 1533.5 MB/s 273.1 MB/s 245.5 MB/s 108.4 MB/s 241.7 MB/s rust/regex 12.5 GB/s 2.9 GB/s 6.5 GB/s 1528.4 MB/s 12.6 GB/s rust/regex/ 32.9 MB/s 23.1 MB/s 52.0 MB/s - 72.2 MB/s lite rust/ 14.3 GB/s 2.7 GB/s 3.0 GB/s 448.4 MB/s 18.8 GB/s regexold Show individual benchmark parameters. sherlock-en Parameter Value full name curated/02-literal-alternate/sherlock-en model count regex Sherlock Holmes|John Watson|Irene Adler|Inspector Lestrade|Professor Moriarty case-insensitive false unicode false haystack-path opensubtitles/en-sampled.txt count(.*) 714 sherlock-casei-en Parameter Value full name curated/02-literal-alternate/sherlock-casei-en model count regex Sherlock Holmes|John Watson|Irene Adler|Inspector Lestrade|Professor Moriarty case-insensitive true unicode false haystack-path opensubtitles/en-sampled.txt count(.*) 725 sherlock-ru Parameter Value full name curated/02-literal-alternate/sherlock-ru model count regex Sherlok Kholms|Dzhon Uotson|Iren Adler|inspektor Lestreid|professor Moriarti case-insensitive false unicode true haystack-path opensubtitles/ru-sampled.txt count(.*) 899 sherlock-casei-ru Parameter Value full name curated/02-literal-alternate/sherlock-casei-ru model count regex Sherlok Kholms|Dzhon Uotson|Iren Adler|inspektor Lestreid|professor Moriarti case-insensitive true unicode true haystack-path opensubtitles/ru-sampled.txt count(.*) 971 rust/regex/lite is not included because it doesn't support Unicode-aware case insensitive matching. sherlock-zh Parameter Value full name curated/02-literal-alternate/sherlock-zh model count regex Xia Luo Ke *Fu Er Mo Si |Yue Han Hua Sheng |A De Le |Lei Si Chui De |Mo Li Ya Di Jiao Shou case-insensitive false unicode true haystack-path opensubtitles/zh-sampled.txt count(.*) 207 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. Engine ascii unicode compile-ascii compile-unicode dotnet/compiled 1150.2 KB/s 1150.8 KB/s - 1.64ms go/regexp 257.3 KB/s - 1.32ms - hyperscan 104.2 MB/s - 648.57ms - icu 320.6 KB/s 322.0 KB/s 432.27us 432.42us java/hotspot 2.0 MB/s 1615.3 KB/s - - javascript/v8 32.8 MB/s 29.4 MB/s - - pcre2 1186.5 KB/s 175.0 KB/s 115.17us 135.36us pcre2/jit 20.8 MB/s 13.0 MB/s 712.71us 1.00ms perl 2.9 MB/s - - - python/re 1094.5 KB/s 893.0 KB/s 3.66ms 3.90ms python/regex 1119.3 KB/s 1021.3 KB/s 10.00ms 29.69ms re2 80.6 MB/s - 1.15ms - regress 1941.8 KB/s 1955.4 KB/s 1.05ms 1.04ms rust/regex 163.3 MB/s 162.2 MB/s 1.52ms 5.27ms rust/regex/lite 914.7 KB/s - 314.18us - rust/regexold 142.4 MB/s 415.7 KB/s 1.76ms 6.14ms Show individual benchmark parameters. ascii Parameter Value full name curated/03-date/ascii model count-spans regex-path wild/date.txt case-insensitive true unicode false haystack-path rust-src-tools-3b0d4813.txt count(dotnet.*) 111825 count(hyperscan) 547662 count(icu) 111825 count(javascript/v8) 111825 count(regress) 111841 count(.*) 111817 As with many other benchmarks, Hyperscan reports all matches, even ones that are overlapping. This particular regex is too big to analyze closely, but it seems plausible one could still use it (possibly with a slightly tweaked regex) for this task. unicode Parameter Value full name curated/03-date/unicode model count-spans regex-path wild/date.txt case-insensitive true unicode true haystack-path rust-src-tools-3b0d4813.txt count(`dotnet/compiled icu count(.*) 111841 regress is included here despite its \d not being Unicode-aware (as required by ECMAScript). Notably, its \s is Unicode aware. (\w is too, but it's not used in this regex.) In this particular haystack, \ d being ASCII-only doesn't impact the match count. However, neither re2 nor go/regexp are included here because neither \d nor \s are Unicode-aware, and the \s being ASCII-only does impact the match count. hyperscan is excluded here because the pattern results in a "too large" compilation error. As far as I know, Hyperscan doesn't expose any knobs for increasing this limit. dotnet/compiled gets a different count here, but it's not clear why. perl is left out of this benchmark because it times out. rust/regex/lite is excluded because it doesn't support Unicode-aware \w, \d or \s. compile-ascii Parameter Value full name curated/03-date/compile-ascii model compile regex-path wild/date.txt case-insensitive true unicode false haystack 2010-03-14 count(hyperscan) 10 count(.*) 5 Notice that regress is now include in the ASCII benchmark, because in compile-unicode we specifically test that the \d used in this regex is Unicode-aware. regress does not make \d Unicode-aware, so it gets thrown into the ASCII group. But do note that it does appear to have some Unicode awareness. compile-unicode Parameter Value full name curated/03-date/compile-unicode model compile regex-path wild/date.txt case-insensitive true unicode true haystack 2010-03-14 count(`javascript/v8 regress`) count(.*) 5 We use "extended arabic-indic digits" to represent the same date, 2010-03-14, that we use for verification in compile-ascii. These digits are part of \d when it is Unicode aware. 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. Engine real tweaked compile-real dotnet/compiled 154.5 MB/s 506.5 MB/s 47.03us dotnet/nobacktrack 243.5 MB/s 449.3 MB/s 436.34us go/regexp 33.8 MB/s 718.3 MB/s 2.75us icu 20.4 MB/s 325.2 MB/s 5.48us java/hotspot 37.9 MB/s 195.3 MB/s - pcre2 126.2 MB/s 1405.6 MB/s 1.14us pcre2/jit 570.7 MB/s 1501.6 MB/s 6.89us perl 104.5 MB/s 136.0 MB/s - python/re 30.4 MB/s 121.9 MB/s 60.36us python/regex 98.9 MB/s 99.1 MB/s 127.87us re2 551.6 MB/s 744.9 MB/s 7.05us rust/regex 1676.1 MB/s 1620.1 MB/s 53.74us rust/regex/lite 29.8 MB/s 46.9 MB/s 1.99us rust/regexold 173.8 MB/s 1252.9 MB/s 40.23us Show individual benchmark parameters. real Parameter Value full name curated/04-ruff-noqa/real model grep-captures regex (\s*)((?i:# noqa)(?::\s?(([A-Z]+[0-9]+(?:[,\s]+)?) +))?) case-insensitive false unicode false haystack-path wild/cpython-226484e4.py count(.*) 84 tweaked Parameter Value full name curated/04-ruff-noqa/tweaked model grep-captures regex (?i:# noqa)(?::\s?(([A-Z]+[0-9]+(?:[,\s]+)?)+))? case-insensitive false unicode false haystack-path wild/cpython-226484e4.py count(.*) 44 compile-real Parameter Value full name curated/04-ruff-noqa/compile-real model compile regex (\s*)((?i:# noqa)(?::\s?(([A-Z]+[0-9]+(?:[,\s]+)?) +))?) case-insensitive false unicode false haystack # noqa count(.*) 1 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. Engine single compile-single multi dotnet/compiled 192.5 KB/s 273.39us - go/regexp 318.9 KB/s 62.81us - hyperscan - - 17.4 MB/s icu 1005.9 KB/s 56.81us - java/hotspot 6.2 MB/s - - javascript/v8 6.8 MB/s - - pcre2 2.8 MB/s 24.72us - pcre2/jit 12.5 MB/s 130.93us - perl 1150.4 KB/s - - python/re 1841.6 KB/s 880.84us - python/regex 1679.5 KB/s 2.41ms - re2 1171.1 KB/s 148.80us - regress 6.1 MB/s - - rust/regex 9.3 MB/s 272.44us 93.9 MB/s rust/regex/lite 539.3 KB/s 39.83us - rust/regexold 235.0 KB/s 245.15us - Show individual benchmark parameters. single Parameter Value full name curated/05-lexer-veryl/single model count-captures regex-path wild/parol-veryl.txt case-insensitive false unicode false haystack-path wild/parol-veryl.vl count(.*) 124800 Note that we don't include Hyperscan here because it doesn't support the count-captures benchmark model. It is included in the multiple benchmark below, which doesn't require capture groups. Also, I tried to use dotnet/nobacktrack here, but it failed because it was too big and it wasn't obvious to me how to raise the limit. compile-single Parameter Value full name curated/05-lexer-veryl/compile-single model compile regex-path wild/parol-veryl.txt case-insensitive false unicode false haystack abcdefg_foobar count(.*) 1 This measures how long it takes to a compile a moderately large lexer. multi Parameter Value full name curated/05-lexer-veryl/multi model count-spans regex-path wild/parol-veryl.txt case-insensitive false unicode false haystack-path wild/parol-veryl.vl count(hyperscan) 669500 count(.*) 150600 Hyperscan reports everything that matches, including overlapping matches, and that's why its count is higher. It is likely still serviceable for this use case, but might in practice require changing the regex to suit Hyperscan's match semantics. Still, it's a decent barometer to include it here, particularly because of its multi-regex support. Most regex engines do not support searching for multiple patterns and finding the corresponding match offsets, which is why this benchmark has very few entries. 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. Engine original simplified-short simplified-long dotnet/compiled 131.3 MB/s 838.6 MB/s 13.4 GB/s dotnet/nobacktrack 12.8 MB/s 189.3 MB/s 289.5 MB/s go/regexp 41.0 MB/s 44.8 MB/s 47.8 MB/s hyperscan 85.0 MB/s 81.1 MB/s 84.7 MB/s icu 3.4 MB/s 3.5 MB/s 42.7 KB/s java/hotspot 5.8 MB/s 6.2 MB/s 99.8 KB/s javascript/v8 19.5 MB/s 18.9 MB/s 335.3 KB/s pcre2 2.9 MB/s 2.7 MB/s 30.2 KB/s pcre2/jit 49.5 MB/s 42.5 MB/s 670.8 KB/s perl 10.3 MB/s 10.0 MB/s 176.5 KB/s python/re 22.7 MB/s 22.3 MB/s 384.8 KB/s python/regex 6.4 MB/s 6.2 MB/s 91.9 KB/s re2 345.9 MB/s 330.9 MB/s 493.4 MB/s regress 8.4 MB/s 8.1 MB/s 106.1 KB/s rust/regex 583.1 MB/s 1835.4 MB/s 83.9 GB/s rust/regex/lite 18.9 MB/s 22.5 MB/s 22.5 MB/s rust/regexold 427.0 MB/s 469.9 MB/s 603.7 MB/s Show individual benchmark parameters. original Parameter Value full name curated/06-cloud-flare-redos/original model count-spans (?:(?:"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null regex |undefined|symbol|math)|`|-|\+)+[)]*;?((?:\s|-|~|!|\ {\}|\|\||\+)*.*(?:.*=.*))) case-insensitive false unicode false math x= haystack xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx [.. snip ..] count(hyperscan) 5757 count(.*) 107 simplified-short Parameter Value full name curated/06-cloud-flare-redos/simplified-short model count-spans regex .*.*=.* case-insensitive false unicode false x= haystack xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx [.. snip ..] count(hyperscan) 5252 count(.*) 102 simplified-long Parameter Value full name curated/06-cloud-flare-redos/simplified-long model count-spans regex .*.*=.* case-insensitive false unicode false haystack-path cloud-flare-redos.txt count(hyperscan) 50004999 count(.*) 10000 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. Engine parse-line compile dotnet/compiled 89.5 MB/s 41.42us dotnet/nobacktrack 17.0 MB/s 152.29us go/regexp 79.6 MB/s 11.85us icu 130.5 MB/s 13.91us java/hotspot 206.5 MB/s - javascript/v8 230.1 MB/s - pcre2 220.4 MB/s 2.16us pcre2/jit 701.9 MB/s 12.47us perl 23.3 MB/s - python/re 52.2 MB/s 101.55us python/regex 36.8 MB/s 267.51us re2 106.7 MB/s 14.48us regress 219.4 MB/s 6.15us rust/regex 330.0 MB/s 28.04us rust/regex/lite 29.9 MB/s 3.81us rust/regexold 95.0 MB/s 18.88us Show individual benchmark parameters. parse-line Parameter Value full name curated/07-unicode-character-data/parse-line model grep-captures regex-path wild/ucd-parse.txt case-insensitive false unicode false haystack-path wild/UnicodeData-15.0.0.txt count(.*) 558784 compile Parameter Value full name curated/07-unicode-character-data/compile model compile regex-path wild/ucd-parse.txt case-insensitive false unicode false haystack 249D;PARENTHESIZED LATIN SMALL LETTER B;So;0;L; 0028 [.. snip ..] count(.*) 1 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). Engine all-english all-russian long-english long-russian dotnet/compiled 59.2 MB/s 97.7 MB/s 178.4 MB/s 113.7 MB/s dotnet/nobacktrack 29.6 MB/s 39.9 MB/s 149.7 MB/s 131.0 MB/s go/regexp 20.5 MB/s - 45.3 MB/s - hyperscan 158.2 MB/s - 439.5 MB/s - icu 78.9 MB/s 106.5 MB/s 41.4 MB/s 55.2 MB/s java/hotspot 76.7 MB/s 137.8 MB/s 71.4 MB/s 113.7 MB/s javascript/v8 169.6 MB/s - 197.9 MB/s - pcre2 98.6 MB/s 130.6 KB/s 70.1 MB/s 6.2 MB/s pcre2/jit 193.3 MB/s 228.8 MB/s 245.4 MB/s 195.9 MB/s perl 13.6 MB/s 34.7 KB/s 107.8 MB/s 1869.9 KB/s python/re 38.6 MB/s 46.2 MB/s 125.8 MB/s 123.1 MB/s python/regex 23.3 MB/s 43.6 MB/s 37.2 MB/s 104.6 MB/s re2 67.5 MB/s - 923.8 MB/s - regress 163.4 MB/s - 152.1 MB/s - rust/regex 119.9 MB/s 19.6 MB/s 802.3 MB/s 33.7 MB/s rust/regex/lite 33.0 MB/s - 43.9 MB/s - rust/regexold 119.3 MB/s 7.1 MB/s 805.5 MB/s 35.0 MB/s Show individual benchmark parameters. all-english Parameter Value full name curated/08-words/all-english model count-spans regex \b[0-9A-Za-z_]+\b case-insensitive false unicode false haystack-path opensubtitles/en-sampled.txt count(dotnet/compiled) 56601 count(dotnet/nobacktrack) 56601 count(icu) 56601 count(.*) 56691 We specifically write out [0-9A-Za-z_] instead of using \w because some regex engines, such as the one found in .NET, make \w Unicode aware and there doesn't appear to be any easy way of disabling it. Also, the .NET engine makes \b Unicode-aware, which also appears impossible to disable. To account for that, we permit a different count. all-russian Parameter Value full name curated/08-words/all-russian model count-spans regex \b\w+\b case-insensitive false unicode true haystack-path opensubtitles/ru-sampled.txt count(dotnet.*) 53960 count(icu) 53960 count(java.*) 53960 count(perl) 53960 count(.*) 107391 rust/regex/lite, regress, re2 and go/regexp are excluded because \w is not Unicode aware. hyperscan is exclude because it doesn't support a Unicode aware \b. For dotnet/compiled, since the length of matching spans is in the number of UTF-16 code units, its expected count is smaller. For perl, it has the same count as dotnet/compiled, but only because it counts total encoded codepoints. Since every match span in this benchmark seemingly corresponds to codepoints in the basic multi-lingual plane, it follows that the number of UTF-16 code units is equivalent to the number of codepoints. long-english Parameter Value full name curated/08-words/long-english model count-spans regex \b[0-9A-Za-z_]{12,}\b case-insensitive false unicode false haystack-path opensubtitles/en-sampled.txt count(.*) 839 We specifically write out [0-9A-Za-z_] instead of using \w because some regex engines, such as the one found in .NET, make \w Unicode aware and there doesn't appear to be any easy way of disabling it. Also, the fact that \b is Unicode-aware in .NET does not seem to impact the match counts in this benchmark. long-russian Parameter Value full name curated/08-words/long-russian model count-spans regex \b\w{12,}\b case-insensitive false unicode true haystack-path opensubtitles/ru-sampled.txt count(dotnet.*) 2747 count(icu) 2747 count(java.*) 2747 count(perl) 2747 count(.*) 5481 rust/regex/lite, regress, re2 and go/regexp are excluded because \w is not Unicode aware. hyperscan is exclude because it doesn't support a Unicode aware \b. For dotnet/compiled, since the length of matching spans is in the number of UTF-16 code units, its expected count is smaller. For perl, it has the same count as dotnet/compiled, but only because it counts total encoded codepoints. Since every match span in this benchmark seemingly corresponds to codepoints in the basic multi-lingual plane, it follows that the number of UTF-16 code units is equivalent to the number of codepoints. aws-keys This measures a regex for detecting AWS keys in source code aws-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.) Engine full quick compile-full compile-quick dotnet/compiled 511.9 MB/s 795.9 MB/s 103.76us 41.85us dotnet/nobacktrack - 665.6 MB/s - 213.13us go/regexp 111.5 MB/s 866.2 MB/s 19.59us 2.91us hyperscan - 1378.8 MB/s - 6.75ms icu 188.5 MB/s 337.9 MB/s 11.47us 2.99us java/hotspot 41.3 MB/s 116.2 MB/s - - javascript/v8 319.0 MB/s 329.3 MB/s - - pcre2 971.4 MB/s 1490.1 MB/s 3.63us 842.00ns pcre2/jit 1217.9 MB/s 1018.7 MB/s 20.15us 4.76us perl 107.7 MB/s 141.4 MB/s - - python/re 106.4 MB/s 183.6 MB/s 172.26us 39.47us python/regex 104.4 MB/s 125.2 MB/s 472.09us 93.85us re2 543.7 MB/s 1036.0 MB/s 69.14us 8.95us regress 269.7 MB/s 742.9 MB/s 8.53us 2.04us rust/regex 1782.1 MB/s 1854.6 MB/s 87.28us 15.13us rust/regex/lite 15.1 MB/s 36.5 MB/s 8.33us 1.33us rust/regexold 678.1 MB/s 1392.4 MB/s 75.53us 18.09us Show individual benchmark parameters. full Parameter Value full name curated/09-aws-keys/full model grep-captures (('|")((?:ASIA|AKIA|AROA|AIDA)([A-Z0-7]{16}))('| regex ").*?(\n^.*?){0,4}(('|")[a-zA-Z0-9+/]{40}('|"))+|('| ")[a-zA-Z0-9+/]{40}('|").*?(\n^.*?){0,3}('|") ((?:ASIA|AKIA|AROA|AIDA)([A-Z0-7]{16}))('|"))+ case-insensitive false unicode false haystack-path wild/cpython-226484e4.py count(.*) 0 quick Parameter Value full name curated/09-aws-keys/quick model grep regex ((?:ASIA|AKIA|AROA|AIDA)([A-Z0-7]{16})) case-insensitive false unicode false haystack-path wild/cpython-226484e4.py count(.*) 0 compile-full Parameter Value full name curated/09-aws-keys/compile-full model compile (('|")((?:ASIA|AKIA|AROA|AIDA)([A-Z0-7]{16}))('|").*?(\n regex ^.*?){0,4}(('|")[a-zA-Z0-9+/]{40}('|"))+|('|")[a-zA-Z0-9+/] {40}('|").*?(\n^.*?){0,3}('|")((?:ASIA|AKIA|AROA|AIDA) ([A-Z0-7]{16}))('|"))+ case-insensitive false unicode false haystack "AIDAABCDEFGHIJKLMNOP""aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa [.. snip ..] count(.*) 1 compile-quick Parameter Value full name curated/09-aws-keys/compile-quick model compile regex ((?:ASIA|AKIA|AROA|AIDA)([A-Z0-7]{16})) case-insensitive false unicode false haystack AIDAABCDEFGHIJKLMNOP count(.*) 1 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. Engine letters-en letters-ru context capitals compile-context compile-capitals dotnet/ 263.6 MB/s 189.9 MB/s 333.1 865.2 MB 33.26us 28.62us compiled MB/s /s dotnet/ 144.5 MB/s 104.1 MB/s 53.2 MB 555.8 MB 202.03us 48.44us nobacktrack /s /s go/regexp 29.6 MB/s 27.8 MB/s 29.6 MB 54.0 MB/ 22.93us 17.30us /s s hyperscan 730.9 MB/s 267.6 MB/s 498.1 2.7 GB/s 24.63ms 653.31us MB/s icu 38.7 MB/s 70.4 MB/s 70.7 MB 265.6 MB 4.03us 2.81us /s /s java/ 92.0 MB/s 152.2 MB/s 74.5 MB 126.1 MB - - hotspot /s /s javascript/ 157.2 MB/s 59.9 MB/s 153.6 742.9 MB - - v8 MB/s /s pcre2 58.3 MB/s 416.5 KB/s 76.5 MB 573.5 MB 4.86us 28.75us /s /s pcre2/jit 333.8 MB/s 286.5 MB/s 373.4 1572.0 13.11us 36.62us MB/s MB/s perl 70.8 MB/s 43.9 MB/s 90.5 MB 226.3 MB - - /s /s python/re 80.7 MB/s - 78.1 MB 63.8 MB/ 47.86us 26.52us /s s python/ 34.7 MB/s 78.3 MB/s 33.1 MB 266.1 MB 107.27us 56.17us regex /s /s re2 501.0 MB/s 7.0 MB/s 87.8 MB 986.3 MB 92.20us 119.47us /s /s regress 167.0 MB/s 30.3 MB/s 169.2 411.8 MB - 1.21us MB/s /s rust/regex 715.0 MB/s 642.7 MB/s 99.6 MB 825.6 MB 61.49us 61.33us /s /s rust/regex/ 28.2 MB/s - 28.7 MB 56.9 MB/ 9.98us 12.59us lite /s s rust/ 608.2 MB/s 529.3 MB/s 20.3 MB 824.6 MB 40.92us 66.59us regexold /s /s Show individual benchmark parameters. letters-en Parameter Value full name curated/10-bounded-repeat/letters-en model count regex [A-Za-z]{8,13} case-insensitive false unicode false haystack-path opensubtitles/en-sampled.txt count(hyperscan) 3724 count(.*) 1833 letters-ru Parameter Value full name curated/10-bounded-repeat/letters-ru model count regex \p{L}{8,13} case-insensitive false unicode true haystack-path opensubtitles/ru-sampled.txt count(hyperscan) 8570 count(.*) 3475 context Parameter Value full name curated/10-bounded-repeat/context model count regex [A-Za-z]{10}\s+[\s\S]{0,100}Result[\s\S]{0,100}\s+ [A-Za-z]{10} case-insensitive false unicode false haystack-path rust-src-tools-3b0d4813.txt count(hyperscan) 109 count(.*) 53 capitals Parameter Value full name curated/10-bounded-repeat/capitals model count regex (?:[A-Z][a-z]+\s*){10,100} case-insensitive false unicode false haystack-path rust-src-tools-3b0d4813.txt count(hyperscan) 237 count(.*) 11 compile-context Parameter Value full name curated/10-bounded-repeat/compile-context model compile regex [A-Za-z]{10}\s+(?s:.){0,100}Result(?s:.){0,100}\s+ [A-Za-z]{10} case-insensitive false unicode false haystack abcdefghij blah blah blah Result blib blab klmnopqrst count(.*) 1 compile-capitals Parameter Value full name curated/10-bounded-repeat/compile-capitals model compile regex (?:[A-Z][a-z]+\s*){10,100} case-insensitive false unicode false haystack Crazy Janey Mission Man Wild Billy Greasy Lake Hazy Davy Kil [.. snip ..] count(hyperscan) 12 count(.*) 1 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[^\ ]+\ [^\ ]+) [\ ](?P[DIWEF])[1234]:[\ ] (?P
(?: (?: \[ [^\]]*? \] | \( [^\)]*? \) ):[\ ] )* ) (?P.*?) [\ ]\{(?P[^\}]*)\} $ (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.) Engine extract compile dotnet/compiled 547.1 MB/s 44.84us dotnet/nobacktrack 17.4 MB/s 505.43us go/regexp 83.9 MB/s 6.25us icu 94.6 MB/s 7.81us java/hotspot 215.0 MB/s - javascript/v8 971.2 MB/s - pcre2 207.3 MB/s 1.34us pcre2/jit 1446.6 MB/s 7.20us perl 149.3 MB/s - python/re 120.3 MB/s 72.37us python/regex 127.5 MB/s 193.25us re2 118.6 MB/s 9.29us regress 287.0 MB/s 4.09us rust/regex 109.5 MB/s 20.06us rust/regex/lite 25.0 MB/s 2.38us rust/regexold 84.1 MB/s 14.16us Show individual benchmark parameters. extract Parameter Value full name curated/11-unstructured-to-json/extract model grep-captures regex-path wild/unstructured-to-json.txt case-insensitive false unicode false haystack-path wild/unstructured-to-json.log count(.*) 600 compile Parameter Value full name curated/11-unstructured-to-json/compile model compile regex-path wild/unstructured-to-json.txt case-insensitive false unicode false haystack 2022/06/17 06:25:22 I4: [17936:140245395805952: (17998)]: (8f [.. snip ..] count(.*) 1 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. Engine single multi compile-single compile-multi dotnet/compiled 1304.8 KB/s - 11.22ms - go/regexp 568.3 KB/s - 5.86ms - hyperscan - 7.8 GB/s - 20.62ms icu 136.4 KB/s - 1.46ms - java/hotspot 108.8 KB/s - - - javascript/v8 28.2 KB/s - - - perl 127.2 MB/s - - - python/re 176.2 KB/s - 25.63ms - python/regex 157.2 KB/s - 69.13ms - re2 5.5 MB/s - 4.15ms - regress 85.8 KB/s - 3.01ms - rust/regex 714.9 MB/s 187.0 MB/s 7.74ms 15.87ms rust/regex/lite 51.7 KB/s - 1.51ms - rust/regexold 22.1 KB/s - 7.60ms - Show individual benchmark parameters. single Parameter Value full name curated/12-dictionary/single model count regex-path dictionary/english/length-15.txt case-insensitive false unicode false haystack-path opensubtitles/en-medium.txt count(.*) 1 dotnet/nobacktrack is omitted because the regex is too large. hyperscan is omitted because the regex is too large. pcre2/* are omitted because the regex is too large. multi Parameter Value full name curated/12-dictionary/multi model count regex-path dictionary/english/length-15.txt case-insensitive false unicode false haystack-path opensubtitles/en-medium.txt count(.*) 1 Only hyperscan and rust/regex are included because they are the only regex engines to support multi-pattern regexes. (Note that the regex crate API does not support this. You need to drop down to the meta::Regex API in the regex-automata crate.) compile-single Parameter Value full name curated/12-dictionary/compile-single model compile regex-path dictionary/english/length-15.txt case-insensitive false unicode false haystack Zubeneschamali's count(.*) 1 dotnet/nobacktrack is omitted because the regex is too large. hyperscan is omitted because the regex is too large. java/hotspot is omitted because we currently don't benchmark Perl regex compilation. javascript/v8 is omitted because we currently don't benchmark Perl regex compilation. pcre2/* are omitted because the regex is too large. perl is omitted because we currently don't benchmark Perl regex compilation. compile-multi Parameter Value full name curated/12-dictionary/compile-multi model compile regex-path dictionary/english/length-15.txt case-insensitive false unicode false haystack Zubeneschamali's count(.*) 1 Only hyperscan and rust/regex are included because they are the only regex engines to support multi-pattern regexes. (Note that the regex crate API does not support this. You need to drop down to the meta::Regex API in the regex-automata crate.) 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. Engine single multi compile-single compile-multi hyperscan 4.3 GB/s 4.3 GB/s 214.46ms 136.38ms pcre2/jit 12.9 MB/s - 615.22us - rust/regex 132.8 MB/s 104.0 MB/s 2.44ms 2.80ms rust/regexold 9.3 MB/s - 4.32ms - Show individual benchmark parameters. single Parameter Value full name curated/13-noseyparker/single model count regex-path wild/noseyparker.txt case-insensitive false unicode false haystack-path wild/cpython-226484e4.py count(hyperscan) 241 count(.*) 55 * dotnet/compiled is omitted because it times out. * dotnet/nobacktrack is omitted because the regex is too big. * go/regexp is omitted because there are bounded repeats that exceed its limit. * icu is omitted because it times out. * java/hotspot is omitted because it times out. * javascript/v8 is omitted because it doesn't support inline flags. * pcre2 is omitted because it times out. * perl is omitted because it times out. * python/* is omitted because it times out. * re2 is omitted because it seems to fail and reports a count of 0. * regress is omitted because it doesn't support inline flags. * rust/regex/lite is omitted because it times out. multi Parameter Value full name curated/13-noseyparker/multi model count regex-path wild/noseyparker.txt case-insensitive false unicode false haystack-path wild/cpython-226484e4.py count(hyperscan) 241 count(.*) 55 Only hyperscan and rust/regex are included because they are the only regex engines to support multi-pattern regexes. (Note that the regex crate API does not support this. You need to drop down to the meta::Regex API in the regex-automata crate.) compile-single Parameter Value full name curated/13-noseyparker/compile-single model compile regex-path wild/noseyparker.txt case-insensitive false unicode false haystack TWITTER_API_KEY = 'UZYoBAfBzNace3mBwPOGYw' count(.*) 1 We only include the engines that are measured in the single benchmark. compile-multi Parameter Value full name curated/13-noseyparker/compile-multi model compile regex-path wild/noseyparker.txt case-insensitive false unicode false haystack TWITTER_API_KEY = 'UZYoBAfBzNace3mBwPOGYw' count(.*) 1 We only include the engines that are measured in the multi benchmark. 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. Engine 1x 2x 10x dotnet/compiled 20.5 MB/s 13.3 MB/s 3.5 MB/s dotnet/nobacktrack 7.9 MB/s 4.8 MB/s 1184.4 KB/s go/regexp 1656.3 KB/s 894.9 KB/s 193.8 KB/s hyperscan 172.8 MB/s 179.9 MB/s 182.3 MB/s icu 3.4 MB/s 1928.1 KB/s 295.9 KB/s java/hotspot 10.0 MB/s 5.9 MB/s 1006.8 KB/s javascript/v8 16.3 MB/s 10.5 MB/s 2.9 MB/s pcre2 2.1 MB/s 1163.1 KB/s 244.1 KB/s pcre2/jit 18.7 MB/s 11.5 MB/s 3.0 MB/s perl 2.4 MB/s 1657.2 KB/s 456.3 KB/s python/re 3.2 MB/s 1998.9 KB/s 460.6 KB/s python/regex 3.8 MB/s 2.5 MB/s 702.6 KB/s re2 9.6 MB/s 6.5 MB/s 1835.6 KB/s regress 5.5 MB/s 3.0 MB/s 678.2 KB/s rust/regex 17.8 MB/s 8.6 MB/s 1706.3 KB/s rust/regex/lite 1136.7 KB/s 599.5 KB/s 125.2 KB/s rust/regexold 13.9 MB/s 7.6 MB/s 1663.5 KB/s Show individual benchmark parameters. 1x Parameter Value full name curated/14-quadratic/1x model count regex .*[^A-Z]|[A-Z] case-insensitive false unicode false haystack AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA [.. snip ..] count(.*) 100 This is our baseline benchmark the searches a haystack with the letter A repeated 100 times. 2x Parameter Value full name curated/14-quadratic/2x model count regex .*[^A-Z]|[A-Z] case-insensitive false unicode false haystack AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA [.. snip ..] count(.*) 200 This is like 1x, but doubles the haystack length. This should provide a way to show the quadratic nature of this particular benchmark. The throughputs reported should remain roughly the same if the time complexity is linear, but in fact, the throughputs decrease by about a factor of 2. That demonstrates a superlinear relationship between the inputs and the time taken. 10x Parameter Value full name curated/14-quadratic/10x model count regex .*[^A-Z]|[A-Z] case-insensitive false unicode false haystack AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA [.. snip ..] count(.*) 1000 This is like 1x, but increases the haystack length by a factor of 10. This should provide more evidence that the relationship is quadratic in the same way that the 2x benchmark does. About A biased barometer for gauging the relative speed of some regex engines on a curated set of tasks. Resources Readme License Unlicense license Stars 62 stars Watchers 3 watching Forks 0 forks Report repository Releases No releases published Packages 0 No packages published Languages * Python 87.9% * C 9.1% * C++ 1.9% * Rust 1.1% * C# 0.0% * Java 0.0% Footer (c) 2023 GitHub, Inc. Footer navigation * Terms * Privacy * Security * Status * Docs * Contact GitHub * Pricing * API * Training * Blog * About You can't perform that action at this time.