tisonkun opened a new pull request, #324: URL: https://github.com/apache/datasketches-rust/pull/324
XOR membership queries were slower than xorf 0.13.0, and constructing filters over independent input sets spent substantial time in conditional singleton enqueues. This change improves both paths and adds benchmarks for batches of independent builds and queries rotating across imported filters. - Inline `contains_hash` across crate boundaries and expose the validated 32-bit segment-length bound to the index reductions. - Apply the known-empty check as a result mask rather than branching on the fingerprint comparison. - Enqueue singleton candidates without a conditional branch. One spare slot per segment makes speculative writes safe even when a neighbor queue is full, adding three `u32` slots to construction scratch space. - Add a regression test for full neighbor queues, and document the new benchmark workloads and fixed round counts. Public APIs, construction seed selection, and serialization remain compatible. Known-empty filters still return false, but now perform the fingerprint probe before applying the empty mask. Imported filters with unknown cardinality retain the raw fingerprint comparison. ### Measurements Apple M4 Max, macOS arm64; rustc 1.101.0-nightly (8006091eb 2026-10-17). All measurements use optimized Cargo bench builds and include fixture construction and cleanup. The full XOR matrix covers 69 scenarios and 159 scenario/implementation combinations, with five repetitions each. The following default-profile build results compare the library at `33ec5c9` with this change using identical benchmark definitions and rounds. Each round builds 32 independent Xor8 filters; times are medians in milliseconds. | Keys per filter | Rounds | Before | After | xorf | | --------------- | ------ | ------ | ----- | ---- | | 16,384 | 40 | 294 | 151 | 359 | | 50,000 | 12 | 296 | 172 | 332 | All 24 single-filter and imported-filter query scenarios had lower measured medians than xorf in the default bench profile. A separate Xor8 run uses fat LTO and one codegen unit, with seven repetitions for each of 25 scenarios. Imported-filter queries use identical payloads and runtime width dispatch on both sides. Each query round performs 256 lookups on each of 32 filters. | Workload | Rounds | DataSketches | xorf | | -------------------------------------- | ------ | ------------ | ------ | | Build batches, 16,384 keys/filter | 40 | 149 ms | 353 ms | | Build batches, 50,000 keys/filter | 12 | 169 ms | 325 ms | | Imported queries, 16,384 keys, present | 20,000 | 335 ms | 340 ms | | Imported queries, 16,384 keys, absent | 20,000 | 336 ms | 336 ms | These query results indicate approximate parity under LTO, not a statistically established speedup. Results are library microbenchmarks on one architecture. The default-seed single-set 16,384-key build remains slower: base seed 0 needs two attempts for that input, while xorf's base seed 1 needs one. The deduplicating entry point also remains slower than xorf's distinct-input construction. Both cases remain in the benchmark matrix. Reproduce with: ```sh cargo x bench -- xor --repeat 5 --raw CARGO_PROFILE_BENCH_LTO=fat CARGO_PROFILE_BENCH_CODEGEN_UNITS=1 cargo x bench -- xor ::8 --repeat 7 --raw ``` ### Validation - `cargo x check` - `cargo x test`: 817 tests passed - `cargo x lint`: passed on an identical clean source copy - `cargo x bench -- --test`: 312 scenario/implementation combinations passed - `cargo +1.86.0 check --package benchmarks --all-targets --locked` - `cargo x bench --no-run` -- 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]
