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 eee824e  fix(bloom)!: correct accuracy sizing and optimize membership 
updates (#360)
eee824e is described below

commit eee824e282df69c220e8a76084abd0b80ad66370
Author: tison <[email protected]>
AuthorDate: Sun Nov 15 00:49:13 2026 +0800

    fix(bloom)!: correct accuracy sizing and optimize membership updates (#360)
---
 CHANGELOG.md                                 |  3 +-
 benchmarks/bloom/update.rs                   | 33 +++++++++--
 datasketches/src/bloom/filter.rs             | 86 ++++++++++++++++++++--------
 tests-integration/tests/bloom_test/filter.rs | 24 ++++++++
 tests-integration/tests/serde_tests/bloom.rs |  9 ++-
 5 files changed, 126 insertions(+), 29 deletions(-)

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 2635ae1..2c8126c 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -6,6 +6,7 @@ All significant changes to this project will be documented in 
this file.
 
 ### Breaking changes
 
+* `BloomFilterBuilder::with_accuracy` now sizes the filter for its integer 
hash count, correcting false-positive targets that previously produced 
undersized filters. Capacity and hash count can differ from earlier versions; 
to combine with an existing filter, use `with_size(existing.capacity(), 
existing.num_hashes())` and the same seed.
 * `BloomFilter::capacity` now returns `u64` instead of `usize`; update callers 
expecting `usize` to use `u64` or convert explicitly.
 * `BloomFilter::contains` and `BloomFilter::contains_and_insert` now take 
`item: T` (`T: Hash`) by value instead of `&T`, matching `BloomFilter::insert`. 
Pass `&item` to retain owned values such as `String` or `Vec<u8>` without 
cloning, and remove explicit turbofish type arguments (or change `T` to `&T`) 
on borrowed calls such as `contains::<u64>(&value)`.
 * Fix 32-bit (`wasm32`) double hashing in `BloomFilter` to use the full 64-bit 
hash consistently with 64-bit targets, Java, C++, and Go. 64-bit targets and 
serialized formats are unchanged; rebuild or re-ingest filters created on 
32-bit targets instead of mixing them across versions.
@@ -26,7 +27,7 @@ All significant changes to this project will be documented in 
this file.
 
 ### Performance improvements
 
-* 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.
+* 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. For `contains_and_insert`, gains are larger on streams 
containing new keys than on repeated-key streams.
 * 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/benchmarks/bloom/update.rs b/benchmarks/bloom/update.rs
index b6212ae..ec4b450 100644
--- a/benchmarks/bloom/update.rs
+++ b/benchmarks/bloom/update.rs
@@ -51,17 +51,21 @@ fn bytes_32(bencher: Bencher) {
     });
 }
 
