costin opened a new pull request, #16849: URL: https://github.com/apache/lucene/pull/16849
Since #16072, BitSetIterator#docIDRunEnd scans to the next clear bit on every call. This becomes a problem on long runs of bits which are rescanned on every window (e.g. DenseConjunctionBulkScore whenever the segment has deletions). To avoid the rescan, the PR extends BitSetIterator to remember the known end of the current and resume scanning from there. Each scan is capped at 2^16 bits past the current doc so callers only consume a prefix (doc-partitioned slices, early terminations) and not all of it. ### Benchmark AMD EPYC 7R32 (c5a.2xlarge), JDK 25 Filters: all = every doc matches prefix = one run over the first 90% of docs striped = one clear bit every 1000 docs (short-run control) liveDocs = ~0.1% deleted docs liveDocsSlice = same, scoring only the first 1/16th of docs conjunction = no deletes, second clause without long runs | filter | maxDoc | shape | main (ms/op) | this PR (ms/op) | speedup | pre-#16072 (ms/op) | |---|---|---|---|---|---|---| | all | 1M | liveDocs | 0.524 | 0.039 | 13x | 0.040 | | all | 10M | liveDocs | 48.80 | 0.511 | 96x | 0.441 | | all | 50M | liveDocs | 1213.0 | 2.159 | 562x | 2.015 | | all | 50M | liveDocsSlice | 150.9 | 0.136 | 1112x | 0.131 | | all | 50M | conjunction | 1212.4 | 2.217 | 547x | 3.299 | | prefix | 50M | liveDocs | 976.4 | 2.001 | 488x | 1.842 | | prefix | 50M | conjunction | 998.0 | 2.002 | 499x | 2.693 | | striped | 50M | liveDocs | 2.223 | 2.254 | 0.99x | 2.022 | | striped | 50M | conjunction | 3.876 | 3.693 | 1.05x | 3.166 | Regarding striped, #16072 itself is 4-20% slower than pre-#16072 since runs of 999 docs are shorter than the threshold (WINDOW_SIZE / 2), so every window pays a short scan to the next clear bit whose result is then discarded. The PR does not touch this. To make the threshold adjustable, the caller would need to inform the iterator the minimum run end needed, however that's beyond the scope of this PR. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
