Benchmark comparison with Rust regex crate

[i11010520]

Here is a benchmark comparison between zig-regex and the Rust regex crate (generated via OpenCode / DeepSeek V4 Flash Free).
While Zig wins on I/O and process startup time, zig-regex lags significantly behind in search throughput—especially for findAll.

What architectural changes or optimizations could we introduce to improve zig-regex performance for both single-match and multi-match operations, particularly for findAll?

---

zig-regex vs Rust regex crate — Performance Comparison

Date: 2026-06-02
Platform: Apple M4, macOS
Zig: 0.16.0
Rust: 1.96.0
Rust regex crate: 1.12.3
zig-regex: zig-utils/zig-regex @ latest (2026-06-02)

Methodology

We compare the search throughput of both engines — how fast they can count all
matches of a pattern in a haystack — excluding process startup time.

Each program:

1. Reads the full haystack from stdin into memory
2. Compiles the regex pattern
3. Runs 1 warmup iteration (ignored from timing)
4. Records a timestamp
5. Runs N iterations (scanning the full haystack each time)
6. Records another timestamp
7. Prints total_matches iterations elapsed_ns to stdout

The elapsed time divided by iterations gives the time per full-scan.

Haystack

A 1.17 MB synthetic text file generated from a pool of words:
hello, world, foo123, bar456, baz789, test, regex, zig, rust

Generated with:

import random
words = ['hello', 'world', 'foo123', 'bar456', 'baz789', 'test', 'regex', 'zig', 'rust']
text = ' '.join(random.choice(words) for _ in range(200000))

Programs

Rust (/tmp/rust-bench)

use std::io::Read;
use std::time::Instant;
use regex::Regex;

fn main() {
    let args: Vec<String> = std::env::args().collect();
    let pattern = &args[1];
    let iterations: usize = args.get(2).and_then(|s| s.parse().ok()).unwrap_or(1);

    let mut haystack = String::new();
    std::io::stdin().read_to_string(&mut haystack).unwrap();

    let re = Regex::new(pattern).unwrap();
    let _ = re.find_iter(&haystack).count(); // warmup

    let start = Instant::now();
    let mut total = 0usize;
    for _ in 0..iterations {
        total += re.find_iter(&haystack).count();
    }
    let elapsed = start.elapsed();

    eprintln!("{} {} {}.{:09}", total, iterations, elapsed.as_secs(), elapsed.subsec_nanos());
}

Uses regex::Regex::find_iter — a lazy, zero-allocation iterator over match
positions. No per-match heap allocations.

Zig (/tmp/zig-bench)

Uses the zig-utils/zig-regex library, built with -Doptimize=ReleaseFast.

const std = @import("std");
const Regex = @import("regex").Regex;

pub fn main(init: std.process.Init) !void {
    const allocator = init.gpa;
    const arena = init.arena.allocator();
    const io = init.io;

    const args = try init.minimal.args.toSlice(arena);
    const pattern = args[1];
    const iterations: usize = if (args.len > 2) try std.fmt.parseInt(usize, args[2], 10) else 1;

    var stdin_buf: [4096]u8 = undefined;
    var reader = std.Io.File.stdin().reader(io, &stdin_buf);
    var result: std.ArrayList(u8) = .empty;
    defer result.deinit(allocator);
    var chunk: [4096]u8 = undefined;
    while (true) {
        const n = try reader.interface.readSliceShort(&chunk);
        if (n == 0) break;
        try result.appendSlice(allocator, chunk[0..n]);
    }
    const haystack = try result.toOwnedSlice(allocator);
    defer allocator.free(haystack);

    var regex = try Regex.compile(allocator, pattern);
    defer regex.deinit();

    const warm_matches = try regex.findAll(allocator, haystack);
    defer {
        for (warm_matches) |*m| m.deinit(allocator);
        allocator.free(warm_matches);
    }

    const start = std.Io.Clock.awake.now(io);
    var total: usize = 0;
    var i: usize = 0;
    while (i < iterations) : (i += 1) {
        const matches = try regex.findAll(allocator, haystack);
        defer {
            for (matches) |*m| m.deinit(allocator);
            allocator.free(matches);
        }
        total += matches.len;
    }
    const end = std.Io.Clock.awake.now(io);
    const elapsed = start.durationTo(end);

    var buf: [64]u8 = undefined;
    var stdout_w = std.Io.File.stdout().writer(io, &buf);
    const stdout = &stdout_w.interface;
    try stdout.print("{} {} {}\n", .{ total, iterations, elapsed.nanoseconds });
    try stdout.flush();
}

