tisonkun opened a new pull request, #786: URL: https://github.com/apache/datasketches-java/pull/786
## Problem `XorFilter` construction peels singleton slots through a single LIFO queue that spans all three segments. The reference C implementation ([FastFilter xor_singleheader `xor8_populate`](https://github.com/FastFilter/xor_singleheader/blob/5426b7d84994ecf60e596fde8ae70bc1ae7a9720/include/xorfilter.h#L717-L794)), the Rust [xorf](https://crates.io/crates/xorf) crate, and the datasketches-rust implementation in apache/datasketches-rust#309 instead keep one queue per segment and drain segment 0, then 1, then 2, repeating until all queues are empty. Whether peeling succeeds does not depend on the order, because the 2-core of the hypergraph is unique. Both orders therefore select the same construction seed and write the same header. The order does decide which slot each key owns, though, so the fingerprint payloads differ. For the same items and base seed, Java and Rust produced different images, and a different set of non-member keys tested as false positives. ## Change - `map()` splits the existing `queue` array into one region per segment and peels in the reference order. A slot is queued at most once, so each region of `segmentLength` entries cannot overflow, and no memory is added. - A peeled key is removed only from its slots in the other two segments. Its own slot holds no other key, so the slot is never queued again. - Queue lengths stay in local variables so the JIT can keep them in registers instead of reloading them from an array that may alias the other `int[]` buffers. - `referenceImplementationImageTest` checks 8- and 16-bit images against bytes produced by datasketches-rust for the same items and base seed. The test fails with the previous peeling order. ## Compatibility The serialized format does not change. Existing images remain readable and answer every query exactly as before, because queries depend only on the stored seed, segment length, and fingerprints. Only newly built images differ. `XorFilter` has not been released yet. ## Verification - `XorFilterTest`: 25 tests pass. - Cross-implementation check against datasketches-rust (apache/datasketches-rust#309): 8- and 16-bit filters, base seeds 42 and 7, and 4, 100, 1,000, 16,384, 100,000, and 1,000,000 items (24 configurations). All images are byte-identical, and each library returns identical answers on the other's images for every member plus 200,000 non-members. - Construction time, measured through the package-private constructor on pre-generated distinct keys, so item hashing and deduplication are excluded. Each figure is the median of six JVM runs, alternating old and new builds; each run reports the median of seven timed rounds after warm-up. JDK 25.0.2, Apple M4 Max. | Workload | Single queue | Segment queues | Change | | -------------------------------- | -----------: | -------------: | -----: | | 1,000 filters of 16,384 keys | 343.6 ms | 346.1 ms | +0.7% | | 5 filters of 1,000,000 keys | 158.3 ms | 129.1 ms | -18.4% | | 1 filter of 8,000,000 keys | 746.9 ms | 476.1 ms | -36.3% | The gain grows once the working set exceeds the CPU caches. Draining one segment at a time keeps its reads close to sequential order, because peeling a key only creates new singletons in the other two segments. With a single LIFO queue, each new singleton is popped immediately, which follows chains of slots across the whole table. -- 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]
