perf: SIMD acceleration for sparse char_class matches

[kolkov]

Summary

Add SIMD-accelerated search for CharClassSearcher when matches are sparse (>64 non-matching bytes between matches).

Background

In PR #63, we evaluated SIMD for char_class patterns but found it slower for the common case where matches are frequent (30-50% of positions). However, SIMD can provide significant speedup when:

• Searching for rare characters in large text
• Patterns like [0-9]+ in mostly alphabetic text
• Log parsing where keywords are sparse

Proposed Implementation

Hybrid Approach

func (s *CharClassSearcher) SearchAt(haystack []byte, at int) (int, int, bool) {
    // For sparse search (gap > 64 bytes), use SIMD to find first match
    if s.sparseHint && len(haystack)-at > 64 {
        pos := simd.MemchrInTable(haystack[at:], &s.membership)
        if pos == -1 {
            return -1, -1, false
        }
        at += pos
    }
    
    // Then use scalar for match extent
    // ...
}

SIMD Functions (already implemented)

• simd.MemchrWord(haystack) - find first [A-Za-z0-9_]
• simd.MemchrNotWord(haystack) - find first non-word char
• simd.MemchrInTable(haystack, table) - generic 256-byte table lookup

Acceptance Criteria

• Detect sparse vs dense patterns (heuristic or adaptive)
• Use SIMD MemchrInTable for sparse search
• Benchmark: >2x speedup on sparse patterns
• No regression on dense patterns (existing tests)

References

• PR perf: streaming state machine for CharClassSearcher FindAll #63: Streaming state machine for CharClassSearcher
• simd/memchr_class_amd64.s: AVX2 implementation ready
• Rust regex approach: Uses DFA with SIMD byte classification

Priority

Low - Current streaming implementation is already 4.9x faster than stdlib. This is an optimization for edge cases.

[kolkov]

Update (v0.10.0):

Current CharClassSearcher is now 35% faster than Rust regex on the char_class benchmark (33.5ms vs 53.0ms).

The 256-byte lookup table approach is optimal for high-frequency matches. SIMD acceleration should only be considered for sparse patterns where matches are rare.

This issue remains valid for the sparse case but is now low priority since we beat Rust on the common case.

See #71 for documentation of this optimization.

[kolkov]

Update: char_class [\w]+ is now 1.3x faster than Rust on EPYC CI (v0.12.21):

char_class: coregex 42.10ms vs Rust 56.42ms (EPYC 9V74, 6MB)

CharClassSearcher with lookup table approach outperforms Rust's DFA for simple character class patterns. No SIMD needed for this specific case.

For more complex sparse character classes, SIMD acceleration could still help — keeping this issue open for those cases.