Uses Regex.findAll — allocates a Match struct (with per-group capture slices)
for every match on every call. Each call also re-initializes the internal VM.

Engine-only results (1.17 MB haystack)

Timed programs that exclude stdin reading and process startup (see source above).

Operation	Matches	Zig	Rust	Ratio
Compile hello	—	6.8 µs	2.8 µs	2.4x
Single find hello	—	2.0 µs	~0.5 µs	~4x
findAll hello	21,899	60 ms	0.51 ms	118x
findAll hello|world|test	66,576	173 ms	2.87 ms	60x
findAll \d+	66,408	83 ms	3.78 ms	22x
findAll \w+	200,000	83 ms	6.35 ms	13x

CLI comparison (hyperfine, full process)

Comparing the zig-regex CLI vs our Rust bench binary on a 1.17 MB file,
both built with optimizations enabled:

Single match (find / find_iter with .count())

$ hyperfine -w 3 -r 30 \
    -n "Rust regex (ReleaseFast)" 'cat haystack.txt | ./rust-bench hello' \
    -n "Zig regex (ReleaseFast CLI)" 'cat haystack.txt | ./regex hello'

Rust (find + count):      5.3 ms
Zig  (find, first match): 4.2 ms    (1.25x **faster**)

For a single find (first match), zig-regex is slightly faster than Rust
in this test. The haystack match is near the beginning of the file, and zig-regex
finds it in ~2 µs after compile. The bulk of both runtimes is stdin I/O and
process startup.

All matches (findAll / find_iter with .count())

$ hyperfine -w 3 -r 20 \
    -n "Rust find_iter" 'cat haystack.txt | ./rust-bench hello' \
    -n "Zig findAll"    'cat haystack.txt | ./regex -g hello | wc -l'

Rust (find_iter):         5.3 ms
Zig  (findAll):          68 ms    (13x slower)

So zig-regex is fast for single matches (microseconds) but slow for findAll
(milliseconds) due to per-match VM re-init and allocation overhead (see below).

Rust compile: 2.82 ms / 1000 = 2.8 µs per compile.
Zig compile: 6.8 µs per compile — 2.4x slower because VM initialization
allocates internal state as part of the compilation path.

Why the gap?

The findAll gap (13-129x) has the same architectural causes. Crucially, for a
single find/isMatch, zig-regex is competitive — the gap only appears when
iterating over many matches because of:

1. VM re-initialization per match

zig-regex creates a new VM instance for every match in findAll (line 312 of
src/regex.zig):

var virtual_machine = vm.VM.init(self.allocator, nfa_mut, ...);

This allocates and sets up the VM's internal state. With 22k matches, that's 22k
VM init/destroy cycles.

Rust's find_iter uses a lazy DFA (deterministic finite automaton) that
runs continuously from one match to the next with no per-match teardown.

2. Per-match heap allocations

zig-regex's findAll allocates a Match struct (with capture group slices) on
the heap for every match:

try matches.append(allocator, Match{ .slice = ..., .captures = ... });

This means 22k heap allocations for 22k matches.

Rust's find_iter returns match offsets through a Match value type on the
stack — no heap allocations during iteration.

3. SIMD literal prefilters

Rust's regex crate uses the Teddy algorithm (SIMD-accelerated substring
search) to skip large non-matching regions. This is especially effective for
literal patterns like hello.

zig-regex implements basic prefix search (std.mem.indexOf) which is scalar
only.

Key takeaways

• Full CLI, single match (find): zig-regex (ReleaseFast CLI) was
  4.2 ms vs Rust 5.3 ms on a 1.17 MB file — both dominated by I/O,
  not regex. Zig was 1.25x faster in this end-to-end test.

• Engine only, compile + single find: zig-regex is 2-4x slower in raw
  engine time (6.8 µs vs 2.8 µs compile, 2.0 µs vs ~0.5 µs find), but these
  are single-digit microseconds — negligible. The CLI results invert because
  Zig's I/O and startup happen to be faster in this workload.

• All matches (findAll): Rust is 13-118x faster. The bottleneck is
  zig-regex's design: it re-initializes the VM and heap-allocates a Match
  (with captures) for every single result, while Rust's find_iter is a
  zero-allocation lazy iterator. A lightweight findIter that keeps the VM
  alive between iterations would shrink this gap significantly.

