jimczi commented on code in PR #16849:
URL: https://github.com/apache/lucene/pull/16849#discussion_r4294246552
##########
lucene/core/src/java/org/apache/lucene/util/BitSetIterator.java:
##########
@@ -96,12 +99,18 @@ public long cost() {
@Override
public int docIDRunEnd() {
assert doc != NO_MORE_DOCS;
- int next = doc + 1;
- if (next >= length) {
- return length;
+ // Called once per window by DenseConjunctionBulkScorer: resume from the
known run end and
+ // bound the scan, otherwise a long run is rescanned on every call, which
is quadratic.
+ if (doc < runStart || doc >= runEnd) {
Review Comment:
Advance can't go backwards, but `setDocId` can. `DefaultBulkScorerBenchmark`
reuses iterators with `setDocId(-1)`, for example. Without `runStart`, a doc
before the old run would get the stale `runEnd`, even with a clear bit in
between, so it'd be wrong, not just slow. We could reset the cache in
`setDocId` instead, but we need one or the other.
##########
lucene/core/src/java/org/apache/lucene/util/BitSetIterator.java:
##########
@@ -51,9 +51,12 @@ public static SparseFixedBitSet
getSparseFixedBitSetOrNull(DocIdSetIterator iter
return getBitSet(iterator, SparseFixedBitSet.class);
}
+ static final int MAX_RUN_END_SCAN = 1 << 16;
Review Comment:
I'd keep it. It's separate from the cache: it stops the first call from
scanning the whole run when the caller only needs a prefix (doc-partitioned
slices, early termination). That's the `liveDocsSlice` row in the benchmark.
##########
lucene/core/src/test/org/apache/lucene/search/TestDenseConjunctionBulkScorer.java:
##########
@@ -1394,4 +1395,121 @@ public void collect(int doc) throws IOException {
scorer.score(collector, null, 0, DocIdSetIterator.NO_MORE_DOCS);
assertEquals(expected.cardinality(), collector.count);
}
+
+ public void testLongRunWithLiveDocsIsScannedOnce() throws IOException {
Review Comment:
I'd keep these. They're the ones that reproduce the quadratic end to end
(they scan 134M bits on `main`), while the `TestBitSetIterator` ones mostly
cover the cap and cache semantics.
--
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]
