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 2025/06/03 05:05:32 UTC
(lucene) branch main updated: Add MathUtil#unsignedMin to simplify dividing the doc ID space into windows. (#14750)
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 2380e0d1ca4 Add MathUtil#unsignedMin to simplify dividing the doc ID space into windows. (#14750)
2380e0d1ca4 is described below
commit 2380e0d1ca40bad21064472d8390cc9d750ebcfe
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Tue Jun 3 07:05:26 2025 +0200
Add MathUtil#unsignedMin to simplify dividing the doc ID space into windows. (#14750)
We often need to divide the doc ID space into sub windows, but this is prone to
integer overflows if the size of the window is greater than `Integer.MAX_VALUE
- windowStart`. This adds `MathUtil#unsignedMin` to make these overflows a bit
easier to manage.
---
.../java/org/apache/lucene/search/BitSetDocIdStream.java | 3 ++-
.../apache/lucene/search/DenseConjunctionBulkScorer.java | 5 +++--
.../apache/lucene/search/DisjunctionMaxBulkScorer.java | 3 ++-
.../java/org/apache/lucene/search/MaxScoreBulkScorer.java | 8 ++++----
.../org/apache/lucene/search/TimeLimitingBulkScorer.java | 3 ++-
.../src/java/org/apache/lucene/util/BitSetIterator.java | 2 +-
.../org/apache/lucene/util/DocBaseBitSetIterator.java | 2 +-
lucene/core/src/java/org/apache/lucene/util/MathUtil.java | 5 +++++
.../src/test/org/apache/lucene/util/TestMathUtil.java | 15 +++++++++++++++
9 files changed, 35 insertions(+), 11 deletions(-)
diff --git a/lucene/core/src/java/org/apache/lucene/search/BitSetDocIdStream.java b/lucene/core/src/java/org/apache/lucene/search/BitSetDocIdStream.java
index 42a75073c81..8c2f01e38e3 100644
--- a/lucene/core/src/java/org/apache/lucene/search/BitSetDocIdStream.java
+++ b/lucene/core/src/java/org/apache/lucene/search/BitSetDocIdStream.java
@@ -18,6 +18,7 @@ package org.apache.lucene.search;
import java.io.IOException;
import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.MathUtil;
final class BitSetDocIdStream extends DocIdStream {
@@ -29,7 +30,7 @@ final class BitSetDocIdStream extends DocIdStream {
this.bitSet = bitSet;
this.offset = offset;
upTo = offset;
- max = (int) Math.min(Integer.MAX_VALUE, (long) offset + bitSet.length());
+ max = MathUtil.unsignedMin(Integer.MAX_VALUE, offset + bitSet.length());
}
@Override
diff --git a/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java b/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
index 22909d45400..08c71a81d7d 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DenseConjunctionBulkScorer.java
@@ -22,6 +22,7 @@ import java.util.Comparator;
import java.util.List;
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.MathUtil;
/**
* BulkScorer implementation of {@link ConjunctionScorer} that is specialized for dense clauses.
@@ -176,7 +177,7 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
// data, which helps evaluate fewer clauses per window - without allowing windows to become too
// small thanks to the WINDOW_SIZE/2 threshold.
int minDocIDRunEnd = max;
- final int minRunEndThreshold = (int) Math.min((long) min + WINDOW_SIZE / 2, max);
+ final int minRunEndThreshold = MathUtil.unsignedMin(min + WINDOW_SIZE / 2, max);
for (DisiWrapper w : iterators) {
int docIdRunEnd = w.docIDRunEnd();
if (w.docID() > min || docIdRunEnd < minRunEndThreshold) {
@@ -195,7 +196,7 @@ final class DenseConjunctionBulkScorer extends BulkScorer {
return minDocIDRunEnd;
}
- int bitsetWindowMax = (int) Math.min(minDocIDRunEnd, (long) WINDOW_SIZE + min);
+ int bitsetWindowMax = MathUtil.unsignedMin(minDocIDRunEnd, WINDOW_SIZE + min);
if (windowTwoPhases.isEmpty()) {
scoreWindowUsingBitSet(collector, acceptDocs, windowApproximations, min, bitsetWindowMax);
diff --git a/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxBulkScorer.java b/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxBulkScorer.java
index 1ee78c3e817..78184b48eda 100644
--- a/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxBulkScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/DisjunctionMaxBulkScorer.java
@@ -22,6 +22,7 @@ import java.util.List;
import java.util.Objects;
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.MathUtil;
import org.apache.lucene.util.PriorityQueue;
/** Bulk scorer for {@link DisjunctionMaxQuery} when the tie-break multiplier is zero. */
@@ -67,7 +68,7 @@ final class DisjunctionMaxBulkScorer extends BulkScorer {
while (top.next < max) {
final int windowMin = Math.max(top.next, min);
- final int windowMax = (int) Math.min(max, (long) windowMin + WINDOW_SIZE);
+ final int windowMax = MathUtil.unsignedMin(max, windowMin + WINDOW_SIZE);
// First compute matches / scores in the window
do {
diff --git a/lucene/core/src/java/org/apache/lucene/search/MaxScoreBulkScorer.java b/lucene/core/src/java/org/apache/lucene/search/MaxScoreBulkScorer.java
index cb212096f75..f6e83c7af52 100644
--- a/lucene/core/src/java/org/apache/lucene/search/MaxScoreBulkScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/MaxScoreBulkScorer.java
@@ -181,7 +181,7 @@ final class MaxScoreBulkScorer extends BulkScorer {
// Only score an inner window, after that we'll check if the min competitive score has increased
// enough for a more favorable partitioning to be used.
int innerWindowMin = top.doc;
- int innerWindowMax = (int) Math.min(max, (long) innerWindowMin + INNER_WINDOW_SIZE);
+ int innerWindowMax = MathUtil.unsignedMin(max, innerWindowMin + INNER_WINDOW_SIZE);
docAndScoreAccBuffer.size = 0;
while (top.doc < innerWindowMax) {
@@ -277,7 +277,7 @@ final class MaxScoreBulkScorer extends BulkScorer {
DisiWrapper top = essentialQueue.top();
int innerWindowMin = top.doc;
- int innerWindowMax = (int) Math.min(max, (long) innerWindowMin + INNER_WINDOW_SIZE);
+ int innerWindowMax = MathUtil.unsignedMin(max, innerWindowMin + INNER_WINDOW_SIZE);
int innerWindowSize = innerWindowMax - innerWindowMin;
// Collect matches of essential clauses into a bitset
@@ -324,7 +324,7 @@ final class MaxScoreBulkScorer extends BulkScorer {
final DisiWrapper scorer = allScorers[i];
if (filter == null || scorer.cost >= filter.cost) {
final int upTo = scorer.scorer.advanceShallow(Math.max(scorer.doc, windowMin));
- windowMax = (int) Math.min(windowMax, upTo + 1L); // upTo is inclusive
+ windowMax = MathUtil.unsignedMin(windowMax, upTo + 1); // upTo is inclusive
}
}
@@ -341,7 +341,7 @@ final class MaxScoreBulkScorer extends BulkScorer {
minWindowSize = 1;
}
- int minWindowMax = (int) Math.min(Integer.MAX_VALUE, (long) windowMin + minWindowSize);
+ int minWindowMax = MathUtil.unsignedMin(Integer.MAX_VALUE, windowMin + minWindowSize);
windowMax = Math.max(windowMax, minWindowMax);
}
diff --git a/lucene/core/src/java/org/apache/lucene/search/TimeLimitingBulkScorer.java b/lucene/core/src/java/org/apache/lucene/search/TimeLimitingBulkScorer.java
index 240dee7f4fd..63e6ba1b294 100644
--- a/lucene/core/src/java/org/apache/lucene/search/TimeLimitingBulkScorer.java
+++ b/lucene/core/src/java/org/apache/lucene/search/TimeLimitingBulkScorer.java
@@ -21,6 +21,7 @@ import java.io.IOException;
import java.util.Objects;
import org.apache.lucene.index.QueryTimeout;
import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.MathUtil;
/**
* The {@link TimeLimitingBulkScorer} is used to timeout search requests that take longer than the
@@ -69,7 +70,7 @@ final class TimeLimitingBulkScorer extends BulkScorer {
public int score(LeafCollector collector, Bits acceptDocs, int min, int max) throws IOException {
int interval = INTERVAL;
while (min < max) {
- final int newMax = (int) Math.min((long) min + interval, max);
+ final int newMax = MathUtil.unsignedMin(min + interval, max);
final int newInterval =
interval + (interval >> 1); // increase the interval by 50% on each iteration
// overflow check
diff --git a/lucene/core/src/java/org/apache/lucene/util/BitSetIterator.java b/lucene/core/src/java/org/apache/lucene/util/BitSetIterator.java
index 23938d9a59b..11ab25700f4 100644
--- a/lucene/core/src/java/org/apache/lucene/util/BitSetIterator.java
+++ b/lucene/core/src/java/org/apache/lucene/util/BitSetIterator.java
@@ -100,7 +100,7 @@ public class BitSetIterator extends AbstractDocIdSetIterator {
// The destination bit set may be shorter than this bit set. This is only legal if all bits
// beyond offset + bitSet.length() are clear. If not, the below call to `super.intoBitSet`
// will throw an exception.
- actualUpto = (int) Math.min(actualUpto, offset + (long) bitSet.length());
+ actualUpto = MathUtil.unsignedMin(actualUpto, offset + bitSet.length());
FixedBitSet.orRange(fixedBits, doc, bitSet, doc - offset, actualUpto - doc);
advance(actualUpto); // set the current doc
}
diff --git a/lucene/core/src/java/org/apache/lucene/util/DocBaseBitSetIterator.java b/lucene/core/src/java/org/apache/lucene/util/DocBaseBitSetIterator.java
index 14a90227168..a7f083b1bda 100644
--- a/lucene/core/src/java/org/apache/lucene/util/DocBaseBitSetIterator.java
+++ b/lucene/core/src/java/org/apache/lucene/util/DocBaseBitSetIterator.java
@@ -92,7 +92,7 @@ public class DocBaseBitSetIterator extends AbstractDocIdSetIterator {
// The destination bit set may be shorter than this bit set. This is only legal if all bits
// beyond offset + bitSet.length() are clear. If not, the below call to `super.intoBitSet` will
// throw an exception.
- actualUpto = (int) Math.min(actualUpto, offset + (long) bitSet.length());
+ actualUpto = MathUtil.unsignedMin(actualUpto, offset + bitSet.length());
if (actualUpto > doc) {
FixedBitSet.orRange(bits, doc - docBase, bitSet, doc - offset, actualUpto - doc);
advance(actualUpto); // set the current doc
diff --git a/lucene/core/src/java/org/apache/lucene/util/MathUtil.java b/lucene/core/src/java/org/apache/lucene/util/MathUtil.java
index 141a4566595..aecf48adaf6 100644
--- a/lucene/core/src/java/org/apache/lucene/util/MathUtil.java
+++ b/lucene/core/src/java/org/apache/lucene/util/MathUtil.java
@@ -192,4 +192,9 @@ public final class MathUtil {
double b = MathUtil.sumRelativeErrorBound(numValues);
return (1.0 + 2 * b) * sum;
}
+
+ /** Return the min of the two given unsigned integers. */
+ public static int unsignedMin(int a, int b) {
+ return Integer.compareUnsigned(a, b) < 0 ? a : b;
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestMathUtil.java b/lucene/core/src/test/org/apache/lucene/util/TestMathUtil.java
index e36df8c51cd..c44e52f6cbd 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestMathUtil.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestMathUtil.java
@@ -181,4 +181,19 @@ public class TestMathUtil extends LuceneTestCase {
assertEquals(0.5493061443340549, MathUtil.atanh(0.5), epsilon);
assertEquals(Double.POSITIVE_INFINITY, MathUtil.atanh(1), 0);
}
+
+ public void testUnsignedMin() {
+ assertEquals(0, MathUtil.unsignedMin(0, 0));
+ assertEquals(0, MathUtil.unsignedMin(0, 3));
+ assertEquals(0, MathUtil.unsignedMin(3, 0));
+ assertEquals(0, MathUtil.unsignedMin(0, Integer.MAX_VALUE));
+ assertEquals(0, MathUtil.unsignedMin(Integer.MAX_VALUE, 0));
+ assertEquals(Integer.MAX_VALUE, MathUtil.unsignedMin(Integer.MAX_VALUE, Integer.MAX_VALUE + 1));
+ assertEquals(Integer.MAX_VALUE, MathUtil.unsignedMin(Integer.MAX_VALUE + 1, Integer.MAX_VALUE));
+ assertEquals(Integer.MAX_VALUE, MathUtil.unsignedMin(Integer.MAX_VALUE, Integer.MIN_VALUE));
+ assertEquals(Integer.MAX_VALUE, MathUtil.unsignedMin(Integer.MIN_VALUE, Integer.MAX_VALUE));
+ assertEquals(Integer.MIN_VALUE, MathUtil.unsignedMin(Integer.MIN_VALUE, -1));
+ assertEquals(Integer.MIN_VALUE, MathUtil.unsignedMin(-1, Integer.MIN_VALUE));
+ assertEquals(Integer.MIN_VALUE, MathUtil.unsignedMin(Integer.MIN_VALUE, Integer.MIN_VALUE));
+ }
}