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 bb6bbec perf: streamline sketch update paths (#267)
bb6bbec is described below
commit bb6bbeca5fcb92730c5bd677dd64dfbe5bc0bb1a
Author: tison <[email protected]>
AuthorDate: Wed Sep 2 21:11:25 2026 +0800
perf: streamline sketch update paths (#267)
---
CHANGELOG.md | 1 +
benchmarks/bloom/update.rs | 20 ++++++++++++++++++++
datasketches/src/bloom/sketch.rs | 20 +++++++++++---------
datasketches/src/thetafamily/common/constants.rs | 2 --
datasketches/src/thetafamily/common/hash_table.rs | 11 ++++-------
5 files changed, 36 insertions(+), 18 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 427ec34..e043ec0 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -16,6 +16,7 @@ All significant changes to this project will be documented in
this file.
* Improve truncated-input diagnostics across sketch deserializers.
* Improve hash-backed sketch update performance for integer and raw-byte
inputs.
+* Improve Bloom filter membership-and-insert performance and simplify
Theta-family hash table thresholds.
### Bug fixes
diff --git a/benchmarks/bloom/update.rs b/benchmarks/bloom/update.rs
index 2aa6b81..7227b21 100644
--- a/benchmarks/bloom/update.rs
+++ b/benchmarks/bloom/update.rs
@@ -51,3 +51,23 @@ fn bytes_32(bencher: Bencher) {
black_box(filter)
});
}
+
+#[divan::bench]
+fn contains_and_insert_present_u64(bencher: Bencher) {
+ let mut populated = BloomFilterBuilder::with_accuracy(ITEMS as u64, 0.01)
+ .build()
+ .unwrap();
+ for value in 0..ITEMS as u64 {
+ populated.insert(value);
+ }
+
+ bencher
+ .counter(ItemsCount::new(ITEMS))
+ .with_inputs(|| populated.clone())
+ .bench_local_values(|mut filter| {
+ for value in 0..ITEMS as u64 {
+ black_box(filter.contains_and_insert(black_box(&value)));
+ }
+ filter
+ });
+}
diff --git a/datasketches/src/bloom/sketch.rs b/datasketches/src/bloom/sketch.rs
index 8bf3922..d0d4b6b 100644
--- a/datasketches/src/bloom/sketch.rs
+++ b/datasketches/src/bloom/sketch.rs
@@ -101,9 +101,7 @@ impl BloomFilter {
/// ```
pub fn contains_and_insert<T: Hash>(&mut self, item: &T) -> bool {
let (h0, h1) = self.compute_hash(item);
- let was_present = self.check_bits(h0, h1);
- self.set_bits(h0, h1);
- was_present
+ self.set_bits(h0, h1)
}
/// Inserts an item into the filter.
@@ -564,12 +562,14 @@ impl BloomFilter {
true
}
- /// Sets all k bits for the given hash values.
- fn set_bits(&mut self, h0: u64, h1: u64) {
+ /// 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);
- self.set_bit(bit_index);
+ were_all_set &= self.set_bit(bit_index);
}
+ were_all_set
}
/// Computes a bit index using double hashing (Kirsch-Mitzenmacher).
@@ -593,16 +593,18 @@ impl BloomFilter {
(self.bit_array[word_index] & mask) != 0
}
- /// Sets a single bit and updates the count if it wasn't already set.
- fn set_bit(&mut self, bit_index: usize) {
+ /// 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 (self.bit_array[word_index] & mask) == 0 {
+ if !was_set {
self.bit_array[word_index] |= mask;
self.num_bits_set += 1;
}
+ was_set
}
/// Returns the estimated size of the filter in bytes.
diff --git a/datasketches/src/thetafamily/common/constants.rs
b/datasketches/src/thetafamily/common/constants.rs
index da1480b..8f0ee6e 100644
--- a/datasketches/src/thetafamily/common/constants.rs
+++ b/datasketches/src/thetafamily/common/constants.rs
@@ -27,8 +27,6 @@ pub const MAX_LG_K: u8 = 26;
/// Default log2 of K.
pub const DEFAULT_LG_K: u8 = 12;
-/// Resize threshold (0.5 = 50% load factor).
-pub const HASH_TABLE_RESIZE_THRESHOLD: f64 = 0.5;
/// Rebuild threshold (15/16 = 93.75% load factor).
pub const HASH_TABLE_REBUILD_THRESHOLD: f64 = 15.0 / 16.0;
diff --git a/datasketches/src/thetafamily/common/hash_table.rs
b/datasketches/src/thetafamily/common/hash_table.rs
index a115a2e..5525f74 100644
--- a/datasketches/src/thetafamily/common/hash_table.rs
+++ b/datasketches/src/thetafamily/common/hash_table.rs
@@ -24,8 +24,6 @@ use crate::error::ErrorKind;
use crate::hash::MurmurHash3X64128;
use crate::hash::compute_seed_hash;
use crate::thetacommon::SketchEntry;
-use crate::thetacommon::constants::HASH_TABLE_REBUILD_THRESHOLD;
-use crate::thetacommon::constants::HASH_TABLE_RESIZE_THRESHOLD;
use crate::thetacommon::constants::MAX_LG_K;
use crate::thetacommon::constants::MAX_THETA;
use crate::thetacommon::constants::MIN_LG_K;
@@ -244,12 +242,11 @@ where
/// Return the current resize or rebuild capacity threshold.
pub fn capacity_threshold(&self) -> usize {
- let fraction = if self.lg_cur_size <= self.lg_nom_size {
- HASH_TABLE_RESIZE_THRESHOLD
+ if self.lg_cur_size <= self.lg_nom_size {
+ self.entries.len() / 2
} else {
- HASH_TABLE_REBUILD_THRESHOLD
- };
- (fraction * self.entries.len() as f64) as usize
+ self.entries.len() - self.entries.len() / 16
+ }
}
/// Trim the table to nominal size k.
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
