moonbitlang / core / 6241

91%

push

github

perf(builtin): guaranteed-linear KMP fallback for substring search

The SIMD two-anchor find/rev_find already cut over to a fallback after
enough dense false-anchor candidates, but that fallback was a naive
scalar scan — still O(target * pattern) on adversarial inputs where
both anchors and long pattern prefixes recur throughout the target
(e.g. needle 'a'*32 + 'Z' + 'a'*31 over all-'a' text). This replaces
the naive fallback with KMP, making find/rev_find O(target + pattern)
in the worst case: the existing cutover budget trips on the 65th
failed verification (`failures > 64`), capping pre-fallback
verification at O(pattern) work, and the fallback itself
is linear. The failure-table allocation is paid only after cutover,
i.e. exclusively on pathological inputs. Resolves the standing TODO on
find/rev_find ("consider using Two-Way algorithm to ensure linear time
complexity") — KMP behind the existing budget gives the same guarantee
with less machinery.

The reverse fallback runs forward KMP over the prefix that can still
contain a hit and keeps the rightmost match, continuing through
overlaps via the failure table.

The idea comes from PR #3786 (mizchi), whose dense-case analysis and
verified-fallback design predate the SIMD two-anchor work that
superseded its scanner; this lands its remaining piece.

Benchmarks (moon bench --release, main -> this branch):

  adversary find  m=64  n=4096:  native 48.6 -> 6.1us (8.0x),
    js 453 -> 27.3us (16.6x), wasm-gc 112 -> 10.6us (10.6x)
  adversary rev_find m=64 n=4096: native 48.8 -> 7.0us,
    js 456 -> 27.4us, wasm-gc 112 -> 12.4us
  scaling adversary m=512 n=65536: native 7.20ms -> 91us (79x),
    js 56.2ms -> 433us (130x), wasm-gc 15.0ms -> 175us (86x) —
    the O(n*m) -> O(n+m) signature
  fast paths (dense miss, rare hit): par on all backends; the SIMD
    two-anchor path is untouched.

Tests: whitebox KMP tests over periodic/overlapping patterns and
boundary starts; blackbox end-to-end tests built from de... (continued)

27 of 27 new or added lines in 1 file covered. (100.0%)

16309 of 17972 relevant lines covered (90.75%)

331892.12 hits per line