You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ch...@apache.org on 2026/09/10 13:30:44 UTC
(lucene) branch main updated: Implement Bits#applyMask in bulk for DenseLiveDocs and SparseLiveDocs (#16593)
This is an automated email from the ASF dual-hosted git repository.
ChrisHegarty 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 25c489a9bab Implement Bits#applyMask in bulk for DenseLiveDocs and SparseLiveDocs (#16593)
25c489a9bab is described below
commit 25c489a9babe1e08b76dd2a10b6d3609b0d34f39
Author: John Maurice <83...@users.noreply.github.com>
AuthorDate: Thu Sep 10 16:30:37 2026 +0300
Implement Bits#applyMask in bulk for DenseLiveDocs and SparseLiveDocs (#16593)
since #15413 live docs read from disk are DenseLiveDocs or SparseLiveDocs, and neither overrides Bits#applyMask, so masking a window by live docs went from a word-wise AND (what FixedBits did) to a get() per set bit. every caller pays it on segments with deletions: AcceptDocs#createBitSet, the four bulk scorers and CheckIndex#bitsCardinality. same hole as #16282, other method
dense delegates to FixedBitSet.andRange, bounded on maxDoc, which is what FixedBitSet#applyMask does. sparse gets a new SparseFixedBitSet.andNotRange, the and-not twin of andRange, that clears the non-zero words of the sparse set out of the window word by word. both are one word op per 64 docs at most, whatever the window holds, and both keep FixedBitSet#applyMask's exception for bits past the end of live docs, which Bits#applyMask now documents
---
lucene/CHANGES.txt | 5 +
.../lucene/benchmark/jmh/LiveDocsBenchmark.java | 170 ++++++++++++++-
.../core/src/java/org/apache/lucene/util/Bits.java | 11 +-
.../java/org/apache/lucene/util/DenseLiveDocs.java | 38 ++++
.../org/apache/lucene/util/SparseFixedBitSet.java | 91 +++++++++
.../org/apache/lucene/util/SparseLiveDocs.java | 27 +++
.../test/org/apache/lucene/util/TestLiveDocs.java | 227 +++++++++++++++++++++
.../apache/lucene/util/TestSparseFixedBitSet.java | 77 +++++++
8 files changed, 644 insertions(+), 2 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index a717eab2e77..e5cd853bcfa 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -423,6 +423,11 @@ Improvements
Optimizations
---------------------
+* GITHUB#16593: DenseLiveDocs and SparseLiveDocs implement Bits#applyMask in bulk, restoring the
+ word-at-a-time masking that live docs had before GITHUB#13084 exposed them as LiveDocs rather than
+ as a FixedBitSet, so AcceptDocs, the bulk scorers and CheckIndex no longer test one bit per
+ candidate document when a segment has deletions. (John Maurice)
+
* GITHUB#16416: Use ArrayDeque instead of ArrayList for FIFO output buffering in
JapaneseCompletionFilter, avoiding repeated element shifting on removal. (Luiz Lima)
diff --git a/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/LiveDocsBenchmark.java b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/LiveDocsBenchmark.java
index 89fa96d1857..aab523afc82 100644
--- a/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/LiveDocsBenchmark.java
+++ b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/LiveDocsBenchmark.java
@@ -22,6 +22,7 @@ import java.util.Random;
import java.util.Set;
import java.util.concurrent.TimeUnit;
import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.Bits;
import org.apache.lucene.util.DenseLiveDocs;
import org.apache.lucene.util.FixedBitSet;
import org.apache.lucene.util.SparseFixedBitSet;
@@ -45,7 +46,7 @@ import org.openjdk.jmh.infra.Blackhole;
* Benchmarks comparing {@link SparseLiveDocs} vs {@link DenseLiveDocs} performance across different
* deletion rates, patterns, and segment sizes.
*
- * <p>This benchmark suite measures four key operations to evaluate the trade-offs between sparse
+ * <p>This benchmark suite measures five key operations to evaluate the trade-offs between sparse
* and dense LiveDocs implementations:
*
* <ul>
@@ -53,6 +54,8 @@ import org.openjdk.jmh.infra.Blackhole;
* <li><b>Deleted docs iteration</b> - O(deletedDocs) for sparse, O(maxDoc) for dense
* <li><b>Live docs iteration (full)</b> - O(maxDoc) for both, tests get() performance at scale
* <li><b>Live docs iteration (range)</b> - O(range) for both, tests advance() and get() on subset
+ * <li><b>Mask application (applyMask)</b> - masks the candidate documents of a segment one
+ * 4096-document window at a time, which is the shape the bulk scorers use
* </ul>
*
* <h2>Benchmark Parameters</h2>
@@ -66,6 +69,11 @@ import org.openjdk.jmh.infra.Blackhole;
* <li>CLUSTERED: Consecutive deletions at start of segment
* <li>UNIFORM: Deletions evenly spaced across segment
* </ul>
+ * <li><b>candidateRate</b> - Fraction of the segment set in the bit set passed to {@code
+ * applyMask}: 1%, 10% or 100%. Only applies to the {@code applyMask} benchmarks.
+ * <li><b>maskImpl</b> - Which {@code Bits#applyMask} implementation the {@code applyMask}
+ * benchmarks call: BULK for the override, DEFAULT for the per-bit {@code Bits} default
+ * implementation it replaces. Only applies to the {@code applyMask} benchmarks.
* </ul>
*
* <h2>Usage</h2>
@@ -128,6 +136,12 @@ public class LiveDocsBenchmark {
/** Dense LiveDocs implementation for comparison. */
private DenseLiveDocs denseLiveDocs;
+ /** {@link #sparseLiveDocs}, exposed so that {@code applyMask} resolves to the default impl. */
+ private Bits sparseDefaultBits;
+
+ /** {@link #denseLiveDocs}, exposed so that {@code applyMask} resolves to the default impl. */
+ private Bits denseDefaultBits;
+
/** Pre-generated random document IDs for random access benchmarks. */
private int[] randomDocIds;
@@ -146,6 +160,78 @@ public class LiveDocsBenchmark {
/** Number of deleted documents. */
private int deleted;
+ /** Number of documents masked per {@code applyMask} call, as in the bulk scorers. */
+ private static final int WINDOW = 4096;
+
+ /** Which {@link Bits#applyMask} implementation the {@code applyMask} benchmarks call. */
+ public enum MaskImpl {
+ /** The bulk override implemented by {@link SparseLiveDocs} and {@link DenseLiveDocs}. */
+ BULK,
+ /** The per-bit {@link Bits} default implementation that the override replaces. */
+ DEFAULT
+ }
+
+ /**
+ * Candidate documents that the mask is applied to, held in its own state so that {@code
+ * candidateRate} and {@code maskImpl} multiply the {@code applyMask} benchmarks only.
+ *
+ * <p>The candidates of the whole segment are kept as words, and each measured call refills a
+ * single {@link #WINDOW}-document scratch bit set from them and masks that, which is how {@code
+ * AcceptDocs} and the bulk scorers use {@code applyMask}: the destination has just been written
+ * and is still in cache. The refill is part of every measured call, so it costs each {@code
+ * maskImpl} the same.
+ */
+ @State(Scope.Thread)
+ public static class Candidates {
+
+ /**
+ * Fraction of the segment's documents that are set in the candidate bit set (1%, 10%, 100%).
+ */
+ @Param({"0.01", "0.10", "1.0"})
+ double candidateRate;
+
+ /** Implementation of {@code applyMask} to call: the bulk override or the per-bit default. */
+ @Param({"BULK", "DEFAULT"})
+ MaskImpl maskImpl;
+
+ /** Candidate documents of the whole segment, as words. */
+ private long[] candidates;
+
+ /** Scratch window that the mask is applied to. */
+ FixedBitSet window;
+
+ /** Number of whole windows in the segment. */
+ int numWindows;
+
+ /**
+ * Builds the candidate documents over the enclosing benchmark's segment.
+ *
+ * @param benchmark the enclosing benchmark state, for its segment size
+ */
+ @Setup(Level.Trial)
+ public void setup(final LiveDocsBenchmark benchmark) {
+ Random random = new Random(17);
+ FixedBitSet bitSet = new FixedBitSet(benchmark.maxDoc);
+ if (candidateRate >= 1.0) {
+ bitSet.set(0, benchmark.maxDoc);
+ } else {
+ for (int doc = 0; doc < benchmark.maxDoc; doc++) {
+ if (random.nextDouble() < candidateRate) {
+ bitSet.set(doc);
+ }
+ }
+ }
+ candidates = bitSet.getBits();
+ window = new FixedBitSet(WINDOW);
+ numWindows = benchmark.maxDoc / WINDOW;
+ }
+
+ /** Refills the scratch window with the candidates of the window starting at {@code base}. */
+ void fillWindow(final int base) {
+ System.arraycopy(candidates, base >> 6, window.getBits(), 0, WINDOW >> 6);
+ }
+ }
+
/**
* JMH auxiliary counters for tracking memory metrics across benchmark runs.
*
@@ -225,6 +311,9 @@ public class LiveDocsBenchmark {
sparseLiveDocs = SparseLiveDocs.builder(sparseSet, maxDoc).build();
denseLiveDocs = DenseLiveDocs.builder(fixedSet, maxDoc).build();
+ sparseDefaultBits = defaultApplyMask(sparseLiveDocs);
+ denseDefaultBits = defaultApplyMask(denseLiveDocs);
+
sparseBytes = sparseLiveDocs.ramBytesUsed();
denseBytes = denseLiveDocs.ramBytesUsed();
overheadPct = ((double) sparseBytes - denseBytes) / denseBytes * 100.0;
@@ -421,6 +510,85 @@ public class LiveDocsBenchmark {
return count;
}
+ /**
+ * Benchmarks {@link SparseLiveDocs#applyMask} over the segment, one window at a time.
+ *
+ * <p>Sparse holds the deleted documents in a {@link SparseFixedBitSet} and and-nots them into the
+ * candidates word by word, so the cost of the {@code BULK} arm depends on how many non-zero words
+ * the deleted documents span in the window, not on the candidate density. The {@code DEFAULT} arm
+ * is the per-bit loop this replaces, whose cost is one {@code get} per candidate.
+ *
+ * @param metrics JMH auxiliary counters for memory statistics
+ * @param candidates the candidate documents to mask
+ * @param blackhole JMH blackhole to prevent dead code elimination
+ */
+ @Benchmark
+ public void sparseApplyMask(
+ final LiveDocsMetrics metrics, final Candidates candidates, final Blackhole blackhole) {
+ fillMetrics(metrics);
+
+ applyMaskOverSegment(
+ candidates,
+ candidates.maskImpl == MaskImpl.BULK ? sparseLiveDocs : sparseDefaultBits,
+ blackhole);
+ }
+
+ /**
+ * Benchmarks {@link DenseLiveDocs#applyMask} over the segment, one window at a time.
+ *
+ * <p>Dense holds live documents in a {@link FixedBitSet}, so the {@code BULK} arm is a word-wise
+ * AND whose cost depends on the window size alone, not on the deletion rate or the candidate
+ * density. The {@code DEFAULT} arm is the per-bit loop this replaces, whose cost is one {@code
+ * get} per candidate.
+ *
+ * @param metrics JMH auxiliary counters for memory statistics
+ * @param candidates the candidate documents to mask
+ * @param blackhole JMH blackhole to prevent dead code elimination
+ */
+ @Benchmark
+ public void denseApplyMask(
+ final LiveDocsMetrics metrics, final Candidates candidates, final Blackhole blackhole) {
+ fillMetrics(metrics);
+
+ applyMaskOverSegment(
+ candidates,
+ candidates.maskImpl == MaskImpl.BULK ? denseLiveDocs : denseDefaultBits,
+ blackhole);
+ }
+
+ /**
+ * Refills a window of candidate documents and masks it, for every whole window of the segment.
+ * The reported time is for the whole sweep; divide by {@code maxDoc / 4096} for a per-window
+ * cost.
+ */
+ private static void applyMaskOverSegment(
+ final Candidates candidates, final Bits liveDocs, final Blackhole blackhole) {
+ FixedBitSet window = candidates.window;
+ for (int i = 0; i < candidates.numWindows; i++) {
+ candidates.fillWindow(i * WINDOW);
+ liveDocs.applyMask(window, i * WINDOW);
+ blackhole.consume(window.getBits());
+ }
+ }
+
+ /**
+ * Wraps a {@link Bits} instance so that {@link Bits#applyMask} resolves to the default
+ * implementation, which is the baseline the bulk overrides are measured against.
+ */
+ private static Bits defaultApplyMask(final Bits in) {
+ return new Bits() {
+ @Override
+ public boolean get(int index) {
+ return in.get(index);
+ }
+
+ @Override
+ public int length() {
+ return in.length();
+ }
+ };
+ }
+
private void fillMetrics(final LiveDocsMetrics metrics) {
metrics.deleted = deleted;
metrics.sparseBytes = sparseBytes;
diff --git a/lucene/core/src/java/org/apache/lucene/util/Bits.java b/lucene/core/src/java/org/apache/lucene/util/Bits.java
index a312a0fd457..cbca3b8a29e 100644
--- a/lucene/core/src/java/org/apache/lucene/util/Bits.java
+++ b/lucene/core/src/java/org/apache/lucene/util/Bits.java
@@ -40,7 +40,16 @@ public interface Bits {
* Apply this {@code Bits} instance to the given {@link FixedBitSet}, which starts at the given
* {@code offset}.
*
- * <p>This should behave the same way as the default implementation, which does the following:
+ * <p>{@code offset} must be non-negative. For each index {@code i} into {@code bitSet}, if {@code
+ * bitSet.get(i)} is set then {@code offset + i} must be less than {@link #length()}: bits of
+ * {@code bitSet} whose corresponding index into this instance is out of range are not covered.
+ * Implementations that can detect such a bit cheaply -- {@link FixedBitSet#applyMask} and the
+ * {@link LiveDocs} implementations do -- throw {@link IllegalArgumentException}; the default
+ * implementation below reads {@link #get(int)} out of bounds instead, which is undefined per
+ * {@link #get}.
+ *
+ * <p>Apart from that, this should behave the same way as the default implementation, which does
+ * the following:
*
* <pre><code class="language-java">
* for (int i = bitSet.nextSetBit(0);
diff --git a/lucene/core/src/java/org/apache/lucene/util/DenseLiveDocs.java b/lucene/core/src/java/org/apache/lucene/util/DenseLiveDocs.java
index 133469fc8bb..0b913b15717 100644
--- a/lucene/core/src/java/org/apache/lucene/util/DenseLiveDocs.java
+++ b/lucene/core/src/java/org/apache/lucene/util/DenseLiveDocs.java
@@ -129,6 +129,44 @@ public final class DenseLiveDocs implements LiveDocs {
return maxDoc;
}
+ /**
+ * {@inheritDoc}
+ *
+ * <p>Live documents are stored in a {@link FixedBitSet}, so the mask is applied with a word-wise
+ * AND through {@link FixedBitSet#andRange}, which auto-vectorizes. Writing {@code w} for the
+ * number of bits of {@code bitSet} that this instance covers, this reads and writes {@code w/64}
+ * words whatever {@code bitSet} contains. The default implementation walks {@code bitSet} with
+ * {@link FixedBitSet#nextSetBit}, which reads the same {@code w/64} words one at a time, and
+ * additionally calls {@link #get} once per set bit. One vectorized word AND is roughly an order
+ * of magnitude cheaper than one {@code get}, so this implementation is the cheaper of the two
+ * from a handful of set bits per window upwards, and the gap grows linearly with the number of
+ * set bits from there. Callers therefore do not need to measure the density of {@code bitSet}
+ * first, and most do not: below the crossover the two are within a few tens of nanoseconds per
+ * window, and for a {@code w} of a few thousand bits {@link FixedBitSet#cardinality} costs about
+ * as much as the mask itself.
+ *
+ * <p>Same structure as {@link FixedBitSet#applyMask}, bounded on {@code maxDoc} rather than
+ * {@code liveDocs.length()} when the backing bit set is padded.
+ *
+ * @throws IllegalArgumentException unless every set bit of {@code bitSet} at index {@code i}
+ * satisfies {@code offset + i < maxDoc}
+ */
+ @Override
+ public void applyMask(FixedBitSet bitSet, int offset) {
+ // Note: Some scorers don't track maxDoc and may thus call this method with an offset that is
+ // beyond maxDoc.
+ // The mask is bounded on maxDoc rather than on liveDocs.length(): the backing bit set is only
+ // required to be at least maxDoc long, and bits beyond maxDoc are not part of this Bits.
+ int length = Math.min(bitSet.length(), maxDoc - offset);
+ if (length >= 0) {
+ FixedBitSet.andRange(liveDocs, offset, bitSet, 0, length);
+ }
+ if (length < bitSet.length()
+ && bitSet.nextSetBit(Math.max(0, length)) != DocIdSetIterator.NO_MORE_DOCS) {
+ throw new IllegalArgumentException("Some bits are set beyond the end of live docs");
+ }
+ }
+
@Override
public DocIdSetIterator liveDocsIterator() {
return new BitSetIterator(liveDocs, maxDoc - deletedCount);
diff --git a/lucene/core/src/java/org/apache/lucene/util/SparseFixedBitSet.java b/lucene/core/src/java/org/apache/lucene/util/SparseFixedBitSet.java
index 6f3c08ced58..af3d47eacc9 100644
--- a/lucene/core/src/java/org/apache/lucene/util/SparseFixedBitSet.java
+++ b/lucene/core/src/java/org/apache/lucene/util/SparseFixedBitSet.java
@@ -18,6 +18,7 @@ package org.apache.lucene.util;
import java.io.IOException;
import java.util.Arrays;
+import java.util.Objects;
import org.apache.lucene.search.DocIdSetIterator;
/**
@@ -712,6 +713,96 @@ public class SparseFixedBitSet extends BitSet {
}
}
+ /**
+ * Clears bits of {@code dest} wherever {@code source} has a set bit, for {@code length} aligned
+ * indices starting at {@code sourceFrom} in {@code source} and {@code destFrom} in {@code dest}:
+ * for each {@code j} in {@code [0, length)}, {@code dest.clear(destFrom + j)} is performed when
+ * {@code source.get(sourceFrom + j)} is set; other bits of {@code dest} are unchanged. Only
+ * {@code dest} is modified.
+ *
+ * <p>Only non-zero longs of {@code source} overlapping the range are visited, so cost is bounded
+ * by {@code length / 64} and does not depend on how many bits of {@code dest} are set. This is
+ * the AND-NOT counterpart of {@link FixedBitSet#andRange}.
+ *
+ * @throws IndexOutOfBoundsException if {@code sourceFrom + length} exceeds {@code
+ * source.length()} or {@code destFrom + length} exceeds {@code dest.length()}
+ */
+ public static void andNotRange(
+ SparseFixedBitSet source, int sourceFrom, FixedBitSet dest, int destFrom, int length) {
+ assert length >= 0 : length;
+ Objects.checkFromIndexSize(sourceFrom, length, source.length());
+ Objects.checkFromIndexSize(destFrom, length, dest.length());
+
+ if (length == 0) {
+ return;
+ }
+
+ final long[] destBits = dest.getBits();
+ final int sourceTo = sourceFrom + length;
+ final int firstLong = sourceFrom >>> 6;
+ final int lastLong = (sourceTo - 1) >>> 6;
+ final int firstBlock = sourceFrom >>> 12;
+ final int lastBlock = (sourceTo - 1) >>> 12;
+ // The long of source that holds bit i64<<6 maps to the bits of dest that start at
+ // (i64<<6) + delta, that is to dest longs i64 + (delta >> 6) and the one after it, with the
+ // bits shifted left by delta modulo 64.
+ final int delta = destFrom - sourceFrom;
+ final int destLongDelta = delta >> 6;
+ final int shift = delta & 0x3F;
+
+ for (int i4096 = firstBlock; i4096 <= lastBlock; ++i4096) {
+ final long index = source.indices[i4096];
+ if (index == 0) {
+ continue;
+ }
+ final long[] bitArray = source.bits[i4096];
+ // Restrict the index to the longs of this block that overlap with [sourceFrom, sourceTo).
+ long inRange = index;
+ if (i4096 == firstBlock) {
+ inRange &= -1L << firstLong; // shifts are mod 64
+ }
+ if (i4096 == lastBlock) {
+ inRange &= -1L >>> -(lastLong + 1); // shifts are mod 64
+ }
+
+ for (long remaining = inRange; remaining != 0; remaining &= remaining - 1) {
+ final int i = Long.numberOfTrailingZeros(remaining);
+ final int i64 = (i4096 << 6) | i;
+ long word = bitArray[Long.bitCount(index & ((1L << i) - 1))];
+ if (i64 == firstLong) {
+ word &= -1L << sourceFrom; // shifts are mod 64
+ }
+ if (i64 == lastLong) {
+ word &= -1L >>> -sourceTo; // shifts are mod 64
+ }
+ if (word == 0) {
+ continue;
+ }
+
+ final int destLong = i64 + destLongDelta;
+ assert destLong < destBits.length;
+ final long lowBits = word << shift;
+ if (destLong >= 0) {
+ destBits[destLong] &= ~lowBits;
+ } else {
+ // The first long of the range starts before the first long of dest, so it may only
+ // contribute to the long after it.
+ assert lowBits == 0;
+ }
+ if (shift != 0) {
+ final long highBits = word >>> -shift;
+ if (destLong + 1 < destBits.length) {
+ destBits[destLong + 1] &= ~highBits;
+ } else {
+ // The last long of the range ends after the last long of dest, so it may only
+ // contribute to the long before it.
+ assert highBits == 0;
+ }
+ }
+ }
+ }
+ }
+
@Override
public long ramBytesUsed() {
return ramBytesUsed;
diff --git a/lucene/core/src/java/org/apache/lucene/util/SparseLiveDocs.java b/lucene/core/src/java/org/apache/lucene/util/SparseLiveDocs.java
index 4220de9d51b..52194969e52 100644
--- a/lucene/core/src/java/org/apache/lucene/util/SparseLiveDocs.java
+++ b/lucene/core/src/java/org/apache/lucene/util/SparseLiveDocs.java
@@ -128,6 +128,33 @@ public final class SparseLiveDocs implements LiveDocs {
return maxDoc;
}
+ /**
+ * {@inheritDoc}
+ *
+ * <p>Applying a mask may only ever clear bits, and the only bits it may clear are the deleted
+ * documents, so this is a word-level and-not of the deleted documents into the destination rather
+ * than the per-bit loop of the default implementation. It runs one word operation per non-zero
+ * word of the deleted documents in the window, that is at most one per 64 documents of the
+ * window, so its cost is bounded by the size of the window and does not depend on how many bits
+ * are set in the destination.
+ *
+ * @throws IllegalArgumentException unless every set bit of {@code bitSet} at index {@code i}
+ * satisfies {@code offset + i < maxDoc}
+ */
+ @Override
+ public void applyMask(FixedBitSet bitSet, int offset) {
+ // Note: Some scorers don't track maxDoc and may thus call this method with an offset that is
+ // beyond maxDoc.
+ int length = Math.min(bitSet.length(), maxDoc - offset);
+ if (length > 0) {
+ SparseFixedBitSet.andNotRange(deletedDocs, offset, bitSet, 0, length);
+ }
+ if (length < bitSet.length()
+ && bitSet.nextSetBit(Math.max(0, length)) != DocIdSetIterator.NO_MORE_DOCS) {
+ throw new IllegalArgumentException("Some bits are set beyond the end of live docs");
+ }
+ }
+
@Override
public DocIdSetIterator liveDocsIterator() {
return new FilteredDocIdSetIterator(
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestLiveDocs.java b/lucene/core/src/test/org/apache/lucene/util/TestLiveDocs.java
index 49767de9d76..9ca5dff38fe 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestLiveDocs.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestLiveDocs.java
@@ -26,6 +26,10 @@ import org.apache.lucene.tests.util.TestUtil;
public class TestLiveDocs extends LuceneTestCase {
+ private static final double[] DELETE_RATES = {0, 0.001, 0.01, 0.05, 0.2, 0.5, 1.0};
+ private static final double[] CANDIDATE_RATES = {0, 0.001, 0.01, 0.5, 1.0};
+ private static final int[] WINDOWS = {64, 128, 1024, 2048, 4096};
+
public void testSparseLiveDocsBasic() {
// GIVEN
final int maxDoc = 1000;
@@ -596,4 +600,227 @@ public class TestLiveDocs extends LuceneTestCase {
assertEquals(1, sparseLive.get(0).intValue());
assertEquals(maxDoc - 2, sparseLive.get(sparseLive.size() - 1).intValue());
}
+
+ public void testApplyMaskMatchesDefault() {
+ final int iters = atLeast(100);
+ for (int iter = 0; iter < iters; iter++) {
+ // GIVEN
+ final int maxDoc = TestUtil.nextInt(random(), 1, 20000);
+ final double deleteRate = DELETE_RATES[random().nextInt(DELETE_RATES.length)];
+ final double candidateRate = CANDIDATE_RATES[random().nextInt(CANDIDATE_RATES.length)];
+ FixedBitSet deleted = randomBitSet(maxDoc, deleteRate);
+ FixedBitSet candidates = randomBitSet(maxDoc, candidateRate);
+
+ for (LiveDocs liveDocs : liveDocsViews(maxDoc, deleted, 0)) {
+ FixedBitSet expected = candidates.clone();
+ FixedBitSet actual = candidates.clone();
+
+ // WHEN
+ defaultApplyMask(liveDocs).applyMask(expected, 0);
+ liveDocs.applyMask(actual, 0);
+
+ // THEN
+ assertEquals(liveDocs.toString(), expected, actual);
+ }
+ }
+ }
+
+ public void testApplyMaskWindowedOffsets() {
+ final int iters = atLeast(20);
+ for (int iter = 0; iter < iters; iter++) {
+ // GIVEN
+ final int maxDoc = TestUtil.nextInt(random(), 1, 20000);
+ final double deleteRate = DELETE_RATES[random().nextInt(DELETE_RATES.length)];
+ FixedBitSet deleted = randomBitSet(maxDoc, deleteRate);
+
+ for (LiveDocs liveDocs : liveDocsViews(maxDoc, deleted, 0)) {
+ for (int window : WINDOWS) {
+ for (int offset : windowOffsets(maxDoc, window)) {
+ FixedBitSet expected = fullWindow(window, maxDoc, offset);
+ FixedBitSet actual = expected.clone();
+
+ // WHEN
+ defaultApplyMask(liveDocs).applyMask(expected, offset);
+ liveDocs.applyMask(actual, offset);
+
+ // THEN
+ assertEquals(liveDocs + " window=" + window + ", offset=" + offset, expected, actual);
+ }
+ }
+ }
+ }
+ }
+
+ public void testApplyMaskTailWindow() {
+ final int window = 1024;
+ for (int maxDoc : new int[] {63, 64, 65, 1023, 1024, 1025, 4095, 4096, 4097}) {
+ // GIVEN
+ FixedBitSet deleted = randomBitSet(maxDoc, 0.2);
+ final int offset = maxDoc - (maxDoc % window);
+
+ for (LiveDocs liveDocs : liveDocsViews(maxDoc, deleted, 0)) {
+ FixedBitSet expected = fullWindow(window, maxDoc, offset);
+ FixedBitSet actual = expected.clone();
+
+ // WHEN
+ defaultApplyMask(liveDocs).applyMask(expected, offset);
+ liveDocs.applyMask(actual, offset);
+
+ // THEN
+ assertEquals(liveDocs + " maxDoc=" + maxDoc, expected, actual);
+ int liveInTail = 0;
+ for (int doc = offset; doc < Math.min(maxDoc, offset + window); doc++) {
+ if (liveDocs.get(doc)) {
+ liveInTail++;
+ }
+ }
+ assertEquals(
+ "live docs in the tail window of " + liveDocs, liveInTail, actual.cardinality());
+ }
+ }
+ }
+
+ public void testApplyMaskNeverSetsBits() {
+ final int iters = atLeast(20);
+ for (int iter = 0; iter < iters; iter++) {
+ // GIVEN
+ final int maxDoc = TestUtil.nextInt(random(), 1, 20000);
+ final double deleteRate = DELETE_RATES[random().nextInt(DELETE_RATES.length)];
+ final double candidateRate = CANDIDATE_RATES[random().nextInt(CANDIDATE_RATES.length)];
+ FixedBitSet deleted = randomBitSet(maxDoc, deleteRate);
+ FixedBitSet before = randomBitSet(maxDoc, candidateRate);
+
+ for (LiveDocs liveDocs : liveDocsViews(maxDoc, deleted, 0)) {
+ FixedBitSet after = before.clone();
+
+ // WHEN
+ liveDocs.applyMask(after, 0);
+
+ // THEN
+ assertEquals(
+ "applyMask must only clear bits on " + liveDocs,
+ 0,
+ FixedBitSet.andNotCount(after, before));
+ }
+ }
+ }
+
+ public void testApplyMaskThrowsOnBitsBeyondLiveDocs() {
+ // GIVEN
+ final int maxDoc = 1000;
+ FixedBitSet deleted = randomBitSet(maxDoc, 0.2);
+
+ for (LiveDocs liveDocs : liveDocsViews(maxDoc, deleted, 0)) {
+ FixedBitSet bitSet = new FixedBitSet(maxDoc + 64);
+ bitSet.set(maxDoc);
+
+ // WHEN
+ IllegalArgumentException e =
+ expectThrows(IllegalArgumentException.class, () -> liveDocs.applyMask(bitSet, 0));
+
+ // THEN
+ assertEquals("Some bits are set beyond the end of live docs", e.getMessage());
+ }
+
+ // The default implementation does not throw when the backing bit set extends beyond maxDoc, so
+ // it silently reads bits that are not part of the Bits instance. The overrides are stricter on
+ // purpose: this is what FixedBitSet#applyMask has always done.
+ for (LiveDocs liveDocs : liveDocsViews(maxDoc, deleted, 64)) {
+ FixedBitSet bitSet = new FixedBitSet(maxDoc + 64);
+ bitSet.set(maxDoc);
+ defaultApplyMask(liveDocs).applyMask(bitSet, 0);
+ }
+ }
+
+ public void testApplyMaskOffsetBeyondMaxDoc() {
+ // GIVEN
+ final int maxDoc = 1000;
+ final int offset = maxDoc + TestUtil.nextInt(random(), 1, 4096);
+ FixedBitSet deleted = randomBitSet(maxDoc, 0.2);
+
+ for (LiveDocs liveDocs : liveDocsViews(maxDoc, deleted, 0)) {
+ FixedBitSet empty = new FixedBitSet(2048);
+ FixedBitSet nonEmpty = new FixedBitSet(2048);
+ nonEmpty.set(0);
+
+ // WHEN
+ liveDocs.applyMask(empty, offset);
+ IllegalArgumentException e =
+ expectThrows(IllegalArgumentException.class, () -> liveDocs.applyMask(nonEmpty, offset));
+
+ // THEN
+ assertEquals("no bits may be set on " + liveDocs, 0, empty.cardinality());
+ assertEquals("Some bits are set beyond the end of live docs", e.getMessage());
+ }
+ }
+
+ /**
+ * Wraps a {@link Bits} instance so that {@link Bits#applyMask} resolves to the default
+ * implementation, which is the specification that overrides must match.
+ */
+ private static Bits defaultApplyMask(Bits in) {
+ return new Bits() {
+ @Override
+ public boolean get(int index) {
+ return in.get(index);
+ }
+
+ @Override
+ public int length() {
+ return in.length();
+ }
+ };
+ }
+
+ /** Returns a sparse and a dense view of the same deleted docs, over the same maxDoc. */
+ private static List<LiveDocs> liveDocsViews(int maxDoc, FixedBitSet deleted, int padding) {
+ SparseFixedBitSet sparseSet = new SparseFixedBitSet(maxDoc + padding);
+ FixedBitSet fixedSet = new FixedBitSet(maxDoc + padding);
+ fixedSet.set(0, maxDoc);
+ for (int doc = deleted.nextSetBit(0);
+ doc != DocIdSetIterator.NO_MORE_DOCS;
+ doc = doc + 1 >= maxDoc ? DocIdSetIterator.NO_MORE_DOCS : deleted.nextSetBit(doc + 1)) {
+ sparseSet.set(doc);
+ fixedSet.clear(doc);
+ }
+ return List.of(
+ SparseLiveDocs.builder(sparseSet, maxDoc).build(),
+ DenseLiveDocs.builder(fixedSet, maxDoc).build());
+ }
+
+ private static FixedBitSet randomBitSet(int length, double setRate) {
+ FixedBitSet bitSet = new FixedBitSet(length);
+ for (int i = 0; i < length; i++) {
+ if (random().nextDouble() < setRate) {
+ bitSet.set(i);
+ }
+ }
+ return bitSet;
+ }
+
+ /** A fully set window of the given size, with the bits beyond maxDoc cleared. */
+ private static FixedBitSet fullWindow(int window, int maxDoc, int offset) {
+ FixedBitSet bitSet = new FixedBitSet(window);
+ bitSet.set(0, window);
+ int live = Math.min(window, maxDoc - offset);
+ if (live < window) {
+ bitSet.clear(Math.max(0, live), window);
+ }
+ return bitSet;
+ }
+
+ /** Aligned offsets sweeping the whole segment, plus a few offsets that are not word aligned. */
+ private static List<Integer> windowOffsets(int maxDoc, int window) {
+ List<Integer> offsets = new ArrayList<>();
+ for (int offset = 0; offset <= maxDoc; offset += window) {
+ offsets.add(offset);
+ }
+ for (int i = 0; i < 3; i++) {
+ int offset = TestUtil.nextInt(random(), 0, maxDoc);
+ if ((offset & 0x3F) != 0) {
+ offsets.add(offset);
+ }
+ }
+ return offsets;
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestSparseFixedBitSet.java b/lucene/core/src/test/org/apache/lucene/util/TestSparseFixedBitSet.java
index b47ff902088..4bf9ab39eca 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestSparseFixedBitSet.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestSparseFixedBitSet.java
@@ -156,6 +156,83 @@ public class TestSparseFixedBitSet extends BaseBitSetTestCase<SparseFixedBitSet>
}
}
+ public void testAndNotRange() {
+ // Three 4096-bit blocks: the first one has all 64 words of its `indices` set, the second one is
+ // strided, and the third one is empty so that the block scan has to skip it.
+ final int numBits = 3 * 4096;
+ SparseFixedBitSet source = new SparseFixedBitSet(numBits);
+ for (int i = 0; i < 4096; ++i) {
+ source.set(i);
+ }
+ for (int i = 4096; i < 2 * 4096; i += 3) {
+ source.set(i);
+ }
+
+ // Test all possible alignments, and both a "short" (less than 64) and a long length, with the
+ // range sweeping the last word before a 4096-bit block boundary across that boundary: first
+ // into a block that has bits set, then into an empty one.
+ for (int blockBoundary : new int[] {4096, 2 * 4096}) {
+ for (int sourceFrom = blockBoundary - 64; sourceFrom < blockBoundary; ++sourceFrom) {
+ for (int alignment = 0; alignment < 64; ++alignment) {
+ for (int length :
+ new int[] {
+ 0,
+ TestUtil.nextInt(random(), 1, Long.SIZE - 1),
+ TestUtil.nextInt(random(), Long.SIZE, 512),
+ blockBoundary - sourceFrom, // ends exactly on the block boundary
+ blockBoundary - sourceFrom + 64 // one word past it
+ }) {
+ // The general case: dest starts a few words in and ends well after the range.
+ assertAndNotRange(source, sourceFrom, 256 + alignment, length, 1_000);
+ // destFrom in dest's first word: a word of source may map before dest's first word.
+ assertAndNotRange(source, sourceFrom, alignment, length, 1_000);
+ if (length > 0) {
+ // dest ends exactly where the range ends: a word of source may map past dest's last
+ // word.
+ assertAndNotRange(source, sourceFrom, alignment, length, alignment + length);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Sets every other bit of a {@code destLength}-bit set, and-nots the given range of {@code
+ * source} into it, and checks every bit of the result.
+ */
+ private static void assertAndNotRange(
+ SparseFixedBitSet source, int sourceFrom, int destFrom, int length, int destLength) {
+ FixedBitSet dest = new FixedBitSet(destLength);
+ for (int i = 0; i < dest.length(); i += 2) {
+ dest.set(i);
+ }
+ SparseFixedBitSet.andNotRange(source, sourceFrom, dest, destFrom, length);
+ for (int i = 0; i < dest.length(); ++i) {
+ boolean destSet = i % 2 == 0;
+ boolean expected;
+ if (i < destFrom || i >= destFrom + length) {
+ // Outside of the range, unmodified
+ expected = destSet;
+ } else {
+ expected = destSet && source.get(sourceFrom + (i - destFrom)) == false;
+ }
+ if (expected != dest.get(i)) {
+ fail(
+ "sourceFrom="
+ + sourceFrom
+ + ", destFrom="
+ + destFrom
+ + ", length="
+ + length
+ + ", destLength="
+ + destLength
+ + ", bit="
+ + i);
+ }
+ }
+ }
+
public void testLargeValuesDoNotOverflow() {
assertEquals(524288, SparseFixedBitSet.blockCount(2147479553));
}