perf: Teddy SIMD 8.6x slower than Rust due to Go/assembly boundary overhead

[kolkov]

Problem

Teddy SIMD multi-pattern prefilter is 8.6x slower than Rust on identical workloads despite implementing the same algorithm (PSHUFB nibble-based matching).

Benchmark (6 MB DNA input, AMD EPYC, regex-bench CI)

Engine	dna_4 time	Throughput
Rust regex (Teddy AVX2, inlined)	3.7 ms	1.6 GB/s
coregex (Teddy SSSE3, Go asm)	32 ms	187 MB/s
Go stdlib regexp	349 ms	17 MB/s

All 9 regexdna patterns affected (v0.12.3, UseTeddy strategy).

Root Cause

Go/assembly function call boundary overhead:

1. Each findSIMD() = Go→asm→Go round-trip (~50-65 cycles: function call + VZEROUPPER + register save/restore)
2. 375K calls per 6MB scan (16 bytes/call with SSSE3)
3. AVX2 disabled — was 4x slower than SSSE3 due to VZEROUPPER cost dominating
4. Rust avoids this entirely — #[inline(always)] keeps the whole find+verify loop in one native code block

Profiling (local, 6MB DNA)

FindAllIndicesStreaming: avg 25.1 ms
Raw Teddy.FindMatch:    avg 24.0 ms  (96%)
FindAll loop overhead:  avg  1.1 ms  ( 4%)

100% of the gap is in SIMD function call overhead.

Breakdown

Factor	Estimated Impact
SSSE3 vs AVX2 (16 vs 32 bytes/iter)	~2x
Go/asm boundary per findSIMD call	~3-4x
Go method dispatch + bounds checks	~1.2x
Combined	~8-10x (measured: 8.6x)

Potential Solutions

A. simd/archsimd Intrinsics (Go 1.26, GOEXPERIMENT=simd)

Rewrite Teddy core using compiler intrinsics — eliminates Go/asm boundary entirely.
Needs POC to verify: Permute() = PSHUFB? ToMask() = PMOVMSKB? Performance?

B. Batch FindAll in Assembly

Single Go→asm call for entire haystack. Find+verify loop stays in asm.
Results written to pre-allocated buffer.

C. Monolithic ASM Teddy

Entire FindMatch loop in assembly. Maximum performance, highest maintenance.

Research

Full analysis: docs/dev/research/teddy-10x-gap-analysis.md

Related

• DNA benchmark results: https://github.com/kolkov/regex-bench/actions/runs/22075682957
• v0.12.3 cross-product fix: fix: cross-product literal expansion for char classes (110x speedup on regexdna) #119
• AVX2 regression: prefilter/teddy_ssse3_amd64.go:76-82

[kolkov]

Research Update: simd/archsimd (Go 1.26) — All Operations Available

Following feedback from @randall77 on golang/go#77647 ("I think some of these are already available"), we investigated the simd/archsimd package (Go 1.26, GOEXPERIMENT=simd).

Result: every operation Teddy needs is available.

Operation Mapping

Teddy Operation	x86 Instruction	archsimd Method
Nibble lookup (128-bit)	VPSHUFB	Uint8x16.PermuteOrZero(Int8x16)
Nibble lookup (256-bit)	VPSHUFB YMM	Uint8x32.PermuteOrZeroGrouped(Int8x32)
Bitmask extraction	VPMOVMSKB	ToMask().ToBits() → uint16/uint32
High nibble shift	VPSRLW $4 + VPAND	AsUint16x8().ShiftAllRight(4).AsUint8x16().And(mask0F)
Bitwise AND/OR	VPAND/VPOR	.And() / .Or()
All-zeros test	VPTEST	.IsZero()
Load 16/32 bytes	VMOVDQU	LoadUint8x16Slice / LoadUint8x32Slice

Key Details

