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 08:29:56 UTC
[lucene-solr] branch master 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 master
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/master by this push:
new 4fd09eb LUCENE-8796: Use exponential search in IntArrayDocIdSetIterator#advance (#667)
4fd09eb is described below
commit 4fd09eb3e386d000ac9e8871c4a5178e66476540
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 b85ddf0..122358d 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -103,6 +103,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