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 aeda4de refactor: simplify estimated_size accounting (#302)
aeda4de is described below
commit aeda4de8f029050dd75063ba6b21a4db8ec09947
Author: tison <[email protected]>
AuthorDate: Sun Oct 25 18:42:22 2026 +0800
refactor: simplify estimated_size accounting (#302)
---
CHANGELOG.md | 1 +
datasketches/src/bloom/sketch.rs | 4 +-
datasketches/src/countmin/sketch.rs | 6 +--
datasketches/src/cpc/pair_table.rs | 2 +-
datasketches/src/cpc/sketch.rs | 8 ++-
datasketches/src/cpc/union.rs | 10 ++--
.../src/frequencies/reverse_purge_item_hash_map.rs | 2 +-
datasketches/src/frequencies/sketch.rs | 4 +-
datasketches/src/hll/array4.rs | 2 +-
datasketches/src/hll/array6.rs | 2 +-
datasketches/src/hll/array8.rs | 2 +-
datasketches/src/hll/aux_map.rs | 2 +-
datasketches/src/hll/container.rs | 2 +-
datasketches/src/hll/sketch.rs | 8 ++-
datasketches/src/hll/union.rs | 5 +-
datasketches/src/tdigest/sketch.rs | 9 ++--
datasketches/src/thetafamily/common/hash_table.rs | 2 +-
.../src/thetafamily/common/intersection.rs | 4 +-
datasketches/src/thetafamily/common/union.rs | 4 +-
datasketches/src/thetafamily/theta/intersection.rs | 4 +-
datasketches/src/thetafamily/theta/sketch.rs | 8 +--
datasketches/src/thetafamily/theta/union.rs | 4 +-
datasketches/src/thetafamily/tuple/intersection.rs | 4 +-
datasketches/src/thetafamily/tuple/sketch.rs | 9 ++--
datasketches/src/thetafamily/tuple/union.rs | 4 +-
tests-integration/tests/bloom_test/sketch.rs | 6 +++
tests-integration/tests/countmin_test/sketch.rs | 4 +-
tests-integration/tests/cpc_test/union.rs | 4 +-
tests-integration/tests/cpc_test/update.rs | 12 +++++
tests-integration/tests/frequencies_test/update.rs | 20 ++++++-
tests-integration/tests/hll_test/union.rs | 4 +-
tests-integration/tests/hll_test/update.rs | 15 ++++++
tests-integration/tests/tdigest_test/sketch.rs | 6 +--
tests-integration/tests/theta_test/intersection.rs | 4 +-
tests-integration/tests/theta_test/sketch.rs | 2 +
tests-integration/tests/theta_test/union.rs | 15 +++++-
tests-integration/tests/tuple_test/intersection.rs | 4 +-
tests-integration/tests/tuple_test/sketch.rs | 61 ++++++++++++++++++++++
tests-integration/tests/tuple_test/union.rs | 15 +++++-
39 files changed, 204 insertions(+), 80 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 6aeb2a9..733a773 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -11,6 +11,7 @@ All significant changes to this project will be documented in
this file.
* `ReqSketch` queries now use `datasketches::common::SearchCriteria` instead
of `datasketches::req::SearchCriteria`. `SearchCriteria` no longer implements
`Default`; explicitly choose `Inclusive` or `Exclusive`.
* `ReqSketch` and `req::SortedView` queries now distinguish empty sketches
from invalid arguments. `rank` returns `Option<f64>`; `quantile`, `quantiles`,
`cdf`, and `pmf`, where available, return `Result<Option<_>, Error>`. Handle
`None` for valid queries on an empty sketch, and propagate or handle
`InvalidArgument` for invalid ranks or split points, which are checked before
emptiness.
* `TDigest` and `TDigestMut` rank, quantile, CDF, and PMF queries now return
`Result<Option<_>, Error>`. Invalid arguments return `InvalidArgument` instead
of panicking, including on empty digests. Propagate or handle the `Result`
before handling `None` for an empty digest; `min_value` and `max_value` still
return `Option<f64>`.
+* `estimated_size` now returns an implementation-dependent estimate of memory
usage. Returned values may change as implementations evolve and should not be
treated as exact totals or a stable accounting contract.
### New features
diff --git a/datasketches/src/bloom/sketch.rs b/datasketches/src/bloom/sketch.rs
index 0d399d5..245a726 100644
--- a/datasketches/src/bloom/sketch.rs
+++ b/datasketches/src/bloom/sketch.rs
@@ -639,9 +639,9 @@ impl BloomFilter {
was_set
}
- /// Returns the estimated size of the filter in bytes.
+ /// Returns an estimate of the filter's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>() + self.bit_array.len() * size_of::<u64>()
+ self.bit_array.len() * size_of::<u64>()
}
}
diff --git a/datasketches/src/countmin/sketch.rs
b/datasketches/src/countmin/sketch.rs
index 7e3c3ed..b81576f 100644
--- a/datasketches/src/countmin/sketch.rs
+++ b/datasketches/src/countmin/sketch.rs
@@ -532,11 +532,9 @@ impl<T: CountMinValue> CountMinSketch<T> {
Ok(sketch)
}
- /// Returns the estimated size of the sketch in bytes.
+ /// Returns an estimate of the sketch's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>()
- + self.counts.capacity() * size_of::<T>()
- + self.hash_seeds.capacity() * size_of::<u64>()
+ self.counts.capacity() * size_of::<T>() + self.hash_seeds.capacity() *
size_of::<u64>()
}
fn make(num_hashes: u8, num_buckets: u32, seed: u64, seed_hash: u16,
entries: usize) -> Self {
diff --git a/datasketches/src/cpc/pair_table.rs
b/datasketches/src/cpc/pair_table.rs
index a476ec1..d8ab5d8 100644
--- a/datasketches/src/cpc/pair_table.rs
+++ b/datasketches/src/cpc/pair_table.rs
@@ -258,7 +258,7 @@ impl PairTable {
}
}
- /// Returns the estimated size of the heap allocations in bytes
+ /// Returns an estimate of memory usage in bytes.
pub fn estimated_size(&self) -> usize {
self.slots.capacity() * size_of::<u32>()
}
diff --git a/datasketches/src/cpc/sketch.rs b/datasketches/src/cpc/sketch.rs
index c42b367..3222cff 100644
--- a/datasketches/src/cpc/sketch.rs
+++ b/datasketches/src/cpc/sketch.rs
@@ -459,16 +459,14 @@ impl CpcSketch {
matrix
}
- /// Returns the estimated size of the sketch in bytes.
+ /// Returns an estimate of the sketch's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- let heap_size = self.sliding_window.capacity()
+ self.sliding_window.capacity()
+ self
.surprising_value_table
.as_ref()
.map(|t| t.estimated_size())
- .unwrap_or(0);
-
- size_of::<Self>() + heap_size
+ .unwrap_or(0)
}
}
diff --git a/datasketches/src/cpc/union.rs b/datasketches/src/cpc/union.rs
index 67870f5..abd473d 100644
--- a/datasketches/src/cpc/union.rs
+++ b/datasketches/src/cpc/union.rs
@@ -347,14 +347,12 @@ impl CpcUnion {
}
}
- /// Returns the estimated size of the union in bytes.
+ /// Returns an estimate of the union's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- // The state's inline size is already covered by size_of::<Self>().
- let heap_size = match &self.state {
- UnionState::Accumulator(sketch) => sketch.estimated_size() -
size_of::<CpcSketch>(),
+ match &self.state {
+ UnionState::Accumulator(sketch) => sketch.estimated_size(),
UnionState::BitMatrix(matrix) => matrix.capacity() *
size_of::<u64>(),
- };
- size_of::<Self>() + heap_size
+ }
}
}
diff --git a/datasketches/src/frequencies/reverse_purge_item_hash_map.rs
b/datasketches/src/frequencies/reverse_purge_item_hash_map.rs
index ce3d62d..7f430f6 100644
--- a/datasketches/src/frequencies/reverse_purge_item_hash_map.rs
+++ b/datasketches/src/frequencies/reverse_purge_item_hash_map.rs
@@ -197,7 +197,7 @@ impl<T: Eq + Hash> ReversePurgeItemHashMap<T> {
self.num_active
}
- /// Returns the estimated size of the heap allocations in bytes.
+ /// Returns an estimate of memory usage in bytes.
pub fn estimated_size(&self) -> usize {
self.keys.capacity() * size_of::<Option<T>>()
+ self.values.capacity() * size_of::<u64>()
diff --git a/datasketches/src/frequencies/sketch.rs
b/datasketches/src/frequencies/sketch.rs
index 4808ef5..617b98e 100644
--- a/datasketches/src/frequencies/sketch.rs
+++ b/datasketches/src/frequencies/sketch.rs
@@ -323,9 +323,9 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
self.hash_map.lg_length()
}
- /// Returns the estimated size of the sketch in bytes.
+ /// Returns an estimate of the sketch's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>() + self.hash_map.estimated_size()
+ self.hash_map.estimated_size()
}
/// Updates the sketch with a count of one.
diff --git a/datasketches/src/hll/array4.rs b/datasketches/src/hll/array4.rs
index 19c9632..4190a3f 100644
--- a/datasketches/src/hll/array4.rs
+++ b/datasketches/src/hll/array4.rs
@@ -419,7 +419,7 @@ impl Array4 {
bytes.into_bytes()
}
- /// Returns the estimated size of the heap allocations in bytes
+ /// Returns an estimate of memory usage in bytes.
pub fn estimated_size(&self) -> usize {
self.bytes.len()
+ self
diff --git a/datasketches/src/hll/array6.rs b/datasketches/src/hll/array6.rs
index c29a901..636da15 100644
--- a/datasketches/src/hll/array6.rs
+++ b/datasketches/src/hll/array6.rs
@@ -233,7 +233,7 @@ impl Array6 {
bytes.into_bytes()
}
- /// Returns the estimated size of the heap allocations in bytes
+ /// Returns an estimate of memory usage in bytes.
pub fn estimated_size(&self) -> usize {
self.bytes.len()
}
diff --git a/datasketches/src/hll/array8.rs b/datasketches/src/hll/array8.rs
index 355bcc1..1269d17 100644
--- a/datasketches/src/hll/array8.rs
+++ b/datasketches/src/hll/array8.rs
@@ -278,7 +278,7 @@ impl Array8 {
bytes.into_bytes()
}
- /// Returns the estimated size of the heap allocations in bytes
+ /// Returns an estimate of memory usage in bytes.
pub fn estimated_size(&self) -> usize {
self.bytes.len()
}
diff --git a/datasketches/src/hll/aux_map.rs b/datasketches/src/hll/aux_map.rs
index e14ef31..2ce25a3 100644
--- a/datasketches/src/hll/aux_map.rs
+++ b/datasketches/src/hll/aux_map.rs
@@ -192,7 +192,7 @@ impl AuxMap {
})
}
- /// Returns the estimated size of the heap allocations in bytes
+ /// Returns an estimate of memory usage in bytes.
pub fn estimated_size(&self) -> usize {
self.entries.len() * size_of::<Coupon>()
}
diff --git a/datasketches/src/hll/container.rs
b/datasketches/src/hll/container.rs
index 8f0313c..bc8cab6 100644
--- a/datasketches/src/hll/container.rs
+++ b/datasketches/src/hll/container.rs
@@ -121,7 +121,7 @@ impl Container {
self.coupons.iter().filter(|&&c| !c.is_empty()).copied()
}
- /// Returns the estimated size of the heap allocations in bytes
+ /// Returns an estimate of memory usage in bytes.
pub fn estimated_size(&self) -> usize {
self.coupons.len() * size_of::<Coupon>()
}
diff --git a/datasketches/src/hll/sketch.rs b/datasketches/src/hll/sketch.rs
index 92d4d5b..910a730 100644
--- a/datasketches/src/hll/sketch.rs
+++ b/datasketches/src/hll/sketch.rs
@@ -470,17 +470,15 @@ impl HllSketch {
}
}
- /// Returns the estimated memory usage in bytes, including owned heap
allocations.
+ /// Returns an estimate of the sketch's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- let heap_size = match &self.mode {
+ match &self.mode {
Mode::List { list, .. } => list.container().estimated_size(),
Mode::Set { set, .. } => set.container().estimated_size(),
Mode::Array4(arr) => arr.estimated_size(),
Mode::Array6(arr) => arr.estimated_size(),
Mode::Array8(arr) => arr.estimated_size(),
- };
-
- size_of::<Self>() + heap_size
+ }
}
}
diff --git a/datasketches/src/hll/union.rs b/datasketches/src/hll/union.rs
index 0f6e20e..b245fa7 100644
--- a/datasketches/src/hll/union.rs
+++ b/datasketches/src/hll/union.rs
@@ -365,10 +365,9 @@ impl HllUnion {
self.gadget.lower_bound(num_std_dev)
}
- /// Returns the estimated memory usage in bytes, including owned heap
allocations.
+ /// Returns an estimate of the union's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- // The gadget's inline size is already covered by size_of::<Self>().
- size_of::<Self>() - size_of::<HllSketch>() +
self.gadget.estimated_size()
+ self.gadget.estimated_size()
}
}
diff --git a/datasketches/src/tdigest/sketch.rs
b/datasketches/src/tdigest/sketch.rs
index 1fb4b16..9bc7b03 100644
--- a/datasketches/src/tdigest/sketch.rs
+++ b/datasketches/src/tdigest/sketch.rs
@@ -156,6 +156,7 @@ impl TDigestBuffer {
self.centroids
}
+ /// Returns an estimate of memory usage in bytes.
fn estimated_size(&self) -> usize {
self.centroids.capacity() * size_of::<Centroid>()
}
@@ -1012,9 +1013,9 @@ impl TDigestMut {
centroids.shrink_to(target_capacity);
}
- /// Returns the estimated size of the sketch in bytes.
+ /// Returns an estimate of the sketch's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>() + self.buffer.estimated_size()
+ self.buffer.estimated_size()
}
}
@@ -1630,9 +1631,9 @@ impl TDigest {
)
}
- /// Returns the estimated size of the sketch in bytes.
+ /// Returns an estimate of the sketch's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>() + self.centroids.capacity() * size_of::<Centroid>()
+ self.centroids.capacity() * size_of::<Centroid>()
}
}
diff --git a/datasketches/src/thetafamily/common/hash_table.rs
b/datasketches/src/thetafamily/common/hash_table.rs
index d2138c9..e0b7523 100644
--- a/datasketches/src/thetafamily/common/hash_table.rs
+++ b/datasketches/src/thetafamily/common/hash_table.rs
@@ -344,7 +344,7 @@ where
})
}
- /// Returns the estimated size of the heap allocations in bytes.
+ /// Returns an estimate of memory usage in bytes.
pub fn estimated_size(&self) -> usize {
self.entries.capacity() * size_of::<Option<E>>()
}
diff --git a/datasketches/src/thetafamily/common/intersection.rs
b/datasketches/src/thetafamily/common/intersection.rs
index 486b2cb..535beba 100644
--- a/datasketches/src/thetafamily/common/intersection.rs
+++ b/datasketches/src/thetafamily/common/intersection.rs
@@ -234,9 +234,9 @@ where
self.result_state != IntersectionResultState::Uninitialized
}
- /// Returns the estimated size of the heap allocations in bytes.
+ /// Returns an estimate of memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- self.table.estimated_size()
+ size_of::<P>() + self.table.estimated_size()
}
/// Returns the current intersection as canonical compact-sketch state.
diff --git a/datasketches/src/thetafamily/common/union.rs
b/datasketches/src/thetafamily/common/union.rs
index 0131b55..4ad3b46 100644
--- a/datasketches/src/thetafamily/common/union.rs
+++ b/datasketches/src/thetafamily/common/union.rs
@@ -150,8 +150,8 @@ where
self.result_theta = None;
}
- /// Returns the estimated size of the heap allocations in bytes.
+ /// Returns an estimate of memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- self.table.estimated_size()
+ size_of::<P>() + self.table.estimated_size()
}
}
diff --git a/datasketches/src/thetafamily/theta/intersection.rs
b/datasketches/src/thetafamily/theta/intersection.rs
index ace0d41..137891d 100644
--- a/datasketches/src/thetafamily/theta/intersection.rs
+++ b/datasketches/src/thetafamily/theta/intersection.rs
@@ -78,9 +78,9 @@ impl ThetaIntersection {
self.state.has_result()
}
- /// Returns the estimated size of the intersection in bytes.
+ /// Returns an estimate of the intersection's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>() + self.state.estimated_size()
+ self.state.estimated_size()
}
/// Returns the current intersection as a compact theta sketch.
diff --git a/datasketches/src/thetafamily/theta/sketch.rs
b/datasketches/src/thetafamily/theta/sketch.rs
index b75d1af..4ec71b7 100644
--- a/datasketches/src/thetafamily/theta/sketch.rs
+++ b/datasketches/src/thetafamily/theta/sketch.rs
@@ -427,9 +427,9 @@ impl ThetaSketch {
.expect("theta should always be valid")
}
- /// Returns the estimated size of the sketch in bytes.
+ /// Returns an estimate of the sketch's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>() + self.table.estimated_size()
+ self.table.estimated_size()
}
}
@@ -1027,9 +1027,9 @@ impl CompactThetaSketch {
Ok(Self::from_compact_state(compact_state))
}
- /// Returns the estimated size of the sketch in bytes.
+ /// Returns an estimate of the sketch's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>() + self.compact_state.retained_entries_capacity() *
size_of::<u64>()
+ self.compact_state.retained_entries_capacity() * size_of::<u64>()
}
}
diff --git a/datasketches/src/thetafamily/theta/union.rs
b/datasketches/src/thetafamily/theta/union.rs
index c315c4f..1b26d7a 100644
--- a/datasketches/src/thetafamily/theta/union.rs
+++ b/datasketches/src/thetafamily/theta/union.rs
@@ -64,9 +64,9 @@ impl ThetaUnion {
self.state.reset();
}
- /// Returns the estimated size of the union in bytes.
+ /// Returns an estimate of the union's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>() + self.state.estimated_size()
+ self.state.estimated_size()
}
}
diff --git a/datasketches/src/thetafamily/tuple/intersection.rs
b/datasketches/src/thetafamily/tuple/intersection.rs
index 38dfe9e..58dce8f 100644
--- a/datasketches/src/thetafamily/tuple/intersection.rs
+++ b/datasketches/src/thetafamily/tuple/intersection.rs
@@ -138,9 +138,9 @@ where
self.state.has_result()
}
- /// Returns the estimated size of the intersection in bytes.
+ /// Returns an estimate of the intersection's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>() + self.state.estimated_size()
+ self.state.estimated_size()
}
/// Returns the current intersection as a compact Tuple sketch.
diff --git a/datasketches/src/thetafamily/tuple/sketch.rs
b/datasketches/src/thetafamily/tuple/sketch.rs
index e3a690f..0fee821 100644
--- a/datasketches/src/thetafamily/tuple/sketch.rs
+++ b/datasketches/src/thetafamily/tuple/sketch.rs
@@ -404,9 +404,9 @@ where
.expect("theta should always be valid")
}
- /// Returns the estimated size of the sketch in bytes.
+ /// Returns an estimate of the sketch's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>() + self.table.estimated_size()
+ size_of::<P>() + self.table.estimated_size()
}
}
@@ -541,10 +541,9 @@ impl<S> CompactTupleSketch<S> {
.expect("compact theta should always be valid")
}
- /// Returns the estimated size of the sketch in bytes.
+ /// Returns an estimate of the sketch's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>()
- + self.compact_state.retained_entries_capacity() *
size_of::<TupleEntry<S>>()
+ self.compact_state.retained_entries_capacity() *
size_of::<TupleEntry<S>>()
}
fn preamble_longs(&self) -> u8 {
diff --git a/datasketches/src/thetafamily/tuple/union.rs
b/datasketches/src/thetafamily/tuple/union.rs
index df7786b..029aeba 100644
--- a/datasketches/src/thetafamily/tuple/union.rs
+++ b/datasketches/src/thetafamily/tuple/union.rs
@@ -112,9 +112,9 @@ where
self.state.reset();
}
- /// Returns the estimated size of the union in bytes.
+ /// Returns an estimate of the union's memory usage in bytes.
pub fn estimated_size(&self) -> usize {
- size_of::<Self>() + self.state.estimated_size()
+ self.state.estimated_size()
}
}
diff --git a/tests-integration/tests/bloom_test/sketch.rs
b/tests-integration/tests/bloom_test/sketch.rs
index db0a0db..7d2b7df 100644
--- a/tests-integration/tests/bloom_test/sketch.rs
+++ b/tests-integration/tests/bloom_test/sketch.rs
@@ -211,6 +211,12 @@ fn test_requested_size_rounds_to_word_boundary() {
assert_eq!(filter.capacity(), 128);
}
+#[test]
+fn test_estimated_size() {
+ let filter = BloomFilterBuilder::with_size(65, 3).build().unwrap();
+ assert_eq!(filter.estimated_size(), 16);
+}
+
#[test]
fn test_accuracy_builder_rejects_zero_items_at_build() {
let error = BloomFilterBuilder::with_accuracy(0, 0.01)
diff --git a/tests-integration/tests/countmin_test/sketch.rs
b/tests-integration/tests/countmin_test/sketch.rs
index 9edae10..b85a887 100644
--- a/tests-integration/tests/countmin_test/sketch.rs
+++ b/tests-integration/tests/countmin_test/sketch.rs
@@ -445,11 +445,11 @@ fn test_increment_single_key_like_rust_count_min_sketch()
{
#[test]
fn test_estimated_size() {
let mut sketch = CountMinSketch::<i64>::new(4, 128).unwrap();
- assert_eq!(sketch.estimated_size(), 4240);
+ assert_eq!(sketch.estimated_size(), 4128);
// The backing tables are allocated up front; updates do not grow the
sketch.
sketch.update("apple");
- assert_eq!(sketch.estimated_size(), 4240);
+ assert_eq!(sketch.estimated_size(), 4128);
}
#[test]
diff --git a/tests-integration/tests/cpc_test/union.rs
b/tests-integration/tests/cpc_test/union.rs
index 7b28034..d72a7d4 100644
--- a/tests-integration/tests/cpc_test/union.rs
+++ b/tests-integration/tests/cpc_test/union.rs
@@ -183,12 +183,12 @@ fn test_lg_k_too_large_returns_error() {
#[test]
fn test_union_estimated_size() {
let mut union = CpcUnion::new(11).unwrap();
- assert_eq!(union.estimated_size(), 112);
+ assert_eq!(union.estimated_size(), 0);
let mut sketch = CpcSketch::new(11).unwrap();
for i in 0..1000 {
sketch.update(i);
}
union.update(&sketch).unwrap();
- assert_eq!(union.estimated_size(), 16496);
+ assert_eq!(union.estimated_size(), 16384);
}
diff --git a/tests-integration/tests/cpc_test/update.rs
b/tests-integration/tests/cpc_test/update.rs
index 99a1cb5..8aec8df 100644
--- a/tests-integration/tests/cpc_test/update.rs
+++ b/tests-integration/tests/cpc_test/update.rs
@@ -67,3 +67,15 @@ fn test_max_serialized_bytes_validates_lg_k() {
assert_eq!(error.kind(), ErrorKind::InvalidArgument);
}
}
+
+#[test]
+fn test_estimated_size() {
+ let mut sketch = CpcSketch::new(11).unwrap();
+ let empty_size = sketch.estimated_size();
+ assert_eq!(empty_size, 0);
+
+ for i in 0..10_000 {
+ sketch.update(i);
+ }
+ assert_eq!(sketch.estimated_size(), 2304);
+}
diff --git a/tests-integration/tests/frequencies_test/update.rs
b/tests-integration/tests/frequencies_test/update.rs
index 06489d3..ca357d6 100644
--- a/tests-integration/tests/frequencies_test/update.rs
+++ b/tests-integration/tests/frequencies_test/update.rs
@@ -634,11 +634,27 @@ fn
test_map_size_above_cross_language_limit_returns_error() {
#[test]
fn test_estimated_size() {
let mut sketch: FrequentItemsSketch<i64> =
FrequentItemsSketch::new(64).unwrap();
- assert_eq!(sketch.estimated_size(), 344);
+ assert_eq!(sketch.estimated_size(), 208);
// The internal map grows from its starting size up to the maximum size.
for i in 0..100 {
sketch.update(i);
}
- assert_eq!(sketch.estimated_size(), 1800);
+ assert_eq!(sketch.estimated_size(), 1664);
+}
+
+#[test]
+fn estimated_size_is_shallow_for_generic_items() {
+ let mut small_item_sketch = FrequentItemsSketch::new(8).unwrap();
+ small_item_sketch.update("key".to_string());
+
+ let mut large_item = String::with_capacity(4096);
+ large_item.push_str("key");
+ let mut large_item_sketch = FrequentItemsSketch::new(8).unwrap();
+ large_item_sketch.update(large_item);
+
+ assert_eq!(
+ small_item_sketch.estimated_size(),
+ large_item_sketch.estimated_size()
+ );
}
diff --git a/tests-integration/tests/hll_test/union.rs
b/tests-integration/tests/hll_test/union.rs
index 7a6409a..c61a171 100644
--- a/tests-integration/tests/hll_test/union.rs
+++ b/tests-integration/tests/hll_test/union.rs
@@ -710,14 +710,14 @@ fn test_union_validation() {
#[test]
fn test_union_estimated_size() {
let mut union = HllUnion::new(10).unwrap();
- assert_eq!(union.estimated_size(), 128);
+ assert_eq!(union.estimated_size(), 32);
let mut sketch = HllSketch::new(10, HllType::Hll8).unwrap();
for i in 0..1000 {
sketch.update(i);
}
union.update(&sketch);
- assert_eq!(union.estimated_size(), 1120);
+ assert_eq!(union.estimated_size(), 1024);
}
#[test]
diff --git a/tests-integration/tests/hll_test/update.rs
b/tests-integration/tests/hll_test/update.rs
index 50fd0b4..5ec6ac8 100644
--- a/tests-integration/tests/hll_test/update.rs
+++ b/tests-integration/tests/hll_test/update.rs
@@ -201,3 +201,18 @@ fn test_invalid_lg_k_high_returns_error() {
let error = HllSketch::new(22, HllType::Hll8).unwrap_err();
assert_eq!(error.kind(), ErrorKind::InvalidArgument);
}
+
+#[test]
+fn estimated_size_tracks_retained_storage() {
+ let mut sketch = HllSketch::new(10, HllType::Hll8).unwrap();
+ let initial_size = sketch.estimated_size();
+ assert_eq!(initial_size, 32);
+
+ sketch.update(0);
+ assert_eq!(sketch.estimated_size(), initial_size);
+
+ for i in 1..1000 {
+ sketch.update(i);
+ }
+ assert_eq!(sketch.estimated_size(), 1024);
+}
diff --git a/tests-integration/tests/tdigest_test/sketch.rs
b/tests-integration/tests/tdigest_test/sketch.rs
index 86bc45f..4eba82d 100644
--- a/tests-integration/tests/tdigest_test/sketch.rs
+++ b/tests-integration/tests/tdigest_test/sketch.rs
@@ -15,7 +15,6 @@
// specific language governing permissions and limitations
// under the License.
-use std::mem::size_of;
use std::panic::AssertUnwindSafe;
use std::panic::catch_unwind;
@@ -119,15 +118,14 @@ fn test_estimated_size_reuses_buffer_after_compression() {
const TARGET_CENTROIDS: usize = 410;
const MAX_UNMERGED: usize = TARGET_CENTROIDS * 4;
- let inline_size = size_of::<TDigestMut>();
let mut tdigest = TDigestMut::new(K).unwrap();
- assert_eq!(tdigest.estimated_size(), inline_size);
+ assert_eq!(tdigest.estimated_size(), 0);
for value in 0..MAX_UNMERGED {
tdigest.update(value as f64);
}
let size_before_compression = tdigest.estimated_size();
- assert!(size_before_compression > inline_size);
+ assert!(size_before_compression > 0);
tdigest.rank(0.5).unwrap();
assert!(tdigest.estimated_size() <= size_before_compression);
diff --git a/tests-integration/tests/theta_test/intersection.rs
b/tests-integration/tests/theta_test/intersection.rs
index 87f545f..f6068a1 100644
--- a/tests-integration/tests/theta_test/intersection.rs
+++ b/tests-integration/tests/theta_test/intersection.rs
@@ -326,9 +326,9 @@ fn test_seed_mismatch_non_empty_returns_error() {
#[test]
fn test_intersection_estimated_size() {
let mut intersection = ThetaIntersection::default();
- assert_eq!(intersection.estimated_size(), 72);
+ assert_eq!(intersection.estimated_size(), 0);
let sketch = sketch_with_range(0, 1000);
intersection.update(&sketch).unwrap();
- assert_eq!(intersection.estimated_size(), 16456);
+ assert_eq!(intersection.estimated_size(), 16384);
}
diff --git a/tests-integration/tests/theta_test/sketch.rs
b/tests-integration/tests/theta_test/sketch.rs
index b900ab1..cd43f36 100644
--- a/tests-integration/tests/theta_test/sketch.rs
+++ b/tests-integration/tests/theta_test/sketch.rs
@@ -157,6 +157,7 @@ fn test_reset() {
assert_that!(sketch.num_retained(), gt(32));
assert_that!(sketch.theta(), lt(1.0));
+ assert_eq!(sketch.estimated_size(), 512);
sketch.reset();
assert!(sketch.is_empty());
assert_eq!(sketch.estimate(), 0.0);
@@ -165,6 +166,7 @@ fn test_reset() {
assert!(!sketch.is_estimation_mode());
assert_eq!(sketch.lower_bound(NumStdDev::One), 0.0);
assert_eq!(sketch.upper_bound(NumStdDev::One), 0.0);
+ assert_eq!(sketch.estimated_size(), 512);
}
#[test]
diff --git a/tests-integration/tests/theta_test/union.rs
b/tests-integration/tests/theta_test/union.rs
index 14df5bf..3935b82 100644
--- a/tests-integration/tests/theta_test/union.rs
+++ b/tests-integration/tests/theta_test/union.rs
@@ -734,9 +734,20 @@ fn test_corner_case_union_states() {
#[test]
fn test_union_estimated_size() {
let mut union = ThetaUnionBuilder::default().build().unwrap();
- assert_eq!(union.estimated_size(), 1104);
+ assert_eq!(union.estimated_size(), 1024);
let sketch = sketch_with_range(12, 0, 1000);
union.update(&sketch).unwrap();
- assert_eq!(union.estimated_size(), 65616);
+ assert_eq!(union.estimated_size(), 65536);
+}
+
+#[test]
+fn compact_estimated_size_includes_retained_capacity() {
+ let sketch = sketch_with_range(5, 0, 1000);
+ let mut union = ThetaUnionBuilder::default().lg_k(5).build().unwrap();
+ union.update(&sketch).unwrap();
+ let result = union.to_sketch(true);
+
+ assert_eq!(result.num_retained(), 32);
+ assert_eq!(result.estimated_size(), 512);
}
diff --git a/tests-integration/tests/tuple_test/intersection.rs
b/tests-integration/tests/tuple_test/intersection.rs
index 9caa0eb..d01381a 100644
--- a/tests-integration/tests/tuple_test/intersection.rs
+++ b/tests-integration/tests/tuple_test/intersection.rs
@@ -185,9 +185,9 @@ fn estimation_bounds_cover_the_true_intersection() {
#[test]
fn intersection_estimated_size_grows_with_updates() {
let mut intersection = TupleIntersection::new(SumPolicy);
- assert_eq!(intersection.estimated_size(), 72);
+ assert_eq!(intersection.estimated_size(), 0);
let sketch = tuple_sketch_with_range(0, 1000);
intersection.update(&sketch).unwrap();
- assert_eq!(intersection.estimated_size(), 32840);
+ assert_eq!(intersection.estimated_size(), 32768);
}
diff --git a/tests-integration/tests/tuple_test/sketch.rs
b/tests-integration/tests/tuple_test/sketch.rs
index 194060d..694644e 100644
--- a/tests-integration/tests/tuple_test/sketch.rs
+++ b/tests-integration/tests/tuple_test/sketch.rs
@@ -131,6 +131,67 @@ fn
custom_update_policy_accepts_multiple_value_representations() {
);
}
+#[test]
+fn estimated_size_is_shallow_for_generic_summaries() {
+ let mut small_summary_sketch = TupleSketchBuilder::new(ArraySumPolicy {
num_values: 1 })
+ .build()
+ .unwrap();
+ small_summary_sketch.update("key", [1.0]);
+
+ let mut large_summary_sketch = TupleSketchBuilder::new(ArraySumPolicy {
num_values: 1024 })
+ .build()
+ .unwrap();
+ large_summary_sketch.update("key", vec![1.0; 1024]);
+
+ assert_eq!(
+ small_summary_sketch.estimated_size(),
+ large_summary_sketch.estimated_size()
+ );
+ assert_eq!(
+ small_summary_sketch.compact(false).estimated_size(),
+ large_summary_sketch.compact(false).estimated_size()
+ );
+}
+
+struct PaddedArraySumPolicy {
+ inner: ArraySumPolicy,
+ _padding: [u8; 1024],
+}
+
+impl SummaryPolicy for PaddedArraySumPolicy {
+ type Summary = Vec<f64>;
+
+ fn create(&self) -> Self::Summary {
+ self.inner.create()
+ }
+}
+
+impl<U> SummaryUpdatePolicy<U> for PaddedArraySumPolicy
+where
+ U: AsRef<[f64]>,
+{
+ fn update(&self, summary: &mut Self::Summary, value: U) {
+ self.inner.update(summary, value);
+ }
+}
+
+#[test]
+fn estimated_size_includes_policy_inline_storage() {
+ let mut small_policy_sketch = TupleSketchBuilder::new(ArraySumPolicy {
num_values: 1 })
+ .build()
+ .unwrap();
+ small_policy_sketch.update("key", [1.0]);
+
+ let policy = PaddedArraySumPolicy {
+ inner: ArraySumPolicy { num_values: 1 },
+ _padding: [0; 1024],
+ };
+ let mut large_policy_sketch =
TupleSketchBuilder::new(policy).build().unwrap();
+ large_policy_sketch.update("key", [1.0]);
+
+ assert!(large_policy_sketch.estimated_size() >
small_policy_sketch.estimated_size());
+}
+
#[test]
fn trim_and_reset_update_public_state() {
let mut sketch = default_tuple_sketch_builder().lg_k(5).build().unwrap();
diff --git a/tests-integration/tests/tuple_test/union.rs
b/tests-integration/tests/tuple_test/union.rs
index 90b68b0..6c23c10 100644
--- a/tests-integration/tests/tuple_test/union.rs
+++ b/tests-integration/tests/tuple_test/union.rs
@@ -186,9 +186,20 @@ fn estimation_bounds_cover_the_true_union() {
#[test]
fn union_estimated_size_grows_with_updates() {
let mut union = default_union_builder().build().unwrap();
- assert_eq!(union.estimated_size(), 2128);
+ assert_eq!(union.estimated_size(), 2048);
let sketch = tuple_sketch_with_range(0, 1000);
union.update(&sketch).unwrap();
- assert_eq!(union.estimated_size(), 131152);
+ assert_eq!(union.estimated_size(), 131072);
+}
+
+#[test]
+fn compact_estimated_size_includes_retained_capacity() {
+ let sketch = tuple_sketch_with_range(0, 1000);
+ let mut union = default_union_builder().lg_k(5).build().unwrap();
+ union.update(&sketch).unwrap();
+ let result = union.to_sketch(true);
+
+ assert_eq!(result.num_retained(), 32);
+ assert_eq!(result.estimated_size(), 1024);
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