• The Rust regex crate is one of the most heavily optimized regex engines
  in existence (DFA compilation, lazy DFAs, SIMD/Teddy prefilters). zig-regex
  is a younger project using Thompson NFA + backtracking without an equivalent
  optimization pipeline.

[chrisbbreuer]

Thanks for sharing this!

I will focus on performance improvements soon! There's a lot of room for improvements 😊

[chrisbbreuer]

Added a reproducible benchmark harness and started closing the gap (commit 836486b on main).

Benchmark harness

• benchmarks/findall_throughput.zig — engine-only compile/find/findAll table, plus a stdin <pattern> <iters> mode that prints total iters elapsed_ns (same shape as the program in this issue). Run with zig build bench-findall.
• benchmarks/rust-bench/ — the Rust regex crate counterpart (find_iter), built --release + LTO.
• benchmarks/compare.sh — generates one deterministic ~1.17 MB haystack and feeds it to both binaries for an apples-to-apples comparison.

First round of optimizations

Two of the three causes called out in the report are addressed:

1. VM re-init per match → findAll now reuses a single VM across all matches.
2. No prefilter in findAll → findAll now uses the literal-prefix std.mem.indexOf prefilter that find already used (it previously re-ran the NFA at every byte).
3. The epsilon-closure visited bitmap is allocated once per VM and reused across positions instead of per-matchAt.

Results (Apple M4, Zig 0.16, 50 iterations)

pattern	matches	zig before	zig now	rust	now vs rust
hello	22,202	~60 ms	~6.7 ms	~0.42 ms	~16x
hello|world|test	66,631	~173 ms	~132 ms	~2.4 ms	~55x
\d+	66,651	~83 ms	~60 ms	~3.0 ms	~20x
\w+	200,000	~83 ms	~68 ms	~4.2 ms	~16x

Literal-led findAll improved the most (~118x → ~16x vs Rust).

What's left (roadmap)

The remaining gap on non-literal / dense-match patterns is architectural — today find runs matchAt from every start position, which is O(n²) when matches are dense. The plan:

1. Single-pass (Pike) VM — one leftmost unanchored pass, O(n·states). Biggest remaining win for \w+ / \d+.
2. Lazy DFA — byte-at-a-time scanning with no per-step thread bookkeeping.
3. Multi-literal / Teddy SIMD prefilter — for literal alternations like hello|world|test that have no single prefix today.

Documented in benchmarks/README.md.

[chrisbbreuer]

Update — the gap is closed. On the issue's 1.17 MB haystack, findAll vs the Rust regex crate went from 13–118x slower to 0.6–1.2x (faster than Rust on hello and \d+, near parity on the rest):

pattern	matches	#10 baseline	zig now	rust	ratio
hello	22,202	~60 ms	~0.6 ms	~0.7 ms	0.8x
hello|world|test	66,631	~173 ms	~2.8 ms	~2.3 ms	1.2x
\d+	66,651	~83 ms	~1.7 ms	~2.8 ms	0.6x
\w+	200,000	~83 ms	~4.7 ms	~4.6 ms	1.2x

Single find is now a few nanoseconds. Run ./benchmarks/compare.sh for your own numbers.

How (commits on main)

A series of fast paths that recognize common pattern shapes and bypass the NFA, plus allocation cuts — each falls back to the Thompson NFA when it doesn't apply, and all preserve the engine's exact match semantics (full test suite green):

• Repeated-atom fast path — \w+, \d+, [a-z]+, a+, x{2,5} match via a tight byte loop over a 256-entry membership table. This is what took \d+/\w+ to parity/better.
• Exact-literal fast path — fixed strings (hello) use a SIMD first-byte scan (indexOfScalarPos) + tail compare.
• Literal-alternation fast path — foo|bar|baz tries each literal directly (longest wins) at first-byte candidates.
• First-byte-set prefilter — skips positions whose byte can't start a match (generalizes the single literal-prefix filter).
• VM allocation cuts — visited bitmap + thread lists reused across positions; capture-less threads allocate nothing; findAll reuses one VM.

Still open (roadmap)

Arbitrary patterns that don't fit a fast path still run the Thompson NFA per position. Closing that fully needs a lazy DFA, Teddy SIMD multi-literal prefilters, and a zero-allocation match iterator/count (the 1.2x on \w+/alternation is partly findAll materializing a result vector, which Rust's lazy find_iter avoids).

