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]

Reply via email to