ChrisHegarty commented on code in PR #16593:
URL: https://github.com/apache/lucene/pull/16593#discussion_r3966759996
##########
lucene/core/src/java/org/apache/lucene/util/Bits.java:
##########
@@ -40,7 +40,14 @@ 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, and no bit of {@code bitSet} at
index {@code length() -
+ * offset} or beyond may be set: those bits are not covered by this
instance. Implementations that
+ * can detect such a bit cheaply -- {@link FixedBitSet#applyMask} and the
{@link LiveDocs}
+ * implementations do -- throw {@link IllegalArgumentException}; the default
implementation below
+ * silently reads out of bounds instead, which is undefined per {@link #get}.
Review Comment:
The new paragraph is good. One tweak: clarify that `length()` is
`this.length()` (the `Bits` instance, e.g. segment `maxDoc`), not
`bitSet.length()`, and phrase the boundary in terms of doc IDs.
```suggestion
* <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}.
```
##########
lucene/core/src/java/org/apache/lucene/util/DenseLiveDocs.java:
##########
@@ -129,6 +129,41 @@ public int length() {
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.
+ *
+ * @throws IllegalArgumentException if a bit of {@code bitSet} at or beyond
{@code maxDoc -
+ * offset} is set
Review Comment:
Positive `@throws` wording:
```suggestion
* @throws IllegalArgumentException unless every set bit of {@code
bitSet} at index {@code i}
* satisfies {@code offset + i < maxDoc}
```
##########
lucene/core/src/java/org/apache/lucene/util/DenseLiveDocs.java:
##########
@@ -129,6 +129,41 @@ public int length() {
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.
Review Comment:
I noticed that `DenseLiveDocs.applyMask` mirrors `FixedBitSet#applyMask`.
Worth calling that out explicitly:
```suggestion
* 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.
```
##########
lucene/core/src/java/org/apache/lucene/util/SparseLiveDocs.java:
##########
@@ -128,6 +128,33 @@ public int length() {
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 if a bit of {@code bitSet} at or beyond
{@code maxDoc -
+ * offset} is set
Review Comment:
Positive `@throws` wording:
```suggestion
* @throws IllegalArgumentException unless every set bit of {@code
bitSet} at index {@code i}
* satisfies {@code offset + i < maxDoc}
```
##########
lucene/core/src/java/org/apache/lucene/util/SparseFixedBitSet.java:
##########
@@ -712,6 +713,92 @@ public void or(DocIdSetIterator it) throws IOException {
}
}
+ /**
+ * And-not {@code length} bits starting at {@code sourceFrom} from {@code
source} into {@code
+ * dest} starting at {@code destFrom}: bits of {@code dest} whose
corresponding bit is set in
+ * {@code source} get cleared, other bits of {@code dest} are left
untouched. Only {@code dest} is
+ * modified.
+ *
+ * <p>Only the longs of {@code source} that are not zero are visited, one
word operation each, so
+ * the cost is bounded by {@code length / 64} and does not depend on how
many bits {@code dest}
+ * has set.
+ */
Review Comment:
The semantics are correct, but a few clarifications would help future
readers and match the level of detail elsewhere in this PR:
```suggestion
/**
* 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()}
*/
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
