This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
The following commit(s) were added to refs/heads/main by this push:
new ef440a814 refactor(xor): remove persisted item counts (#795)
ef440a814 is described below
commit ef440a814319f57d165dfbe2c39fc07bf4a0a1e7
Author: tison <[email protected]>
AuthorDate: Sun Nov 8 13:17:48 2026 +0800
refactor(xor): remove persisted item counts (#795)
---
.../datasketches/filters/xorfilter/XorFilter.java | 67 ++++++----------------
.../filters/xorfilter/XorFilterBenchmark.java | 2 +-
.../filters/xorfilter/XorFilterTest.java | 66 ++++++++++-----------
3 files changed, 54 insertions(+), 81 deletions(-)
diff --git
a/src/main/java/org/apache/datasketches/filters/xorfilter/XorFilter.java
b/src/main/java/org/apache/datasketches/filters/xorfilter/XorFilter.java
index ae0923f5d..be4291550 100644
--- a/src/main/java/org/apache/datasketches/filters/xorfilter/XorFilter.java
+++ b/src/main/java/org/apache/datasketches/filters/xorfilter/XorFilter.java
@@ -84,7 +84,6 @@ public final class XorFilter implements MemorySegmentStatus {
private final int bitsPerFingerprint_; // fingerprint width in bits, 8 or
16
private final int segmentLength_; // number of fingerprint slots
per hash segment
- private final int numKeys_; // number of distinct keys used
to build the filter
private final long seed_; // winning construction seed for
the murmur mix
private final MemorySegment fpSeg_; // holds the raw fingerprint
payload
private final MemorySegment wseg_; // used only when wrapping a
serialized image
@@ -100,7 +99,6 @@ public final class XorFilter implements MemorySegmentStatus {
*/
XorFilter(final int bitsPerFingerprint, final long seed, final long[] keys,
final int numKeys) {
bitsPerFingerprint_ = bitsPerFingerprint;
- numKeys_ = numKeys;
final int capacity = computeCapacity(numKeys);
segmentLength_ = capacity / NUM_HASHES;
@@ -142,11 +140,10 @@ public final class XorFilter implements
MemorySegmentStatus {
}
// Constructor used with internalHeapifyOrWrap()
- XorFilter(final int bitsPerFingerprint, final int segmentLength, final int
numKeys, final long seed,
+ XorFilter(final int bitsPerFingerprint, final int segmentLength, final long
seed,
final MemorySegment fpSeg, final MemorySegment wseg) {
bitsPerFingerprint_ = bitsPerFingerprint;
segmentLength_ = segmentLength;
- numKeys_ = numKeys;
seed_ = seed;
fpSeg_ = fpSeg;
wseg_ = wseg;
@@ -179,54 +176,40 @@ public final class XorFilter implements
MemorySegmentStatus {
final int preLongs = posSeg.getByte();
final int serVer = posSeg.getByte();
final int familyID = posSeg.getByte();
- posSeg.getByte(); // flags, reserved
checkArgument((preLongs < Family.XORFILTER.getMinPreLongs()) || (preLongs
> Family.XORFILTER.getMaxPreLongs()),
- "Possible corruption: Incorrect number of preamble bytes specified in
header");
+ "Possible corruption: Incorrect number of preamble longs specified in
header");
checkArgument(serVer != SER_VER, "Possible corruption: Unrecognized
serialization version: " + serVer);
checkArgument(familyID != Family.XORFILTER.getID(), "Possible corruption:
Incorrect FamilyID for xor filter. Found: " + familyID);
+ final int flags = posSeg.getByte();
+ checkArgument(flags != 0, "Possible corruption: Unsupported xor filter
flags: " + flags);
final int bitsPerFingerprint = posSeg.getByte();
checkArgument((bitsPerFingerprint != 8) && (bitsPerFingerprint != 16),
"Possible corruption: Fingerprint width must be 8 or 16. Found: " +
bitsPerFingerprint);
- final int numHashes = posSeg.getByte();
- checkArgument(numHashes != NUM_HASHES, "Possible corruption: Number of
hash functions must be " + NUM_HASHES
- + ". Found: " + numHashes);
- posSeg.getShort(); // unused
-
+ // Skip padding to the seed at byte 8.
+ posSeg.getByte();
+ posSeg.getShort();
final long seed = posSeg.getLong();
final int segmentLength = posSeg.getInt();
- final int numKeys = posSeg.getInt();
checkArgument(segmentLength < 1, "Possible corruption: Segment length must
be strictly positive. Found: " + segmentLength);
- checkArgument(numKeys < 0, "Possible corruption: Number of keys must be
non-negative. Found: " + numKeys);
+ posSeg.getInt(); // Skip padding to the end of the three-long preamble.
- final long fingerprintBytes = (long) numHashes * segmentLength *
(bitsPerFingerprint >>> 3);
+ final long fingerprintBytes = (long) NUM_HASHES * segmentLength *
(bitsPerFingerprint >>> 3);
checkArgument(seg.byteSize() < (PREAMBLE_SIZE_BYTES + fingerprintBytes),
"Possible corruption: MemorySegment capacity insufficient to hold the
fingerprint array");
final MemorySegment payload = seg.asSlice(PREAMBLE_SIZE_BYTES,
fingerprintBytes);
if (isWrap) {
- return new XorFilter(bitsPerFingerprint, segmentLength, numKeys, seed,
payload, seg);
+ return new XorFilter(bitsPerFingerprint, segmentLength, seed, payload,
seg);
}
// heapify copies the payload onto the Java heap
checkArgument(fingerprintBytes > Integer.MAX_VALUE, "Filter is too large
to heapify; use wrap() instead");
final byte[] fingerprints = new byte[(int) fingerprintBytes];
MemorySegment.copy(payload, JAVA_BYTE, 0, fingerprints, 0, (int)
fingerprintBytes);
- return new XorFilter(bitsPerFingerprint, segmentLength, numKeys, seed,
MemorySegment.ofArray(fingerprints), null);
+ return new XorFilter(bitsPerFingerprint, segmentLength, seed,
MemorySegment.ofArray(fingerprints), null);
}
- /**
- * Checks if the XorFilter was built from any items.
- * @return True if the XorFilter holds no items, otherwise False
- */
- public boolean isEmpty() { return numKeys_ == 0; }
-
- /**
- * Returns the number of distinct items used to build this XorFilter.
- * @return The number of distinct items in this filter
- */
- public int getNumItems() { return numKeys_; }
-
/**
* Returns the fixed number of hash functions used by the three-partite xor
construction.
* @return The number of hash functions used by this filter
@@ -251,16 +234,6 @@ public final class XorFilter implements
MemorySegmentStatus {
*/
public long getSeed() { return seed_; }
- /**
- * Returns the average number of bits stored per item by this XorFilter, a
measure of its
- * space efficiency. This is approximately 1.23 times the fingerprint width.
- * @return The number of bits used per item, or 0 for an empty filter
- */
- public double getBitsPerItem() {
- if (numKeys_ == 0) { return 0.0; }
- return ((double) getCapacity() * bitsPerFingerprint_) / numKeys_;
- }
-
@Override
public boolean hasMemorySegment() { return wseg_ != null; }
@@ -597,23 +570,22 @@ public final class XorFilter implements
MemorySegmentStatus {
}
/*
- * An Xor Filter's serialized image always uses 3 longs of preamble, as the
filter is
- * immutable and therefore has no empty or growable state:
+ * An Xor Filter's serialized image uses 3 longs of preamble:
*
* <pre>
* Long || Start Byte Adr:
* Adr:
* || 0 | 1 | 2 | 3 | 4 | 5 | 6
| 7 |
- * 0 || Preamble_Longs | SerVer | FamID | Flags | BitsPFP|NumHash
|-----Unused------|
+ * 0 || Preamble_Longs | SerVer | FamID | Flags |
BitsPFP|---------Padding---------|
*
* || 8 | 9 | 10 | 11 | 12 | 13 | 14
| 15 |
* 1 ||-------------------------------Construction
Seed-------------------------------|
*
* || 16 | 17 | 18 | 19 | 20 | 21 | 22
| 23 |
- * 2 ||----------Segment Length (int)-------------|-----------Num Keys
(int)----------|
+ * 2 ||----------Segment Length
(int)-------------|-------------Padding--------------|
* </pre>
*
- * The raw fingerprint array starts at byte 24.
+ * The raw fingerprint array starts at byte 24. The layout always has three
segments.
*/
/**
@@ -656,11 +628,12 @@ public final class XorFilter implements
MemorySegmentStatus {
posSeg.setByte((byte) Family.XORFILTER.getID());
posSeg.setByte((byte) 0); // flags
posSeg.setByte((byte) bitsPerFingerprint_);
- posSeg.setByte((byte) NUM_HASHES);
- posSeg.setShort((short) 0); // unused
+ // Pad to the seed at byte 8.
+ posSeg.setByte((byte) 0);
+ posSeg.setShort((short) 0);
posSeg.setLong(seed_);
posSeg.setInt(segmentLength_);
- posSeg.setInt(numKeys_);
+ posSeg.setInt(0); // Pad the preamble to three 64-bit words.
MemorySegment.copy(fpSeg_, JAVA_BYTE, 0, seg, JAVA_BYTE,
PREAMBLE_SIZE_BYTES, fpSeg_.byteSize());
}
@@ -676,12 +649,10 @@ public final class XorFilter implements
MemorySegmentStatus {
sb.append(LS);
final String thisSimpleName = this.getClass().getSimpleName();
sb.append("### ").append(thisSimpleName).append(" SUMMARY: ").append(LS);
- sb.append(" numItems : ").append(numKeys_).append(LS);
sb.append(" numHashes : ").append(NUM_HASHES).append(LS);
sb.append(" bitsPerFP : ").append(bitsPerFingerprint_).append(LS);
sb.append(" capacity : ").append(getCapacity()).append(LS);
sb.append(" seed : ").append(seed_).append(LS);
- sb.append(" bits/item : ").append(getBitsPerItem()).append(LS);
sb.append("### END SKETCH SUMMARY").append(LS);
return sb.toString();
diff --git
a/src/test/java/org/apache/datasketches/filters/xorfilter/XorFilterBenchmark.java
b/src/test/java/org/apache/datasketches/filters/xorfilter/XorFilterBenchmark.java
index af6ae0122..1846d744c 100644
---
a/src/test/java/org/apache/datasketches/filters/xorfilter/XorFilterBenchmark.java
+++
b/src/test/java/org/apache/datasketches/filters/xorfilter/XorFilterBenchmark.java
@@ -90,7 +90,7 @@ public final class XorFilterBenchmark {
final Result r = new Result();
r.buildNanosPerKey = (double) buildElapsed / numKeys;
r.queryNanosPerOp = (double) queryElapsed / numKeys;
- r.bitsPerItem = filter.getBitsPerItem();
+ r.bitsPerItem = (double) filter.getCapacity() * bits / numKeys;
r.observedFpp = (double) falsePositives / numKeys;
return r;
}
diff --git
a/src/test/java/org/apache/datasketches/filters/xorfilter/XorFilterTest.java
b/src/test/java/org/apache/datasketches/filters/xorfilter/XorFilterTest.java
index 453393eb8..7e690ef20 100644
--- a/src/test/java/org/apache/datasketches/filters/xorfilter/XorFilterTest.java
+++ b/src/test/java/org/apache/datasketches/filters/xorfilter/XorFilterTest.java
@@ -26,6 +26,7 @@ import static org.testng.Assert.assertTrue;
import java.lang.foreign.Arena;
import java.lang.foreign.MemorySegment;
+import java.util.Arrays;
import java.util.HexFormat;
import org.apache.datasketches.common.SketchesArgumentException;
@@ -137,6 +138,7 @@ public class XorFilterTest {
for (int i = 0; i < 1000; ++i) {
builder.update(i % 100); // only 100 distinct values, each added 10 times
}
+ assertEquals(builder.getNumItems(), 1000L);
final XorFilter filter = builder.build();
for (int i = 0; i < 100; ++i) {
assertTrue(filter.query(i));
@@ -148,8 +150,6 @@ public class XorFilterTest {
@Test
public void emptyFilterTest() {
final XorFilter filter = new XorFilterBuilder(8, 7L).build();
- assertTrue(filter.isEmpty());
- assertEquals(filter.getNumItems(), 0);
long positives = 0;
for (long i = 0; i < 100_000; ++i) {
@@ -187,7 +187,6 @@ public class XorFilterTest {
final XorFilter rebuilt = XorFilter.heapify(MemorySegment.ofArray(bytes));
assertEquals(rebuilt.getBitsPerFingerprint(),
filter.getBitsPerFingerprint());
- assertEquals(rebuilt.getNumItems(), filter.getNumItems());
assertEquals(rebuilt.getSeed(), filter.getSeed());
for (long i = 0; i < numItems; ++i) {
assertTrue(rebuilt.query(i));
@@ -378,43 +377,25 @@ public class XorFilterTest {
builder.update(i);
}
final XorFilter filter = builder.build();
- assertEquals(filter.getNumItems(), n);
for (long i = 0; i < n; ++i) {
assertTrue(filter.query(i));
}
}
}
- // the accessors report the expected metadata
+ // the serialized footprint stays near ten bits per input for an 8-bit filter
@Test
- public void gettersTest() {
+ public void spaceUsageTest() {
final int numItems = 10_000;
final XorFilterBuilder builder = new XorFilterBuilder(8, 2L);
for (long i = 0; i < numItems; ++i) {
builder.update(i);
}
final XorFilter filter = builder.build();
- assertEquals(filter.getNumHashes(), 3);
- assertEquals(filter.getBitsPerFingerprint(), 8);
- assertEquals(filter.getNumItems(), numItems);
- final long capacity = filter.getCapacity();
- assertEquals(capacity, 3L * (capacity / 3)); // a multiple of the segment
count
- assertTrue(capacity >= numItems); // roughly 1.23 times the
item count
- final double bitsPerItem = filter.getBitsPerItem();
+ final double bitsPerItem = (double) filter.getSerializedSizeBytes() *
Byte.SIZE / numItems;
assertTrue((bitsPerItem > 9.5) && (bitsPerItem < 10.5), "unexpected
bits/item: " + bitsPerItem);
}
- // the builder counts every item added while the filter counts only the
distinct ones
- @Test
- public void builderNumItemsTest() {
- final XorFilterBuilder builder = new XorFilterBuilder(8, 4L);
- for (int i = 0; i < 1000; ++i) {
- builder.update(i % 100);
- }
- assertEquals(builder.getNumItems(), 1000L);
- assertEquals(builder.build().getNumItems(), 100);
- }
-
// 16-bit construction must also be deterministic for a fixed seed and item
set
@Test
public void determinism16Test() {
@@ -452,20 +433,27 @@ public class XorFilterTest {
}
final byte[] valid = builder.build().toByteArray();
+ assertThrows(SketchesArgumentException.class, () ->
XorFilter.heapify(corrupt(valid, 0, (byte) 2))); // preamble
assertThrows(SketchesArgumentException.class, () ->
XorFilter.heapify(corrupt(valid, 1, (byte) 99))); // serVer
assertThrows(SketchesArgumentException.class, () ->
XorFilter.heapify(corrupt(valid, 2, (byte) 7))); // familyID
assertThrows(SketchesArgumentException.class, () ->
XorFilter.heapify(corrupt(valid, 4, (byte) 5))); // bitsPerFP
- assertThrows(SketchesArgumentException.class, () ->
XorFilter.heapify(corrupt(valid, 5, (byte) 4))); // numHashes
- assertThrows(SketchesArgumentException.class, () ->
XorFilter.heapify(MemorySegment.ofArray(new byte[16])));
+ assertThrows(SketchesArgumentException.class, () ->
XorFilter.heapify(corrupt(valid, 19, (byte) 0x80))); // negative length
+ assertThrows(SketchesArgumentException.class, () ->
XorFilter.heapify(corrupt(valid, 3, (byte) 1))); // flags
+ assertThrows(SketchesArgumentException.class, () ->
XorFilter.wrap(corrupt(valid, 3, (byte) 1)));
+ for (int length = 0; length < valid.length; ++length) {
+ final MemorySegment truncated =
MemorySegment.ofArray(Arrays.copyOf(valid, length));
+ assertThrows(SketchesArgumentException.class, () ->
XorFilter.heapify(truncated));
+ assertThrows(SketchesArgumentException.class, () ->
XorFilter.wrap(truncated));
+ }
}
- // Images built by datasketches-rust for the same items and base seed. Both
libraries peel through
- // one queue per segment, so their images must be identical.
+ // Fingerprint payloads generated by datasketches-rust for the same items
and base seed.
+ // Both libraries peel through one queue per segment.
private static final String REFERENCE_XOR8_IMAGE =
- "0301160008030000956eeb2f2632d7bd0c00000004000000"
+ "0301160008000000956eeb2f2632d7bd0c00000000000000"
+
"000000000000000400dd0000000000000000ce0000c50000000000000000000000000000";
private static final String REFERENCE_XOR16_IMAGE =
- "0301160010030000956eeb2f2632d7bd0c00000004000000"
+ "0301160010000000956eeb2f2632d7bd0c00000000000000"
+
"000000000000000000000000000004e80000dd6e00000000000000000000000000000000"
+
"ce9500000000c5b600000000000000000000000000000000000000000000000000000000";
@@ -473,8 +461,22 @@ public class XorFilterTest {
@Test
public void referenceImplementationImageTest() {
final long[] items = { 1, 2, 3, Long.MIN_VALUE };
- assertEquals(XorFilterBuilder.create(items, 8, 42L).toByteArray(),
HexFormat.of().parseHex(REFERENCE_XOR8_IMAGE));
- assertEquals(XorFilterBuilder.create(items, 16, 42L).toByteArray(),
HexFormat.of().parseHex(REFERENCE_XOR16_IMAGE));
+ for (final int bits : new int[] { 8, 16 }) {
+ final byte[] image = HexFormat.of().parseHex(bits == 8 ?
REFERENCE_XOR8_IMAGE : REFERENCE_XOR16_IMAGE);
+ final XorFilter built = XorFilterBuilder.create(items, bits, 42L);
+ assertEquals(built.toByteArray(), image);
+ final MemorySegment seg = MemorySegment.ofArray(image);
+ for (final XorFilter restored : new XorFilter[] { built,
XorFilter.heapify(seg), XorFilter.wrap(seg) }) {
+ assertEquals(restored.getNumHashes(), 3);
+ assertEquals(restored.getBitsPerFingerprint(), bits);
+ assertEquals(restored.getCapacity() % 3, 0L);
+ assertTrue(restored.getCapacity() >= items.length);
+ assertEquals(restored.toByteArray(), image);
+ for (final long item : items) {
+ assertTrue(restored.query(item));
+ }
+ }
+ }
}
// returns a copy of the image with a single byte replaced
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]