epotyom commented on code in PR #16349:
URL: https://github.com/apache/lucene/pull/16349#discussion_r4145247868
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java:
##########
@@ -524,7 +527,15 @@ private void readBlockHeader() throws IOException {
nextBlockIndex = index + numValues;
if (numValues <= MAX_ARRAY_LENGTH) {
method = Method.SPARSE;
- blockEnd = slice.getFilePointer() + (numValues << 1);
+ // Pre-load sparse block into memory so we can binary-search within it
instead of
+ // streaming reads. This avoids repeated slice reads for multiple
advances inside
+ // the same block.
+ blockBaseIndex = index;
+ sparseDocs = new int[numValues];
+ for (int i = 0; i < numValues; i++) {
+ sparseDocs[i] = Short.toUnsignedInt(slice.readShort());
Review Comment:
I suspect a large part of the cost of an `advance()` call is the IO in
`slice.readShort()`. We used to do it lazily, and with this change we do it up
front, so this looks expensive.
What if instead we binary-search directly in `slice`? Each element has a
fixed size, so we can compute the offset and read the value from it.
We might want to keep the `sparseDocs` array though, but fill it lazily:
while binary-searching, whenever a value is missing from it (e.g. is -1) we
read it from `slice` and add it to the array. Might not be worth the overhead
though, as we'd need to "clean" the array for every block, so that's something
we might want to benchmark.
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java:
##########
@@ -524,7 +527,15 @@ private void readBlockHeader() throws IOException {
nextBlockIndex = index + numValues;
if (numValues <= MAX_ARRAY_LENGTH) {
method = Method.SPARSE;
- blockEnd = slice.getFilePointer() + (numValues << 1);
+ // Pre-load sparse block into memory so we can binary-search within it
instead of
+ // streaming reads. This avoids repeated slice reads for multiple
advances inside
+ // the same block.
+ blockBaseIndex = index;
+ sparseDocs = new int[numValues];
Review Comment:
Can we allocate the array once and reuse it for all blocks? I.e. init it as
`null`, then the first time we need it allocate an array of size `numValues`,
and for the next blocks that need it use `ArrayUtil.growNoCopy` to make sure it
is big enough.
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java:
##########
@@ -579,57 +590,68 @@ enum Method {
@Override
boolean advanceWithinBlock(IndexedDISI disi, int target) throws
IOException {
final int targetInBlock = target & 0xFFFF;
- // TODO: binary search
- for (; disi.index < disi.nextBlockIndex; ) {
- int doc = Short.toUnsignedInt(disi.slice.readShort());
- disi.index++;
- if (doc >= targetInBlock) {
- disi.doc = disi.block | doc;
- disi.exists = true;
- disi.nextExistDocInBlock = doc;
- return true;
- }
+ final int start = Math.max(0, disi.index - disi.blockBaseIndex);
+ final int end = disi.nextBlockIndex - disi.blockBaseIndex;
+ if (start >= end) {
+ return false;
}
- return false;
+ int pos = Arrays.binarySearch(disi.sparseDocs, start, end,
targetInBlock);
+ if (pos < 0) {
+ pos = -pos - 1;
+ }
+ if (pos >= end) {
+ return false;
+ }
+ disi.index = disi.blockBaseIndex + pos + 1; // advance index to one
past found
+ int docInBlock = disi.sparseDocs[pos];
+ disi.doc = disi.block | docInBlock;
+ disi.exists = true;
+ disi.nextExistDocInBlock = docInBlock;
+ return true;
}
@Override
boolean advanceExactWithinBlock(IndexedDISI disi, int target) throws
IOException {
final int targetInBlock = target & 0xFFFF;
- // TODO: binary search
if (disi.nextExistDocInBlock > targetInBlock) {
assert !disi.exists;
return false;
}
if (target == disi.doc) {
return disi.exists;
}
- for (; disi.index < disi.nextBlockIndex; ) {
- int doc = Short.toUnsignedInt(disi.slice.readShort());
- disi.index++;
- if (doc >= targetInBlock) {
- disi.nextExistDocInBlock = doc;
- if (doc != targetInBlock) {
- disi.index--;
- disi.slice.seek(disi.slice.getFilePointer() - Short.BYTES);
- break;
- }
- disi.exists = true;
- return true;
- }
+ final int start = Math.max(0, disi.index - disi.blockBaseIndex);
+ final int end = disi.nextBlockIndex - disi.blockBaseIndex;
+ if (start >= end) {
+ disi.exists = false;
+ return false;
}
- disi.exists = false;
- return false;
+ int pos = Arrays.binarySearch(disi.sparseDocs, start, end,
targetInBlock);
+ if (pos < 0) {
+ pos = -pos - 1;
+ }
+ if (pos >= end || disi.sparseDocs[pos] != targetInBlock) {
+ disi.exists = false;
+ // set index to position where next greater element would be
+ disi.index = disi.blockBaseIndex + pos;
+ return false;
+ }
+ // found exact match
+ disi.exists = true;
+ disi.index = disi.blockBaseIndex + pos + 1; // one past found
Review Comment:
Looks like `disi.nextExistDocInBlock` update is gone - is that intentional?
--
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]
