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 e4609c6 perf: avoid clone on serialize frequency items (#144)
e4609c6 is described below
commit e4609c63048138cd26b54b55dbac5c6f12b2fb2d
Author: tison <[email protected]>
AuthorDate: Sun Jul 5 07:39:30 2026 +0800
perf: avoid clone on serialize frequency items (#144)
Signed-off-by: tison <[email protected]>
---
CHANGELOG.md | 1 +
.../src/frequencies/reverse_purge_item_hash_map.rs | 30 +++-----------
datasketches/src/frequencies/serialization.rs | 2 +-
datasketches/src/frequencies/sketch.rs | 47 ++++++++++------------
.../tests/frequencies_serialization_test.rs | 40 ++++++++++++++++++
datasketches/tests/frequencies_update_test.rs | 17 ++++++++
6 files changed, 86 insertions(+), 51 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 5f28eda..e7ada56 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -7,6 +7,7 @@ All significant changes to this project will be documented in
this file.
### New features
* `FrequentItemsSketch` now supports borrowed-key updates via `update_ref` and
`update_with_count_ref`, allowing sketches such as
`FrequentItemsSketch<String>` to update from `&str` without allocating on
existing-key hits. Frequency queries also accept borrowed key forms matching
`Borrow<Q>`.
+* `FrequentItemsSketch` no longer requires item types to implement `Clone` for
core updates, queries, and serialization. Custom `FrequentItemValue`
implementations can now be non-`Clone`; APIs that return or merge owned items
still require `Clone`.
### Bug fixes
diff --git a/datasketches/src/frequencies/reverse_purge_item_hash_map.rs
b/datasketches/src/frequencies/reverse_purge_item_hash_map.rs
index 0e59745..c26f1b5 100644
--- a/datasketches/src/frequencies/reverse_purge_item_hash_map.rs
+++ b/datasketches/src/frequencies/reverse_purge_item_hash_map.rs
@@ -197,37 +197,17 @@ impl<T: Eq + Hash> ReversePurgeItemHashMap<T> {
self.num_active
}
- /// Returns the active keys in the map.
- pub fn active_keys(&self) -> Vec<T>
- where
- T: Clone,
- {
- if self.num_active == 0 {
- return vec![];
- }
- let mut keys = Vec::with_capacity(self.num_active);
+ /// Returns active keys and values in storage order.
+ pub fn active_entries(&self) -> Vec<(&T, u64)> {
+ let mut entries = Vec::with_capacity(self.num_active);
for i in 0..self.keys.len() {
if self.states[i] > 0 {
if let Some(key) = self.keys[i].as_ref() {
- keys.push(key.clone());
+ entries.push((key, self.values[i]));
}
}
}
- keys
- }
-
- /// Returns the active values in the map.
- pub fn active_values(&self) -> Vec<u64> {
- if self.num_active == 0 {
- return vec![];
- }
- let mut values = Vec::with_capacity(self.num_active);
- for i in 0..self.values.len() {
- if self.states[i] > 0 {
- values.push(self.values[i]);
- }
- }
- values
+ entries
}
/// Returns an iterator over active keys and values.
diff --git a/datasketches/src/frequencies/serialization.rs
b/datasketches/src/frequencies/serialization.rs
index ed7a898..f1f8f0c 100644
--- a/datasketches/src/frequencies/serialization.rs
+++ b/datasketches/src/frequencies/serialization.rs
@@ -33,7 +33,7 @@ pub const PREAMBLE_LONGS_NONEMPTY: u8 = 4;
pub const EMPTY_FLAG_MASK: u8 = 5;
/// Trait for serializing and deserializing frequent item values.
-pub trait FrequentItemValue: Sized + Eq + Hash + Clone {
+pub trait FrequentItemValue: Sized + Eq + Hash {
/// Returns the size in bytes required to serialize the given item.
fn serialize_size(item: &Self) -> usize;
/// Serializes the item into the given byte buffer.
diff --git a/datasketches/src/frequencies/sketch.rs
b/datasketches/src/frequencies/sketch.rs
index cf9f06d..49dce3b 100644
--- a/datasketches/src/frequencies/sketch.rs
+++ b/datasketches/src/frequencies/sketch.rs
@@ -34,8 +34,8 @@ use crate::frequencies::serialization::PREAMBLE_LONGS_EMPTY;
use crate::frequencies::serialization::PREAMBLE_LONGS_NONEMPTY;
use crate::frequencies::serialization::SERIAL_VERSION;
-type CountSerializeSize<T> = fn(&[T]) -> usize;
-type SerializeItems<T> = fn(&mut SketchBytes, &[T]);
+type CountSerializeSize<T> = fn(&T) -> usize;
+type SerializeItem<T> = fn(&mut SketchBytes, &T);
type DeserializeItems<T> = fn(SketchSlice<'_>, usize) -> Result<Vec<T>, Error>;
const LG_MIN_MAP_SIZE: u8 = 3;
@@ -352,7 +352,7 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
}
let merged_total = self.stream_weight + other.stream_weight;
for (item, count) in other.hash_map.iter() {
- self.update_with_count(item.clone(), count);
+ self.update_with_count_ref(item, count);
}
self.offset += other.offset;
self.stream_weight = merged_total;
@@ -472,11 +472,8 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
fn serialize_inner(
&self,
count_serialize_size: CountSerializeSize<T>,
- serialize_items: SerializeItems<T>,
- ) -> Vec<u8>
- where
- T: Clone, // for self.hash_map.active_keys()
- {
+ serialize_item: SerializeItem<T>,
+ ) -> Vec<u8> {
if self.is_empty() {
let mut bytes = SketchBytes::with_capacity(PREAMBLE_LONGS_EMPTY as
usize * 8);
bytes.write_u8(PREAMBLE_LONGS_EMPTY);
@@ -490,12 +487,17 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
}
let active_items = self.num_active_items();
- let values = self.hash_map.active_values();
- let keys = self.hash_map.active_keys();
- let total_bytes =
- PREAMBLE_LONGS_NONEMPTY as usize * 8 + (active_items * 8) +
count_serialize_size(&keys);
-
- let mut bytes = SketchBytes::with_capacity(total_bytes);
+ let active_entries = self.hash_map.active_entries();
+
+ let mut bytes = SketchBytes::with_capacity({
+ let mut total_bytes = 0;
+ total_bytes += PREAMBLE_LONGS_NONEMPTY as usize * 8;
+ total_bytes += active_items * 8;
+ for (k, _) in &active_entries {
+ total_bytes += count_serialize_size(k);
+ }
+ total_bytes
+ });
bytes.write_u8(PREAMBLE_LONGS_NONEMPTY);
bytes.write_u8(SERIAL_VERSION);
bytes.write_u8(Family::FREQUENCY.id);
@@ -509,10 +511,12 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
bytes.write_u64_le(self.stream_weight);
bytes.write_u64_le(self.offset);
- for value in values {
- bytes.write_u64_le(value);
+ for (_, v) in &active_entries {
+ bytes.write_u64_le(*v);
+ }
+ for (k, _) in &active_entries {
+ serialize_item(&mut bytes, k);
}
- serialize_items(&mut bytes, &keys);
bytes.into_bytes()
}
@@ -618,14 +622,7 @@ impl<T: FrequentItemValue> FrequentItemsSketch<T> {
/// assert!(decoded.estimate(&apple) >= 2);
/// ```
pub fn serialize(&self) -> Vec<u8> {
- self.serialize_inner(
- |items| items.iter().map(T::serialize_size).sum(),
- |bytes, items| {
- for item in items {
- item.serialize_value(bytes);
- }
- },
- )
+ self.serialize_inner(T::serialize_size, |bytes, item|
item.serialize_value(bytes))
}
/// Deserializes a sketch from bytes.
diff --git a/datasketches/tests/frequencies_serialization_test.rs
b/datasketches/tests/frequencies_serialization_test.rs
index f070e91..4c0944e 100644
--- a/datasketches/tests/frequencies_serialization_test.rs
+++ b/datasketches/tests/frequencies_serialization_test.rs
@@ -22,9 +22,35 @@ mod common;
use std::fs;
use common::serialization_test_data;
+use datasketches::codec::SketchBytes;
+use datasketches::codec::SketchSlice;
+use datasketches::error::Error;
use datasketches::error::ErrorKind;
+use datasketches::frequencies::FrequentItemValue;
use datasketches::frequencies::FrequentItemsSketch;
+#[derive(Debug, PartialEq, Eq, Hash)]
+struct NonCloneSerializableItem(i64);
+
+impl FrequentItemValue for NonCloneSerializableItem {
+ fn serialize_size(_item: &Self) -> usize {
+ size_of::<i64>()
+ }
+
+ fn serialize_value(&self, bytes: &mut SketchBytes) {
+ bytes.write_i64_le(self.0);
+ }
+
+ fn deserialize_value(cursor: &mut SketchSlice<'_>) -> Result<Self, Error> {
+ cursor.read_i64_le().map(Self).map_err(|_| {
+ Error::new(
+ ErrorKind::InvalidData,
+ "failed to read non-clone item bytes",
+ )
+ })
+ }
+}
+
#[test]
fn test_longs_round_trip() {
let mut sketch: FrequentItemsSketch<i64> = FrequentItemsSketch::new(32);
@@ -52,6 +78,20 @@ fn test_items_round_trip() {
assert_eq!(restored.maximum_error(), sketch.maximum_error());
}
+#[test]
+fn test_non_clone_item_round_trip() {
+ let mut sketch = FrequentItemsSketch::<NonCloneSerializableItem>::new(32);
+ sketch.update_with_count(NonCloneSerializableItem(1), 2);
+ sketch.update_with_count(NonCloneSerializableItem(2), 5);
+
+ let bytes = sketch.serialize();
+ let restored =
FrequentItemsSketch::<NonCloneSerializableItem>::deserialize(&bytes).unwrap();
+
+ assert_eq!(restored.total_weight(), sketch.total_weight());
+ assert_eq!(restored.estimate(&NonCloneSerializableItem(1)), 2);
+ assert_eq!(restored.estimate(&NonCloneSerializableItem(2)), 5);
+}
+
#[test]
fn test_empty_round_trip() {
let sketch = FrequentItemsSketch::<i64>::new(32);
diff --git a/datasketches/tests/frequencies_update_test.rs
b/datasketches/tests/frequencies_update_test.rs
index 87c702a..792fa9d 100644
--- a/datasketches/tests/frequencies_update_test.rs
+++ b/datasketches/tests/frequencies_update_test.rs
@@ -23,6 +23,23 @@ use datasketches::frequencies::FrequentItemsSketch;
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct TestItem(i32);
+#[derive(Debug, PartialEq, Eq, Hash)]
+struct NonCloneItem(i32);
+
+#[test]
+fn test_non_clone_items_update_and_query() {
+ let mut sketch = FrequentItemsSketch::<NonCloneItem>::new(8);
+
+ sketch.update(NonCloneItem(7));
+ sketch.update_with_count(NonCloneItem(11), 3);
+
+ assert_eq!(sketch.total_weight(), 4);
+ assert_eq!(sketch.num_active_items(), 2);
+ assert_eq!(sketch.estimate(&NonCloneItem(7)), 1);
+ assert_eq!(sketch.lower_bound(&NonCloneItem(11)), 3);
+ assert_eq!(sketch.upper_bound(&NonCloneItem(11)), 3);
+}
+
#[test]
fn test_longs_update_with_zero_count_is_noop() {
let mut sketch: FrequentItemsSketch<i64> = FrequentItemsSketch::new(8);
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
