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 5011658  perf(bloom): division-free bit indexes and inline u64 hashing 
(#330)
5011658 is described below

commit 501165830a28378cf4592bb9341556b8d6d89ec3
Author: Song Bian <[email protected]>
AuthorDate: Sat Nov 14 05:00:48 2026 -0800

    perf(bloom): division-free bit indexes and inline u64 hashing (#330)
    
    Co-authored-by: Claude Sonnet 5.5 <[email protected]>
    Co-authored-by: Patrick McGleenon <[email protected]>
    Co-authored-by: tison <[email protected]>
---
 CHANGELOG.md                     |   2 +-
 datasketches/src/bloom/sketch.rs | 222 +++++++++++++++++++++++++++++++++------
 datasketches/src/hash/xxhash.rs  | 100 ++++++++++++++++++
 3 files changed, 288 insertions(+), 36 deletions(-)

diff --git a/CHANGELOG.md b/CHANGELOG.md
index b4839ae..0dafb20 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -24,7 +24,7 @@ All significant changes to this project will be documented in 
this file.
 
 ### Performance improvements
 
-* Speed up `BloomFilter::insert` when adding new items to filters configured 
with multiple hash functions; single-hash, repeated-item, and saturated-filter 
workloads see smaller gains.
+* Speed up `BloomFilter::contains`, `BloomFilter::insert`, and 
`BloomFilter::contains_and_insert` across filter saturation levels, 
particularly for primitive and scalar-wrapped integer inputs and multi-hash 
configurations; longer byte-slice inputs on CPUs with fast hardware dividers 
see smaller gains.
 * Reduce `FrequentItemsSketch` update cost on streams of distinct items while 
growing toward `max_map_size`, particularly for keys such as strings or byte 
slices whose comparisons cost more than integers; updates once at capacity are 
unchanged.
 * Speed up `HllUnion::update` when adopting a high-cardinality `HllType::Hll8` 
sketch within `lg_max_k` or merging multiple high-cardinality sketches before 
querying or serializing the union; workloads that query after every merge are 
roughly unchanged.
 * Speed up `KllSketch::rank` in estimation mode while keeping exact-mode query 
latency unchanged.
diff --git a/datasketches/src/bloom/sketch.rs b/datasketches/src/bloom/sketch.rs
index b1ec95c..59b644b 100644
--- a/datasketches/src/bloom/sketch.rs
+++ b/datasketches/src/bloom/sketch.rs
@@ -51,6 +51,8 @@ pub struct BloomFilter {
     num_bits_set: u64,
     /// Bit array packed into u64 words
     bit_array: Box<[u64]>,
+    /// Reduces shifted hashes modulo the bit capacity; derived from 
`bit_array`.
+    reducer: CapacityReducer,
 }
 
 impl BloomFilter {
@@ -72,6 +74,7 @@ impl BloomFilter {
     /// assert!(filter.contains("apple")); // true - possibly present (and 
known to be inserted here)
     /// assert!(!filter.contains("grape")); // false - definitely not present
     /// ```
+    #[inline]
     pub fn contains<T: Hash>(&self, item: T) -> bool {
         if self.is_empty() {
             return false;
@@ -100,23 +103,30 @@ impl BloomFilter {
     /// let was_present = filter.contains_and_insert("apple");
     /// assert!(was_present); // Now it's in the set
     /// ```
+    #[inline]
     pub fn contains_and_insert<T: Hash>(&mut self, item: T) -> bool {
         let (h0, h1) = self.compute_hash(item);
-        let mut were_all_set = true;
-        for i in 1..=self.num_hashes {
-            let bit_index = self.compute_bit_index(h0, h1, i);
+        let num_hashes = self.num_hashes;
+        let reducer = self.reducer;
+        let bit_array = &mut *self.bit_array;
+        let mut bits_added = 0;
+        for i in 1..=num_hashes {
+            let bit_index = reducer.bit_index(h0, h1, i);
             let word_index = bit_index >> 6;
             let bit_offset = bit_index & 63;
             let mask = 1u64 << bit_offset;
-            let word = &mut self.bit_array[word_index];
+            let word = &mut bit_array[word_index];
 
             if (*word & mask) == 0 {
                 *word |= mask;
-                self.num_bits_set += 1;
-                were_all_set = false;
+                bits_added += 1;
             }
         }
-        were_all_set
+        if bits_added != 0 {
+            self.num_bits_set += bits_added;
+            return false;
+        }
+        true
     }
 
     /// Inserts an item into the filter.
@@ -138,19 +148,25 @@ impl BloomFilter {
     ///
     /// assert!(filter.contains("apple"));
     /// ```
+    #[inline]
     pub fn insert<T: Hash>(&mut self, item: T) {
         let (h0, h1) = self.compute_hash(item);
-        for i in 1..=self.num_hashes {
-            let bit_index = self.compute_bit_index(h0, h1, i);
+        let num_hashes = self.num_hashes;
+        let reducer = self.reducer;
+        let bit_array = &mut *self.bit_array;
+        let mut bits_added = 0;
+        for i in 1..=num_hashes {
+            let bit_index = reducer.bit_index(h0, h1, i);
             let word_index = bit_index >> 6;
             let bit_offset = bit_index & 63;
             let mask = 1u64 << bit_offset;
-            let word = &mut self.bit_array[word_index];
+            let word = &mut bit_array[word_index];
             let was_set = (*word & mask) != 0;
 
             *word |= mask;
-            self.num_bits_set += u64::from(!was_set);
+            bits_added += u64::from(!was_set);
         }
+        self.num_bits_set += bits_added;
     }
 
     /// Resets the filter to its initial empty state.
@@ -340,6 +356,7 @@ impl BloomFilter {
     ///
     /// This is the case when no items were inserted, after 
[`reset()`](Self::reset), or when a
     /// set operation cleared every bit.
+    #[inline]
     pub fn is_empty(&self) -> bool {
         self.num_bits_set == 0
     }
@@ -590,6 +607,7 @@ impl BloomFilter {
             seed,
             num_hashes,
             num_bits_set,
+            reducer: CapacityReducer::new(bit_array.len() as u64 * 64),
             bit_array,
         })
     }
@@ -599,6 +617,7 @@ impl BloomFilter {
     /// Uses a two-hash approach:
     /// * h0 = XXHash64(item, seed)
     /// * h1 = XXHash64(item, h0)
+    #[inline]
     fn compute_hash<T: Hash>(&self, item: T) -> (u64, u64) {
         // First hash with the configured seed
         let mut hasher = XxHash64::with_seed(self.seed);
@@ -614,37 +633,23 @@ impl BloomFilter {
     }
 
     /// Checks if all k bits are set for the given hash values.
+    #[inline]
     fn check_bits(&self, h0: u64, h1: u64) -> bool {
-        for i in 1..=self.num_hashes {
-            let bit_index = self.compute_bit_index(h0, h1, i);
-            if !self.get_bit(bit_index) {
+        let num_hashes = self.num_hashes;
+        let reducer = self.reducer;
+        let bit_array = &*self.bit_array;
+        for i in 1..=num_hashes {
+            let bit_index = reducer.bit_index(h0, h1, i);
+            let word_index = bit_index >> 6;
+            let bit_offset = bit_index & 63;
+            let mask = 1u64 << bit_offset;
+            if (bit_array[word_index] & mask) == 0 {
                 return false;
             }
         }
         true
     }
 
-    /// Computes a bit index using double hashing (Kirsch-Mitzenmacher).
-    ///
-    /// Formula:
-    /// ```text
-    /// hash_index = ((h0 + i * h1) >> 1) % capacity_bits
-    /// ```
-    ///
-    /// The right shift by 1 improves bit-distribution. The index `i` is 
1-based.
-    fn compute_bit_index(&self, h0: u64, h1: u64, i: u16) -> usize {
-        let hash = h0.wrapping_add(u64::from(i).wrapping_mul(h1)) as usize;
-        (hash >> 1) % self.capacity()
-    }
-
-    /// Gets the value of a single bit.
-    fn get_bit(&self, bit_index: usize) -> bool {
-        let word_index = bit_index >> 6; // Equivalent to bit_index / 64
-        let bit_offset = bit_index & 63; // Equivalent to bit_index % 64
-        let mask = 1u64 << bit_offset;
-        (self.bit_array[word_index] & mask) != 0
-    }
-
     /// Returns an estimate of the filter's memory usage in bytes.
     pub fn estimated_size(&self) -> usize {
         self.bit_array.len() * size_of::<u64>()
@@ -663,6 +668,51 @@ impl fmt::Debug for BloomFilter {
     }
 }
 
+/// Reduces shifted hashes (below `2^63`) modulo the bit capacity without a 
hardware division.
+#[derive(Clone, Copy, PartialEq)]
+struct CapacityReducer {
+    capacity: u64,
+    /// `ceil(2^(63 + l) / capacity)` with `l = ceil(log2(capacity))`.
+    multiplier: u64,
+    /// `l - 1`.
+    shift: u32,
+}
+
+impl CapacityReducer {
+    /// `capacity` is a positive multiple of 64.
+    fn new(capacity: u64) -> Self {
+        // `capacity > 2^(l - 1)`, so the multiplier is below `2^64`.
+        let l = 64 - (capacity - 1).leading_zeros();
+        let multiplier = (1u128 << (63 + l)).div_ceil(u128::from(capacity)) as 
u64;
+        Self {
+            capacity,
+            multiplier,
+            shift: l - 1,
+        }
+    }
+
+    /// Computes a bit index using double hashing (Kirsch-Mitzenmacher):
+    /// `((h0 + i * h1) >> 1) % capacity`, where `i` is 1-based.
+    #[inline]
+    fn bit_index(self, h0: u64, h1: u64, i: u16) -> usize {
+        // The conversion to `usize` truncates the hash on 32-bit targets. 
Filters serialized
+        // there depend on it, so it is part of the bit layout.
+        let hash = h0.wrapping_add(u64::from(i).wrapping_mul(h1)) as usize;
+        self.remainder((hash >> 1) as u64) as usize
+    }
+
+    /// Returns `hash % capacity` for every `hash < 2^63`, using division by 
an invariant integer
+    /// (Granlund and Montgomery, 1994): `hash / capacity == (multiplier * 
hash) >> (63 + l)`,
+    /// which is one high multiply and one shift.
+    #[inline]
+    fn remainder(self, hash: u64) -> u64 {
+        debug_assert!(hash < 1 << 63);
+        let quotient =
+            ((u128::from(hash) * u128::from(self.multiplier)) >> 64) as u64 >> 
self.shift;
+        hash - quotient * self.capacity
+    }
+}
+
 /// Builder for creating [`BloomFilter`] instances.
 ///
 /// Provides two construction modes:
@@ -854,7 +904,109 @@ impl BloomFilterBuilder {
             seed: self.seed,
             num_hashes,
             num_bits_set: 0,
+            reducer: CapacityReducer::new(bit_array.len() as u64 * 64),
             bit_array,
         })
     }
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    /// The cached-multiplier reduction must equal the `%` operator it 
replaces for every hash.
+    #[test]
+    fn bit_index_equals_remainder_of_shifted_hash() {
+        let mut hashes = vec![
+            0,
+            1,
+            2,
+            63,
+            64,
+            65,
+            u64::MAX,
+            u64::MAX - 1,
+            1 << 63,
+            (1 << 63) - 1,
+            0x9e37_79b9_7f4a_7c15,
+        ];
+        let mut state = 0x2545_f491_4f6c_dd1d_u64;
+        for _ in 0..200 {
+            state ^= state << 13;
+            state ^= state >> 7;
+            state ^= state << 17;
+            hashes.push(state);
+        }
+
+        for num_bits in [
+            1, 64, 65, 127, 1_000, 4_096, 4_097, 95_851, 131_072, 3_000_017,
+        ] {
+            let filter = BloomFilterBuilder::with_size(num_bits, 
1).build().unwrap();
+            let capacity = filter.capacity();
+            for &h0 in &hashes {
+                for &h1 in &hashes {
+                    for i in [1, 2, 3, 7, 64, 1_000, u16::MAX] {
+                        let hash = 
h0.wrapping_add(u64::from(i).wrapping_mul(h1)) as usize;
+                        assert_eq!(
+                            filter.reducer.bit_index(h0, h1, i),
+                            (hash >> 1) % capacity,
+                            "capacity {capacity}, h0 {h0}, h1 {h1}, i {i}"
+                        );
+                    }
+                }
+            }
+        }
+    }
+
+    /// The reducer must equal `%` for every shifted hash (below `2^63`) and 
every supported
+    /// capacity, including capacities too large to allocate here.
+    #[test]
+    fn capacity_reducer_equals_remainder_for_supported_capacities() {
+        let max = BloomFilterBuilder::MAX_NUM_BITS;
+        let capacities = [
+            64,
+            128,
+            192,
+            4_096,
+            4_160,
+            95_872,
+            131_072,
+            3_000_064,
+            1 << 36,
+            (1 << 36) + 64,
+            (1 << 37) - 64,
+            max - 64,
+            max,
+        ];
+        let mut state = 0x2545_f491_4f6c_dd1d_u64;
+        for capacity in capacities {
+            assert_eq!(capacity % 64, 0);
+            let reducer = CapacityReducer::new(capacity);
+            let max_quotient = ((1u64 << 63) - 1) / capacity;
+            let mut hashes = vec![
+                0,
+                1,
+                capacity - 1,
+                capacity,
+                capacity + 1,
+                max_quotient * capacity - 1,
+                max_quotient * capacity,
+                (1 << 63) - capacity,
+                (1 << 63) - 1,
+            ];
+            for _ in 0..10_000 {
+                state ^= state << 13;
+                state ^= state >> 7;
+                state ^= state << 17;
+                hashes.push(state >> 1);
+            }
+            for hash in hashes {
+                assert_eq!(
+                    reducer.remainder(hash),
+                    hash % capacity,
+                    "capacity {capacity}, hash {hash}"
+                );
+            }
+        }
+    }
+}
diff --git a/datasketches/src/hash/xxhash.rs b/datasketches/src/hash/xxhash.rs
index 1ea5503..76116ce 100644
--- a/datasketches/src/hash/xxhash.rs
+++ b/datasketches/src/hash/xxhash.rs
@@ -144,7 +144,62 @@ impl Hasher for XxHash64 {
     #[inline(always)]
     fn write(&mut self, bytes: &[u8]) {
         self.total_len = self.total_len.wrapping_add(bytes.len() as u64);
+        self.write_bytes(bytes);
+    }
+
+    #[inline(always)]
+    fn write_u8(&mut self, i: u8) {
+        self.write_fixed(i.to_ne_bytes());
+    }
+
+    #[inline(always)]
+    fn write_u16(&mut self, i: u16) {
+        self.write_fixed(i.to_ne_bytes());
+    }
+
+    #[inline(always)]
+    fn write_u32(&mut self, i: u32) {
+        self.write_fixed(i.to_ne_bytes());
+    }
+
+    #[inline(always)]
+    fn write_u64(&mut self, i: u64) {
+        self.write_fixed(i.to_ne_bytes());
+    }
+
+    #[inline(always)]
+    fn write_u128(&mut self, i: u128) {
+        self.write_fixed(i.to_ne_bytes());
+    }
+
+    #[inline(always)]
+    fn write_usize(&mut self, i: usize) {
+        self.write_fixed(i.to_ne_bytes());
+    }
+}
+
+impl XxHash64 {
+    /// Same result as `write(&bytes)`, with an inlined body small enough that 
hashing a
+    /// fixed-width integer folds to register arithmetic at the call site.
+    #[inline(always)]
+    fn write_fixed<const N: usize>(&mut self, bytes: [u8; N]) {
+        debug_assert!(N < 32);
+        self.total_len = self.total_len.wrapping_add(N as u64);
+        if self.buffer_len + N < 32 {
+            self.buffer[self.buffer_len..self.buffer_len + 
N].copy_from_slice(&bytes);
+            self.buffer_len += N;
+        } else {
+            self.write_bytes_outlined(&bytes);
+        }
+    }
 
+    #[inline(never)]
+    fn write_bytes_outlined(&mut self, bytes: &[u8]) {
+        self.write_bytes(bytes);
+    }
+
+    #[inline(always)]
+    fn write_bytes(&mut self, bytes: &[u8]) {
         if self.buffer_len + bytes.len() < 32 {
             self.buffer[self.buffer_len..self.buffer_len + 
bytes.len()].copy_from_slice(bytes);
             self.buffer_len += bytes.len();
@@ -270,4 +325,49 @@ mod tests {
         let hash2 = hasher.finish64();
         assert_eq!(hash2, hash1);
     }
+
+    #[test]
+    fn write_integers_match_write_of_native_bytes() {
+        let input: Vec<u8> = (0..=40).collect();
+
+        macro_rules! check_write {
+            ($method:ident, $values:expr) => {
+                for prefix in 0..=input.len() {
+                    for value in $values {
+                        let mut expected = XxHash64::with_seed(PRIME32);
+                        expected.write(&input[..prefix]);
+                        expected.write(&value.to_ne_bytes());
+                        expected.write(&input[..prefix]);
+
+                        let mut hasher = XxHash64::with_seed(PRIME32);
+                        hasher.write(&input[..prefix]);
+                        hasher.$method(value);
+                        hasher.write(&input[..prefix]);
+
+                        assert_eq!(
+                            hasher.finish64(),
+                            expected.finish64(),
+                            "{} prefix {prefix}, value {value:#x}",
+                            stringify!($method)
+                        );
+                    }
+                }
+            };
+        }
+
+        check_write!(write_u8, [0u8, 1, 0x7f, u8::MAX]);
+        check_write!(write_u16, [0u16, 1, 0x1234, u16::MAX]);
+        check_write!(write_u32, [0u32, 1, 0x0123_4567, u32::MAX]);
+        check_write!(write_u64, [0u64, 1, 0x0123_4567_89ab_cdef, u64::MAX]);
+        check_write!(
+            write_u128,
+            [
+                0u128,
+                1,
+                0x0123_4567_89ab_cdef_fedc_ba98_7654_3210,
+                u128::MAX
+            ]
+        );
+        check_write!(write_usize, [0usize, 1, 0x1234_5678, usize::MAX]);
+    }
 }


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to