This is an automated email from the ASF dual-hosted git repository. tisonkun pushed a commit to branch avoid-clone in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
commit 5a52ba111b59b33b6cf0d08b677c0509864078f9 Author: tison <[email protected]> AuthorDate: Sat Jul 4 02:11:47 2026 +0800 perf: avoid clone on serialize frequency items Signed-off-by: tison <[email protected]> --- .../src/frequencies/reverse_purge_item_hash_map.rs | 30 +++------------ datasketches/src/frequencies/serialization.rs | 2 +- datasketches/src/frequencies/sketch.rs | 45 ++++++++++------------ .../tests/frequencies_serialization_test.rs | 40 +++++++++++++++++++ datasketches/tests/frequencies_update_test.rs | 17 ++++++++ 5 files changed, 84 insertions(+), 50 deletions(-) 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..4b263a6 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; @@ -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]
