javanna commented on a change in pull request #667: LUCENE-8796: Use
exponential search in IntArrayDocIdSetIterator#advance
URL: https://github.com/apache/lucene-solr/pull/667#discussion_r292879271
##########
File path: lucene/core/src/java/org/apache/lucene/util/IntArrayDocIdSet.java
##########
@@ -67,16 +67,21 @@ public int docID() {
@Override
public int nextDoc() throws IOException {
- return doc = docs[++i];
+ return doc = docs[i++];
}
@Override
public int advance(int target) throws IOException {
- i = Arrays.binarySearch(docs, i + 1, length, target);
+ int bound = 1;
+ //given that we use this for small arrays only, this is very unlikely to
overflow
+ while(i + bound < length && docs[i + bound] < target) {
+ bound *= 2;
+ }
+ i = Arrays.binarySearch(docs, i + bound / 2, Math.min(i + bound,
length), target);
Review comment:
correct, the upper bound is exclusive in Arrays.binarySearch . Funnily
enough, this does not seem to cause any problem, as the returned value is `-
insertion point - 1` with which we do `i = -1 - i`. If the docId was not in the
array, we'd return the docId at the hypothetical position where the docId would
be if it was in the array. In reality it is there, and what we return is the
proper value still :) I think the test coverage is already good enough, I have
corrected this, but I am not sure how to test it given that it did not end up
causing any bug.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
[email protected]
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
