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-rust.git
The following commit(s) were added to refs/heads/main by this push:
new 541f87e perf(xor): speed up membership queries and filter
construction (#324)
541f87e is described below
commit 541f87ef6b727742eb6591260a23220fca378d37
Author: tison <[email protected]>
AuthorDate: Thu Nov 5 07:27:34 2026 +0800
perf(xor): speed up membership queries and filter construction (#324)
---
CHANGELOG.md | 2 +-
CONTRIBUTING.md | 12 ++--
benchmarks/xor/build_batches.rs | 67 ++++++++++++++++++
benchmarks/xor/mod.rs | 4 ++
benchmarks/xor/query_shards.rs | 153 ++++++++++++++++++++++++++++++++++++++++
datasketches/src/xor/filter.rs | 58 +++++++++++----
6 files changed, 274 insertions(+), 22 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 8f254ac..5503e35 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -7,7 +7,7 @@ All significant changes to this project will be documented in
this file.
### New features
* Add `HllUnion::serialize` to serialize union results directly.
-* Add immutable `XorFilter` and `XorFilterBuilder` behind the `xor` feature,
with 8-, 16-, and 32-bit fingerprints, consuming builder configuration with
complete-input construction, bounded seeded retries and compact temporary
storage, optional cardinality metadata for imported filters, standard
serialization for all three widths (Java-compatible for 8/16-bit filters), and
raw parts for application-defined storage.
+* Add immutable `XorFilter` and `XorFilterBuilder` behind the `xor` feature,
with 8-, 16-, and 32-bit fingerprints, precomputed-hash queries and borrowed
distinct-hash construction, bounded seeded retries and compact temporary
storage, optional cardinality metadata for imported filters, standard
serialization for all three widths (Java-compatible for 8/16-bit filters), and
raw parts for application-defined storage.
### Improvements
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index 05089af..f409f69 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -91,17 +91,13 @@ Filters are substrings; a scenario must match all supplied
filters. Use `--exact
### Fixed workloads and timing
-[Benchmark In
Milliseconds](https://matklad.github.io/2026/10/05/benchmark-milliseconds.html)
recommends sizing useful work to take roughly 300 ms. Choose that work size on
a reference revision, then preserve it across comparisons. The runner never
calibrates rounds automatically: an optimization should reduce elapsed time for
the same work. The initial counts were sized against the library at `5f080f9`
using the timing boundaries below. Hardware and toolchains affect duration, so
300 ms [...]
+[Benchmark In
Milliseconds](https://matklad.github.io/2026/10/05/benchmark-milliseconds.html)
recommends sizing useful work to take roughly 300 ms. Choose a fixed round
count on a reference revision and preserve it across comparisons; the runner
never calibrates rounds automatically. Hardware and toolchains affect duration,
so 300 ms is a sizing guideline, not a performance assertion.
-Each repetition starts the clock before fixture construction and stops after
cleanup. A fixture is built once per repetition and may be reused across its
fixed rounds. Updates rebuild the sketch each round; read-only queries reuse a
prepared sketch; destructive operations clone their inputs each round. Input
generation, cloning, allocations, output destruction, and fixture validation
all count toward elapsed time. No allocation profiler is installed. These
measurements establish a new ba [...]
+Each repetition times the entire workload, including fixture construction,
input preparation, allocations, output destruction, validation, and cleanup. A
round invokes the workload closure once and may process a batch of items.
Define the workload and fixture reuse to reflect the operation being measured,
and keep input sizes, parameters, timing boundaries, and round counts identical
when comparing implementations or revisions.
-A round is one invocation of the workload closure, not necessarily one item.
For example, hash-based updates process 10,000 inputs, parameterized updates
process the named input size, XOR queries visit every key in the selected
present or absent set, and aggregation rounds process the entire specified
group of partial states. Keep inner batch sizes and sketch parameters stable
when adjusting outer rounds; changing cardinality can change the algorithmic
path.
+The runner reports the median and full minimum-to-maximum range in integer
milliseconds over five repetitions by default. Use `--raw` to retain individual
measurements, including the first run and outliers. Comparison groups
interleave implementations and rotate their execution order. `vs ref` divides
each median by the first implementation's median; `0.80x` means 20% less
elapsed time for the same workload. `--baseline-only` runs just the first
implementation. Different scenario rows ca [...]
-The default is five repetitions. Output reports the median and full
minimum-to-maximum range in integer milliseconds. `--raw` includes every
elapsed time in measurement order, including the first run and outliers. XOR
tables interleave implementations and rotate the first implementation across
repetitions, using identical rounds and input parameters. `vs ref` divides each
median by the first implementation's median before rounding; `0.80x` means 20%
less elapsed time for that workload. ` [...]
-
-XOR build tables compare DataSketches' distinct-hash and deduplicating entry
points with xorf on distinct inputs. The `matched_build` scenarios additionally
align the seed sequence and check each resulting seed against the expected
first or second attempt, including a case requiring a second attempt. Query
tables use the same key sets and fingerprint widths. These comparisons include
each implementation's fixture construction and cleanup. Different scenario rows
may have different round [...]
-
-To add or resize a scenario, select a reference revision and run it with an
explicit `--rounds` value and several repetitions. Choose a convenient fixed
count that puts the reference in the hundreds of milliseconds, then record it
in the workload registration. Give all implementations of that scenario the
same count. Keep it fixed for later revisions and faster peers. When inputs,
rounds, or timing boundaries change, rerun both sides under the new definition.
Inspect the measured range b [...]
+When adding or resizing a scenario, use `--rounds` to select a suitable fixed
count, then record it in the workload registration. If the workload or timing
boundaries change, rerun both sides under the new definition. Explain
scenario-specific assumptions in the benchmark source, and report the measured
revisions, environment, commands, and results in the pull request. Inspect the
measured range before drawing conclusions; changing rounds alone does not
eliminate noise.
## Public API documentation
diff --git a/benchmarks/xor/build_batches.rs b/benchmarks/xor/build_batches.rs
new file mode 100644
index 0000000..dff95af
--- /dev/null
+++ b/benchmarks/xor/build_batches.rs
@@ -0,0 +1,67 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::hint::black_box;
+
+use benchmarks::Bencher;
+use benchmarks::Runner;
+use datasketches::xor::XorFilterBuilder;
+use datasketches::xor::XorFilterType;
+
+use crate::xor::hashes_with_offset;
+
+fn build<F>(bencher: Bencher, cardinality: usize, build: impl Fn(&[u64]) -> F)
{
+ // Multiple independent sets keep a particular seed's retry count on one
set
+ // from dominating the comparison of default construction policies.
+ let inputs: Vec<_> = (0..32)
+ .map(|i| hashes_with_offset(cardinality, i * cardinality as u64))
+ .collect();
+ bencher.bench_local(|| {
+ for keys in &inputs {
+ black_box(build(keys));
+ }
+ });
+}
+
+pub fn register(runner: &mut Runner) {
+ for (cardinality, rounds) in [(128, 10_000), (16_384, 40), (50_000, 12)] {
+ runner.compare(
+ &format!("xor::build_batches::8/{cardinality}"),
+ rounds,
+ &[
+ ("default_seed", &|b| {
+ build(b, cardinality, |keys| {
+ XorFilterBuilder::new(XorFilterType::Xor8)
+ .build_from_distinct_hashes(keys)
+ .unwrap()
+ })
+ }),
+ ("matched_seed", &|b| {
+ build(b, cardinality, |keys| {
+ XorFilterBuilder::new(XorFilterType::Xor8)
+ .seed(1)
+ .build_from_distinct_hashes(keys)
+ .unwrap()
+ })
+ }),
+ ("xorf", &|b| {
+ build(b, cardinality, |keys| xorf::Xor8::from(keys))
+ }),
+ ],
+ );
+ }
+}
diff --git a/benchmarks/xor/mod.rs b/benchmarks/xor/mod.rs
index bfdb47e..ec01d9b 100644
--- a/benchmarks/xor/mod.rs
+++ b/benchmarks/xor/mod.rs
@@ -16,8 +16,10 @@
// under the License.
mod build;
+mod build_batches;
mod matched_build;
mod query;
+mod query_shards;
// SplitMix is a permutation, so these pseudorandom precomputed hashes are
distinct.
fn hashes(count: usize) -> Vec<u64> {
@@ -37,6 +39,8 @@ fn hashes_with_offset(count: usize, offset: u64) -> Vec<u64> {
pub fn register(runner: &mut benchmarks::Runner) {
build::register(runner);
+ build_batches::register(runner);
matched_build::register(runner);
query::register(runner);
+ query_shards::register(runner);
}
diff --git a/benchmarks/xor/query_shards.rs b/benchmarks/xor/query_shards.rs
new file mode 100644
index 0000000..9cd5baa
--- /dev/null
+++ b/benchmarks/xor/query_shards.rs
@@ -0,0 +1,153 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::hint::black_box;
+
+use benchmarks::Bencher;
+use benchmarks::Runner;
+use datasketches::xor::XorFilter;
+use datasketches::xor::XorFilterParts;
+use datasketches::xor::XorFilterType;
+use datasketches::xor::XorFingerprints;
+use xorf::Filter;
+
+use crate::xor::hashes_with_offset;
+
+const SHARDS: usize = 32;
+const QUERIES: usize = 256;
+
+// Storage formats can choose a fingerprint width at runtime. Give both peers
+// this dispatch, and import identical payloads without cardinality metadata.
+enum Reference {
+ Xor8(xorf::Xor8),
+ Xor16(xorf::Xor16),
+ Xor32(xorf::Xor32),
+}
+
+impl Reference {
+ fn new(keys: &[u64], kind: XorFilterType) -> Self {
+ match kind {
+ XorFilterType::Xor8 => Self::Xor8(xorf::Xor8::from(keys)),
+ XorFilterType::Xor16 => Self::Xor16(xorf::Xor16::from(keys)),
+ XorFilterType::Xor32 => Self::Xor32(xorf::Xor32::from(keys)),
+ }
+ }
+
+ #[inline(always)]
+ fn contains(&self, key: u64) -> bool {
+ match self {
+ Self::Xor8(filter) => filter.contains(&key),
+ Self::Xor16(filter) => filter.contains(&key),
+ Self::Xor32(filter) => filter.contains(&key),
+ }
+ }
+
+ fn into_datasketches(self) -> XorFilter {
+ let (seed, segment, fingerprints) = match self {
+ Self::Xor8(f) => (
+ f.seed,
+ f.block_length,
+ XorFingerprints::Xor8(f.fingerprints),
+ ),
+ Self::Xor16(f) => (
+ f.seed,
+ f.block_length,
+ XorFingerprints::Xor16(f.fingerprints),
+ ),
+ Self::Xor32(f) => (
+ f.seed,
+ f.block_length,
+ XorFingerprints::Xor32(f.fingerprints),
+ ),
+ };
+ XorFilter::from_parts(XorFilterParts::new(seed, segment,
fingerprints)).unwrap()
+ }
+}
+
+fn query<F>(
+ bencher: Bencher,
+ cardinality: usize,
+ present: bool,
+ make_filter: impl Fn(&[u64]) -> F,
+ contains: impl Fn(&F, u64) -> bool,
+) {
+ let mut filters = Vec::with_capacity(SHARDS);
+ let mut queries = Vec::with_capacity(SHARDS);
+ for shard in 0..SHARDS {
+ let offset = shard as u64 * cardinality as u64;
+ let keys = hashes_with_offset(cardinality, offset);
+ filters.push(make_filter(&keys));
+ queries.push(if present {
+ keys.iter()
+ .copied()
+ .cycle()
+ .take(QUERIES)
+ .collect::<Vec<_>>()
+ } else {
+ hashes_with_offset(QUERIES, (1 << 40) + shard as u64 * QUERIES as
u64)
+ });
+ }
+ let filters = black_box(filters);
+ let queries = black_box(queries);
+ bencher.bench_local(|| {
+ for query in 0..QUERIES {
+ for (filter, keys) in filters.iter().zip(&queries) {
+ black_box(contains(filter, black_box(keys[query])));
+ }
+ }
+ });
+}
+
+pub fn register(runner: &mut Runner) {
+ for kind in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ for cardinality in [128, 16_384] {
+ for (name, present) in [("present", true), ("absent", false)] {
+ runner.compare(
+ &format!(
+ "xor::query_shards::{}_{name}/{cardinality}",
+ kind.bits_per_fingerprint()
+ ),
+ 20_000,
+ &[
+ ("DataSketches", &|b| {
+ query(
+ b,
+ cardinality,
+ present,
+ |keys| Reference::new(keys,
kind).into_datasketches(),
+ XorFilter::contains_hash,
+ )
+ }),
+ ("xorf", &|b| {
+ query(
+ b,
+ cardinality,
+ present,
+ |keys| Reference::new(keys, kind),
+ Reference::contains,
+ )
+ }),
+ ],
+ );
+ }
+ }
+ }
+}
diff --git a/datasketches/src/xor/filter.rs b/datasketches/src/xor/filter.rs
index 0bf297b..9068447 100644
--- a/datasketches/src/xor/filter.rs
+++ b/datasketches/src/xor/filter.rs
@@ -267,15 +267,13 @@ impl XorFilter {
///
/// This method bypasses xxHash64. The caller must use the same hash value
during construction
/// and queries; mixing raw values with precomputed hashes can introduce
false negatives.
- #[inline]
+ // Keep the width dispatch in the caller's hot loop, including across
crates.
+ #[inline(always)]
pub fn contains_hash(&self, hash: u64) -> bool {
- if self.num_items == Some(0) {
- return false;
- }
let mixed = mix(hash, self.seed);
let [h0, h1, h2] = indexes(mixed, self.segment_length);
- match &self.fingerprints {
+ let found = match &self.fingerprints {
XorFingerprints::Xor8(fingerprints) => {
fingerprint(mixed) as u8 == fingerprints[h0] ^
fingerprints[h1] ^ fingerprints[h2]
}
@@ -285,7 +283,10 @@ impl XorFilter {
XorFingerprints::Xor32(fingerprints) => {
fingerprint(mixed) as u32 == fingerprints[h0] ^
fingerprints[h1] ^ fingerprints[h2]
}
- }
+ };
+ // Avoid branching on the fingerprint comparison, including rare false
+ // positives. Unknown counts must preserve the raw comparison.
+ found & (self.num_items != Some(0))
}
/// Returns whether the input set was empty, or `None` if imported without
an item count.
@@ -361,7 +362,8 @@ impl XorFilter {
let segment_length = capacity / usize::from(NUM_HASHES);
let mut xor_mask = vec![0_u64; capacity];
let mut count = vec![0_u32; capacity];
- let mut queue = vec![0_u32; capacity];
+ // One spare slot per segment allows a speculative enqueue even when
full.
+ let mut queue = vec![0_u32; capacity + 3];
let mut stack_hash = vec![0_u64; num_items];
let mut stack_index = vec![0_u32; num_items];
@@ -596,10 +598,10 @@ fn map(
stack_index: &mut [u32],
) -> usize {
// Separate queues keep each drain within one segment and make the two
neighbor
- // segments statically known. Scratch space remains one slot per
fingerprint.
+ // segments statically known.
let mut masks = split_segments(xor_mask, segment_length);
let mut counts = split_segments(count, segment_length);
- let mut queues = split_segments(queue, segment_length);
+ let mut queues = split_segments(queue, segment_length + 1);
// Reuse the peel stack for mixed hashes while mapping one segment at a
time.
// This bounds the random-access working set without allocating another
buffer.
for (&key, hash) in keys.iter().zip(stack_hash.iter_mut()) {
@@ -690,10 +692,11 @@ fn peel_block<const BLOCK: usize>(
let index = reduce(hash.rotate_left(other as u32 * 21) as u32,
segment_length);
masks[other][index] ^= hash;
counts[other][index] -= 1;
- if counts[other][index] == 1 {
- queues[other][queue_sizes[other]] = index as u32;
- queue_sizes[other] += 1;
- }
+ // A slot enters its queue at most once. The extra slot
accommodates
+ // this write when every real slot is already queued; retain it
only
+ // when the neighbor becomes a singleton.
+ queues[other][queue_sizes[other]] = index as u32;
+ queue_sizes[other] += usize::from(counts[other][index] == 1);
}
}
}
@@ -715,6 +718,9 @@ fn assign_fingerprints<T: Copy + BitXor<Output = T>>(
#[inline]
fn indexes(hash: u64, segment_length: usize) -> [usize; 3] {
+ // Construction and import validate this bound. Exposing it here allows
+ // widening 32-bit multiplies for the three range reductions.
+ let segment_length = segment_length as u32 as usize;
[
reduce(hash as u32, segment_length),
reduce(hash.rotate_left(21) as u32, segment_length) + segment_length,
@@ -764,6 +770,32 @@ mod tests {
}
}
+ #[test]
+ fn peeling_handles_full_neighbor_queues() {
+ // All three singleton queues are full. Removing the only edge makes
+ // both neighbors stale, so speculative enqueues must not retain them.
+ let mut masks = [0; 3];
+ let mut counts = [0; 3];
+ let mut queues = [0; 6];
+ let mut hashes = [0; 1];
+ let mut indexes = [0; 1];
+ assert_eq!(
+ map(
+ &[42],
+ 1,
+ 1,
+ &mut masks,
+ &mut counts,
+ &mut queues,
+ &mut hashes,
+ &mut indexes
+ ),
+ 1,
+ );
+ assert_eq!(hashes, [mix(42, 1)]);
+ assert_eq!(indexes, [0]);
+ }
+
#[test]
fn borrowed_input_survives_exhaustion_and_can_retry() {
// This synthetic set fails its first peeling attempt with base seed 1.
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]