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 e7d151e refactor(req): use usize for in-memory counts and fix merge
compaction (#354)
e7d151e is described below
commit e7d151e0925ca64410875194ae21fbfdcdb409c9
Author: tison <[email protected]>
AuthorDate: Thu Nov 12 22:16:11 2026 +0800
refactor(req): use usize for in-memory counts and fix merge compaction
(#354)
---
CHANGELOG.md | 3 ++
datasketches/src/req/compactor.rs | 46 ++++++++++++++++--------------
datasketches/src/req/mod.rs | 4 +--
datasketches/src/req/serialization.rs | 7 +++--
datasketches/src/req/sketch.rs | 28 +++++++++---------
tests-integration/tests/req_test/core.rs | 2 +-
tests-integration/tests/req_test/merge.rs | 29 +++++++++++++++++++
tests-integration/tests/serde_tests/req.rs | 24 +++++++++++++---
8 files changed, 99 insertions(+), 44 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 2c05111..b4839ae 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -11,6 +11,7 @@ All significant changes to this project will be documented in
this file.
* `CpcSketch::max_serialized_bytes` and `ReqSketch::serialized_size_bytes` are
removed; serialize the sketch and inspect `len()` on the returned byte buffer
when the encoded size is needed.
* `ThetaJaccardSimilarity::compute` and `TupleJaccardSimilarity::compute` now
return `datasketches::common::JaccardSimilarity` instead of
`datasketches::thetacommon::JaccardSimilarity`, and `datasketches::thetacommon`
is no longer part of the public API.
* `FrequentItemsSketch::update_with_count` and
`FrequentItemsSketch::update_with_count_ref` are renamed to
`update_with_weight` and `update_with_weight_ref` to match weighted update
naming across the crate.
+* `ReqSketch::num_retained` now returns `usize` instead of `u32`, matching
`KllSketch`, `ThetaSketch`, and `TupleSketch`.
### New features
@@ -35,6 +36,8 @@ All significant changes to this project will be documented in
this file.
### Bug fixes
+* `ReqSketch::merge` now cascades compaction across newly grown levels when a
merged sketch overflows the top compactor's nominal capacity.
+* `ReqSketch::deserialize` now returns `InvalidData` for out-of-range or
non-finite compactor `section_size_raw` values instead of overflowing
section-size rounding.
* `ThetaJaccardSimilarity` and `TupleJaccardSimilarity` now return
`InvalidArgument` instead of `InvalidData` when a non-empty input sketch's seed
hash does not match the configured seed.
## v0.6.0 (2026-10-29)
diff --git a/datasketches/src/req/compactor.rs
b/datasketches/src/req/compactor.rs
index c6f6461..d2f8c92 100644
--- a/datasketches/src/req/compactor.rs
+++ b/datasketches/src/req/compactor.rs
@@ -19,6 +19,9 @@
//!
//! Each level compacts a selected range, retaining one item from each pair at
twice the weight.
+use crate::codec::SketchBytes;
+use crate::codec::SketchSlice;
+use crate::codec::assert::insufficient_data;
use crate::common::random::random_bit;
use crate::error::Error;
use crate::req::INITIAL_SECTIONS_PER_COMPACTOR;
@@ -38,7 +41,7 @@ pub struct Compactor<T> {
/// Determines which sections are compacted and when their count doubles.
state: u64,
scratch_buffer: Vec<T>,
- section_size: u32,
+ section_size: usize,
num_sections: u8,
lg_weight: u8,
rank_accuracy: RankAccuracy,
@@ -57,7 +60,7 @@ where
let section_size = nearest_even_section_size(section_size_raw);
let num_sections = INITIAL_SECTIONS_PER_COMPACTOR;
- let nominal: usize = (2 * section_size * num_sections as u32) as usize;
+ let nominal = 2 * section_size * usize::from(num_sections);
Self {
items: Vec::with_capacity(nominal),
@@ -76,13 +79,13 @@ where
}
/// Returns the number of items currently in this compactor.
- pub fn num_items(&self) -> u32 {
- self.items.len() as u32
+ pub fn num_items(&self) -> usize {
+ self.items.len()
}
/// Returns the nominal capacity of this compactor.
- pub fn nominal_capacity(&self) -> u32 {
- 2 * self.section_size * self.num_sections as u32
+ pub fn nominal_capacity(&self) -> usize {
+ 2 * self.section_size * usize::from(self.num_sections)
}
/// Returns whether the items are currently sorted.
@@ -253,7 +256,7 @@ where
let section_size_raw = self.section_size_raw /
std::f32::consts::SQRT_2;
let section_size = nearest_even_section_size(section_size_raw);
- if self.state >= threshold && section_size >= u32::from(MIN_K) {
+ if self.state >= threshold && section_size >= usize::from(MIN_K) {
self.section_size_raw = section_size_raw;
self.section_size = section_size;
self.num_sections = num_sections;
@@ -264,9 +267,9 @@ where
#[inline(always)]
fn compute_compaction_range(&self, secs_to_compact: u8) -> (usize, usize) {
- let nom_capacity = self.nominal_capacity() as usize;
- let mut non_compact = nom_capacity / 2
- + (self.num_sections - secs_to_compact) as usize *
self.section_size as usize;
+ let nom_capacity = self.nominal_capacity();
+ let mut non_compact =
+ nom_capacity / 2 + usize::from(self.num_sections -
secs_to_compact) * self.section_size;
// Preserve an extra item when needed to make the compacted range even.
if self.items.len() >= non_compact && ((self.items.len() -
non_compact) & 1) == 1 {
@@ -283,16 +286,18 @@ where
}
/// Serialize this compactor (preamble + items) into the byte buffer.
- pub fn serialize_into(&self, bytes: &mut crate::codec::SketchBytes)
+ pub fn serialize_into(&self, bytes: &mut SketchBytes)
where
T: ReqValue,
{
+ let num_items =
+ u32::try_from(self.num_items()).expect("REQ compactor item count
exceeds u32::MAX");
bytes.write_u64_le(self.state);
bytes.write_f32_le(self.section_size_raw);
bytes.write_u8(self.lg_weight);
bytes.write_u8(self.num_sections);
bytes.write_u16_le(0); // padding
- bytes.write_u32_le(self.num_items());
+ bytes.write_u32_le(num_items);
for item in self.iter() {
item.serialize_value(bytes);
}
@@ -300,7 +305,7 @@ where
/// Deserialize a compactor (preamble + items) from the byte cursor.
pub fn deserialize(
- cursor: &mut crate::codec::SketchSlice<'_>,
+ cursor: &mut SketchSlice<'_>,
k: u16,
expected_lg_weight: u8,
rank_accuracy: RankAccuracy,
@@ -309,7 +314,6 @@ where
where
T: ReqValue,
{
- use crate::codec::assert::insufficient_data;
let state = cursor
.read_u64_le()
.map_err(insufficient_data("compactor.state"))?;
@@ -325,9 +329,12 @@ where
let _padding = cursor
.read_u16_le()
.map_err(insufficient_data("compactor.padding"))?;
- let num_items = cursor
- .read_u32_le()
- .map_err(insufficient_data("compactor.num_items"))?;
+ let num_items = usize::try_from(
+ cursor
+ .read_u32_le()
+ .map_err(insufficient_data("compactor.num_items"))?,
+ )
+ .map_err(|_| Error::deserial("REQ compactor item count overflows
usize"))?;
validate_compactor_state(
k,
@@ -342,7 +349,7 @@ where
// a multi-gigabyte reservation before the per-item reads below fail.
The buffer
// holds at most `remaining` more items (each item is ≥ 1 byte), so
cap the
// pre-allocation there; `push` still grows the Vec as the validated
data needs.
- let capacity = (num_items as usize).min(cursor.remaining().len());
+ let capacity = num_items.min(cursor.remaining().len());
let mut items = Vec::with_capacity(capacity);
for _ in 0..num_items {
items.push(T::deserialize_value(cursor)?);
@@ -476,9 +483,6 @@ mod tests {
#[test]
fn compactor_serialization_round_trip() {
- use crate::codec::SketchBytes;
- use crate::codec::SketchSlice;
-
let mut c: Compactor<ReqFloat<f32>> = Compactor::new(0, 12,
RankAccuracy::HighRank);
for i in 0..30 {
c.append(ReqFloat::<f32>::new(i as f32).unwrap());
diff --git a/datasketches/src/req/mod.rs b/datasketches/src/req/mod.rs
index 91bc2ba..ff0ed71 100644
--- a/datasketches/src/req/mod.rs
+++ b/datasketches/src/req/mod.rs
@@ -83,6 +83,6 @@ pub enum RankAccuracy {
/// determine its capacity and compaction range; the count doubles as its
state grows.
const INITIAL_SECTIONS_PER_COMPACTOR: u8 = 3;
-fn nearest_even_section_size(value: f32) -> u32 {
- ((value / 2.0).round() as u32) << 1
+fn nearest_even_section_size(value: f32) -> usize {
+ ((value / 2.0).round() as usize) << 1
}
diff --git a/datasketches/src/req/serialization.rs
b/datasketches/src/req/serialization.rs
index c4d1f23..bdc0cb4 100644
--- a/datasketches/src/req/serialization.rs
+++ b/datasketches/src/req/serialization.rs
@@ -72,9 +72,10 @@ pub fn validate_compactor_state(
"REQ compactor lg_weight {lg_weight} does not match level
{expected_lg_weight}"
)));
}
- let section_size = nearest_even_section_size(section_size_raw);
- if !section_size_raw.is_finite()
- || !(u32::from(MIN_K)..=u32::from(k)).contains(§ion_size)
+ let max_raw = f32::from(k) + 2.0;
+ if !(0.0..=max_raw).contains(§ion_size_raw)
+ || !(usize::from(MIN_K)..=usize::from(k))
+ .contains(&nearest_even_section_size(section_size_raw))
|| !has_reachable_section_count(state, num_sections)
{
return Err(Error::deserial(format!(
diff --git a/datasketches/src/req/sketch.rs b/datasketches/src/req/sketch.rs
index abc240e..b9b4c09 100644
--- a/datasketches/src/req/sketch.rs
+++ b/datasketches/src/req/sketch.rs
@@ -54,8 +54,8 @@ pub struct ReqSketch<T> {
k: u16,
rank_accuracy: RankAccuracy,
n: u64,
- max_nom_size: u32,
- num_retained: u32,
+ max_nom_size: usize,
+ num_retained: usize,
compactors: Vec<Compactor<T>>,
promotion_buf: Vec<T>,
min_item: Option<T>,
@@ -136,7 +136,7 @@ where
}
/// Returns the number of items currently stored across all compactors.
- pub fn num_retained(&self) -> u32 {
+ pub fn num_retained(&self) -> usize {
self.num_retained
}
@@ -324,7 +324,7 @@ where
/// queries at ranks strictly between `0.0` and `1.0`, or repeated
[`Self::pmf`]/[`Self::cdf`]
/// queries.
pub fn sorted_view(&self) -> SortedView<T> {
- let mut weighted_items = Vec::with_capacity(self.num_retained as
usize);
+ let mut weighted_items = Vec::with_capacity(self.num_retained);
for compactor in &self.compactors {
let weight = compactor.weight();
for item in compactor.iter() {
@@ -738,7 +738,8 @@ where
if num_levels == 1 {
// Recover n / min / max from level 0 (these aren't in the
preamble for exact mode).
let level0 = &compactors[0];
- n = level0.num_items() as u64;
+ n = u64::try_from(level0.num_items())
+ .map_err(|_| Error::deserial("REQ level 0 item count overflows
u64"))?;
let mut iter = level0.iter();
if let Some(first) = iter.next() {
let mut mn = first.clone();
@@ -782,14 +783,13 @@ where
let (retained_count, nominal_capacity, weighted_count) = compactors
.iter()
.try_fold(
- (0u32, 0u32, 0u64),
+ (0usize, 0usize, 0u64),
|(retained, capacity, weighted), compactor| {
+ let level_items =
u64::try_from(compactor.num_items()).ok()?;
Some((
retained.checked_add(compactor.num_items())?,
capacity.checked_add(compactor.nominal_capacity())?,
- weighted.checked_add(
- (compactor.num_items() as
u64).checked_mul(compactor.weight())?,
- )?,
+
weighted.checked_add(level_items.checked_mul(compactor.weight())?)?,
))
},
)
@@ -822,7 +822,7 @@ where
max_nom_size: 0,
num_retained: 0,
compactors: vec![],
- promotion_buf: Vec::with_capacity(k as usize),
+ promotion_buf: Vec::with_capacity(usize::from(k)),
min_item: None,
max_item: None,
};
@@ -840,7 +840,8 @@ where
}
fn compress(&mut self) {
- for h in 0..self.compactors.len() {
+ let mut h = 0;
+ while h < self.compactors.len() {
if self.compactors[h].num_items() >=
self.compactors[h].nominal_capacity() {
if h + 1 >= self.compactors.len() {
self.grow();
@@ -850,10 +851,11 @@ where
self.compactors[h + 1].sort();
self.compactors[h + 1].merge_sorted(&self.promotion_buf);
}
- self.update_max_nom_size();
- self.update_num_retained();
}
+ h += 1;
}
+ self.update_max_nom_size();
+ self.update_num_retained();
}
fn update_max_nom_size(&mut self) {
diff --git a/tests-integration/tests/req_test/core.rs
b/tests-integration/tests/req_test/core.rs
index 1a3622e..876c8c8 100644
--- a/tests-integration/tests/req_test/core.rs
+++ b/tests-integration/tests/req_test/core.rs
@@ -184,7 +184,7 @@ fn estimation_mode_compresses_and_keeps_min_max() {
assert!(!sketch.is_empty());
assert!(sketch.is_estimation_mode());
assert_eq!(sketch.n(), n);
- assert_that!(sketch.num_retained(), lt(n as u32));
+ assert_that!(sketch.num_retained(), lt(n as usize));
assert_eq!(sketch.min_item().copied(), Some(req_f64(0.0)));
assert_eq!(sketch.max_item().copied(), Some(req_f64((n - 1) as f64)));
diff --git a/tests-integration/tests/req_test/merge.rs
b/tests-integration/tests/req_test/merge.rs
index d24d6e7..8de74c8 100644
--- a/tests-integration/tests/req_test/merge.rs
+++ b/tests-integration/tests/req_test/merge.rs
@@ -23,6 +23,7 @@ use datasketches::req::ReqSketch;
use googletest::assert_that;
use googletest::prelude::anything;
use googletest::prelude::err;
+use googletest::prelude::lt;
use googletest::prelude::near;
use super::ReqF64;
@@ -132,3 +133,31 @@ fn many_small_merges_preserve_count_bounds_and_median() {
.expect("the sketch is non-empty");
assert_that!(*median, near(4999.5, 500.0));
}
+
+#[test]
+fn merge_larger_k_into_smaller_k_cascades_compaction_across_new_levels() {
+ let mut target: ReqSketch<ReqF64> = ReqSketch::new(4,
RankAccuracy::HighRank).unwrap();
+ let mut source: ReqSketch<ReqF64> = ReqSketch::new(200,
RankAccuracy::HighRank).unwrap();
+
+ // 500 items fit in level 0 of k=200 (nominal capacity 1200), so source
has 1 level.
+ // Merging into k=4 (level nominal capacity 24) promotes 240 items into a
newly grown
+ // level 1, which must cascade further compactions across newly grown
upper levels.
+ for i in 0..500 {
+ source.update(req_f64(i as f64));
+ }
+ assert!(!source.is_estimation_mode());
+
+ target.merge(&source).expect("merge should succeed");
+
+ assert_eq!(target.n(), 500);
+ assert!(target.is_estimation_mode());
+ assert_that!(target.num_retained(), lt(120));
+ let weighted_sum: u64 = target.iter().map(|(_, weight)| weight).sum();
+ assert_eq!(weighted_sum, 500);
+ assert_eq!(target.min_item().copied(), Some(req_f64(0.0)));
+ assert_eq!(target.max_item().copied(), Some(req_f64(499.0)));
+
+ let round_trip =
ReqSketch::<ReqF64>::deserialize(&target.serialize()).unwrap();
+ assert_eq!(round_trip.n(), target.n());
+ assert_eq!(round_trip.num_retained(), target.num_retained());
+}
diff --git a/tests-integration/tests/serde_tests/req.rs
b/tests-integration/tests/serde_tests/req.rs
index 7c14763..fa1fc1d 100644
--- a/tests-integration/tests/serde_tests/req.rs
+++ b/tests-integration/tests/serde_tests/req.rs
@@ -335,11 +335,27 @@ fn deserialize_rejects_inconsistent_weighted_count() {
#[test]
fn deserialize_rejects_unreachable_section_configuration() {
- let mut invalid_raw = exact_image(12, &[1.0, 2.0, 3.0, 4.0, 5.0]);
- invalid_raw[EXACT_COMPACTOR_OFFSET + SECTION_SIZE_RAW_OFFSET
+ for raw in [
+ 0.0f32,
+ -6.0,
+ f32::NAN,
+ f32::INFINITY,
+ f32::NEG_INFINITY,
+ f32::MAX,
+ ] {
+ let mut invalid_raw = exact_image(12, &[1.0, 2.0, 3.0, 4.0, 5.0]);
+ invalid_raw[EXACT_COMPACTOR_OFFSET + SECTION_SIZE_RAW_OFFSET
+ ..EXACT_COMPACTOR_OFFSET + SECTION_SIZE_RAW_OFFSET + 4]
+ .copy_from_slice(&raw.to_le_bytes());
+ assert_invalid_data(&invalid_raw);
+ }
+
+ // (4_294_967_808.0 / 2.0) = 0x8000_0100; shifting left in u32 would wrap
to 512 == k.
+ let mut wrapping_raw = exact_image(512, &[1.0, 2.0, 3.0, 4.0, 5.0]);
+ wrapping_raw[EXACT_COMPACTOR_OFFSET + SECTION_SIZE_RAW_OFFSET
..EXACT_COMPACTOR_OFFSET + SECTION_SIZE_RAW_OFFSET + 4]
- .copy_from_slice(&0.0f32.to_le_bytes());
- assert_invalid_data(&invalid_raw);
+ .copy_from_slice(&4_294_967_808.0f32.to_le_bytes());
+ assert_invalid_data(&wrapping_raw);
let mut invalid_sections = exact_image(12, &[1.0, 2.0, 3.0, 4.0, 5.0]);
invalid_sections[EXACT_COMPACTOR_OFFSET + NUM_SECTIONS_OFFSET] = 6;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]