You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by ti...@apache.org on 2026/09/02 13:05:08 UTC
(datasketches-rust) branch codex/sketch-update-performance created (now 778d859)
This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a change to branch codex/sketch-update-performance
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
at 778d859 perf: streamline sketch update paths
This branch includes the following new commits:
new 778d859 perf: streamline sketch update paths
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
(datasketches-rust) 01/01: perf: streamline sketch update paths
Posted by ti...@apache.org.
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 <wa...@gmail.com>
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: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org