refactor(xor): remove persisted item counts for 9.1.0 (#796)
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 ae0923f..be42915 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 @@ 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 @@ */ 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 @@ } // 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,55 +176,41 @@ 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 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 @@ } /* - * 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 @@ 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 @@ 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 af6ae01..1846d74 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 @@ 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 453393e..7e690ef 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 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 @@ 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 @@ @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 @@ 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 @@ 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 @@ } 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 @@ @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