-fn contains_and_insert_present_u64(bencher: Bencher) {
+fn contains_and_insert(
+    bencher: Bencher,
+    initial_items: u64,
+    values: impl Iterator<Item = u64> + Clone,
+) {
     let mut populated = BloomFilterBuilder::with_accuracy(ITEMS as u64, 0.01)
         .build()
         .unwrap();
-    for value in 0..ITEMS as u64 {
+    for value in 0..initial_items {
         populated.insert(value);
     }
 
     bencher.bench_local(|| {
         let mut filter = populated.clone();
-        for value in 0..ITEMS as u64 {
+        for value in values.clone() {
             black_box(filter.contains_and_insert(black_box(value)));
         }
         filter
@@ -74,6 +78,27 @@ pub fn register(runner: &mut Runner) {
     runner.case(
         "bloom::update::contains_and_insert_present_u64",
         2_000,
-        contains_and_insert_present_u64,
+        |b| contains_and_insert(b, ITEMS as u64, 0..ITEMS as u64),
+    );
+    runner.case(
+        "bloom::update::contains_and_insert_absent_u64",
+        1_000,
+        |b| contains_and_insert(b, ITEMS as u64, ITEMS as u64..(2 * ITEMS) as 
u64),
     );
+    runner.case("bloom::update::contains_and_insert_mixed_u64", 1_000, |b| {
+        contains_and_insert(
+            b,
+            ITEMS as u64,
+            (0..ITEMS as u64).map(|value| {
+                if value % 2 == 0 {
+                    value
+                } else {
+                    value + ITEMS as u64
+                }
+            }),
+        )
+    });
+    runner.case("bloom::update::contains_and_insert_build_u64", 1_000, |b| {
+        contains_and_insert(b, 0, 0..ITEMS as u64)
+    });
 }
diff --git a/datasketches/src/bloom/filter.rs b/datasketches/src/bloom/filter.rs
index 838cbf4..f5b70c3 100644
--- a/datasketches/src/bloom/filter.rs
+++ b/datasketches/src/bloom/filter.rs
@@ -134,8 +134,20 @@ impl BloomFilterBuilder {
                 }
 
                 let n = max_items as f64;
-                let ln2_squared = std::f64::consts::LN_2 * 
std::f64::consts::LN_2;
-                let bits = (-n * fpp.ln() / ln2_squared).ceil();
+                let log_fpp = fpp.ln();
+
+                // Kirsch and Mitzenmacher (2008), Section 2: 
https://doi.org/10.1002/rsa.20208
+                // For n items, m bits and k independent hash probes, a bit 
stays unset with
+                // probability (1 - 1/m)^(k*n) ≈ exp(-k*n/m), so p ≈ (1 - 
exp(-k*n/m))^k.
+                // At the continuous optimum half the bits are set: p = 2^-k, 
or k = -ln(p)/ln(2).
+                // Since fpp >= 2^-1074 for positive f64, k <= 1074 < 
MAX_NUM_HASHES.
+                let num_hashes = (-log_fpp / 
std::f64::consts::LN_2).ceil().max(1.0) as u16;
+                let k = f64::from(num_hashes);
+
+                // With integer k fixed, solve for m = -k*n / ln(1 - p^(1/k)).
+                let bit_set_probability = (log_fpp / k).exp();
+                let log_unset_probability = (-bit_set_probability).ln_1p();
+                let bits = (-k * n / log_unset_probability).ceil();
                 if bits > MAX_NUM_BITS as f64 {
                     return Err(Error::invalid_argument(format!(
                         "target accuracy requires {bits:.0} bits, but at most 
{MAX_NUM_BITS} are supported"
@@ -143,10 +155,6 @@ impl BloomFilterBuilder {
                 }
 
                 let num_bits = (bits as u64).max(MIN_NUM_BITS);
-                let num_hashes = (num_bits as f64 / n * std::f64::consts::LN_2)
-                    .ceil()
-                    .clamp(f64::from(MIN_NUM_HASHES), 
f64::from(MAX_NUM_HASHES))
-                    as u16;
                 (num_bits, num_hashes)
             }
             SizingMode::Size {
@@ -511,14 +519,11 @@ impl BitArray {
 
     fn from_words(bits_used: u64, words: Box<[u64]>) -> Self {
         let capacity = (words.len() as u64) << 6;
-        // `capacity` is a positive multiple of 64, so `2^(l - 1) < capacity 
<= 2^l`
-        // and `ceil(2^(63 + l) / capacity)` fits in `u64`.
-        let l = 64 - (capacity - 1).leading_zeros();
-        let multiplier = (1_u128 << (63 + l)).div_ceil(u128::from(capacity)) 
as u64;
+        let (multiplier, shift) = reduction_parameters(capacity);
         Self {
             bits_used,
             multiplier,
-            shift: l - 1,
+            shift,
             words,
         }
     }
@@ -561,24 +566,22 @@ impl BitArray {
     }
 
     #[inline(always)]
-    fn contains_and_insert(&mut self, h0: u64, h1: u64, num_hashes: u16) -> 
bool {
+    fn contains_and_insert(&mut self, mut h0: u64, h1: u64, num_hashes: u16) 
-> bool {
         let capacity = self.capacity();
         let multiplier = self.multiplier;
         let shift = self.shift;
         let words = &mut *self.words;
-        let mut bits_added = 0_u64;
-        for i in 1..=num_hashes {
-            let (word_index, mask) = probe_slot(h0, h1, i, capacity, 
multiplier, shift);
-            let word = &mut words[word_index];
-            if (*word & mask) == 0 {
-                *word |= mask;
-                bits_added += 1;
+        for i in 0..num_hashes {
+            let (word_index, mask) = probe_slot(h0, h1, 1, capacity, 
multiplier, shift);
+            h0 = h0.wrapping_add(h1);
+            if (words[word_index] & mask) == 0 {
+                words[word_index] |= mask;
+                self.bits_used += 1;
+                // Continue after the first missing probe using the branchless 
insertion loop.
+                self.insert(h0, h1, num_hashes - i - 1);
+                return false;
             }
         }
-        if bits_added != 0 {
-            self.bits_used += bits_added;
-            return false;
-        }
         true
     }
 
@@ -628,3 +631,40 @@ fn bit_index(shifted: u64, capacity: u64, multiplier: u64, 
shift: u32) -> u64 {
     let quotient = ((u128::from(shifted) * u128::from(multiplier)) >> 64) as 
u64 >> shift;
     shifted - quotient * capacity
 }
+
+fn reduction_parameters(capacity: u64) -> (u64, u32) {
+    // `capacity` is a positive multiple of 64, so `2^(l - 1) < capacity <= 
2^l`
+    // and `ceil(2^(63 + l) / capacity)` fits in `u64`.
+    let l = 64 - (capacity - 1).leading_zeros();
+    let multiplier = (1_u128 << (63 + l)).div_ceil(u128::from(capacity)) as 
u64;
+    (multiplier, l - 1)
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn bit_indexes_match_remainder_at_boundaries() {
+        for capacity in [64, 192, 95_872, (1 << 36) + 64, MAX_NUM_BITS] {
+            let (multiplier, shift) = reduction_parameters(capacity);
+            let max_hash = (1_u64 << 63) - 1;
+            let last_multiple = max_hash - max_hash % capacity;
+            for hash in [
+                0,
+                capacity - 1,
+                capacity,
+                capacity + 1,
+                last_multiple - 1,
+                last_multiple,
+                max_hash,
+            ] {
+                assert_eq!(
+                    bit_index(hash, capacity, multiplier, shift),
+                    hash % capacity,
+                    "capacity {capacity}, hash {hash}"
+                );
+            }
+        }
+    }
+}
diff --git a/tests-integration/tests/bloom_test/filter.rs 
b/tests-integration/tests/bloom_test/filter.rs
index ed7dee5..7a6d614 100644
--- a/tests-integration/tests/bloom_test/filter.rs
+++ b/tests-integration/tests/bloom_test/filter.rs
@@ -367,6 +367,30 @@ fn builder_validation_and_word_rounding() {
     }
 }
 
+#[test]
+fn accuracy_sizing_accounts_for_integer_hash_count() {
+    for fpp in [
+        f64::from_bits(1),
+        0.01,
+        0.1,
+        0.5,
+        0.9,
+        1.0 - f64::EPSILON,
+        1.0,
+    ] {
+        let filter = BloomFilterBuilder::with_accuracy(10_000, fpp)
+            .build()
+            .unwrap();
+        let k = f64::from(filter.num_hashes());
+        let occupancy = -(-k * 10_000.0 / filter.capacity() as f64).exp_m1();
+        let modeled_fpp = occupancy.powi(i32::from(filter.num_hashes()));
+        assert!(
+            modeled_fpp <= fpp * (1.0 + 1e-12),
+            "{filter:?}, target {fpp}"
+        );
+    }
+}
+
 #[test]
 fn serialized_bit_layout_matches_cross_language_vector() {
     let expected = decode_hex(concat!(
diff --git a/tests-integration/tests/serde_tests/bloom.rs 
b/tests-integration/tests/serde_tests/bloom.rs
index 2931e55..e4a4c74 100644
--- a/tests-integration/tests/serde_tests/bloom.rs
+++ b/tests-integration/tests/serde_tests/bloom.rs
@@ -154,7 +154,7 @@ fn test_cached_num_bits_set_is_validated_or_recomputed() {
 }
 
 #[test]
-fn test_invalid_num_longs_are_rejected() {
+fn test_invalid_bit_array_lengths_are_rejected() {
     const NUM_LONGS_OFFSET: usize = 16;
 
     let empty = BloomFilterBuilder::with_accuracy(100, 0.01)
@@ -175,4 +175,11 @@ fn test_invalid_num_longs_are_rejected() {
             );
         }
     }
+
+    let mut truncated = non_empty.serialize();
+    truncated.pop();
+    assert_eq!(
+        BloomFilter::deserialize(&truncated).unwrap_err().kind(),
+        ErrorKind::InvalidData
+    );
 }


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

Reply via email to