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 76ab65b perf(theta,tuple): hash a-not-b keys with a seeded folded
multiply (#343)
76ab65b is described below
commit 76ab65ba6857b2860ed65301350e8487c6e9a7b4
Author: David Cromberge <[email protected]>
AuthorDate: Wed Nov 11 14:58:56 2026 +0200
perf(theta,tuple): hash a-not-b keys with a seeded folded multiply (#343)
Co-authored-by: Claude Opus 5.5 <[email protected]>
Co-authored-by: tison <[email protected]>
---
CHANGELOG.md | 1 +
datasketches/src/common/mod.rs | 2 +-
datasketches/src/common/random.rs | 20 +++-
datasketches/src/thetafamily/common/a_not_b.rs | 102 ++++++++++++++++++---
datasketches/src/thetafamily/common/hash_table.rs | 2 +
.../src/thetafamily/common/jaccard_similarity.rs | 6 ++
datasketches/src/thetafamily/common/mod.rs | 3 +
datasketches/src/thetafamily/theta/sketch.rs | 10 ++
datasketches/src/thetafamily/tuple/sketch.rs | 10 ++
tests-integration/tests/theta_test/a_not_b.rs | 42 +++++++++
tests-integration/tests/tuple_test/a_not_b.rs | 71 ++++++++++++++
11 files changed, 249 insertions(+), 20 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 3660298..8a3fc88 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -22,6 +22,7 @@ All significant changes to this project will be documented in
this file.
* `BloomFilter::insert` is faster for streams of new items when multiple
hashes are configured.
* Compressed `CompactThetaSketch` serialization and deserialization are faster.
* Tuple sketch serialization and deserialization are faster.
+* `ThetaANotB` and `TupleANotB` are faster when either input is unordered.
## v0.6.0 (2026-10-29)
diff --git a/datasketches/src/common/mod.rs b/datasketches/src/common/mod.rs
index c9c1cf7..232f830 100644
--- a/datasketches/src/common/mod.rs
+++ b/datasketches/src/common/mod.rs
@@ -26,5 +26,5 @@ pub use self::search_criteria::SearchCriteria;
#[cfg(any(feature = "cpc", feature = "hll"))]
pub(crate) mod inv_pow2;
-#[cfg(any(feature = "kll", feature = "req"))]
+#[cfg(any(feature = "kll", feature = "req", feature = "theta", feature =
"tuple"))]
pub(crate) mod random;
diff --git a/datasketches/src/common/random.rs
b/datasketches/src/common/random.rs
index 9959b58..1155a9d 100644
--- a/datasketches/src/common/random.rs
+++ b/datasketches/src/common/random.rs
@@ -60,20 +60,32 @@ thread_local! {
static STATE: Cell<u64> = Cell::new(random_seed());
}
-/// Returns `true` or `false`, each with probability 1/2.
+/// Returns a uniformly distributed `u64` from the calling thread's stream.
///
-/// The bit is the low bit of the next output of the calling thread's stream.
/// The call is a handful of arithmetic operations on thread-local state: it
/// never allocates, locks, or blocks. The first call on a thread seeds that
/// thread's state.
-pub fn random_bit() -> bool {
+#[inline]
+pub fn random_u64() -> u64 {
STATE.with(|state| {
let (next, value) = next_u64(state.get());
state.set(next);
- value & 1 == 1
+ value
})
}
+/// Returns `true` or `false`, each with probability 1/2.
+///
+/// The bit is the low bit of the next output of the calling thread's stream.
+/// The call is a handful of arithmetic operations on thread-local state: it
+/// never allocates, locks, or blocks. The first call on a thread seeds that
+/// thread's state.
+#[cfg(any(test, feature = "kll", feature = "req"))]
+#[inline]
+pub fn random_bit() -> bool {
+ random_u64() & 1 == 1
+}
+
#[cfg(test)]
mod tests {
use super::*;
diff --git a/datasketches/src/thetafamily/common/a_not_b.rs
b/datasketches/src/thetafamily/common/a_not_b.rs
index d1caeea..7c01b40 100644
--- a/datasketches/src/thetafamily/common/a_not_b.rs
+++ b/datasketches/src/thetafamily/common/a_not_b.rs
@@ -16,6 +16,8 @@
// under the License.
use std::collections::HashSet;
+use std::hash::BuildHasher;
+use std::hash::Hasher;
use crate::error::Error;
use crate::error::ErrorKind;
@@ -81,7 +83,7 @@ where
let theta = a_theta.min(b_theta);
let entries: Vec<A::Entry> = if b_num_retained == 0 {
- a.entries().filter(|entry| entry.hash() < theta).collect()
+ retain_not_in_b(a, theta, a_ordered, |_| false)
} else if a_ordered && b_ordered {
// Both inputs are sorted ascending by hash: merge-scan without a hash
set. Only
// B hashes below theta can exclude an A entry (A entries are all <
theta), so
@@ -105,8 +107,14 @@ where
}
}
entries
+ } else if let Some(b_table) = b.hash_table() {
+ // Mutable B sketches already own an open-addressed hash table
populated through
+ // MurmurHash3. Probing it directly avoids scanning B or allocating a
temporary set; keys
+ // in B at or above theta are harmless because A entries are screened
by theta first.
+ retain_not_in_b(a, theta, a_ordered, |hash|
b_table.entry(hash).is_some())
} else {
- let mut b_keys: HashSet<u64> = HashSet::with_capacity(b_num_retained);
+ let mut b_keys: HashSet<u64, FoldHashState> =
+ HashSet::with_capacity_and_hasher(b_num_retained,
FoldHashState::new());
for hash in b.hashes() {
if hash < theta {
b_keys.insert(hash);
@@ -114,19 +122,7 @@ where
break;
}
}
-
- let mut entries = vec![];
- for entry in a.entries() {
- let hash = entry.hash();
- if hash < theta {
- if !b_keys.contains(&hash) {
- entries.push(entry);
- }
- } else if a_ordered {
- break;
- }
- }
- entries
+ retain_not_in_b(a, theta, a_ordered, |hash| b_keys.contains(&hash))
};
if entries.is_empty() && theta == MAX_THETA {
@@ -147,6 +143,29 @@ where
))
}
+fn retain_not_in_b<A>(
+ a: A,
+ theta: u64,
+ a_ordered: bool,
+ b_contains: impl Fn(u64) -> bool,
+) -> Vec<A::Entry>
+where
+ A: EntrySketch,
+{
+ let mut entries = vec![];
+ for entry in a.entries() {
+ let hash = entry.hash();
+ if hash < theta {
+ if !b_contains(hash) {
+ entries.push(entry);
+ }
+ } else if a_ordered {
+ break;
+ }
+ }
+ entries
+}
+
fn copy_to_compact_state<S>(sketch: S, ordered: bool) ->
CompactSketchState<S::Entry>
where
S: EntrySketch,
@@ -170,3 +189,56 @@ where
let out_ordered = ordered || input_ordered || (entries.len() == 1 && theta
== MAX_THETA);
CompactSketchState::non_empty(entries, theta, seed_hash, out_ordered)
}
+
+const FOLD_MULTIPLIER: u64 = 0x9E37_79B9_7F4A_7C15;
+
+#[inline]
+fn folded_multiply(x: u64, y: u64) -> u64 {
+ let product = u128::from(x) * u128::from(y);
+ (product as u64) ^ ((product >> 64) as u64)
+}
+
+/// Per-operation random state for hashing pre-hashed 64-bit sketch keys.
+///
+/// Keys in Theta and Tuple sketches are already uniform MurmurHash3 outputs,
so SipHash is
+/// unnecessary overhead, but compact sketches can be deserialized from
untrusted bytes whose raw
+/// hashes were chosen to collide. Seeding a 128-bit folded multiply from the
thread-local PRNG on
+/// each call prevents crafted inputs from forcing worst-case probe chains.
+struct FoldHashState(u64);
+
+impl FoldHashState {
+ #[inline]
+ fn new() -> Self {
+ Self(crate::common::random::random_u64())
+ }
+}
+
+impl BuildHasher for FoldHashState {
+ type Hasher = FoldHasher;
+
+ #[inline]
+ fn build_hasher(&self) -> FoldHasher {
+ FoldHasher(self.0)
+ }
+}
+
+struct FoldHasher(u64);
+
+impl Hasher for FoldHasher {
+ #[inline]
+ fn finish(&self) -> u64 {
+ self.0
+ }
+
+ #[inline]
+ fn write(&mut self, bytes: &[u8]) {
+ for &byte in bytes {
+ self.0 = folded_multiply(self.0 ^ u64::from(byte),
FOLD_MULTIPLIER);
+ }
+ }
+
+ #[inline]
+ fn write_u64(&mut self, value: u64) {
+ self.0 = folded_multiply(self.0 ^ value, FOLD_MULTIPLIER);
+ }
+}
diff --git a/datasketches/src/thetafamily/common/hash_table.rs
b/datasketches/src/thetafamily/common/hash_table.rs
index f57d786..35c5106 100644
--- a/datasketches/src/thetafamily/common/hash_table.rs
+++ b/datasketches/src/thetafamily/common/hash_table.rs
@@ -230,6 +230,7 @@ where
}
/// Returns a reference to the entry stored for `hash`, or `None` if the
hash is not retained.
+ #[inline]
pub fn entry(&self, hash: u64) -> Option<&E> {
if hash == 0 {
return None;
@@ -350,6 +351,7 @@ where
self.entries.capacity() * size_of::<Option<E>>()
}
+ #[inline]
fn find_in_curr_entries(&self, key: u64) -> Option<usize> {
Self::find_in_entries(&self.entries, key, self.lg_cur_size)
}
diff --git a/datasketches/src/thetafamily/common/jaccard_similarity.rs
b/datasketches/src/thetafamily/common/jaccard_similarity.rs
index ec67ba0..6c37bec 100644
--- a/datasketches/src/thetafamily/common/jaccard_similarity.rs
+++ b/datasketches/src/thetafamily/common/jaccard_similarity.rs
@@ -27,6 +27,7 @@ use crate::thetacommon::binomial_bounds;
use crate::thetacommon::constants::MAX_LG_K;
use crate::thetacommon::constants::MAX_THETA;
use crate::thetacommon::constants::MIN_LG_K;
+use crate::thetacommon::hash_table::SketchHashTable;
use crate::thetacommon::intersection::IntersectionMergePolicy;
use crate::thetacommon::intersection::IntersectionState;
use crate::thetacommon::sketch_state::CompactSketchState;
@@ -142,6 +143,11 @@ where
fn hashes(self) -> impl Iterator<Item = u64> {
self.0.hashes()
}
+
+ #[inline]
+ fn hash_table(&self) -> Option<&SketchHashTable<impl SketchEntry>> {
+ self.0.hash_table()
+ }
}
impl<S> EntrySketch for KeyEntries<S>
diff --git a/datasketches/src/thetafamily/common/mod.rs
b/datasketches/src/thetafamily/common/mod.rs
index e1a9ae8..12d5d91 100644
--- a/datasketches/src/thetafamily/common/mod.rs
+++ b/datasketches/src/thetafamily/common/mod.rs
@@ -49,6 +49,9 @@ pub(super) trait KeySketch: Copy {
fn metadata(self) -> sketch_state::ThetaFamilySketchMetadata;
fn hashes(self) -> impl Iterator<Item = u64>;
+
+ /// Returns the backing hash table when this sketch stores entries in one.
+ fn hash_table(&self) -> Option<&hash_table::SketchHashTable<impl
SketchEntry>>;
}
pub(super) trait EntrySketch: KeySketch {
diff --git a/datasketches/src/thetafamily/theta/sketch.rs
b/datasketches/src/thetafamily/theta/sketch.rs
index 82197df..26918ac 100644
--- a/datasketches/src/thetafamily/theta/sketch.rs
+++ b/datasketches/src/thetafamily/theta/sketch.rs
@@ -43,6 +43,7 @@ use crate::theta::serialization::V2_PREAMBLE_ESTIMATE;
use crate::theta::serialization::V2_PREAMBLE_PRECISE;
use crate::thetacommon::EntrySketch;
use crate::thetacommon::KeySketch;
+use crate::thetacommon::SketchEntry;
use crate::thetacommon::binomial_bounds;
use crate::thetacommon::constants::DEFAULT_LG_K;
use crate::thetacommon::constants::FLAGS_IS_COMPACT;
@@ -50,6 +51,7 @@ use crate::thetacommon::constants::FLAGS_IS_EMPTY;
use crate::thetacommon::constants::FLAGS_IS_ORDERED;
use crate::thetacommon::constants::FLAGS_IS_READ_ONLY;
use crate::thetacommon::constants::MAX_THETA;
+use crate::thetacommon::hash_table::SketchHashTable;
use crate::thetacommon::hash_table::SketchHashTableIter;
use crate::thetacommon::sketch_state::CompactSketchState;
use crate::thetacommon::sketch_state::ThetaFamilySketchMetadata;
@@ -175,6 +177,14 @@ impl KeySketch for ThetaSketchView<'_> {
fn hashes(self) -> impl Iterator<Item = u64> {
self.iter().map(|entry| entry.hash())
}
+
+ #[inline]
+ fn hash_table(&self) -> Option<&SketchHashTable<impl SketchEntry>> {
+ match self.0 {
+ ThetaSketchViewState::Mutable(sketch) => Some(&sketch.table),
+ ThetaSketchViewState::Compact(_) => None,
+ }
+ }
}
impl EntrySketch for ThetaSketchView<'_> {
diff --git a/datasketches/src/thetafamily/tuple/sketch.rs
b/datasketches/src/thetafamily/tuple/sketch.rs
index 0cd368b..e62e269 100644
--- a/datasketches/src/thetafamily/tuple/sketch.rs
+++ b/datasketches/src/thetafamily/tuple/sketch.rs
@@ -38,11 +38,13 @@ use crate::hash::check_seed_hash;
use crate::hash::compute_seed_hash;
use crate::thetacommon::EntrySketch;
use crate::thetacommon::KeySketch;
+use crate::thetacommon::SketchEntry;
use crate::thetacommon::binomial_bounds;
use crate::thetacommon::constants::DEFAULT_LG_K;
use crate::thetacommon::constants::FLAGS_IS_EMPTY;
use crate::thetacommon::constants::FLAGS_IS_ORDERED;
use crate::thetacommon::constants::MAX_THETA;
+use crate::thetacommon::hash_table::SketchHashTable;
use crate::thetacommon::hash_table::SketchHashTableIter;
use crate::thetacommon::sketch_state::CompactSketchState;
use crate::thetacommon::sketch_state::ThetaFamilySketchMetadata;
@@ -205,6 +207,14 @@ impl<S> KeySketch for TupleSketchView<'_, S> {
fn hashes(self) -> impl Iterator<Item = u64> {
self.iter().map(TupleEntry::hash)
}
+
+ #[inline]
+ fn hash_table(&self) -> Option<&SketchHashTable<impl SketchEntry>> {
+ match self.0 {
+ TupleSketchViewState::Mutable { table, .. } => Some(table),
+ TupleSketchViewState::Compact(_) => None,
+ }
+ }
}
impl<'a, S> EntrySketch for TupleSketchView<'a, S>
diff --git a/tests-integration/tests/theta_test/a_not_b.rs
b/tests-integration/tests/theta_test/a_not_b.rs
index ff8e64c..c4734b8 100644
--- a/tests-integration/tests/theta_test/a_not_b.rs
+++ b/tests-integration/tests/theta_test/a_not_b.rs
@@ -219,6 +219,23 @@ fn test_estimation_lower_theta_b_unordered() {
assert_that!(r.estimate(), near(5000.0, 5000.0 * 0.03));
}
+#[test]
+fn test_estimation_lower_theta_a_mutable_b() {
+ let a = sketch_with_range(0, 25000);
+ let b = sketch_with_range(5000, 10000);
+ assert_that!(a.theta64(), lt(b.theta64()));
+
+ let a_not_b = ThetaANotB::default();
+ let from_mutable_b = a_not_b.compute(&a, &b, true).unwrap();
+ let from_compact_b = a_not_b.compute(&a, &b.compact(false), true).unwrap();
+
+ assert_eq!(from_mutable_b.theta64(), a.theta64());
+ let mutable_hashes: Vec<u64> = from_mutable_b.iter().map(|entry|
entry.hash()).collect();
+ let compact_hashes: Vec<u64> = from_compact_b.iter().map(|entry|
entry.hash()).collect();
+ assert_eq!(mutable_hashes, compact_hashes);
+ assert_that!(from_mutable_b.estimate(), near(15000.0, 15000.0 * 0.03));
+}
+
#[test]
fn test_estimation_lower_theta_b_ordered() {
let a = sketch_with_range(0, 10000);
@@ -263,3 +280,28 @@ fn test_estimation_disjoint_returns_a() {
assert!(r.is_estimation_mode());
assert_that!(r.estimate(), near(10000.0, 10000.0 * 0.02));
}
+
+fn unordered_sketch_with_hashes(hashes: &[u64]) -> CompactThetaSketch {
+ let mut bytes = sketch_with_range(0, hashes.len() as u64)
+ .compact(false)
+ .serialize();
+ let offset = bytes.len() - hashes.len() * 8;
+ for (slot, hash) in bytes[offset..].chunks_exact_mut(8).zip(hashes) {
+ slot.copy_from_slice(&hash.to_le_bytes());
+ }
+ CompactThetaSketch::deserialize(&bytes).unwrap()
+}
+
+#[test]
+fn test_unordered_hashes_sharing_low_bits() {
+ let hash = |k: u64| (k << 32) | 0x5A5A_5A5A;
+ let a: Vec<u64> = (1..=3000).map(hash).collect();
+ let b: Vec<u64> = (1001..=4000).map(hash).collect();
+ let a = unordered_sketch_with_hashes(&a);
+ let b = unordered_sketch_with_hashes(&b);
+ assert!(!a.is_ordered() && !b.is_ordered());
+
+ let r = ThetaANotB::default().compute(&a, &b, true).unwrap();
+ let retained: Vec<u64> = r.iter().map(|entry| entry.hash()).collect();
+ assert_eq!(retained, (1..=1000).map(hash).collect::<Vec<_>>());
+}
diff --git a/tests-integration/tests/tuple_test/a_not_b.rs
b/tests-integration/tests/tuple_test/a_not_b.rs
index 60bd308..d1e648b 100644
--- a/tests-integration/tests/tuple_test/a_not_b.rs
+++ b/tests-integration/tests/tuple_test/a_not_b.rs
@@ -15,10 +15,16 @@
// specific language governing permissions and limitations
// under the License.
+use std::cell::Cell;
+use std::ops::AddAssign;
+use std::rc::Rc;
+
use datasketches::common::NumStdDev;
use datasketches::error::ErrorKind;
use datasketches::tuple::CompactTupleSketch;
+use datasketches::tuple::DefaultUpdatePolicy;
use datasketches::tuple::TupleANotB;
+use datasketches::tuple::TupleSketchBuilder;
use googletest::assert_that;
use googletest::prelude::all;
use googletest::prelude::ge;
@@ -171,6 +177,71 @@ fn
empty_b_preserves_logically_non_empty_a_without_retained_entries() {
assert_eq!(result.theta64(), a.theta64());
}
+#[test]
+fn non_empty_b_without_retained_entries_screens_ordered_a_with_early_stop() {
+ #[derive(Default)]
+ struct CountingSummary {
+ value: u64,
+ clones: Option<Rc<Cell<usize>>>,
+ }
+
+ impl Clone for CountingSummary {
+ fn clone(&self) -> Self {
+ if let Some(clones) = &self.clones {
+ clones.set(clones.get() + 1);
+ }
+ Self {
+ value: self.value,
+ clones: self.clones.clone(),
+ }
+ }
+ }
+
+ impl AddAssign<(u64, Rc<Cell<usize>>)> for CountingSummary {
+ fn add_assign(&mut self, (value, clones): (u64, Rc<Cell<usize>>)) {
+ self.value += value;
+ self.clones = Some(clones);
+ }
+ }
+
+ let clones = Rc::new(Cell::new(0));
+ let mut a =
TupleSketchBuilder::new(DefaultUpdatePolicy::<CountingSummary>::default())
+ .build()
+ .unwrap();
+ for key in 0..1000u64 {
+ a.update(key, (1u64, Rc::clone(&clones)));
+ }
+ let a_ordered = a.compact(true);
+ clones.set(0);
+
+ let screened_value = (0u64..)
+ .find(|candidate| {
+ let mut sketch = default_tuple_sketch_builder()
+ .sampling_probability(0.1)
+ .build()
+ .unwrap();
+ sketch.update(*candidate, 1u64);
+ !sketch.is_empty() && sketch.num_retained() == 0
+ })
+ .expect("failed to find a value screened out by the sampling theta");
+
+ let mut b = default_tuple_sketch_builder()
+ .sampling_probability(0.1)
+ .build()
+ .unwrap();
+ b.update(screened_value, 1u64);
+ assert!(!b.is_empty() && b.num_retained() == 0);
+
+ let result = TupleANotB::default().compute(&a_ordered, &b, true).unwrap();
+
+ assert_eq!(result.theta64(), b.theta64());
+ assert!(result.iter().all(|entry| entry.hash() < b.theta64()));
+ // Ordered A stops at the first entry at or above theta, cloning at most
one boundary entry
+ // beyond the surviving prefix rather than all 1000 summaries.
+ assert!(clones.get() <= result.num_retained() + 1);
+ assert!(result.num_retained() + 1 < a_ordered.num_retained());
+}
+
#[test]
fn estimation_bounds_cover_the_true_difference() {
let mut a = default_tuple_sketch_builder().lg_k(8).build().unwrap();
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]