Skip to content

perf: v0.11.3 prefix fast path 319-552x speedup (#99) #101

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
kolkov merged 1 commit into from
Jan 16, 2026
Merged

perf: v0.11.3 prefix fast path 319-552x speedup (#99) #101

kolkov merged 1 commit into from
Jan 16, 2026

Conversation

@kolkov
Copy link
Contributor

@kolkov kolkov commented Jan 16, 2026

Summary

  • Prefix verification fast path for UseMultilineReverseSuffix
  • Pattern (?m)^/.*\.php now 319-552x faster than stdlib

Algorithm

  1. Suffix prefilter finds .php candidates (SIMD memmem)
  2. SIMD backward scan to find line start (bytes.LastIndexByte)
  3. O(1) prefix byte check (/ at line start)
  4. Skip-to-next-line on mismatch (avoids O(n²) worst case)
  5. DFA fallback for complex patterns without extractable prefix

Benchmarks (pattern (?m)^/.*\.php on 1KB log)

Operation coregex stdlib Speedup
IsMatch 182 ns 100 µs 552x
Find 240 ns 81 µs 338x
CountAll 58 µs 18.7 ms 319x

Test plan

  • All multiline tests pass
  • No regressions on other patterns
  • Linter passes

Fixes #99

@kolkov
perf: UseMultilineReverseSuffix prefix fast path 319-552x speedup (#99)
f075328 
Algorithm: suffix prefilter → SIMD backward scan → O(1) prefix byte check
Skip-to-next-line optimization avoids O(n²) worst case
DFA fallback for complex patterns without extractable prefix

Benchmarks (pattern (?m)^/.*\.php on 1KB log):
- IsMatch: 182 ns vs 100 µs stdlib = 552x faster
- Find: 240 ns vs 81 µs stdlib = 338x faster
- CountAll: 58 µs vs 18.7 ms stdlib = 319x faster

Fixes #99
@github-actions
Copy link

github-actions bot commented Jan 16, 2026

Benchmark Comparison

Comparing main → PR #101

Summary: geomean 252.6n 252.5n -0.03%

⚠️ Potential regressions detected:

geomean                               ³                +0.00%               ³
geomean                               ³                +0.00%               ³
geomean                         ³                +0.00%               ³
geomean                         ³                +0.00%               ³
AhoCorasickVsStdlib/stdlib_FindAllIndex-4               199.2µ ± ∞ ¹    203.9µ ± ∞ ¹    +2.35% (p=0.016 n=5)
MatchAnchoredLiteral/short_match-4                      6.855n ± ∞ ¹    7.190n ± ∞ ¹    +4.89% (p=0.008 n=5)
MatchAnchoredLiteral/no_match_suffix-4                  4.098n ± ∞ ¹    4.387n ± ∞ ¹    +7.05% (p=0.008 n=5)
AnchoredLiteralVsStdlib/coregex_short-4                 8.783n ± ∞ ¹    9.069n ± ∞ ¹    +3.26% (p=0.008 n=5)
AnchoredLiteralVsStdlib/coregex_medium-4                9.510n ± ∞ ¹    9.693n ± ∞ ¹    +1.92% (p=0.008 n=5)
AnchoredLiteralVsStdlib/coregex_no_match-4              5.963n ± ∞ ¹    6.299n ± ∞ ¹    +5.63% (p=0.008 n=5)

Full results available in workflow artifacts. CI runners have ~10-20% variance.
For accurate benchmarks, run locally: ./scripts/bench.sh --compare

@kolkov kolkov merged commit 43efbbd into main Jan 16, 2026
15 checks passed
@kolkov kolkov deleted the hotfix/v0.11.3-prefix-fastpath branch January 16, 2026 14:44
@kolkov kolkov mentioned this pull request Jan 16, 2026
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

perf: Multiline patterns 84x slower than Rust regex

2 participants

@kolkov