Files
Adrien GuilloandClaude Opus 4.8 a0a7ad549c perf(query): gallop sorted-array intersections in phrase scorer
The phrase scorer intersects sorted position lists with a linear
two-pointer merge (O(n+m)). When the two lists differ greatly in size
(e.g. a rare term and a frequent one in a phrase), this walks the long
list element by element to find a handful of matches.

Add a galloping (exponential + binary search) variant, shared via a
`gallop_find` helper, and route `intersection_count` / `intersection`
to it behind a size guard (`GALLOP_RATIO = 64`): gallop only when one
list is >=64x the other, otherwise keep the cache-friendly two-pointer.
This avoids the known galloping regression on balanced/dense inputs.

Equivalence with the linear reference is checked by a proptest over a
wide range of sizes (both small/large branches). Slop variants are left
on the two-pointer (range-match + best-match bookkeeping make galloping
correctness-risky, and slop>0 phrases are less common).

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
2026-10-14 16:10:25 -04:00
..
2026-09-23 20:21:08 +08:00
2023-07-03 22:05:11 +09:00
2026-07-03 13:42:33 +02:00
2023-05-10 13:01:56 +02:00
2026-07-10 12:33:33 +02:00
2026-07-10 12:33:33 +02:00
2023-05-10 13:01:56 +02:00