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 86eb143 perf(frequencies): skip key comparisons when rehashing (#331)
86eb143 is described below
commit 86eb143601ddbf12a332beddaeab9fbea73127ac
Author: Song Bian <[email protected]>
AuthorDate: Fri Nov 6 22:59:34 2026 -0800
perf(frequencies): skip key comparisons when rehashing (#331)
Co-authored-by: Claude Sonnet 5.5 <[email protected]>
Co-authored-by: tison <[email protected]>
---
CHANGELOG.md | 1 +
.../src/frequencies/reverse_purge_item_hash_map.rs | 20 +++-
tests-integration/tests/frequencies_test/main.rs | 1 +
tests-integration/tests/frequencies_test/rehash.rs | 111 +++++++++++++++++++++
tests-integration/tests/serde_tests/frequencies.rs | 17 ++++
5 files changed, 149 insertions(+), 1 deletion(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 7d7158f..545914c 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -12,6 +12,7 @@ All significant changes to this project will be documented in
this file.
### Improvements
+* `FrequentItemsSketch` updates are faster for streams of distinct items while
the map is growing.
* `HllUnion` is faster when adopting HLL8 inputs without downsampling or
merging multiple dense inputs before querying or serializing the result.
* `KllSketch::rank` is faster for repeated queries on compacted sketches.
* Repeated scalar `TDigest::rank` queries are faster, including small digests
and data with repeated values.
diff --git a/datasketches/src/frequencies/reverse_purge_item_hash_map.rs
b/datasketches/src/frequencies/reverse_purge_item_hash_map.rs
index 7f430f6..bb5ebff 100644
--- a/datasketches/src/frequencies/reverse_purge_item_hash_map.rs
+++ b/datasketches/src/frequencies/reverse_purge_item_hash_map.rs
@@ -171,12 +171,30 @@ impl<T: Eq + Hash> ReversePurgeItemHashMap<T> {
for i in 0..old_keys.len() {
if old_states[i] > 0 {
if let Some(key) = old_keys[i].take() {
- self.adjust_or_put_value(key, old_values[i]);
+ self.insert_absent(key, old_values[i]);
}
}
}
}
+ /// Inserts a key that is known to be absent, such as when rehashing
distinct keys.
+ ///
+ /// This probes the same slots as [`Self::adjust_or_put_value`] but skips
key comparisons.
+ fn insert_absent(&mut self, key: T, value: u64) {
+ let mask = self.keys.len() - 1;
+ let mut probe = (hash_item(&key) as usize) & mask;
+ let mut drift: usize = 1;
+ while self.states[probe] > 0 {
+ probe = (probe + 1) & mask;
+ drift += 1;
+ debug_assert!(drift < DRIFT_LIMIT, "drift limit exceeded");
+ }
+ self.keys[probe] = Some(key);
+ self.values[probe] = value;
+ self.states[probe] = drift as u16;
+ self.num_active += 1;
+ }
+
/// Returns the length of the underlying arrays.
pub fn len(&self) -> usize {
self.keys.len()
diff --git a/tests-integration/tests/frequencies_test/main.rs
b/tests-integration/tests/frequencies_test/main.rs
index 1dea33b..6181db4 100644
--- a/tests-integration/tests/frequencies_test/main.rs
+++ b/tests-integration/tests/frequencies_test/main.rs
@@ -15,4 +15,5 @@
// specific language governing permissions and limitations
// under the License.
+mod rehash;
mod update;
diff --git a/tests-integration/tests/frequencies_test/rehash.rs
b/tests-integration/tests/frequencies_test/rehash.rs
new file mode 100644
index 0000000..e166c55
--- /dev/null
+++ b/tests-integration/tests/frequencies_test/rehash.rs
@@ -0,0 +1,111 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! Growing the item map must keep every item with its exact weight.
+
+use std::hash::Hash;
+use std::hash::Hasher;
+
+use datasketches::frequencies::FrequentItemsSketch;
+
+fn weight(i: u64) -> u64 {
+ i % 5 + 1
+}
+
+// Stay below the purge threshold and check all counts at each growth boundary.
+fn check_growth<T: Eq + Hash>(max_map_size: usize, distinct: u64, item: impl
Fn(u64) -> T) {
+ let mut sketch = FrequentItemsSketch::new(max_map_size).unwrap();
+ let initial_capacity = sketch.current_map_capacity();
+ let mut total_weight = 0;
+ for i in 0..distinct {
+ let capacity = sketch.current_map_capacity();
+ sketch.update_with_count(item(i), weight(i));
+ total_weight += weight(i);
+ if sketch.current_map_capacity() != capacity || i + 1 == distinct {
+ assert_eq!(sketch.total_weight(), total_weight);
+ assert_eq!(sketch.num_active_items() as u64, i + 1);
+ assert_eq!(sketch.maximum_error(), 0);
+ for j in 0..=i {
+ assert_eq!(sketch.estimate(&item(j)), weight(j), "item {j}
after {i}");
+ }
+ }
+ }
+ assert!(sketch.current_map_capacity() > initial_capacity);
+}
+
+#[test]
+fn test_longs_growth_keeps_every_item() {
+ check_growth(1 << 12, 2_000, |i| (i * 7_919 + 13) as i64);
+}
+
+#[test]
+fn test_items_growth_keeps_every_item() {
+ check_growth(1 << 12, 2_000, |i| format!("item-{i}"));
+}
+
+#[derive(Debug, PartialEq, Eq)]
+struct CollidingItem(u64);
+
+impl Hash for CollidingItem {
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ 0u64.hash(state);
+ }
+}
+
+#[test]
+fn test_colliding_items_survive_growth_updates_and_purge() {
+ let mut sketch = FrequentItemsSketch::new(64).unwrap();
+ for i in 0..48 {
+ sketch.update_with_count(CollidingItem(i), if i % 4 == 0 { 100 } else
{ 1 });
+ }
+ assert_eq!(sketch.current_map_capacity(), sketch.maximum_map_capacity());
+ assert_eq!(sketch.maximum_error(), 0);
+ for i in 0..48 {
+ assert_eq!(
+ sketch.estimate(&CollidingItem(i)),
+ if i % 4 == 0 { 100 } else { 1 }
+ );
+ }
+
+ for i in (0..48).step_by(4) {
+ sketch.update_with_count(CollidingItem(i), 7);
+ }
+ assert_eq!(sketch.num_active_items(), 48);
+ assert_eq!(sketch.maximum_error(), 0);
+
+ // The new key triggers a purge with median 1. Deleting light items from
+ // the collision chain must preserve access to every displaced heavy item.
+ sketch.update(CollidingItem(48));
+ assert_eq!(sketch.maximum_error(), 1);
+ assert_eq!(sketch.num_active_items(), 12);
+ for i in 0..49 {
+ if i < 48 && i % 4 == 0 {
+ assert_eq!(sketch.estimate(&CollidingItem(i)), 107);
+ assert_eq!(sketch.lower_bound(&CollidingItem(i)), 106);
+ } else {
+ assert_eq!(sketch.estimate(&CollidingItem(i)), 0);
+ assert_eq!(sketch.upper_bound(&CollidingItem(i)), 1);
+ }
+ }
+
+ sketch.update_with_count(CollidingItem(44), 3);
+ sketch.update_with_count(CollidingItem(1), 5);
+ assert_eq!(sketch.estimate(&CollidingItem(44)), 110);
+ assert_eq!(sketch.estimate(&CollidingItem(1)), 6);
+ assert_eq!(sketch.num_active_items(), 13);
+ assert_eq!(sketch.total_weight(), 12 * 107 + 37 + 3 + 5);
+}
diff --git a/tests-integration/tests/serde_tests/frequencies.rs
b/tests-integration/tests/serde_tests/frequencies.rs
index 9c1df36..dd301cc 100644
--- a/tests-integration/tests/serde_tests/frequencies.rs
+++ b/tests-integration/tests/serde_tests/frequencies.rs
@@ -64,6 +64,23 @@ fn test_longs_round_trip() {
assert_eq!(restored.maximum_error(), sketch.maximum_error());
}
+#[test]
+fn test_growth_survives_serialization() {
+ let mut sketch = FrequentItemsSketch::<i64>::new(1 << 12).unwrap();
+ for i in 0..2_000 {
+ sketch.update_with_count(i * 7_919 + 13, (i % 5 + 1) as u64);
+ }
+ let bytes = sketch.serialize();
+ let restored = FrequentItemsSketch::<i64>::deserialize(&bytes).unwrap();
+ assert_eq!(restored.serialize(), bytes);
+ assert_eq!(restored.total_weight(), sketch.total_weight());
+ assert_eq!(restored.num_active_items(), 2_000);
+ assert_eq!(restored.maximum_error(), 0);
+ for i in 0..2_000 {
+ assert_eq!(restored.estimate(&(i * 7_919 + 13)), (i % 5 + 1) as u64);
+ }
+}
+
#[test]
fn test_items_round_trip() {
let mut sketch = FrequentItemsSketch::new(32).unwrap();
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]