You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2024/04/02 13:59:00 UTC
(lucene) branch branch_9x updated: Made DocIdsWriter use DISI when reading documents with an IntersectVisitor (#13149)
This is an automated email from the ASF dual-hosted git repository.
mikemccand pushed a commit to branch branch_9x
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/branch_9x by this push:
new a633334f7cd Made DocIdsWriter use DISI when reading documents with an IntersectVisitor (#13149)
a633334f7cd is described below
commit a633334f7cdd9047f4df26d12285c9ea1ed3c65f
Author: Anton Hägerstrand <an...@gmail.com>
AuthorDate: Tue Apr 2 15:44:31 2024 +0200
Made DocIdsWriter use DISI when reading documents with an IntersectVisitor (#13149)
* Made DocIdsWriter use DISI when reading documents with an IntersectVisitor.
Instead of calling IntersectVisitor.visit for each doc in the
readDelta16 and readInts32 methods, create a DocIdSetIterator
and call IntersectVisitor.visit(DocIdSetIterator) instead.
This seems to make Lucene faster at sorting and range querying
tasks - the hypothesis being that it is due to fewer virtual calls.
* Spotless
* Changed bulk iteration to use IntsRef instead.
* Clearer comment.
* Decrease cost outside loop
* Added test to make inverse intsref be used.
* Wording improvement in javadoc.
* Added CHANGES.txt entry.
---
lucene/CHANGES.txt | 3 +++
.../java/org/apache/lucene/index/PointValues.java | 14 ++++++++++-
.../org/apache/lucene/search/PointRangeQuery.java | 16 ++++++++++++
.../org/apache/lucene/util/bkd/DocIdsWriter.java | 29 +++++++++++++++++-----
.../org/apache/lucene/search/TestPointQueries.java | 12 ++++++++-
5 files changed, 66 insertions(+), 8 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index e9869c2fdf0..0cb2005d161 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -67,6 +67,9 @@ Optimizations
* GITHUB#11888: Binary search the BlockTree terms dictionary entries when all suffixes have the same length
in a leaf block, speeding up cases like primary key lookup on an id field when all ids are the same length. (zhouhui)
+* GITHUB#13149: Made PointRangeQuery faster, for some segment sizes, by reducing the amount of virtual calls to
+ IntersectVisitor::visit(int). (Anton Hägerstrand)
+
Bug Fixes
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/index/PointValues.java b/lucene/core/src/java/org/apache/lucene/index/PointValues.java
index 3430de0d349..aebcaa90e2a 100644
--- a/lucene/core/src/java/org/apache/lucene/index/PointValues.java
+++ b/lucene/core/src/java/org/apache/lucene/index/PointValues.java
@@ -31,6 +31,7 @@ import org.apache.lucene.document.LongPoint;
import org.apache.lucene.search.DocIdSetIterator;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.ArrayUtil.ByteArrayComparator;
+import org.apache.lucene.util.IntsRef;
import org.apache.lucene.util.bkd.BKDConfig;
/**
@@ -288,7 +289,7 @@ public abstract class PointValues {
void visit(int docID) throws IOException;
/**
- * Similar to {@link IntersectVisitor#visit(int)}, but a bulk visit and implements may have
+ * Similar to {@link IntersectVisitor#visit(int)}, but a bulk visit and implementations may have
* their optimizations.
*/
default void visit(DocIdSetIterator iterator) throws IOException {
@@ -298,6 +299,17 @@ public abstract class PointValues {
}
}
+ /**
+ * Similar to {@link IntersectVisitor#visit(int)}, but a bulk visit and implements may have
+ * their optimizations. Even if the implementation does the same thing this method, this may be
+ * a speed improvement due to fewer virtual calls.
+ */
+ default void visit(IntsRef ref) throws IOException {
+ for (int i = ref.offset; i < ref.length + ref.offset; i++) {
+ visit(ref.ints[i]);
+ }
+ }
+
/**
* Called for all documents in a leaf cell that crosses the query. The consumer should
* scrutinize the packedValue to decide whether to accept it. In the 1D case, values are visited
diff --git a/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java b/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java
index 64fb00bdb34..ad5f7bd9a04 100644
--- a/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java
@@ -32,6 +32,7 @@ import org.apache.lucene.util.ArrayUtil.ByteArrayComparator;
import org.apache.lucene.util.BitSetIterator;
import org.apache.lucene.util.DocIdSetBuilder;
import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.IntsRef;
/**
* Abstract class for range queries against single or multidimensional points such as {@link
@@ -185,6 +186,13 @@ public abstract class PointRangeQuery extends Query {
adder.add(iterator);
}
+ @Override
+ public void visit(IntsRef ref) {
+ for (int i = ref.offset; i < ref.offset + ref.length; i++) {
+ adder.add(ref.ints[i]);
+ }
+ }
+
@Override
public void visit(int docID, byte[] packedValue) {
if (matches(packedValue)) {
@@ -222,6 +230,14 @@ public abstract class PointRangeQuery extends Query {
cost[0] = Math.max(0, cost[0] - iterator.cost());
}
+ @Override
+ public void visit(IntsRef ref) {
+ for (int i = ref.offset; i < ref.offset + ref.length; i++) {
+ result.clear(ref.ints[i]);
+ }
+ cost[0] -= ref.length;
+ }
+
@Override
public void visit(int docID, byte[] packedValue) {
if (matches(packedValue) == false) {
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/DocIdsWriter.java b/lucene/core/src/java/org/apache/lucene/util/bkd/DocIdsWriter.java
index 69818b337f2..9f6a10b9ddc 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/DocIdsWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/DocIdsWriter.java
@@ -23,6 +23,7 @@ import org.apache.lucene.store.DataOutput;
import org.apache.lucene.store.IndexInput;
import org.apache.lucene.util.DocBaseBitSetIterator;
import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.IntsRef;
final class DocIdsWriter {
@@ -36,6 +37,22 @@ final class DocIdsWriter {
private final int[] scratch;
+ /**
+ * IntsRef to be used to iterate over the scratch buffer. A single instance is reused to avoid
+ * re-allocating the object. The ints and length fields need to be reset each use.
+ *
+ * <p>The main reason for existing is to be able to call the {@link
+ * IntersectVisitor#visit(IntsRef)} method rather than the {@link IntersectVisitor#visit(int)}
+ * method. This seems to make a difference in performance, probably due to fewer virtual calls
+ * then happening (once per read call rather than once per doc).
+ */
+ private final IntsRef scratchIntsRef = new IntsRef();
+
+ {
+ // This is here to not rely on the default constructor of IntsRef to set offset to 0
+ scratchIntsRef.offset = 0;
+ }
+
DocIdsWriter(int maxPointsInLeaf) {
scratch = new int[maxPointsInLeaf];
}
@@ -318,9 +335,9 @@ final class DocIdsWriter {
private void readDelta16(IndexInput in, int count, IntersectVisitor visitor) throws IOException {
readDelta16(in, count, scratch);
- for (int i = 0; i < count; i++) {
- visitor.visit(scratch[i]);
- }
+ scratchIntsRef.ints = scratch;
+ scratchIntsRef.length = count;
+ visitor.visit(scratchIntsRef);
}
private static void readInts24(IndexInput in, int count, IntersectVisitor visitor)
@@ -346,8 +363,8 @@ final class DocIdsWriter {
private void readInts32(IndexInput in, int count, IntersectVisitor visitor) throws IOException {
in.readInts(scratch, 0, count);
- for (int i = 0; i < count; i++) {
- visitor.visit(scratch[i]);
- }
+ scratchIntsRef.ints = scratch;
+ scratchIntsRef.length = count;
+ visitor.visit(scratchIntsRef);
}
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java b/lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java
index b4780bbe089..f1edb332fa3 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java
@@ -374,6 +374,10 @@ public class TestPointQueries extends LuceneTestCase {
doTestRandomLongs(1000);
}
+ public void testRandomLongsBig() throws Exception {
+ doTestRandomLongs(20_000);
+ }
+
private void doTestRandomLongs(int count) throws Exception {
int numValues = TestUtil.nextInt(random(), count, count * 2);
@@ -434,7 +438,13 @@ public class TestPointQueries extends LuceneTestCase {
dir = newMaybeVirusCheckingDirectory();
}
- int missingPct = random().nextInt(100);
+ /*
+ The point range query chooses only considers using an inverse BKD visitor if
+ there is exactly one value per document. If any document misses a value that
+ code is not exercised. Using a nextBoolean() here increases the likelihood
+ that there is no missing values, making the test more likely to test that code.
+ */
+ int missingPct = random().nextBoolean() ? 0 : random().nextInt(100);
int deletedPct = random().nextInt(100);
if (VERBOSE) {
System.out.println(" missingPct=" + missingPct);