You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2019/06/18 10:00:33 UTC
[lucene-solr] branch branch_8x updated: LUCENE-8796: Use
exponential search in IntArrayDocIdSetIterator#advance (#667)
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/branch_8x by this push:
new 327a6df LUCENE-8796: Use exponential search in IntArrayDocIdSetIterator#advance (#667)
327a6df is described below
commit 327a6dfeb45e2443d5c2f325441a6b4eb18e096b
Author: Luca Cavanna <ja...@users.noreply.github.com>
AuthorDate: Tue Jun 18 10:29:51 2019 +0200
LUCENE-8796: Use exponential search in IntArrayDocIdSetIterator#advance (#667)
---
lucene/CHANGES.txt | 5 +++++
.../src/java/org/apache/lucene/util/IntArrayDocIdSet.java | 13 +++++++++----
2 files changed, 14 insertions(+), 4 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index adbd1f1..351df99 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -79,6 +79,11 @@ Improvements
* LUCENE-8845: Allow Intervals.prefix() and Intervals.wildcard() to specify
their maximum allowed expansions (Alan Woodward)
+Optimizations
+
+* LUCENE-8796: Use exponential search instead of binary search in
+ IntArrayDocIdSet#advance method (Luca Cavanna via Adrien Grand)
+
Test Framework
* LUCENE-8825: CheckHits now display the shard index in case of mismatch
diff --git a/lucene/core/src/java/org/apache/lucene/util/IntArrayDocIdSet.java b/lucene/core/src/java/org/apache/lucene/util/IntArrayDocIdSet.java
index e82956c..c3ed8ca 100644
--- a/lucene/core/src/java/org/apache/lucene/util/IntArrayDocIdSet.java
+++ b/lucene/core/src/java/org/apache/lucene/util/IntArrayDocIdSet.java
@@ -52,7 +52,7 @@ final class IntArrayDocIdSet extends DocIdSet {
private final int[] docs;
private final int length;
- private int i = -1;
+ private int i = 0;
private int doc = -1;
IntArrayDocIdSetIterator(int[] docs, int length) {
@@ -67,16 +67,21 @@ final class IntArrayDocIdSet extends DocIdSet {
@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 + 1, length), target);
if (i < 0) {
i = -1 - i;
}
- return doc = docs[i];
+ return doc = docs[i++];
}
@Override