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 db1bca8 perf(bloom): streamline insertion without membership checks
(#306)
db1bca8 is described below
commit db1bca8231f444b2fca0992a0fa68c4d874a953b
Author: Xuanwo <[email protected]>
AuthorDate: Tue Oct 27 14:28:16 2026 +0800
perf(bloom): streamline insertion without membership checks (#306)
---
CHANGELOG.md | 4 ++
datasketches/src/bloom/sketch.rs | 58 +++++++++++---------
tests-integration/tests/bloom_test/sketch.rs | 47 ++++++++++++++--
tests-integration/tests/serde_tests/bloom.rs | 82 +++++-----------------------
4 files changed, 91 insertions(+), 100 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index af0429a..32c8aec 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -4,6 +4,10 @@ All significant changes to this project will be documented in
this file.
## Unreleased
+### Improvements
+
+* `BloomFilter::insert` is faster for streams of new items when multiple
hashes are configured.
+
## v0.6.0
### Breaking changes
diff --git a/datasketches/src/bloom/sketch.rs b/datasketches/src/bloom/sketch.rs
index 245a726..020f7a4 100644
--- a/datasketches/src/bloom/sketch.rs
+++ b/datasketches/src/bloom/sketch.rs
@@ -99,7 +99,21 @@ impl BloomFilter {
/// ```
pub fn contains_and_insert<T: Hash>(&mut self, item: &T) -> bool {
let (h0, h1) = self.compute_hash(item);
- self.set_bits(h0, h1)
+ let mut were_all_set = true;
+ for i in 1..=self.num_hashes {
+ let bit_index = self.compute_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];
+
+ if (*word & mask) == 0 {
+ *word |= mask;
+ self.num_bits_set += 1;
+ were_all_set = false;
+ }
+ }
+ were_all_set
}
/// Inserts an item into the filter.
@@ -122,8 +136,24 @@ impl BloomFilter {
/// assert!(filter.contains(&"apple"));
/// ```
pub fn insert<T: Hash>(&mut self, item: T) {
+ // Reuse the conditional path when skipping writes on repeats is
cheaper.
+ if self.num_hashes == 1 {
+ let _ = self.contains_and_insert(&item);
+ return;
+ }
+
let (h0, h1) = self.compute_hash(&item);
- self.set_bits(h0, h1);
+ for i in 1..=self.num_hashes {
+ let bit_index = self.compute_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 was_set = (*word & mask) != 0;
+
+ *word |= mask;
+ self.num_bits_set += u64::from(!was_set);
+ }
}
/// Resets the filter to its initial empty state.
@@ -594,16 +624,6 @@ impl BloomFilter {
true
}
- /// Sets all k bits and returns whether they were already set.
- fn set_bits(&mut self, h0: u64, h1: u64) -> bool {
- let mut were_all_set = true;
- for i in 1..=self.num_hashes {
- let bit_index = self.compute_bit_index(h0, h1, i);
- were_all_set &= self.set_bit(bit_index);
- }
- were_all_set
- }
-
/// Computes a bit index using double hashing (Kirsch-Mitzenmacher).
///
/// Formula:
@@ -625,20 +645,6 @@ impl BloomFilter {
(self.bit_array[word_index] & mask) != 0
}
- /// Sets a single bit and returns whether it was already set.
- fn set_bit(&mut 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;
- let was_set = (self.bit_array[word_index] & mask) != 0;
-
- if !was_set {
- self.bit_array[word_index] |= mask;
- self.num_bits_set += 1;
- }
- was_set
- }
-
/// Returns an estimate of the filter's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
self.bit_array.len() * size_of::<u64>()
diff --git a/tests-integration/tests/bloom_test/sketch.rs
b/tests-integration/tests/bloom_test/sketch.rs
index 7d2b7df..fe0a0a7 100644
--- a/tests-integration/tests/bloom_test/sketch.rs
+++ b/tests-integration/tests/bloom_test/sketch.rs
@@ -55,6 +55,48 @@ fn test_membership_statistics_and_reset() {
assert!(!filter.contains(&"apple"));
}
+#[test]
+fn test_insert_matches_membership_and_insert() {
+ let mut inserted = filter();
+ let mut checked = inserted.clone();
+
+ for value in 0..128_u64 {
+ let was_present = inserted.contains(&value);
+ assert_eq!(checked.contains_and_insert(&value), was_present);
+ inserted.insert(value);
+ assert!(inserted.contains(&value));
+ assert_eq!(checked, inserted);
+ }
+}
+
+#[test]
+fn test_collisions_and_repeated_inserts_do_not_overcount_bits() {
+ // Cover the single-hash path and force within-item collisions: 65 hashes
cannot
+ // select distinct positions in a 64-bit filter.
+ for num_hashes in [1, 65] {
+ let mut inserted = BloomFilterBuilder::with_size(64, num_hashes)
+ .build()
+ .unwrap();
+ let mut checked = inserted.clone();
+ inserted.insert(42_u64);
+ assert!(!checked.contains_and_insert(&42_u64));
+
+ for filter in [&mut inserted, &mut checked] {
+ let before_repeat = filter.clone();
+ filter.insert(42_u64);
+ assert_eq!(*filter, before_repeat);
+ assert!(filter.contains_and_insert(&42_u64));
+ assert_eq!(*filter, before_repeat);
+
+ // Recount the backing bits independently of either insertion path.
+ assert_eq!(
+ BloomFilter::deserialize(&filter.serialize()).unwrap(),
+ *filter
+ );
+ }
+ }
+}
+
#[test]
fn test_union_and_intersection() {
let mut left = filter();
@@ -209,11 +251,6 @@ fn test_intersection_rejects_incompatible_filters() {
fn test_requested_size_rounds_to_word_boundary() {
let filter = BloomFilterBuilder::with_size(65, 3).build().unwrap();
assert_eq!(filter.capacity(), 128);
-}
-
-#[test]
-fn test_estimated_size() {
- let filter = BloomFilterBuilder::with_size(65, 3).build().unwrap();
assert_eq!(filter.estimated_size(), 16);
}
diff --git a/tests-integration/tests/serde_tests/bloom.rs
b/tests-integration/tests/serde_tests/bloom.rs
index 1416645..a7bd340 100644
--- a/tests-integration/tests/serde_tests/bloom.rs
+++ b/tests-integration/tests/serde_tests/bloom.rs
@@ -29,58 +29,28 @@ fn test_bloom_filter_file(path: PathBuf,
expected_num_items: u64, expected_num_h
let bytes = fs::read(&path).unwrap();
let filter1 = BloomFilter::deserialize(&bytes).unwrap();
- // Verify basic properties
assert_eq!(
filter1.num_hashes(),
expected_num_hashes,
"Wrong num_hashes in {}",
path.display()
);
+ assert_eq!(
+ filter1.is_empty(),
+ expected_num_items == 0,
+ "Wrong empty state in {}",
+ path.display()
+ );
- // Check empty state
- if expected_num_items == 0 {
- assert!(filter1.is_empty(), "Filter should be empty for n=0");
- assert_eq!(
- filter1.bits_used(),
- 0,
- "Empty filter should have 0 bits set"
- );
- } else {
+ // TCK fixtures insert integers 0..n/10. Bound the sample for large
fixtures.
+ for item in 0..(expected_num_items / 10).min(100) {
assert!(
- !filter1.is_empty(),
- "Filter should not be empty for n={}",
- expected_num_items
- );
- assert_that!(filter1.bits_used(), gt(0));
- }
-
- // Verify the items that were inserted (integers 0 to n/10-1)
- // datasketches-cpp code: for (uint64_t i = 0; i < n / 10; ++i)
bf.update(i);
- let num_inserted = expected_num_items / 10;
-
- if num_inserted > 0 {
- // Check a sample of inserted items
- // For large n, we only check a sample to keep tests fast
- let sample_size = std::cmp::min(num_inserted, 100);
- let mut false_negatives = 0;
-
- for i in 0..sample_size {
- if !filter1.contains(&i) {
- false_negatives += 1;
- }
- }
-
- assert_eq!(
- false_negatives,
- 0,
- "Found {} false negatives out of {} items in {}",
- false_negatives,
- sample_size,
+ filter1.contains(&item),
+ "Missing item {item} in {}",
path.display()
);
}
- // Serialize and deserialize again to test round-trip
let serialized_bytes = filter1.serialize();
let filter2 =
BloomFilter::deserialize(&serialized_bytes).unwrap_or_else(|err| {
panic!(
@@ -90,38 +60,12 @@ fn test_bloom_filter_file(path: PathBuf,
expected_num_items: u64, expected_num_h
)
});
- // Check that both filters are functionally equivalent
- assert_eq!(
- filter1.num_hashes(),
- filter2.num_hashes(),
- "num_hashes mismatch after round-trip for {}",
- path.display()
- );
- assert_eq!(
- filter1.capacity(),
- filter2.capacity(),
- "capacity mismatch after round-trip for {}",
- path.display()
- );
assert_eq!(
- filter1.bits_used(),
- filter2.bits_used(),
- "bits_used mismatch after round-trip for {}",
+ filter1,
+ filter2,
+ "Filter changed after round-trip for {}",
path.display()
);
-
- // Verify same items are present after round-trip
- if num_inserted > 0 {
- let sample_size = std::cmp::min(num_inserted, 100);
- for i in 0..sample_size {
- assert_eq!(
- filter1.contains(&i),
- filter2.contains(&i),
- "Item {} presence differs after round-trip",
- i
- );
- }
- }
}
#[test]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
