coregex FindAllStringIndex slower than stdlib

[tjbrains]

To find variables in a string, we use regexp to match \${[@\w.|-]+}:

func BenchmarkFindStringIndex_Found_regexp(b *testing.B) {
	var reg = regexp.MustCompile(`\${[@\w.|-]+}`)

	b.ReportAllocs()
	b.ResetTimer()

	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			var indexes = reg.FindAllStringIndex("hello, ${name}, ${age}, ${gender}, ${home}, world", -1)
			if len(indexes) != 4 {
				b.Fatal(len(indexes))
			}
		}
	})
}

func BenchmarkFindStringIndex_Found_coregex(b *testing.B) {
	var reg = coregex.MustCompile(`\${[@\w.|-]+}`)

	b.ReportAllocs()
	b.ResetTimer()

	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			var indexes = reg.FindAllStringIndex("hello, ${name}, ${age}, ${gender}, ${home}, world", -1)
			if len(indexes) != 4 {
				b.Fatal(len(indexes))
			}
		}
	})
}

func BenchmarkFindStringIndex_NotFound_regexp(b *testing.B) {
	var reg = regexp.MustCompile(`\${[@\w.|-]+}`)

	b.ReportAllocs()
	b.ResetTimer()

	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			var indexes = reg.FindAllStringIndex("hello, world", -1)
			if len(indexes) != 0 {
				b.Fatal(len(indexes))
			}
		}
	})
}

func BenchmarkFindStringIndex_NotFound_coregex(b *testing.B) {
	var reg = coregex.MustCompile(`\${[@\w.|-]+}`)

	b.ReportAllocs()
	b.ResetTimer()

	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			var indexes = reg.FindAllStringIndex("hello, world", -1)
			if len(indexes) != 0 {
				b.Fatal(len(indexes))
			}
		}
	})
}

benchmark result:

goos: darwin
goarch: arm64
cpu: Apple M2 Max
BenchmarkFindStringIndex_Found_regexp-12                 7014567               171.8 ns/op           324 B/op          5 allocs/op
BenchmarkFindStringIndex_Found_coregex-12                1586851               757.5 ns/op           161 B/op          5 allocs/op
BenchmarkFindStringIndex_NotFound_regexp-12             124449542                9.214 ns/op           0 B/op          0 allocs/op
BenchmarkFindStringIndex_NotFound_coregex-12            14020056                84.74 ns/op            0 B/op          0 allocs/op
PASS
ok 

As we see, coregex is ~6x-8x slower than stdlib.

[tjbrains]

coregex version: v0.12.19

[kolkov]

Thanks for the report! Investigated this on v0.12.20.

Root cause: Strategy selects UseNFA (PikeVM) instead of UseDFA for this pattern. PikeVM is O(n×states) per byte, while lazy DFA is O(n). On short inputs the per-match overhead dominates.

On our Intel i7-1255U (x86 with AVX2 SIMD):

Found (49 bytes, 4 matches):
  stdlib:  945 ns/op
  coregex: 1186 ns/op  (1.3x slower)

NotFound (12 bytes):
  stdlib:  41 ns/op
  coregex: 65 ns/op  (1.6x slower)

Your M2 ARM64 shows a much larger gap (4.4x / 9.2x) because ARM64 currently has no SIMD prefilters — the Memmem scan for ${ falls back to pure Go scalar code.

Two issues to fix:

1. Route this pattern to DFA instead of NFA (tracked internally)
2. ARM64 prefilter fallback is too slow without NEON SIMD (tracked in v0.9.0+: ARM NEON SIMD support #23)

coregex is optimized for bulk text processing (KB-MB inputs) where prefilters and DFA amortize their setup cost. On ~50 byte inputs, stdlib's simpler NFA has less overhead. We're working on reducing the per-call overhead.

[kolkov]

Update: verified against Rust regex on the same machine (Intel i7-1255U, x86):

Pattern: \${[@\w.|-]+}
Input: "hello, ${name}, ${age}, ${gender}, ${home}, world" (49 bytes, 4 matches)

Found:
  Go stdlib:  1465 ns/op
  coregex:    1386 ns/op  (1.05x faster than stdlib)
  Rust regex:  285 ns/op  (4.9x faster than coregex)

NotFound (12 bytes):
  Go stdlib:    47 ns/op
  coregex:      67 ns/op  (1.4x slower than stdlib)
  Rust regex:   49 ns/op  (1.4x faster than coregex)

So on x86 coregex matches stdlib, but Rust is ~5x faster on this short input. The gap comes from:

1. Strategy selects UseNFA (PikeVM) instead of UseDFA — fixing this should close most of the gap
2. Per-call overhead on short inputs: sync.Pool, result slice allocation

On your M2 ARM64 the gap is larger because there are no SIMD prefilters yet — tracked in #23.

Working on both — DFA routing fix and ARM64 SIMD.

[kolkov]

Update: v0.12.21 released with improvements relevant to this issue:

1. Strategy fix: patterns like \${[@\w.|-]+} now route to DFA instead of PikeVM (7x faster on large inputs)
2. zx+ correctness fix: MatchString("zzx") now returns true (was false due to prefilter skip bug)
3. New zero-alloc API — for performance-sensitive code:

// Zero allocation iterator (Go 1.23+, like Rust find_iter):
for m := range re.AllIndex(data) {
    // m[0] = start, m[1] = end
}

// Buffer-reuse (strconv.Append* pattern):
var buf [][2]int
buf = re.AppendAllIndex(buf[:0], data, -1)

Our results on Intel i7-1255U (x86, same pattern):

Found (49 bytes, 4 matches):
  Go stdlib:  1465 ns/op
  coregex:    1386 ns/op  (1.05x faster than stdlib)
  Rust regex:  285 ns/op  (4.9x faster than coregex)

The remaining gap vs Rust is per-call overhead (sync.Pool, function dispatch). On large inputs coregex is significantly faster than stdlib.

ARM64 SIMD prefilters tracked in #23 — this will close the gap on your M2.

go get github.com/coregx/coregex@v0.12.21