This is an automated email from the ASF dual-hosted git repository. tisonkun pushed a commit to branch codex/sketch-update-performance in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
commit 778d859b902c7d5ca05101ff00754efe3e609d23 Author: tison <[email protected]> AuthorDate: Wed Sep 2 21:04:44 2026 +0800 perf: streamline sketch update paths --- 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]
