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 114c4c5 refactor(xor): simplify construction and focus benchmark
workloads (#325)
114c4c5 is described below
commit 114c4c516788eba45790b005e40f527514fd512c
Author: tison <[email protected]>
AuthorDate: Thu Nov 5 08:32:20 2026 +0800
refactor(xor): simplify construction and focus benchmark workloads (#325)
---
CONTRIBUTING.md | 2 +-
benchmarks/xor/build.rs | 133 ++++++++++++++++---------
benchmarks/xor/matched_build.rs | 149 -----------------------------
benchmarks/xor/mod.rs | 2 -
datasketches/src/xor/filter.rs | 125 +++++++++---------------
tests-integration/tests/xor_test/filter.rs | 19 ----
tests-integration/tests/xor_test/parts.rs | 13 ---
7 files changed, 133 insertions(+), 310 deletions(-)
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index f409f69..4a06fb0 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -83,7 +83,7 @@ To select workloads and inspect repeated measurements:
```shell
cargo x bench -- cpc::serde --repeat 10 --raw
-cargo x bench -- xor::matched_build::8 --repeat 5
+cargo x bench -- xor::build::8 --repeat 5
cargo x bench -- 'kll::query::quantile/0.5' --exact --rounds 100000
```
diff --git a/benchmarks/xor/build.rs b/benchmarks/xor/build.rs
index 482c1f9..0a9426c 100644
--- a/benchmarks/xor/build.rs
+++ b/benchmarks/xor/build.rs
@@ -24,7 +24,12 @@ use datasketches::xor::XorFilterType;
use crate::xor::hashes;
-fn datasketches_distinct_8(bencher: Bencher, cardinality: usize) {
+// Repeated values model a column batch with four rows per distinct hash.
+fn repeated_hashes(rows: usize) -> Vec<u64> {
+ hashes(rows / 4).into_iter().cycle().take(rows).collect()
+}
+
+fn distinct_8(bencher: Bencher, cardinality: usize) {
let keys = hashes(cardinality);
bencher.bench_local(|| {
black_box(
@@ -35,8 +40,13 @@ fn datasketches_distinct_8(bencher: Bencher, cardinality:
usize) {
});
}
-fn datasketches_deduplicate_8(bencher: Bencher, cardinality: usize) {
+fn xorf_distinct_8(bencher: Bencher, cardinality: usize) {
let keys = hashes(cardinality);
+ bencher.bench_local(|| black_box(xorf::Xor8::from(keys.as_slice())));
+}
+
+fn deduplicate_8(bencher: Bencher, rows: usize) {
+ let keys = repeated_hashes(rows);
bencher.bench_local(|| {
black_box(
XorFilterBuilder::new(XorFilterType::Xor8)
@@ -46,12 +56,18 @@ fn datasketches_deduplicate_8(bencher: Bencher,
cardinality: usize) {
});
}
-fn xorf_8(bencher: Bencher, cardinality: usize) {
- let keys = hashes(cardinality);
- bencher.bench_local(||
black_box(xorf::Xor8::from_iterator(keys.iter().copied())));
+fn xorf_deduplicate_8(bencher: Bencher, rows: usize) {
+ let keys = repeated_hashes(rows);
+ bencher.bench_local(|| {
+ // xorf requires distinct input, so include the caller's preprocessing.
+ let mut distinct = keys.clone();
+ distinct.sort_unstable();
+ distinct.dedup();
+ black_box(xorf::Xor8::from(distinct.as_slice()))
+ });
}
-fn datasketches_distinct_16(bencher: Bencher, cardinality: usize) {
+fn distinct_16(bencher: Bencher, cardinality: usize) {
let keys = hashes(cardinality);
bencher.bench_local(|| {
black_box(
@@ -62,8 +78,13 @@ fn datasketches_distinct_16(bencher: Bencher, cardinality:
usize) {
});
}
-fn datasketches_deduplicate_16(bencher: Bencher, cardinality: usize) {
+fn xorf_distinct_16(bencher: Bencher, cardinality: usize) {
let keys = hashes(cardinality);
+ bencher.bench_local(|| black_box(xorf::Xor16::from(keys.as_slice())));
+}
+
+fn deduplicate_16(bencher: Bencher, rows: usize) {
+ let keys = repeated_hashes(rows);
bencher.bench_local(|| {
black_box(
XorFilterBuilder::new(XorFilterType::Xor16)
@@ -73,12 +94,18 @@ fn datasketches_deduplicate_16(bencher: Bencher,
cardinality: usize) {
});
}
-fn xorf_16(bencher: Bencher, cardinality: usize) {
- let keys = hashes(cardinality);
- bencher.bench_local(||
black_box(xorf::Xor16::from_iterator(keys.iter().copied())));
+fn xorf_deduplicate_16(bencher: Bencher, rows: usize) {
+ let keys = repeated_hashes(rows);
+ bencher.bench_local(|| {
+ // xorf requires distinct input, so include the caller's preprocessing.
+ let mut distinct = keys.clone();
+ distinct.sort_unstable();
+ distinct.dedup();
+ black_box(xorf::Xor16::from(distinct.as_slice()))
+ });
}
-fn datasketches_distinct_32(bencher: Bencher, cardinality: usize) {
+fn distinct_32(bencher: Bencher, cardinality: usize) {
let keys = hashes(cardinality);
bencher.bench_local(|| {
black_box(
@@ -89,8 +116,13 @@ fn datasketches_distinct_32(bencher: Bencher, cardinality:
usize) {
});
}
-fn datasketches_deduplicate_32(bencher: Bencher, cardinality: usize) {
+fn xorf_distinct_32(bencher: Bencher, cardinality: usize) {
let keys = hashes(cardinality);
+ bencher.bench_local(|| black_box(xorf::Xor32::from(keys.as_slice())));
+}
+
+fn deduplicate_32(bencher: Bencher, rows: usize) {
+ let keys = repeated_hashes(rows);
bencher.bench_local(|| {
black_box(
XorFilterBuilder::new(XorFilterType::Xor32)
@@ -100,56 +132,65 @@ fn datasketches_deduplicate_32(bencher: Bencher,
cardinality: usize) {
});
}
-fn xorf_32(bencher: Bencher, cardinality: usize) {
- let keys = hashes(cardinality);
- bencher.bench_local(||
black_box(xorf::Xor32::from_iterator(keys.iter().copied())));
+fn xorf_deduplicate_32(bencher: Bencher, rows: usize) {
+ let keys = repeated_hashes(rows);
+ bencher.bench_local(|| {
+ // xorf requires distinct input, so include the caller's preprocessing.
+ let mut distinct = keys.clone();
+ distinct.sort_unstable();
+ distinct.dedup();
+ black_box(xorf::Xor32::from(distinct.as_slice()))
+ });
}
pub fn register(runner: &mut Runner) {
- let cases = &[
- (1_000, 60_000),
- (16_384, 2_000),
- (49_999, 600),
- (50_000, 600),
- (50_001, 600),
- (100_000, 200),
- ];
- for &(cardinality, rounds) in cases {
+ for (size, rounds) in [(1_000, 60_000), (16_384, 2_000), (1_000_000, 12)] {
runner.compare(
- &format!("xor::build::8/{cardinality}"),
+ &format!("xor::build::8_distinct/{size}"),
rounds,
&[
- ("distinct", &|b| datasketches_distinct_8(b, cardinality)),
- ("deduplicate", &|b| {
- datasketches_deduplicate_8(b, cardinality)
- }),
- ("xorf", &|b| xorf_8(b, cardinality)),
+ ("DataSketches", &|b| distinct_8(b, size)),
+ ("xorf", &|b| xorf_distinct_8(b, size)),
],
);
- }
- for &(cardinality, rounds) in cases {
runner.compare(
- &format!("xor::build::16/{cardinality}"),
+ &format!("xor::build::8_deduplicate/{size}"),
rounds,
&[
- ("distinct", &|b| datasketches_distinct_16(b, cardinality)),
- ("deduplicate", &|b| {
- datasketches_deduplicate_16(b, cardinality)
- }),
- ("xorf", &|b| xorf_16(b, cardinality)),
+ ("DataSketches", &|b| deduplicate_8(b, size)),
+ ("xorf", &|b| xorf_deduplicate_8(b, size)),
+ ],
+ );
+ runner.compare(
+ &format!("xor::build::16_distinct/{size}"),
+ rounds,
+ &[
+ ("DataSketches", &|b| distinct_16(b, size)),
+ ("xorf", &|b| xorf_distinct_16(b, size)),
+ ],
+ );
+ runner.compare(
+ &format!("xor::build::16_deduplicate/{size}"),
+ rounds,
+ &[
+ ("DataSketches", &|b| deduplicate_16(b, size)),
+ ("xorf", &|b| xorf_deduplicate_16(b, size)),
+ ],
+ );
+ runner.compare(
+ &format!("xor::build::32_distinct/{size}"),
+ rounds,
+ &[
+ ("DataSketches", &|b| distinct_32(b, size)),
+ ("xorf", &|b| xorf_distinct_32(b, size)),
],
);
- }
- for &(cardinality, rounds) in cases {
runner.compare(
- &format!("xor::build::32/{cardinality}"),
+ &format!("xor::build::32_deduplicate/{size}"),
rounds,
&[
- ("distinct", &|b| datasketches_distinct_32(b, cardinality)),
- ("deduplicate", &|b| {
- datasketches_deduplicate_32(b, cardinality)
- }),
- ("xorf", &|b| xorf_32(b, cardinality)),
+ ("DataSketches", &|b| deduplicate_32(b, size)),
+ ("xorf", &|b| xorf_deduplicate_32(b, size)),
],
);
}
diff --git a/benchmarks/xor/matched_build.rs b/benchmarks/xor/matched_build.rs
deleted file mode 100644
index 34b8666..0000000
--- a/benchmarks/xor/matched_build.rs
+++ /dev/null
@@ -1,149 +0,0 @@
-// 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;
-
-// xorf 0.13 starts SplitMix at 1. These are its first two construction seeds.
-// Check each result directly: building a peer for validation inside the timed
-// workload would dilute the comparison, especially for the single-round cases.
-fn verify_seed(seed: u64, offset: u64) {
- let expected = match offset {
- 0 => 0x910a_2dec_8902_5cc1,
- 917_504 => 0xbeeb_8da1_658e_ec67,
- _ => unreachable!("unregistered input offset"),
- };
- assert_eq!(seed, expected, "construction attempt count changed");
-}
-
-fn datasketches_8(bencher: Bencher, case: (usize, u64)) {
- let (cardinality, offset) = case;
- let keys = hashes_with_offset(cardinality, offset);
- bencher.bench_local(|| {
- let filter = XorFilterBuilder::new(XorFilterType::Xor8)
- .seed(1)
- .build_from_distinct_hashes(&keys)
- .unwrap();
- verify_seed(filter.seed(), offset);
- black_box(filter)
- });
-}
-
-fn xorf_8(bencher: Bencher, case: (usize, u64)) {
- let (cardinality, offset) = case;
- let keys = hashes_with_offset(cardinality, offset);
- bencher.bench_local(|| {
- let filter = xorf::Xor8::from_iterator(keys.iter().copied());
- verify_seed(filter.seed, offset);
- black_box(filter)
- });
-}
-
-fn datasketches_16(bencher: Bencher, case: (usize, u64)) {
- let (cardinality, offset) = case;
- let keys = hashes_with_offset(cardinality, offset);
- bencher.bench_local(|| {
- let filter = XorFilterBuilder::new(XorFilterType::Xor16)
- .seed(1)
- .build_from_distinct_hashes(&keys)
- .unwrap();
- verify_seed(filter.seed(), offset);
- black_box(filter)
- });
-}
-
-fn xorf_16(bencher: Bencher, case: (usize, u64)) {
- let (cardinality, offset) = case;
- let keys = hashes_with_offset(cardinality, offset);
- bencher.bench_local(|| {
- let filter = xorf::Xor16::from_iterator(keys.iter().copied());
- verify_seed(filter.seed, offset);
- black_box(filter)
- });
-}
-
-fn datasketches_32(bencher: Bencher, case: (usize, u64)) {
- let (cardinality, offset) = case;
- let keys = hashes_with_offset(cardinality, offset);
- bencher.bench_local(|| {
- let filter = XorFilterBuilder::new(XorFilterType::Xor32)
- .seed(1)
- .build_from_distinct_hashes(&keys)
- .unwrap();
- verify_seed(filter.seed(), offset);
- black_box(filter)
- });
-}
-
-fn xorf_32(bencher: Bencher, case: (usize, u64)) {
- let (cardinality, offset) = case;
- let keys = hashes_with_offset(cardinality, offset);
- bencher.bench_local(|| {
- let filter = xorf::Xor32::from_iterator(keys.iter().copied());
- verify_seed(filter.seed, offset);
- black_box(filter)
- });
-}
-
-pub fn register(runner: &mut Runner) {
- let cases = &[
- ((1_000, 0), 60_000),
- ((16_384, 0), 3_000),
- ((16_384, 917_504), 2_000),
- ((49_999, 0), 600),
- ((50_000, 0), 600),
- ((50_001, 0), 600),
- ((100_000, 0), 200),
- ((8_000_000, 0), 1),
- ];
- for &(case, rounds) in cases {
- runner.compare(
- &format!("xor::matched_build::8/{case:?}"),
- rounds,
- &[
- ("DataSketches", &|b| datasketches_8(b, case)),
- ("xorf", &|b| xorf_8(b, case)),
- ],
- );
- }
- for &(case, rounds) in cases {
- runner.compare(
- &format!("xor::matched_build::16/{case:?}"),
- rounds,
- &[
- ("DataSketches", &|b| datasketches_16(b, case)),
- ("xorf", &|b| xorf_16(b, case)),
- ],
- );
- }
- for &(case, rounds) in cases {
- runner.compare(
- &format!("xor::matched_build::32/{case:?}"),
- rounds,
- &[
- ("DataSketches", &|b| datasketches_32(b, case)),
- ("xorf", &|b| xorf_32(b, case)),
- ],
- );
- }
-}
diff --git a/benchmarks/xor/mod.rs b/benchmarks/xor/mod.rs
index ec01d9b..e7167a7 100644
--- a/benchmarks/xor/mod.rs
+++ b/benchmarks/xor/mod.rs
@@ -17,7 +17,6 @@
mod build;
mod build_batches;
-mod matched_build;
mod query;
mod query_shards;
@@ -40,7 +39,6 @@ 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/datasketches/src/xor/filter.rs b/datasketches/src/xor/filter.rs
index 9068447..166e24f 100644
--- a/datasketches/src/xor/filter.rs
+++ b/datasketches/src/xor/filter.rs
@@ -414,39 +414,27 @@ impl XorFilter {
drop(queue);
let fingerprints = match filter_type {
- XorFilterType::Xor8 => {
- let mut values = vec![0_u8; capacity].into_boxed_slice();
- assign_fingerprints(
- &mut values,
- segment_length,
- &stack_hash[..stack_size],
- &stack_index[..stack_size],
- |hash| fingerprint(hash) as u8,
- );
- XorFingerprints::Xor8(values)
- }
- XorFilterType::Xor16 => {
- let mut values = vec![0_u16; capacity].into_boxed_slice();
- assign_fingerprints(
- &mut values,
- segment_length,
- &stack_hash[..stack_size],
- &stack_index[..stack_size],
- |hash| fingerprint(hash) as u16,
- );
- XorFingerprints::Xor16(values)
- }
- XorFilterType::Xor32 => {
- let mut values = vec![0_u32; capacity].into_boxed_slice();
- assign_fingerprints(
- &mut values,
- segment_length,
- &stack_hash[..stack_size],
- &stack_index[..stack_size],
- |hash| fingerprint(hash) as u32,
- );
- XorFingerprints::Xor32(values)
- }
+ XorFilterType::Xor8 => XorFingerprints::Xor8(assign_fingerprints(
+ capacity,
+ segment_length,
+ &stack_hash,
+ &stack_index,
+ |hash| fingerprint(hash) as u8,
+ )),
+ XorFilterType::Xor16 => XorFingerprints::Xor16(assign_fingerprints(
+ capacity,
+ segment_length,
+ &stack_hash,
+ &stack_index,
+ |hash| fingerprint(hash) as u16,
+ )),
+ XorFilterType::Xor32 => XorFingerprints::Xor32(assign_fingerprints(
+ capacity,
+ segment_length,
+ &stack_hash,
+ &stack_index,
+ |hash| fingerprint(hash) as u32,
+ )),
};
Ok(Self {
@@ -554,12 +542,12 @@ impl XorFilterBuilder {
/// but detection is not guaranteed. Use
[`build_from_hashes`](Self::build_from_hashes) to
/// remove duplicates.
pub fn build_from_distinct_hashes(self, hashes: &[u64]) ->
Result<XorFilter, Error> {
- self.build_with_attempts(hashes, MAX_CONSTRUCTION_ATTEMPTS)
- }
-
- // A private attempt bound makes exhaustion and recovery deterministic in
unit tests.
- fn build_with_attempts(self, hashes: &[u64], max_attempts: usize) ->
Result<XorFilter, Error> {
- XorFilter::build(hashes, self.filter_type, self.seed, max_attempts)
+ XorFilter::build(
+ hashes,
+ self.filter_type,
+ self.seed,
+ MAX_CONSTRUCTION_ATTEMPTS,
+ )
}
}
@@ -701,26 +689,25 @@ fn peel_block<const BLOCK: usize>(
}
}
-fn assign_fingerprints<T: Copy + BitXor<Output = T>>(
- fingerprints: &mut [T],
+fn assign_fingerprints<T: Copy + Default + BitXor<Output = T>>(
+ capacity: usize,
segment_length: usize,
stack_hash: &[u64],
stack_index: &[u32],
fingerprint_of: impl Fn(u64) -> T,
-) {
+) -> Box<[T]> {
+ let mut fingerprints = vec![T::default(); capacity].into_boxed_slice();
for (&hash, &index) in stack_hash.iter().zip(stack_index).rev() {
let index = index as usize;
let [h0, h1, h2] = indexes(hash, segment_length);
fingerprints[index] =
fingerprint_of(hash) ^ fingerprints[h0] ^ fingerprints[h1] ^
fingerprints[h2];
}
+ fingerprints
}
#[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,
@@ -730,7 +717,9 @@ fn indexes(hash: u64, segment_length: usize) -> [usize; 3] {
#[inline]
fn reduce(hash: u32, range: usize) -> usize {
- ((u64::from(hash) * range as u64) >> 32) as usize
+ // Construction and import validate the 32-bit segment bound. Keep both
inputs
+ // narrow so mapping, peeling, and queries can use widening 32-bit
multiplies.
+ ((u64::from(hash) * u64::from(range as u32)) >> 32) as usize
}
#[inline]
@@ -804,40 +793,16 @@ mod tests {
let keys: Vec<_> = (917_504..917_504 + 16_384u64)
.map(|i| splitmix64(i.wrapping_add(SPLITMIX_GAMMA)))
.collect();
- for kind in [
- XorFilterType::Xor8,
- XorFilterType::Xor16,
- XorFilterType::Xor32,
- ] {
- let original = keys.clone();
- let error = XorFilterBuilder::new(kind)
- .seed(1)
- .build_with_attempts(&keys, 1)
- .unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
- assert_eq!(keys, original);
-
- let builder =
XorFilterBuilder::new(kind).seed(1_u64.wrapping_add(SPLITMIX_GAMMA));
- let filter =
builder.clone().build_from_distinct_hashes(&keys).unwrap();
- assert_eq!(filter.num_items(), Some(keys.len()));
- for &key in &keys {
- assert!(filter.contains_hash(key));
- }
- // A failed peel overwrites the mixed hashes in the scratch stack.
An automatic
- // retry must remap the original input before attempting the next
seed.
- assert_eq!(
- XorFilterBuilder::new(kind)
- .seed(1)
- .build_from_distinct_hashes(&keys)
- .unwrap(),
- filter,
- );
- assert_eq!(
- builder
-
.build_from_hashes(keys.iter().copied().chain(keys.iter().copied()))
- .unwrap(),
- filter,
- );
+ let error = XorFilter::build(&keys, XorFilterType::Xor8, 1,
1).unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::InvalidArgument);
+
+ let filter = XorFilterBuilder::new(XorFilterType::Xor8)
+ .seed(1_u64.wrapping_add(SPLITMIX_GAMMA))
+ .build_from_distinct_hashes(&keys)
+ .unwrap();
+ assert_eq!(filter.num_items(), Some(keys.len()));
+ for &key in &keys {
+ assert!(filter.contains_hash(key));
}
}
}
diff --git a/tests-integration/tests/xor_test/filter.rs
b/tests-integration/tests/xor_test/filter.rs
index bda1197..96919e8 100644
--- a/tests-integration/tests/xor_test/filter.rs
+++ b/tests-integration/tests/xor_test/filter.rs
@@ -72,25 +72,6 @@ fn duplicates_are_removed_before_construction() {
assert!(filter.contains_hash(11));
}
-#[test]
-fn construction_is_independent_of_input_order() {
- let ascending = XorFilterBuilder::new(XorFilterType::Xor8).seed(424_242);
- let descending = ascending.clone();
-
- assert_eq!(
- ascending
- .build_from_hashes(0..50_000_u64)
- .unwrap()
- .serialize()
- .unwrap(),
- descending
- .build_from_hashes((0..50_000_u64).rev())
- .unwrap()
- .serialize()
- .unwrap()
- );
-}
-
#[test]
fn metadata_describes_the_compact_payload() {
let filter = XorFilterBuilder::new(XorFilterType::Xor8)
diff --git a/tests-integration/tests/xor_test/parts.rs
b/tests-integration/tests/xor_test/parts.rs
index 61bf186..9004026 100644
--- a/tests-integration/tests/xor_test/parts.rs
+++ b/tests-integration/tests/xor_test/parts.rs
@@ -147,19 +147,6 @@ fn
distinct_construction_is_bounded_and_does_not_deduplicate() {
}
}
-#[test]
-fn empty_filters_never_match_even_when_the_fingerprint_is_zero() {
- for kind in [
- XorFilterType::Xor8,
- XorFilterType::Xor16,
- XorFilterType::Xor32,
- ] {
- let f = XorFilterBuilder::new(kind).build_from_hashes([]).unwrap();
- // This key mixes to zero under the filter's construction seed.
- assert!(!f.contains_hash(f.seed().wrapping_neg()));
- }
-}
-
#[test]
fn construction_recovers_after_an_unpeelable_first_attempt() {
// This distinct set needs two attempts with base seed 1. All fingerprint
widths
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]