Summary Regex.findAll (and everything built on it: findIter, replaceAll, split) has quadratic time complexity in the input length, despite the engine's documented linear-time guarantee. The linear-time property holds for a single NFA simulation, but findAll constructs a fresh VM and rescans input[pos..] from scratch for every match, so scanning a string with m matches costs ~O(n·m).
Location src/regex.zig:289-328 — the findAll loop:
while (pos < input.len) {
.thompson_nfa => {
const nfa_mut = @constCast(&self.nfa);
var virtual_machine = vm.VM.init(self.allocator, nfa_mut, self.capture_count, self.flags); // re-init every match
if (try virtual_machine.find(input[pos..])) |result| { ... pos = ... }A new vm.VM is constructed per match and find re-scans the entire remaining input each iteration instead of resuming from where the previous match ended.
Reproduction Self-contained, depends only on the public API and Zig 0.16. Save as repro.zig in the repo root:
const std = ;
const Regex = .Regex;
// libc monotonic clock (Zig 0.16 std.time has no Timer/nanoTimestamp).
fn nowNs() u64 {
var ts: std.c.timespec = undefined;
_ = std.c.clock_gettime(.UPTIME_RAW, &ts);
return @as(u64, @intCast(ts.sec)) * 1_000_000_000 + @as(u64, @intCast(ts.nsec));
}
pub fn main() !void {
const a = std.heap.c_allocator;
var re = try Regex.compile(a, "Sherlock");
defer re.deinit();
// "Sherlock" every 64 bytes; double the input size each step.
for ([_]usize{ 1, 2, 4, 8, 16 }) |k| {
const n = k * 16 * 1024;
const buf = try a.alloc(u8, n);
defer a.free(buf);
@memset(buf, '.');
var i: usize = 0;
while (i + 8 <= n) : (i += 64) @memcpy(buf[i .. i + 8], "Sherlock");
const t0 = nowNs();
const matches = try re.findAll(a, buf);
const dt_ms = @as(f64, @floatFromInt(nowNs() - t0)) / 1_000_000.0;
for (matches) |*m| {
var mm = m.*;
mm.deinit(a);
}
a.free(matches);
std.debug.print("{d:>6} KiB -> {d:.1} ms ({d} matches)\n", .{ n / 1024, dt_ms, matches.len });
}
}Build and run (links libc for the clock and the c_allocator):
zig build-exe repro.zig --dep regex -Mregex=src/root.zig -Mroot=repro.zig -lc -OReleaseFast ./repro Observed output (Apple Silicon, Zig 0.16.0, ReleaseFast):
16 KiB -> ~400 ms (256 matches)
32 KiB -> ~1600 ms (512 matches)
64 KiB -> ~6500 ms (1024 matches)128 KiB -> ~26000 ms (2048 matches) Doubling the input ~quadruples the time — clearly quadratic. The match counts are correct; this is purely a performance defect. (Larger inputs are impractical to include in the repro for the same reason.)
Impact findAll / findIter / replaceAll / split are unusable on inputs beyond a few KB. Contradicts the O(n×m) linear-time claim in docs/BENCHMARKS.md and the README for any "find all" use case. Suggested fix Single-pass multi-match scan instead of restart-per-match:
Reuse one vm.VM across matches (init once, reset state between matches) rather than VM.init per iteration. Resume scanning from the previous match end without re-walking already-consumed input — a true streaming cursor. Keep the existing zero-width-match guard (pos = if (end > start) end else end + 1). This restores linear O(n·states) for "find all" and aligns it with the documented complexity.