perf: excessive memory usage with multiple patterns on large inputs (237MB vs 28MB stdlib)

[kolkov]

Problem

When multiple compiled patterns are used on large inputs, memory usage becomes excessive. On LangArena's LogParser benchmark (13 patterns × 7MB text), coregex uses 237MB vs stdlib 28MB (8.5x more) vs Rust 11MB (21x more).

Root Causes

1. BoundedBacktracker visited tables: Each FindAllStringIndex call allocates a visited table sized len(haystack) * nfa_states. With uint16 generation counters, each entry is 2 bytes. For 7MB × 35 states = 245MB per pattern scan.
2. Lazy DFA cache: Each compiled pattern has its own DFA state cache. 13 patterns × independent caches.
3. No sharing: Unlike Rust, visited tables and DFA caches are not shared across patterns.

Proposed Solutions

1. Visited table reuse via sync.Pool — Pool visited tables by size class, reuse across FindAll calls
2. Visited table cap — Limit visited table to search span, not full haystack (partially done in v0.12.6 span fix, but could be more aggressive)
3. Shared DFA cache pool — Allow multiple compiled patterns to share a DFA cache pool
4. 1-bit visited with lazy reset — Use 1-bit per entry with segmented lazy clear (avoid O(n) full clear)

Impact

• LogParser: 237MB → ~30-50MB target
• Any workload with multiple patterns on large inputs

References

• Issue Not success usage in my project #124 (original report by @kostya)

[kolkov]

Update with v0.12.21 results:

FindAllStringIndex (stdlib-compat API) still allocates [][]int per match:

• TotalAlloc: 237 MB for 13 patterns × 10 iterations (was 237 MB in issue)
• This is []int{start, end} per match × 203K matches per iteration

New zero-alloc API added in v0.12.21 eliminates this entirely:

// Zero allocation — iterator (like Rust find_iter):
for m := range re.AllIndex(data) {
    // m[0] = start, m[1] = end — stack-allocated, no heap
}

// Or buffer-reuse:
var buf [][2]int
buf = re.AppendAllIndex(buf[:0], data, -1)

Benchmark (errors pattern, 33K matches):

Method	Alloc	Mallocs	Time
FindAllStringIndex	3890 KB	19	8.2ms
AllIndex (iter)	0 KB	0	5.9ms
AppendAllIndex	0 KB	0	5.5ms

Also: mallocs per iteration dropped from 203K to 182 (flat buffer for stdlib-compat path).

RSS (Sys): 42.7 MB → 38.2 MB.

The remaining ~38 MB is Go runtime overhead (~8 MB) + DFA caches (2 MB × patterns) + heap for log data (7.2 MB). Rust uses ~15-20 MB (no GC overhead).