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]