tisonkun opened a new pull request, #309: URL: https://github.com/apache/datasketches-rust/pull/309
Adds immutable XOR filters for complete input sets, with 8-, 16-, and 32-bit fingerprints behind the `xor` feature. Construction has bounded retries and compact scratch storage; the library gains no runtime dependency. ## API semantics - `XorFilterBuilder` accepts ordinary Rust `Hash` values or precomputed `u64` hashes. `build(&mut self)` deduplicates in place and retains the input on both success and failure, allowing reseeding, rebuilding, or further updates. Drop the builder to release its retained input. - `from_hashes` handles duplicates; `from_distinct_hashes` and its explicit-seed variant borrow a distinct hash slice without copying or sorting. These fast paths do not separately detect duplicates. - Construction makes at most 100 attempts. Size violations return `InvalidArgument`; exhaustion returns `ConstructionFailed`, including when duplicate hashes prevent peeling. A new seed does not guarantee recovery. - Filters are immutable after construction. With consistent input hashing, `false` proves absence and `true` may be a false positive. There is no incremental insertion or merge API. - `num_items`, `is_empty`, and `bits_per_item` return optional metadata: imported raw parts may have no item count. A known-empty filter always rejects queries; an unknown count preserves the fingerprint comparison, including possible false positives. `capacity` counts fingerprint slots, not input items. ## Format and interoperability boundaries - Standard serialization uses DataSketches family 22, version 1, with little-endian fields and 8/16-bit fingerprints, matching the merged Java implementation. It requires a known item count. Item count and segment length must fit signed 32-bit header fields; total slots must also fit `i32::MAX` for Java indexing. Construction and raw parts can support larger capacities, so successful construction does not guarantee standard serialization. - `from_parts` / `into_parts` transfer the seed, segment length, typed fingerprint slots, and optional count. They support all three widths and application-defined storage without adding a standard header. Import validates layout and count bounds; callers remain responsible for the original seed, slot order, count, and hash encoding. - Raw parts interoperate with `xorf 0.13.0` for 8/16/32-bit filters. The standard Java format does not support 32-bit fingerprints. Rust deserialization owns its data; there is no counterpart to Java's zero-copy `wrap`. - Format compatibility does not imply matching hashes. Ordinary values use xxHash64 with seed 0, but Rust `Hash` encodings can differ from Java. Use the documented integer/raw-byte encodings for Java interoperability; skip empty strings explicitly when matching Java. Externally computed hashes must use the precomputed-hash APIs throughout; Java's typed query APIs hash their arguments again. - Independently constructed filters need not have identical fingerprint bytes. Existing compatible images retain their representation when decoded and re-encoded. Reserved header fields are ignored on read and written as zero; trailing storage is ignored. ## Construction performance The committed `xor::matched_build` benchmarks use synthetic distinct hashes and base seed 1 for both implementations. Setup checks that the winning seeds agree, ensuring equal attempt counts. Input generation is outside timing; these measurements compare the borrowed distinct-hash path with `xorf::from_iterator`, without deduplication. Example Xor8 medians from 50 Divan samples on Apple M4 Max (arm64), rustc 1.101.0-nightly (2026-10-17), optimized bench profile: | Hashes | Attempts | This implementation | xorf 0.13.0 | | ---: | ---: | ---: | ---: | | 16,384 | 1 | 119.4 µs | 140.1 µs | | 16,384, alternate synthetic set | 2 | 216.0 µs | 269.2 µs | | 50,000 | 1 | 621.0 µs | 697.7 µs | | 100,000 | 1 | 1.555 ms | 1.651 ms | For 16,384 hashes, the measured peak heap allocation during Xor8 construction is approximately 540 KB versus 2.22 MB, excluding the preexisting input. Segment-local peeling queues and compact reusable scratch arrays retain the lower memory usage. These are workload-specific local measurements, not a universal speed guarantee; results vary with data, retries, and hardware. Callers with only an iterator must collect a slice for the distinct fast path. Reproduce all three widths with: ```sh cargo bench --package benchmarks --bench benchmarks -- xor::matched_build --sample-count 50 ``` ## Validation - `cargo x check`, `cargo x test` (803 passing tests, including doctests), and `cargo x lint` passed on the submitted commit's contents. - `cargo +1.86.0 check -p datasketches --no-default-features --features xor` passed. - Deterministic exhaustion/recovery tests cover retained builder input, reseeding, rebuilding, and subsequent updates. Additional tests cover unknown counts, zero fingerprints, malformed/truncated images, and bounded duplicate-input failures. - Java fixtures cover integer and UTF-8/raw-byte inputs and exact image round trips. Manual bidirectional Java/Rust validation covers 8/16-bit filters at 0, 1, 4, 16,384, and 50,001 items. The pinned TCK has no XOR fixtures yet, so fixtures document the merged Java source revision. - Raw-parts tests cover bidirectional xorf interoperability across all three widths and a synthetic storage envelope without cardinality metadata. All fixtures and workloads use public or synthetic data. -- 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]
