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 5011658 perf(bloom): division-free bit indexes and inline u64 hashing
(#330)
5011658 is described below
commit 501165830a28378cf4592bb9341556b8d6d89ec3
Author: Song Bian <[email protected]>
AuthorDate: Sat Nov 14 05:00:48 2026 -0800
perf(bloom): division-free bit indexes and inline u64 hashing (#330)
Co-authored-by: Claude Sonnet 5.5 <[email protected]>
Co-authored-by: Patrick McGleenon <[email protected]>
Co-authored-by: tison <[email protected]>
---
CHANGELOG.md | 2 +-
datasketches/src/bloom/sketch.rs | 222 +++++++++++++++++++++++++++++++++------
datasketches/src/hash/xxhash.rs | 100 ++++++++++++++++++
3 files changed, 288 insertions(+), 36 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index b4839ae..0dafb20 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -24,7 +24,7 @@ All significant changes to this project will be documented in
this file.
### Performance improvements
-* Speed up `BloomFilter::insert` when adding new items to filters configured
with multiple hash functions; single-hash, repeated-item, and saturated-filter
workloads 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.
* 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/datasketches/src/bloom/sketch.rs b/datasketches/src/bloom/sketch.rs
index b1ec95c..59b644b 100644
--- a/datasketches/src/bloom/sketch.rs
+++ b/datasketches/src/bloom/sketch.rs
@@ -51,6 +51,8 @@ pub struct BloomFilter {
num_bits_set: u64,
/// Bit array packed into u64 words
bit_array: Box<[u64]>,
+ /// Reduces shifted hashes modulo the bit capacity; derived from
`bit_array`.
+ reducer: CapacityReducer,
}
impl BloomFilter {
@@ -72,6 +74,7 @@ impl BloomFilter {
/// assert!(filter.contains("apple")); // true - possibly present (and
known to be inserted here)
/// assert!(!filter.contains("grape")); // false - definitely not present
/// ```
+ #[inline]
pub fn contains<T: Hash>(&self, item: T) -> bool {
if self.is_empty() {
return false;
@@ -100,23 +103,30 @@ impl BloomFilter {
/// let was_present = filter.contains_and_insert("apple");
/// assert!(was_present); // Now it's in the set
/// ```
+ #[inline]
pub fn contains_and_insert<T: Hash>(&mut self, item: T) -> bool {
let (h0, h1) = self.compute_hash(item);
- let mut were_all_set = true;
- for i in 1..=self.num_hashes {
- let bit_index = self.compute_bit_index(h0, h1, i);
+ let num_hashes = self.num_hashes;
+ let reducer = self.reducer;
+ let bit_array = &mut *self.bit_array;
+ let mut bits_added = 0;
+ for i in 1..=num_hashes {
+ let bit_index = reducer.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 word = &mut bit_array[word_index];
if (*word & mask) == 0 {
*word |= mask;
- self.num_bits_set += 1;
- were_all_set = false;
+ bits_added += 1;
}
}
- were_all_set
+ if bits_added != 0 {
+ self.num_bits_set += bits_added;
+ return false;
+ }
+ true
}
/// Inserts an item into the filter.
@@ -138,19 +148,25 @@ impl BloomFilter {
///
/// assert!(filter.contains("apple"));
/// ```
+ #[inline]
pub fn insert<T: Hash>(&mut self, item: T) {
let (h0, h1) = self.compute_hash(item);
- for i in 1..=self.num_hashes {
- let bit_index = self.compute_bit_index(h0, h1, i);
+ let num_hashes = self.num_hashes;
+ let reducer = self.reducer;
+ let bit_array = &mut *self.bit_array;
+ let mut bits_added = 0;
+ for i in 1..=num_hashes {
+ let bit_index = reducer.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 word = &mut bit_array[word_index];
let was_set = (*word & mask) != 0;
*word |= mask;
- self.num_bits_set += u64::from(!was_set);
+ bits_added += u64::from(!was_set);
}
+ self.num_bits_set += bits_added;
}
/// Resets the filter to its initial empty state.
@@ -340,6 +356,7 @@ impl BloomFilter {
///
/// This is the case when no items were inserted, after
[`reset()`](Self::reset), or when a
/// set operation cleared every bit.
+ #[inline]
pub fn is_empty(&self) -> bool {
self.num_bits_set == 0
}
@@ -590,6 +607,7 @@ impl BloomFilter {
seed,
num_hashes,
num_bits_set,
+ reducer: CapacityReducer::new(bit_array.len() as u64 * 64),
bit_array,
})
}
@@ -599,6 +617,7 @@ impl BloomFilter {
/// Uses a two-hash approach:
/// * h0 = XXHash64(item, seed)
/// * h1 = XXHash64(item, h0)
+ #[inline]
fn compute_hash<T: Hash>(&self, item: T) -> (u64, u64) {
// First hash with the configured seed
let mut hasher = XxHash64::with_seed(self.seed);
@@ -614,37 +633,23 @@ impl BloomFilter {
}
/// Checks if all k bits are set for the given hash values.
+ #[inline]
fn check_bits(&self, h0: u64, h1: u64) -> bool {
- for i in 1..=self.num_hashes {
- let bit_index = self.compute_bit_index(h0, h1, i);
- if !self.get_bit(bit_index) {
+ let num_hashes = self.num_hashes;
+ let reducer = self.reducer;
+ let bit_array = &*self.bit_array;
+ for i in 1..=num_hashes {
+ let bit_index = reducer.bit_index(h0, h1, i);
+ let word_index = bit_index >> 6;
+ let bit_offset = bit_index & 63;
+ let mask = 1u64 << bit_offset;
+ if (bit_array[word_index] & mask) == 0 {
return false;
}
}
true
}
- /// Computes a bit index using double hashing (Kirsch-Mitzenmacher).
- ///
- /// Formula:
- /// ```text
- /// hash_index = ((h0 + i * h1) >> 1) % capacity_bits
- /// ```
- ///
- /// The right shift by 1 improves bit-distribution. The index `i` is
1-based.
- fn compute_bit_index(&self, h0: u64, h1: u64, i: u16) -> usize {
- let hash = h0.wrapping_add(u64::from(i).wrapping_mul(h1)) as usize;
- (hash >> 1) % self.capacity()
- }
-
- /// Gets the value of a single bit.
- fn get_bit(&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;
- (self.bit_array[word_index] & mask) != 0
- }
-
/// Returns an estimate of the filter's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
self.bit_array.len() * size_of::<u64>()
@@ -663,6 +668,51 @@ impl fmt::Debug for BloomFilter {
}
}
+/// Reduces shifted hashes (below `2^63`) modulo the bit capacity without a
hardware division.
+#[derive(Clone, Copy, PartialEq)]
+struct CapacityReducer {
+ capacity: u64,
+ /// `ceil(2^(63 + l) / capacity)` with `l = ceil(log2(capacity))`.
+ multiplier: u64,
+ /// `l - 1`.
+ shift: u32,
+}
+
+impl CapacityReducer {
+ /// `capacity` is a positive multiple of 64.
+ fn new(capacity: u64) -> Self {
+ // `capacity > 2^(l - 1)`, so the multiplier is below `2^64`.
+ let l = 64 - (capacity - 1).leading_zeros();
+ let multiplier = (1u128 << (63 + l)).div_ceil(u128::from(capacity)) as
u64;
+ Self {
+ capacity,
+ multiplier,
+ shift: l - 1,
+ }
+ }
+
+ /// Computes a bit index using double hashing (Kirsch-Mitzenmacher):
+ /// `((h0 + i * h1) >> 1) % capacity`, where `i` is 1-based.
+ #[inline]
+ fn bit_index(self, h0: u64, h1: u64, i: u16) -> usize {
+ // The conversion to `usize` truncates the hash on 32-bit targets.
Filters serialized
+ // there depend on it, so it is part of the bit layout.
+ let hash = h0.wrapping_add(u64::from(i).wrapping_mul(h1)) as usize;
+ self.remainder((hash >> 1) as u64) as usize
+ }
+
+ /// Returns `hash % capacity` for every `hash < 2^63`, using division by
an invariant integer
+ /// (Granlund and Montgomery, 1994): `hash / capacity == (multiplier *
hash) >> (63 + l)`,
+ /// which is one high multiply and one shift.
+ #[inline]
+ fn remainder(self, hash: u64) -> u64 {
+ debug_assert!(hash < 1 << 63);
+ let quotient =
+ ((u128::from(hash) * u128::from(self.multiplier)) >> 64) as u64 >>
self.shift;
+ hash - quotient * self.capacity
+ }
+}
+
/// Builder for creating [`BloomFilter`] instances.
///
/// Provides two construction modes:
@@ -854,7 +904,109 @@ impl BloomFilterBuilder {
seed: self.seed,
num_hashes,
num_bits_set: 0,
+ reducer: CapacityReducer::new(bit_array.len() as u64 * 64),
bit_array,
})
}
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ /// The cached-multiplier reduction must equal the `%` operator it
replaces for every hash.
+ #[test]
+ fn bit_index_equals_remainder_of_shifted_hash() {
+ let mut hashes = vec![
+ 0,
+ 1,
+ 2,
+ 63,
+ 64,
+ 65,
+ u64::MAX,
+ u64::MAX - 1,
+ 1 << 63,
+ (1 << 63) - 1,
+ 0x9e37_79b9_7f4a_7c15,
+ ];
+ let mut state = 0x2545_f491_4f6c_dd1d_u64;
+ for _ in 0..200 {
+ state ^= state << 13;
+ state ^= state >> 7;
+ state ^= state << 17;
+ hashes.push(state);
+ }
+
+ for num_bits in [
+ 1, 64, 65, 127, 1_000, 4_096, 4_097, 95_851, 131_072, 3_000_017,
+ ] {
+ let filter = BloomFilterBuilder::with_size(num_bits,
1).build().unwrap();
+ let capacity = filter.capacity();
+ for &h0 in &hashes {
+ for &h1 in &hashes {
+ for i in [1, 2, 3, 7, 64, 1_000, u16::MAX] {
+ let hash =
h0.wrapping_add(u64::from(i).wrapping_mul(h1)) as usize;
+ assert_eq!(
+ filter.reducer.bit_index(h0, h1, i),
+ (hash >> 1) % capacity,
+ "capacity {capacity}, h0 {h0}, h1 {h1}, i {i}"
+ );
+ }
+ }
+ }
+ }
+ }
+
+ /// The reducer must equal `%` for every shifted hash (below `2^63`) and
every supported
+ /// capacity, including capacities too large to allocate here.
+ #[test]
+ fn capacity_reducer_equals_remainder_for_supported_capacities() {
+ let max = BloomFilterBuilder::MAX_NUM_BITS;
+ let capacities = [
+ 64,
+ 128,
+ 192,
+ 4_096,
+ 4_160,
+ 95_872,
+ 131_072,
+ 3_000_064,
+ 1 << 36,
+ (1 << 36) + 64,
+ (1 << 37) - 64,
+ max - 64,
+ max,
+ ];
+ let mut state = 0x2545_f491_4f6c_dd1d_u64;
+ for capacity in capacities {
+ assert_eq!(capacity % 64, 0);
+ let reducer = CapacityReducer::new(capacity);
+ let max_quotient = ((1u64 << 63) - 1) / capacity;
+ let mut hashes = vec![
+ 0,
+ 1,
+ capacity - 1,
+ capacity,
+ capacity + 1,
+ max_quotient * capacity - 1,
+ max_quotient * capacity,
+ (1 << 63) - capacity,
+ (1 << 63) - 1,
+ ];
+ for _ in 0..10_000 {
+ state ^= state << 13;
+ state ^= state >> 7;
+ state ^= state << 17;
+ hashes.push(state >> 1);
+ }
+ for hash in hashes {
+ assert_eq!(
+ reducer.remainder(hash),
+ hash % capacity,
+ "capacity {capacity}, hash {hash}"
+ );
+ }
+ }
+ }
+}
diff --git a/datasketches/src/hash/xxhash.rs b/datasketches/src/hash/xxhash.rs
index 1ea5503..76116ce 100644
--- a/datasketches/src/hash/xxhash.rs
+++ b/datasketches/src/hash/xxhash.rs
@@ -144,7 +144,62 @@ impl Hasher for XxHash64 {
#[inline(always)]
fn write(&mut self, bytes: &[u8]) {
self.total_len = self.total_len.wrapping_add(bytes.len() as u64);
+ self.write_bytes(bytes);
+ }
+
+ #[inline(always)]
+ fn write_u8(&mut self, i: u8) {
+ self.write_fixed(i.to_ne_bytes());
+ }
+
+ #[inline(always)]
+ fn write_u16(&mut self, i: u16) {
+ self.write_fixed(i.to_ne_bytes());
+ }
+
+ #[inline(always)]
+ fn write_u32(&mut self, i: u32) {
+ self.write_fixed(i.to_ne_bytes());
+ }
+
+ #[inline(always)]
+ fn write_u64(&mut self, i: u64) {
+ self.write_fixed(i.to_ne_bytes());
+ }
+
+ #[inline(always)]
+ fn write_u128(&mut self, i: u128) {
+ self.write_fixed(i.to_ne_bytes());
+ }
+
+ #[inline(always)]
+ fn write_usize(&mut self, i: usize) {
+ self.write_fixed(i.to_ne_bytes());
+ }
+}
+
+impl XxHash64 {
+ /// Same result as `write(&bytes)`, with an inlined body small enough that
hashing a
+ /// fixed-width integer folds to register arithmetic at the call site.
+ #[inline(always)]
+ fn write_fixed<const N: usize>(&mut self, bytes: [u8; N]) {
+ debug_assert!(N < 32);
+ self.total_len = self.total_len.wrapping_add(N as u64);
+ if self.buffer_len + N < 32 {
+ self.buffer[self.buffer_len..self.buffer_len +
N].copy_from_slice(&bytes);
+ self.buffer_len += N;
+ } else {
+ self.write_bytes_outlined(&bytes);
+ }
+ }
+ #[inline(never)]
+ fn write_bytes_outlined(&mut self, bytes: &[u8]) {
+ self.write_bytes(bytes);
+ }
+
+ #[inline(always)]
+ fn write_bytes(&mut self, bytes: &[u8]) {
if self.buffer_len + bytes.len() < 32 {
self.buffer[self.buffer_len..self.buffer_len +
bytes.len()].copy_from_slice(bytes);
self.buffer_len += bytes.len();
@@ -270,4 +325,49 @@ mod tests {
let hash2 = hasher.finish64();
assert_eq!(hash2, hash1);
}
+
+ #[test]
+ fn write_integers_match_write_of_native_bytes() {
+ let input: Vec<u8> = (0..=40).collect();
+
+ macro_rules! check_write {
+ ($method:ident, $values:expr) => {
+ for prefix in 0..=input.len() {
+ for value in $values {
+ let mut expected = XxHash64::with_seed(PRIME32);
+ expected.write(&input[..prefix]);
+ expected.write(&value.to_ne_bytes());
+ expected.write(&input[..prefix]);
+
+ let mut hasher = XxHash64::with_seed(PRIME32);
+ hasher.write(&input[..prefix]);
+ hasher.$method(value);
+ hasher.write(&input[..prefix]);
+
+ assert_eq!(
+ hasher.finish64(),
+ expected.finish64(),
+ "{} prefix {prefix}, value {value:#x}",
+ stringify!($method)
+ );
+ }
+ }
+ };
+ }
+
+ check_write!(write_u8, [0u8, 1, 0x7f, u8::MAX]);
+ check_write!(write_u16, [0u16, 1, 0x1234, u16::MAX]);
+ check_write!(write_u32, [0u32, 1, 0x0123_4567, u32::MAX]);
+ check_write!(write_u64, [0u64, 1, 0x0123_4567_89ab_cdef, u64::MAX]);
+ check_write!(
+ write_u128,
+ [
+ 0u128,
+ 1,
+ 0x0123_4567_89ab_cdef_fedc_ba98_7654_3210,
+ u128::MAX
+ ]
+ );
+ check_write!(write_usize, [0usize, 1, 0x1234_5678, usize::MAX]);
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]