• PermuteOrZero uses signed Int8x16 — bit-7 zeroing semantics match PSHUFB exactly
• PermuteOrZeroGrouped (AVX2) operates within 128-bit lanes — correct for Teddy
• No VZEROUPPER penalty — compiler manages AVX/SSE transitions automatically
• AVX2 should work — our current AVX2 is disabled because VZEROUPPER per Go/asm call makes it 4x slower than SSSE3 (perf: AVX2 Slim Teddy shows 6x regression in high false-positive workloads #74). With archsimd, AVX2 can be re-enabled

Example: Teddy core in pure Go

mask0F := archsimd.BroadcastUint8x16(0x0F)

// Low nibble lookup
loNibbles := input.And(mask0F)
loRes := loTable.PermuteOrZero(loNibbles.AsInt8x16())

// High nibble lookup
hiNibbles := input.AsUint16x8().ShiftAllRight(4).AsUint8x16().And(mask0F)
hiRes := hiTable.PermuteOrZero(hiNibbles.AsInt8x16())

// Combine + extract candidates
bits := loRes.And(hiRes).ToMask().ToBits()

Maps 1:1 to our current hand-written assembly, but with zero Go/asm boundary crossings.

Plan

1. V130-002: SSSE3 Teddy rewrite with archsimd (128-bit)
2. V130-003: AVX2 Teddy with archsimd (256-bit, re-enabled)
3. V130-004: Benchmark validation on regex-bench CI vs Rust

Risk

• simd/archsimd is experimental (not under Go 1 compatibility promise)
• Known codegen bug: simd/archsimd: Generated code doesn't use Y15 but spills register to stack golang/go#76969 (Y15 register spill)
• Assembly fallback kept for !goexperiment.simd builds

References

• simd/archsimd: architecture-specific SIMD intrinsics under a GOEXPERIMENT golang/go#73787 — archsimd proposal (our comment posted)
• simd/archsimd: would intrinsics eliminate Go/assembly boundary overhead for SIMD prefilter? golang/go#77647 — our feature request (closed, but @randall77 confirmed ops exist)

[kolkov]

Update: archsimd experiment plan (Go 1.26)

Go 1.26 shipped simd/archsimd (Feb 2026) — compiler intrinsics that eliminate the Go/assembly boundary overhead identified as the root cause of the 8.6x gap.

Status: Experimental (GOEXPERIMENT=simd), not covered by Go 1 compatibility promise. API may change. Suitable for POC experimentation, not production yet.

Experiment Plan

Six sequential tasks planned:

Task	Description	Priority	Depends on
V128-001	Upgrade Go toolchain to 1.26	critical	—
V128-002	archsimd API verification — verify PSHUFB/PMOVMSKB mapping, micro-benchmarks	critical	V128-001
V128-003	archsimd Teddy SSSE3 (128-bit) rewrite	critical	V128-002
V128-004	archsimd Teddy AVX2 (256-bit) — re-enable without VZEROUPPER	high	V128-003
V128-005	archsimd Memchr/Memmem rewrite	medium	V128-001
V128-006	CI + regex-bench validation with GOEXPERIMENT=simd	high	V128-003

Key questions to validate in V128-002

1. PermuteOrZero = PSHUFB semantics? (zero when index high bit set)
2. ToMask().ToBits() = PMOVMSKB? (extract byte high bits to uint16/uint32)
3. Byte-level shift right by 4 for nibble extraction?
4. AVX2 PermuteOrZeroGrouped = per-lane (not cross-lane)?
5. Known issue simd/archsimd: Generated code doesn't use Y15 but spills register to stack golang/go#76969 — Y15 register spilling impact on AVX2?

Expected outcome

If archsimd intrinsics inline correctly, the 375K Go→asm round-trips per 6MB scan become zero. Combined with AVX2 re-enablement (no VZEROUPPER needed), the theoretical gap should narrow from 8.6x to ~2x (remaining: Rust's auto-vectorization and loop unrolling advantages).

Timeline

Blocked on Go 1.26 local setup (V128-001). archsimd is experimental — results will determine whether to ship behind //go:build goexperiment.simd or wait for stable API in Go 1.27+.