TOtosh·May 30, 2026Submission
Rebar: A biased barometer for gauging the relative speed of some regex engines
3 points · Open discussionBurntSushi
rebar
Python2023–2026
BurntSushi / rebar
rebar
A biased barometer for gauging the relative speed of some regex engines on a curated set of tasks.
6Distinct people
44Mentions
1Explicit recommenders
327GitHub stars
What to know before exploring
What it is
A biased barometer for gauging the relative speed of some regex engines on a curated set of tasks.
GitHub
Where it is used
No documented product use has been verified yet.
What people are saying
I love the flourish of "in the world." I had never thought about it that way. Which makes me wonder if there are any regex engines that aren't in rebar that could conceivably…
burntsushi used a recommendation phrase. One indexed comment matches. This is a phrase match, not a verdict.
No classified warning is attached to this page. Read the discussions before treating silence as approval.
Also in these discussions
- burntsushi/memchr · linked in 3 of the same discussions
Mentioned in the same Hacker News threads. That is not proof they are substitutes.
This week on Hacker News
Nov 7–Nov 14 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/14/2026, 5:04:57 PM UTC.
No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.
Mentions over time
HN mentions by year44 dated mentions
Observed mentions: 2023-07-05 13:48:49 UTC to 2026-05-30 15:54:58 UTC.
* An incomplete calendar period is marked with an outlined bar. Its count is not directly comparable with a full period.
Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.
View mention counts and date ranges
| Period | Start (UTC) | End (exclusive, UTC) | Mentions | Submissions | Comments |
|---|---|---|---|---|---|
| 2023 | 2023-01-01 00:00:00 UTC | 2024-01-01 00:00:00 UTC | 22 | 2 | 20 |
| 2024 | 2024-01-01 00:00:00 UTC | 2025-01-01 00:00:00 UTC | 14 | 0 | 14 |
| 2025 | 2025-01-01 00:00:00 UTC | 2026-01-01 00:00:00 UTC | 5 | 0 | 5 |
| 2026 (partial) | 2026-01-01 00:00:00 UTC | 2027-01-01 00:00:00 UTC | 3 | 1 | 2 |
What Hacker News says
44 sourcesFWIW, nim-regex does achieve linear time in the rebar test[0], even if the regex includes capture groups. It's NFA based.
[0]: https://github.com/BurntSushi/rebar/pull/20#issuecomment-256...
In Finding all regex matches has always been O(n²)Not necessarily at all. Go peruse the `regex` crate source code, including its dependencies.
The biggest `unsafe` sections are probably for SIMD accelerated search. There's no "unnatural abstractions" there. Just a memmem-like interface.
There's some `unsafe` for eliding bounds checks in the main DFA search loops. No unnatural abstractions there either.
There's also some `unsafe` for some synchronization primitives for managing mutable scratch space to use during a search. A C library (e.g., PCRE2) makes the caller handle this. The `regex` crate does it for you. But not for unnatural reasons. To make using regexes simpler. There are lower level APIs that provide the control of C if you need it.
That's pretty much it. All told, this is a teeny tiny fraction of the code in the `regex` crate (and all of its dependencies).
Finally, a demonstr
Read the rest
ation of C-like speed: https://github.com/BurntSushi/rebar?tab=readme-ov-file#summa...
> Is is a tradeoff, not a silver bullet.
Uncontroversial.
Nope. ripgrep uses the `memchr` crate for substring search, and in my benchmarks it's generally faster than stringzilla:
$ rebar cmp results.csv --intersection -f huge
benchmark rust/memchr/memmem/prebuilt stringzilla/memmem/oneshot
--------- --------------------------- --------------------------
memmem/pathological/md5-huge-no-hash 47.4 GB/s (1.00x) 38.1 GB/s (1.25x)
memmem/pathological/md5-huge-last-hash 40.3 GB/s (1.00x) 23.4 GB/s (1.72x)
memmem/pathological/rare-repeated-huge-tricky 40.4 GB/s (1.04x) 42.0 GB/s (1.00x)
memmem/pathological/rare-repeated-huge-match 1977.7 MB/s (1.00x) 563.3 MB/s (3.51x)
memmem/subtitles/common/huge-en-that 35.9 G
Read the rest
B/s (1.00x) 25.3 GB/s (1.42x)
memmem/subtitles/common/huge-en-you 15.9 GB/s (1.00x) 9.5 GB/s (1.67x)
memmem/subtitles/common/huge-en-one-space 1376.4 MB/s (1.00x) 1364.0 MB/s (1.01x)
memmem/subtitles/common/huge-ru-that 29.0 GB/s (1.00x) 15.5 GB/s (1.87x)
memmem/subtitles/common/huge-ru-not 16.0 GB/s (1.00x) 3.5 GB/s (4.53x)
memmem/subtitles/common/huge-ru-one-space 2.6 GB/s (1.00x) 2.4 GB/s (1.08x)
memmem/subtitles/common/huge-zh-that 31.2 GB/s (1.00x) 23.8 GB/s (1.31x)
memmem/subtitles/common/huge-zh-do-not 19.4 GB/s (1.00x) 12.1 GB/s (1.59x)
memmem/subtitles/common/huge-zh-one-space 5.3 GB/s (1.05x) 5.6 GB/s (1.00x)
memmem/subtitles/never/huge-en-john-watson 41.2 GB/s (1.00x) 31.2 GB/s (1.32x)
memmem/subtitles/never/huge-en-all-common-bytes 47.9 GB/s (1.00x) 37.5 GB/s (1.28x)
memmem/subtitles/never/huge-en-some-rare-bytes 43.4 GB/s (1.00x) 42.7 GB/s (1.02x)
memmem/subtitles/never/huge-en-two-space 42.2 GB/s (1.00x) 30.7 GB/s (1.37x)
memmem/subtitles/never/huge-ru-john-watson 42.2 GB/s (1.00x) 42.1 GB/s (1.00x)
memmem/subtitles/never/huge-zh-john-watson 47.6 GB/s (1.00x) 34.0 GB/s (1.40x)
memmem/subtitles/rare/huge-en-sherlock-holmes 40.8 GB/s (1.05x) 42.9 GB/s (1.00x)
memmem/subtitles/rare/huge-en-sherlock 36.7 GB/s (1.16x) 42.5 GB/s (1.00x)
memmem/subtitles/rare/huge-en-medium-needle 47.7 GB/s (1.00x) 31.3 GB/s (1.52x)
memmem/subtitles/rare/huge-en-long-needle 44.5 GB/s (1.00x) 32.0 GB/s (1.39x)
memmem/subtitles/rare/huge-en-huge-needle 45.7 GB/s (1.00x) 33.4 GB/s (1.37x)
memmem/subtitles/rare/huge-ru-sherlock-holmes 42.1 GB/s (1.00x) 42.2 GB/s (1.00x)
memmem/subtitles/rare/huge-ru-sherlock 42.3 GB/s (1.01x) 42.9 GB/s (1.00x)
memmem/subtitles/rare/huge-zh-sherlock-holmes 46.7 GB/s (1.00x) 33.1 GB/s (1.41x)
memmem/subtitles/rare/huge-zh-sherlock 47.4 GB/s (1.00x) 42.8 GB/s (1.11x)
But I would say they are overall pretty competitive.
If you want to run the benchmarks yourself, you can. First, get rebar[1]. Then, from the root of the `memchr` repository[2]:
$ rebar build -e 'rust/memchr/memmem/prebuilt' -e 'stringzilla/memmem/oneshot'
stringzilla/memmem/oneshot: running: cd "benchmarks/./engines/stringzilla" && "cargo" "build" "--release"
stringzilla/memmem/oneshot: build complete for version 3.12.3
rust/memchr/memmem/prebuilt: running: cd "benchmarks/./engines/rust-memchr" && "cargo" "build" "--release"
rust/memchr/memmem/prebuilt: build complete for version 2.7.4
$ rebar measure -e 'rust/memchr/memmem/prebuilt' -e 'stringzilla/memmem/oneshot' | tee results.csv
$ rebar rank results.csv
Engine Version Geometric mean of speed ratios Benchmark count
------ ------- ------------------------------ ---------------
rust/memchr/memmem/prebuilt 2.7.4 1.14 57
stringzilla/memmem/oneshot 3.12.3 1.43 54
$ rebar cmp results.csv --intersection -f never/huge
benchmark rust/memchr/memmem/prebuilt stringzilla/memmem/oneshot
--------- --------------------------- --------------------------
memmem/subtitles/never/huge-en-john-watson 41.2 GB/s (1.00x) 31.2 GB/s (1.32x)
memmem/subtitles/never/huge-en-all-common-bytes 47.9 GB/s (1.00x) 37.5 GB/s (1.28x)
memmem/subtitles/never/huge-en-some-rare-bytes 43.4 GB/s (1.00x) 42.7 GB/s (1.02x)
memmem/subtitles/never/huge-en-two-space 42.2 GB/s (1.00x) 30.7 GB/s (1.37x)
memmem/subtitles/never/huge-ru-john-watson 42.2 GB/s (1.00x) 42.1 GB/s (1.00x)
memmem/subtitles/never/huge-zh-john-watson 47.6 GB/s (1.00x) 34.0 GB/s (1.40x)
See also: https://github.com/BurntSushi/memchr/discussions/159
[1]: https://github.com/BurntSushi/rebar
[2]: https://github.com/BurntSushi/memchr
It's not only just getting some "regex basics." The `fancy-regex` crate has provided look-behind for years. The OP is about adopting look-behind to the linear time guarantee required by the `regex` crate.
My main focus for the `regex` crate has been on performance: https://github.com/BurntSushi/rebar
How does Raku's regex performance compare to Perl?
In Adding lookbehinds to rust-lang/regexTo be fair I think Rust has very healthy selection of options for both, with Serde and Reqwest/Hyper being de-facto standard.
Rust has other challenges it needs to overcome but this isn't one.
I'd put Go behind both C#/F# and Rust in this area. It has spartan tooling in odd areas it's expected to be strong at like gRPC and the serialization story in Go is quite a bit more painful and bare bones compared to what you get out of System.Text.Json and Serde.
The difference is especially stark with Regex where Go ships with a slow engine (because it does not allow writing sufficiently fast code in this area at this moment) where-as both Rust and C# have top of the line implementations in each which beat every other engine save for Intel Hyperscan[0].
[0]: https://github.com/BurntSushi/rebar?tab=readme-ov-file#summa... (note this is without .NET
Read the rest
9 or 10 preview updates)
I try my best to interpret pithy phrases describing a project as first order approximations, rather than literal statements of truth that perfectly generalize. Pithiness is important for communicating ideas quickly, but precision and pithiness are often in tension with one another. So I adjust my expectations accordingly.
Yes, I agree that the wrong results are bad. But that doesn't invalidate my point. I even went out of my way to clarify that the benchmark wasn't worthless. Benchmarking the small input case is absolutely worth it. You just can't tell much about its scaling properties when your measurement is basically "how fast does the process start and stop." Which, again, to be clear, IT MATTERS. It just probably doesn't matter as much as readers might think it matters when they see it.
So treat my comment as adding helpful context f
Read the rest
or readers that aren't experts in benchmarking grep tools from someone experienced in... benchmarking grep tools. :-) (And regexes in general. See: https://github.com/BurntSushi/rebar)
Not easily. But not all use cases require it. The regex crate makes heavy use of this pattern for finite machine states, for example. But this fits nicely with an arena allocation pattern, so everything can just be dropped at once.
Despite this, it's one of the fastest regex engines around: https://github.com/BurntSushi/rebar#summary-of-search-time-b...
Here's a related but more isolated analysis: https://github.com/burntsushi/rsc-regexp
In Static search trees: faster than binary searchNo. I've written about why: https://blog.burntsushi.net/ripgrep/
That blog is eight years old now, but still pretty accurate.
For more details at the level of the regex engine, see: https://github.com/BurntSushi/rebar
In Notepad++ is 21 years oldIt does not. Almost no regex engine does that.
To add more color to this, the precise details of what "Unicode support" means are documented here: https://github.com/rust-lang/regex/blob/master/UNICODE.md
In effect, all of UTS#18 Level 1 is covered with a couple caveats. This is already a far cry better than most regex engines, like PCRE2, which has limited support for properties and no way to do subtraction or intersection of character classes. Other regex engines, like Javascript, are catching up. While UTS#18 Level 1 make ripgrep's Unicode support better than most, it does not make it the best. The third party Python `regex` library, for example, has very good support, although it is not especially fast[1].
Short of building UTS#18 2.1[2] support into the regex engine (unlikely to ever happen), it's likely ripgrep could offer some sort
Read the rest
of escape hatch. Perhaps, for example, an option to normalize all text searched to whatever form you want (nfc, nfd, nfkc or nfkd). The onus would still be on you to write the corresponding regex pattern though. You can technically do this today with ripgrep's `--pre` flag, but having something built-in might be nice. Indeed, if you read UTS#18 2.1, you'll note that it is self-aware about how difficult matching canonical equivalents is, and essentially suggests this exact work-around instead. The problem is that it would need to be opt-in and the user would need to be aware of the problem in the first place. That's... a stretch, but probably better than nothing.
[1]: https://github.com/BurntSushi/rebar?tab=readme-ov-file#summa...
[2]: https://unicode.org/reports/tr18/#Canonical_Equivalents
The C#'s regex engine would have run circles around Go's here though while doing so :)
https://github.com/BurntSushi/rebar?tab=readme-ov-file#summa...
In Go is my hammer, and everything is a nail> I suspect it will very hard to get good performance from the API as provided
PCRE2's jit engine, which is powered by sljit, is one of the fastest regex engines in existence (according to my own benchmarks): https://github.com/BurntSushi/rebar?tab=readme-ov-file#summa...
In Sljit: Platform independent low-level JIT compilerAt search time, the principle difference between an NFA and a DFA is that, in an NFA, you can be in more than one state at the same time. There's no problem with implementing your transition function to advance all states you are in simultaneously for each character of input. You'll get `O(m * n)` time, where `m` is proportional to the number of states in the NFA and `n` is proportional to the length of the input.
The GP is remarking on a confusable term, "NFA algorithm," that has come to mean something different from its underlying theory. The PCRE2 documentation itself, for example[1], remarks about how it uses the "NFA algorithm" as its standard approach to matching. But of course, PCRE2 supports way more than the theoretical model of non-deterministic finite automata (NFA) actually supports. PCRE2 is much more expressive. Yet, the imp
Read the rest
lementation approach is still called "NFA algorithm." Presumably the reason for this is that an NFA can be simulated by doing backtracking, but if you don't keep track of where you've visited, the worst case runtime of this is superlinear, possibly catastrophically so[2]. The problem is that the backtracking regex engines have evolved well beyond what an NFA actually supports. But the name stuck.
To make things even more confusing, as I mentioned above, an NFA can be used to execute a search in O(m * n) time. (We typically call that "linear in the size of the input" since the NFA itself can usually, but not always, be regarded as a constant factor. i.e., A literal regex string in your program source code.) So when you say something like, "a finite automata regex engine uses NFAs to guarantee linear time," you might be really confused if your background is in backtracking engines which... also use an "NFA," but of course cannot guarantee linear search time.
So what we have is ambiguous terminology, not unlike "regex" itself, which could perhaps mean a real theoretical "regular expression" (in the case of Hyperscan, RE2, Go's regexp package and Rust's regex crate) or it could mean "a very expressive DSL for pattern matching that supports more than what regular languages can describe" (in the case of PCRE2, ECMAScript's regex engine, Ruby's Oniguruma, Python's `re` module, and more). I've made my peace with "regex" being ambiguous, but the fact that "NFA algorithm" is itself ambiguous despite "non-deterministic finite automata" being a somewhat baroque and specific technical term, is very unfortunate.
To make things even worse---and I shit you not, I am not joking---the backtracking people seem to have taken to calling a linear time NFA search the "DFA algorithm."[3] (At least the PCRE2 docs mention it's not a "traditional" finite state machine...) But... it's not a DFA. The backtracking folks have effectively elevated the terms "NFA" and "DFA" to mean something very different from their theoretical underpinnings.
So when you have people that are only aware of one meaning of "NFA algorithm" talking to other people only aware of the other meaning of "NFA algorithm," chaos ensues.
[1]: https://www.pcre.org/current/doc/html/pcre2matching.html
[2]: https://github.com/BurntSushi/rebar?tab=readme-ov-file#cloud...
[3]: https://www.pcre.org/current/doc/html/pcre2matching.html#TOC...
As the author of ripgrep, I wouldn't necessarily buy this. I suppose I might agree with it in the extremes, but SIMD prefilters are quite exceptionally difficult to beat with scalar code in the common cases. Longer patterns are great for the SIMD algorithms in ripgrep because of its use of background frequency distribution heuristics. That is, the longer the pattern, the less likely your candidate detection is to produce a false positive in its hot path. (I say "less likely" here intentionally. One can of course pick specific needles and haystacks where a false positive is reported at every position for any length N.)
I don't mean to 100% disagree with you, but I think it's misleading to suggest a sort of one dimensional view of things where, as the pattern gets larger, SIMD gets worse compared to sublinear search algorithms. There are ot
Read the rest
her factors at play here, and, importantly, what "long" means in this context.
In many practical circumstances, "short" might be a few bytes, while "long" is 16 bytes. But maybe your idea of "long" is actually much longer.
If you're curious how your own algorithm stacks up to ripgrep's, you can plug your implementation into the `memchr` crate's benchmark harness: https://github.com/BurntSushi/memchr
It uses rebar: https://github.com/BurntSushi/rebar
There's pretty wide variety in the performance of regular expressions between different languages, and efficient implementations will often recognize when your regular expression has a literal suffix/prefix, and optimize accordingly.
That doesn't help you if you're stuck using a library that doesn't perform those optimizations, but it means you need to be careful about importing your assumptions about regex performance from one language to another.
See also: https://github.com/burntSushi/rebar
In Regular expression matching can be simple and fast (2007)Showing the 15 most recent of 44 sources. Enable JavaScript to search and browse every indexed mention.