Benchmarks & Performance
regex.zig includes a dedicated client-side benchmark suite (bench/main.zig) measuring real-world regex compilation, literal prefiltering, submatch extraction, string transformation, and adversarial input resilience.
Measured Performance Results
Benchmarks executed natively on a 64-bit target using Zig 0.17.0 with -O ReleaseFast using an industry-standard benchmark harness (warmup phase followed by multi-round statistical averaging across 5 independent measurement passes):
| Scenario | Iterations (5 rounds) | Avg Latency (ns/op) | Throughput (ops/s) | Bandwidth / Note |
|---|---|---|---|---|
| Literal search (2KB haystack) | 10,000 | 22.0 ns | 45,438,023 ops/s | 86,926.15 MB/s (SIMD substring prefilter) |
| Email pattern compilation | 5,000 | 54.2 µs | 18,438 ops/s | 0.81 MB/s (AST parsing & NFA compilation) |
| Email matching throughput | 20,000 | 1.5 µs | 659,599 ops/s | 45.29 MB/s (PikeVM dual-queue execution) |
| Named captures extraction | 20,000 | 3.8 µs | 258,818 ops/s | 9.63 MB/s (Zero-alloc capture slot resolution) |
| ReplaceAll 10 numbers | 10,000 | 7.1 µs | 139,142 ops/s | 6.24 MB/s (Dynamic template expansion) |
Pathological pattern (a+)+$ | 1,000 | 11.8 µs | 84,552 ops/s | Linear-Time $O(N)$ execution |
Linear-Time Execution & ReDoS Immunity
Regular Expression Denial of Service (ReDoS) occurs when an engine attempts exponential numbers of paths through an expression with nested repetitions.
In regex.zig, execution is powered by an in-order Thompson Non-Deterministic Finite Automaton (NFA) executed with Rob Pike's Virtual Machine (PikeVM):
$$\text{Worst-Case Runtime: } O(M \times N)$$
Where:
- $M$ is the number of instructions in the compiled program.
- $N$ is the input length in bytes.
Pathological Test Case: (a+)+$ on a^30!
When evaluated against the pathological input $a^{30}!$, regex.zig advances all active candidate states in parallel across lockstep thread queues. Redundant states at the same byte position are pruned in $O(1)$ time using a compact visited bitmap.
- Execution Time: 12.6 microseconds
- Backtracking Steps: 0 (non-backtracking)
- Outcome: Deterministic linear-time rejection without CPU spikes or thread freezing.
Running Benchmarks Locally
Execute the benchmark suite using the standard Zig build system:
zig build benchTo run benchmarks in ReleaseFast mode:
zig build bench -Doptimize=ReleaseFast