[i11010520]

@chrisbbreuer What amazing improvement!

[chrisbbreuer]

Further update — the engine now beats the Rust regex crate on most patterns and is within ~2x on the rest. Full sweep over the 1.17 MB haystack (Regex.count vs find_iter().count(), both lazy & allocation-free; match counts verified identical):

pattern	zig	rust	ratio
hello	0.31 ms	0.37 ms	0.83x
hello|world|test	2.26 ms	2.51 ms	0.90x
\d+	0.86 ms	3.27 ms	0.26x
\w+	1.61 ms	4.21 ms	0.38x
[A-Za-z]+	1.73 ms	6.12 ms	0.28x
\d{1,3}	0.88 ms	2.92 ms	0.30x
foo[0-9]+	0.93 ms	1.04 ms	0.90x
([a-z]+)([0-9]+)	4.82 ms	3.78 ms	1.27x
a.c	1.09 ms	0.66 ms	1.66x
\w+[0-9]	8.23 ms	4.25 ms	1.94x

(Started at 13–118x slower in this issue.)

What was built (all on main, 457 tests)

• Regex.count — allocation-free counting (fair vs find_iter().count()).
• Fast paths: exact-literal (SIMD), repeated-atom (\w+/\d+/[a-z]+), literal-alternation, first-byte prefilter, required-literal fast-fail (mandatory literal absent ⇒ instant no-match).
• Lazy DFA (src/dfa.zig) for count/isMatch and capture-free find/findAll on general patterns.
• One-pass capture plan (src/onepass.zig) — deterministic capture extraction for disjoint-boundary atom sequences ((\w+)@(\w+), ([a-z]+)([0-9]+), …), incl. nullable atoms and a first-atom run-skip; differential-tested against the NFA.
• Case-insensitive fast paths — exact-literal (SIMD dual-case scan) and folded repeated-atom tables.
• VM allocation cuts (pooled visited bitmap / thread lists / capture buffers).

Remaining (modest)

The >1x cases (a.c, \w+[0-9], ([a-z]+)([0-9]+)) are general/ambiguous patterns that still do per-start anchored scanning. An unanchored DFA (single O(n) leftmost pass) would close those; it's the last architectural piece and is tracked for follow-up.

[i11010520]

I'm trying to build zg by AI, a grep replacement in Zig using zig-regex to beat ripgrep/rg.
Benchmark shows that test cases for patterns without literal prefix are 30-600x slower than rg.

Benchmark setup:
zig source tree (43,781 files, ~2.9 GB total), ReleaseSafe build, hyperfine 3 runs.

Pattern	zg	rg	Ratio
fn (literal)	368 ms	370 ms	~1.0x
fn|fn\s (alternation, literal prefix fn)	374 ms	373 ms	~1.0x
\w+\s+\w+ (no literal prefix)	17.1 s	0.51 s	33x
\w+\s+\w+ on single 2.9 GB file	5.2 s	8.6 ms	607x

Root cause guess:
The first two cases are on par because the application pre-filter catches lines before the regex engine runs.
The moment the pattern has no literal prefix, every line hits zig-regex and performance collapses.

ripgrep's grep crate builds a SIMD-accelerated multi-byte literal pre-filter (via memchr/aho-corasick) from the regex's required_literal or first_bytes hints, then feeds only candidate positions to the lazy DFA. For \w+\s+\w+, ripgrep likely extracts \s as a required literal byte (0x20, 0x09, etc.) and uses SIMD memchr to skip non-whitespace runs.

zig-regex already computes OptimizationInfo.required_literal and first_bytes, but there's no public API to expose these hints to the caller for building an application-level pre-filter. The caller's only option is to call find/findAll on every input — there's no way to ask "is this input worth feeding to the engine?" without running the engine.

Question:
Could zig-regex expose the pre-filter hints from OptimizationInfo (specifically literal_prefix, required_literal, first_bytes) through the public Regex API? Something like:

pub fn literalPrefix(self: *const Regex) ?[]const u8
pub fn requiredLiteral(self: *const Regex) ?[]const u8
pub fn firstBytes(self: *const Regex) ?std.StaticBitSet(256)

This would let callers build their own SIMD pre-filter (using std.mem.indexOf, memchr, or @import("builtin").cpu.features.*) and skip the engine call for non-matching inputs — the same strategy ripgrep uses.

(mainly generated by OpenCode/DeepSeek V4 Flash Free)