mirror of
https://github.com/quickwit-oss/tantivy.git
synced 2026-11-20 01:24:15 +00:00
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>