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 5f080f9 perf(hll): reduce union copying and defer dense estimator
rebuilds (#317)
5f080f9 is described below
commit 5f080f98e5eedb79b51c84e3e855a300ddbdfc89
Author: tison <[email protected]>
AuthorDate: Wed Nov 4 11:38:57 2026 +0800
perf(hll): reduce union copying and defer dense estimator rebuilds (#317)
---
CHANGELOG.md | 2 +
benchmarks/hll/mod.rs | 2 +
benchmarks/hll/{mod.rs => serde.rs} | 25 ++++-
benchmarks/hll/union.rs | 112 +++++++++++++++++++
datasketches/src/hll/array8.rs | 170 ++++++++++++++++++++---------
datasketches/src/hll/estimator.rs | 26 ++---
datasketches/src/hll/union.rs | 50 ++++++---
tests-integration/tests/hll_test/union.rs | 113 +++++++++++++++++++
tests-integration/tests/serde_tests/hll.rs | 35 ++++++
9 files changed, 451 insertions(+), 84 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index cbc6000..8f254ac 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -6,10 +6,12 @@ All significant changes to this project will be documented in
this file.
### New features
+* Add `HllUnion::serialize` to serialize union results directly.
* Add immutable `XorFilter` and `XorFilterBuilder` behind the `xor` feature,
with 8-, 16-, and 32-bit fingerprints, consuming builder configuration with
complete-input construction, bounded seeded retries and compact temporary
storage, optional cardinality metadata for imported filters, standard
serialization for all three widths (Java-compatible for 8/16-bit filters), and
raw parts for application-defined storage.
### Improvements
+* `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.
* `TDigest` and `TDigestMut` CDF and PMF batches are faster for many split
points; batches with sparse split points keep the original binary-search
behavior.
diff --git a/benchmarks/hll/mod.rs b/benchmarks/hll/mod.rs
index 1dea33b..9e440b2 100644
--- a/benchmarks/hll/mod.rs
+++ b/benchmarks/hll/mod.rs
@@ -15,4 +15,6 @@
// specific language governing permissions and limitations
// under the License.
+mod serde;
+mod union;
mod update;
diff --git a/benchmarks/hll/mod.rs b/benchmarks/hll/serde.rs
similarity index 54%
copy from benchmarks/hll/mod.rs
copy to benchmarks/hll/serde.rs
index 1dea33b..8bafba4 100644
--- a/benchmarks/hll/mod.rs
+++ b/benchmarks/hll/serde.rs
@@ -15,4 +15,27 @@
// specific language governing permissions and limitations
// under the License.
-mod update;
+use datasketches::hll::HllType;
+use datasketches::hll::HllUnion;
+use divan::Bencher;
+use divan::black_box;
+
+fn union(rows: u64) -> HllUnion {
+ let mut union = HllUnion::new(18).unwrap();
+ for value in 0..rows {
+ union.update_value(value);
+ }
+ union
+}
+
+#[divan::bench(args = [0, 4, 100, 80_000])]
+fn serialize_union(bencher: Bencher, rows: u64) {
+ let union = union(rows);
+ bencher.bench_local(|| black_box(&union).serialize());
+}
+
+#[divan::bench(args = [0, 4, 100, 80_000])]
+fn serialize_union_via_sketch(bencher: Bencher, rows: u64) {
+ let union = union(rows);
+ bencher.bench_local(||
black_box(&union).to_sketch(HllType::Hll8).serialize());
+}
diff --git a/benchmarks/hll/union.rs b/benchmarks/hll/union.rs
new file mode 100644
index 0000000..c6be59c
--- /dev/null
+++ b/benchmarks/hll/union.rs
@@ -0,0 +1,112 @@
+// 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.
+
+use datasketches::hll::HllSketch;
+use datasketches::hll::HllType;
+use datasketches::hll::HllUnion;
+use divan::Bencher;
+use divan::black_box;
+
+fn partials(lg_k: u8, count: usize, rows: usize) -> Vec<HllSketch> {
+ (0..count)
+ .map(|partial| {
+ let mut sketch = HllSketch::new(lg_k, HllType::Hll8).unwrap();
+ for value in partial * rows..(partial + 1) * rows {
+ sketch.update(value as u64);
+ }
+ sketch
+ })
+ .collect()
+}
+
+#[divan::bench(args = [12, 18])]
+fn empty_from_dense(bencher: Bencher, lg_k: u8) {
+ let source = partials(lg_k, 1, 1 << lg_k).pop().unwrap();
+ bencher.bench_local(|| {
+ let mut union = HllUnion::new(lg_k).unwrap();
+ union.update(black_box(&source));
+ black_box(union)
+ });
+}
+
+#[divan::bench(args = [12, 18])]
+fn recreated_small_partials(bencher: Bencher, lg_k: u8) {
+ let partials = partials(lg_k, 400, 200);
+ bencher.bench_local(|| {
+ let mut sketch = HllSketch::new(lg_k, HllType::Hll8).unwrap();
+ for partial in black_box(&partials) {
+ let mut union = HllUnion::new(lg_k).unwrap();
+ union.update(&sketch);
+ union.update(partial);
+ sketch = union.to_sketch(HllType::Hll8);
+ }
+ black_box(sketch.estimate());
+ black_box(sketch)
+ });
+}
+
+#[divan::bench(args = [12, 18])]
+fn persistent_small_partials(bencher: Bencher, lg_k: u8) {
+ let partials = partials(lg_k, 400, 200);
+ bencher.bench_local(|| {
+ let mut union = HllUnion::new(lg_k).unwrap();
+ for partial in black_box(&partials) {
+ union.update(partial);
+ }
+ black_box(union.estimate());
+ black_box(union.to_sketch(HllType::Hll8))
+ });
+}
+
+#[divan::bench(args = [12, 18])]
+fn dense_partials(bencher: Bencher, lg_k: u8) {
+ let partials = partials(lg_k, 16, (1 << lg_k) / 4);
+ bencher.bench_local(|| {
+ let mut union = HllUnion::new(lg_k).unwrap();
+ for partial in black_box(&partials) {
+ union.update(partial);
+ }
+ black_box(union.estimate());
+ black_box(union.to_sketch(HllType::Hll8))
+ });
+}
+
+#[divan::bench(args = [12, 18])]
+fn dense_partials_with_queries(bencher: Bencher, lg_k: u8) {
+ let partials = partials(lg_k, 16, (1 << lg_k) / 4);
+ bencher.bench_local(|| {
+ let mut union = HllUnion::new(lg_k).unwrap();
+ for partial in black_box(&partials) {
+ union.update(partial);
+ black_box(union.estimate());
+ }
+ black_box(union.to_sketch(HllType::Hll8))
+ });
+}
+
+#[divan::bench(args = [12, 18])]
+fn downsampled_dense_partials(bencher: Bencher, lg_k: u8) {
+ let partials = partials(lg_k + 1, 16, (1 << lg_k) / 2);
+ bencher.bench_local(|| {
+ let mut union = HllUnion::new(lg_k).unwrap();
+ for partial in black_box(&partials) {
+ union.update(partial);
+ }
+ black_box(union.estimate());
+ black_box(union.to_sketch(HllType::Hll8))
+ });
+}
diff --git a/datasketches/src/hll/array8.rs b/datasketches/src/hll/array8.rs
index 1269d17..6586104 100644
--- a/datasketches/src/hll/array8.rs
+++ b/datasketches/src/hll/array8.rs
@@ -15,6 +15,8 @@
// specific language governing permissions and limitations
// under the License.
+use std::sync::OnceLock;
+
use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::assert::insufficient_data;
@@ -33,14 +35,30 @@ use crate::hll::serialization::TGT_HLL8;
use crate::hll::serialization::encode_mode_byte;
/// Registers stored one per byte.
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone)]
pub struct Array8 {
lg_config_k: u8,
bytes: Box<[u8]>,
+ /// Absent estimation data means a bulk merge invalidated HIP and the
register-derived fields.
+ /// Shared queries initialize it once; exclusive updates can maintain or
invalidate it.
+ estimation: OnceLock<Estimation>,
+}
+
+/// Zero-register count and estimator used for cardinality queries.
+#[derive(Debug, Clone, PartialEq)]
+struct Estimation {
num_zeros: u32,
estimator: Estimator,
}
+impl PartialEq for Array8 {
+ fn eq(&self, other: &Self) -> bool {
+ self.lg_config_k == other.lg_config_k
+ && self.bytes == other.bytes
+ && self.estimation() == other.estimation()
+ }
+}
+
impl Array8 {
pub fn new(lg_config_k: u8) -> Self {
let k = 1 << lg_config_k;
@@ -48,8 +66,10 @@ impl Array8 {
Self {
lg_config_k,
bytes: vec![0u8; k as usize].into_boxed_slice(),
- num_zeros: k,
- estimator: Estimator::new(lg_config_k),
+ estimation: OnceLock::from(Estimation {
+ num_zeros: k,
+ estimator: Estimator::new(lg_config_k),
+ }),
}
}
@@ -71,39 +91,58 @@ impl Array8 {
let old_value = self.get(slot);
if new_value > old_value {
- self.estimator
- .update(self.lg_config_k, old_value, new_value);
-
- self.put(slot, new_value);
-
- if old_value == 0 {
- self.num_zeros -= 1;
+ if let Some(estimation) = self.estimation.get_mut() {
+ estimation
+ .estimator
+ .update(self.lg_config_k, old_value, new_value);
+ if old_value == 0 {
+ estimation.num_zeros -= 1;
+ }
}
+ self.put(slot, new_value);
}
}
pub fn estimate(&self) -> f64 {
+ let Estimation {
+ num_zeros,
+ estimator,
+ } = self.estimation();
// Array8 doesn't use cur_min (always 0), so num_at_cur_min = num_zeros
- self.estimator.estimate(self.lg_config_k, 0, self.num_zeros)
+ estimator.estimate(self.lg_config_k, 0, *num_zeros)
}
pub fn composite_estimate(&self) -> f64 {
- self.estimator
- .composite_estimate(self.lg_config_k, 0, self.num_zeros)
+ let Estimation {
+ num_zeros,
+ estimator,
+ } = self.estimation();
+ estimator.composite_estimate(self.lg_config_k, 0, *num_zeros)
}
pub fn upper_bound(&self, num_std_dev: NumStdDev) -> f64 {
- self.estimator
- .upper_bound(self.lg_config_k, 0, self.num_zeros, num_std_dev)
+ let Estimation {
+ num_zeros,
+ estimator,
+ } = self.estimation();
+ estimator.upper_bound(self.lg_config_k, 0, *num_zeros, num_std_dev)
}
pub fn lower_bound(&self, num_std_dev: NumStdDev) -> f64 {
- self.estimator
- .lower_bound(self.lg_config_k, 0, self.num_zeros, num_std_dev)
+ let Estimation {
+ num_zeros,
+ estimator,
+ } = self.estimation();
+ estimator.lower_bound(self.lg_config_k, 0, *num_zeros, num_std_dev)
}
pub fn is_empty(&self) -> bool {
- self.num_zeros == (1 << self.lg_config_k)
+ if let Some(estimation) = self.estimation.get() {
+ return estimation.num_zeros == (1 << self.lg_config_k);
+ }
+ // Union checks emptiness between merges. A nonzero register answers
that without
+ // rebuilding all estimator fields and defeating deferred
reconstruction.
+ self.bytes.iter().all(|&value| value == 0)
}
pub fn values(&self) -> &[u8] {
@@ -115,22 +154,31 @@ impl Array8 {
}
pub fn estimate_state(&self) -> EstimateState {
- self.estimator.estimate_state()
+ self.estimation
+ .get()
+ .map_or(EstimateState::Composite, |estimation| {
+ estimation.estimator.estimate_state()
+ })
}
pub fn restore_estimate_state(&mut self, state: EstimateState) {
- self.estimator.restore_estimate_state(state);
+ if let Some(estimation) = self.estimation.get_mut() {
+ estimation.estimator.restore_estimate_state(state);
+ } else if let EstimateState::Hip(_) = state {
+ let mut estimation = self.rebuild_estimation();
+ estimation.estimator.restore_estimate_state(state);
+ self.estimation = OnceLock::from(estimation);
+ }
}
- /// Bypasses estimator updates. Call `rebuild_estimator_from_registers`
after all writes.
+ /// Bypasses estimator updates. Call `invalidate_estimator` after all
writes.
pub fn set_register(&mut self, slot: usize, value: u8) {
self.bytes[slot] = value;
}
- /// Rebuilds register-derived caches and invalidates HIP after bulk writes.
- pub fn rebuild_estimator_from_registers(&mut self) {
- self.rebuild_cached_values();
- self.estimator.invalidate_hip();
+ /// Invalidates HIP and defers rebuilding register-derived fields until a
query needs them.
+ pub fn invalidate_estimator(&mut self) {
+ self.estimation.take();
}
/// Merges registers and invalidates HIP because their update order is
unavailable.
@@ -145,8 +193,7 @@ impl Array8 {
self.bytes[i] = self.bytes[i].max(val);
}
- self.rebuild_cached_values();
- self.estimator.invalidate_hip();
+ self.invalidate_estimator();
}
/// Register values come from a separate hash word, so folding slot
indices needs no
@@ -169,13 +216,15 @@ impl Array8 {
self.bytes[dst_slot] = self.bytes[dst_slot].max(val);
}
- self.rebuild_cached_values();
- self.estimator.invalidate_hip();
+ self.invalidate_estimator();
}
- /// Rebuilds register-derived caches without changing the estimate state.
- fn rebuild_cached_values(&mut self) {
- self.num_zeros = self.bytes.iter().filter(|&&v| v == 0).count() as u32;
+ fn estimation(&self) -> &Estimation {
+ self.estimation.get_or_init(|| self.rebuild_estimation())
+ }
+
+ fn rebuild_estimation(&self) -> Estimation {
+ let num_zeros = self.bytes.iter().filter(|&&v| v == 0).count() as u32;
let mut kxq0_sum = 0.0;
let mut kxq1_sum = 0.0;
@@ -190,7 +239,13 @@ impl Array8 {
}
}
- self.estimator.restore_kxq(kxq0_sum, kxq1_sum);
+ let mut estimator = Estimator::new(self.lg_config_k);
+ estimator.restore_kxq(kxq0_sum, kxq1_sum);
+ estimator.invalidate_hip();
+ Estimation {
+ num_zeros,
+ estimator,
+ }
}
pub fn deserialize_registers(
@@ -236,12 +291,15 @@ impl Array8 {
Ok(Self {
lg_config_k,
bytes: data.into_boxed_slice(),
- num_zeros,
- estimator,
+ estimation: OnceLock::from(Estimation {
+ num_zeros,
+ estimator,
+ }),
})
}
pub fn serialize(&self, lg_config_k: u8) -> Vec<u8> {
+ let estimation = self.estimation();
let k = 1 << lg_config_k;
let total_size = HLL_PREAMBLE_SIZE + k as usize;
let mut bytes = SketchBytes::with_capacity(total_size);
@@ -253,7 +311,7 @@ impl Array8 {
bytes.write_u8(0); // unused for HLL mode
let mut flags = 0u8;
- if self.estimator.uses_composite_estimate() {
+ if estimation.estimator.uses_composite_estimate() {
flags |= OUT_OF_ORDER_FLAG_MASK;
}
bytes.write_u8(flags);
@@ -263,12 +321,12 @@ impl Array8 {
bytes.write_u8(encode_mode_byte(CUR_MODE_HLL, TGT_HLL8));
- bytes.write_f64_le(self.estimator.hip_accum());
- bytes.write_f64_le(self.estimator.kxq0());
- bytes.write_f64_le(self.estimator.kxq1());
+ bytes.write_f64_le(estimation.estimator.hip_accum());
+ bytes.write_f64_le(estimation.estimator.kxq0());
+ bytes.write_f64_le(estimation.estimator.kxq1());
// Write num_at_cur_min (num_zeros for Array8)
- bytes.write_u32_le(self.num_zeros);
+ bytes.write_u32_le(estimation.num_zeros);
// Write aux_count (always 0 for Array8)
bytes.write_u32_le(0);
@@ -398,11 +456,11 @@ mod tests {
arr.update(Coupon::pack(1, 50)); // value >= 32, goes to kxq1
// Initial kxq0 = 256 (all zeros = 1.0 each)
- assert_that!(arr.estimator.kxq0(), lt(256.0));
+ assert_that!(arr.estimation().estimator.kxq0(), lt(256.0));
// kxq1 should have a positive value (from 1/2^50)
- assert_that!(arr.estimator.kxq1(), gt(0.0));
- assert_that!(arr.estimator.kxq1(), lt(1e-10));
+ assert_that!(arr.estimation().estimator.kxq1(), gt(0.0));
+ assert_that!(arr.estimation().estimator.kxq1(), lt(1e-10));
}
#[test]
@@ -442,9 +500,9 @@ mod tests {
assert_eq!(dst.get(3), 40, "dst[3] got new value");
// Bulk merges require composite estimation.
- assert!(dst.estimator.uses_composite_estimate());
+ assert!(dst.estimation().estimator.uses_composite_estimate());
- assert_eq!(dst.num_zeros, 12);
+ assert_eq!(dst.estimation().num_zeros, 12);
}
#[test]
@@ -468,7 +526,7 @@ mod tests {
assert_eq!(dst.get(1), 30, "dst[1] = max(20, 18, 30)");
// Bulk merges require composite estimation.
- assert!(dst.estimator.uses_composite_estimate());
+ assert!(dst.estimation().estimator.uses_composite_estimate());
}
#[test]
@@ -490,18 +548,28 @@ mod tests {
}
#[test]
- fn test_rebuild_cached_values() {
+ fn test_rebuild_estimation() {
let mut arr = Array8::new(4); // 16 slots
arr.put(0, 10);
arr.put(1, 20);
arr.put(2, 30);
- arr.num_zeros = 999;
-
- arr.rebuild_cached_values();
+ arr.put(3, 31);
+ arr.put(4, 32);
+ arr.put(5, 63);
+ arr.invalidate_estimator();
- assert_eq!(arr.num_zeros, 13);
+ let estimation = arr.estimation();
+ assert_eq!(estimation.num_zeros, 10);
+ assert_eq!(
+ estimation.estimator.kxq0(),
+ 10.0 + 2_f64.powi(-10) + 2_f64.powi(-20) + 2_f64.powi(-30) +
2_f64.powi(-31)
+ );
+ assert_eq!(
+ estimation.estimator.kxq1(),
+ 2_f64.powi(-32) + 2_f64.powi(-63)
+ );
}
#[test]
diff --git a/datasketches/src/hll/estimator.rs
b/datasketches/src/hll/estimator.rs
index a72fcca..631d31f 100644
--- a/datasketches/src/hll/estimator.rs
+++ b/datasketches/src/hll/estimator.rs
@@ -42,7 +42,7 @@ pub enum EstimateState {
/// precision when large and small contributions coexist.
#[derive(Debug, Clone, PartialEq)]
pub struct Estimator {
- estimate_state: EstimateState,
+ state: EstimateState,
/// KxQ register for values < 32 (larger inverse powers)
kxq0: f64,
/// KxQ register for values >= 32 (tiny inverse powers)
@@ -53,7 +53,7 @@ impl Estimator {
pub fn new(lg_config_k: u8) -> Self {
let k = 1 << lg_config_k;
Self {
- estimate_state: EstimateState::Hip(0.0),
+ state: EstimateState::Hip(0.0),
kxq0: k as f64, // All registers start at 0, so kxq0 = k * (1/2^0)
= k
kxq1: 0.0,
}
@@ -61,16 +61,12 @@ impl Estimator {
/// Restores estimator fields from an HLL serialization preamble.
pub fn from_serialized(hip_accum: f64, kxq0: f64, kxq1: f64, out_of_order:
bool) -> Self {
- let estimate_state = if out_of_order {
+ let state = if out_of_order {
EstimateState::Composite
} else {
EstimateState::Hip(hip_accum)
};
- Self {
- estimate_state,
- kxq0,
- kxq1,
- }
+ Self { state, kxq0, kxq1 }
}
/// Applies a register increase; requires `new_value > old_value`.
@@ -78,7 +74,7 @@ impl Estimator {
let k = (1 << lg_config_k) as f64;
// HIP must use the KxQ sums from before this register update.
- if let EstimateState::Hip(hip_accum) = &mut self.estimate_state {
+ if let EstimateState::Hip(hip_accum) = &mut self.state {
*hip_accum += k / (self.kxq0 + self.kxq1);
}
@@ -103,7 +99,7 @@ impl Estimator {
/// For `Array6`/`Array8`, pass zero for `cur_min` and the zero-register
count for
/// `num_at_cur_min`. `Array4` tracks its actual minimum and its count.
pub fn estimate(&self, lg_config_k: u8, cur_min: u8, num_at_cur_min: u32)
-> f64 {
- match self.estimate_state {
+ match self.state {
EstimateState::Hip(hip_accum) => hip_accum,
EstimateState::Composite => {
self.composite_estimate(lg_config_k, cur_min, num_at_cur_min)
@@ -234,7 +230,7 @@ impl Estimator {
}
pub fn hip_accum(&self) -> f64 {
- match self.estimate_state {
+ match self.state {
EstimateState::Hip(hip_accum) => hip_accum,
EstimateState::Composite => 0.0,
}
@@ -249,21 +245,21 @@ impl Estimator {
}
pub fn uses_composite_estimate(&self) -> bool {
- matches!(self.estimate_state, EstimateState::Composite)
+ matches!(self.state, EstimateState::Composite)
}
pub fn estimate_state(&self) -> EstimateState {
- self.estimate_state
+ self.state
}
/// Restores estimate state after copying or transforming the same logical
sketch.
pub fn restore_estimate_state(&mut self, state: EstimateState) {
- self.estimate_state = state;
+ self.state = state;
}
/// Invalidates HIP after registers from independent histories are merged.
pub fn invalidate_hip(&mut self) {
- self.estimate_state = EstimateState::Composite;
+ self.state = EstimateState::Composite;
}
/// Replaces register-derived KxQ values after a bulk register operation.
diff --git a/datasketches/src/hll/union.rs b/datasketches/src/hll/union.rs
index b245fa7..f942fc0 100644
--- a/datasketches/src/hll/union.rs
+++ b/datasketches/src/hll/union.rs
@@ -166,15 +166,10 @@ impl HllUnion {
match self.gadget.mode() {
Mode::Array8(old_gadget) => {
- merge_array_with_downsample(
- &mut new_array,
- src_lg_k,
- &Mode::Array8(old_gadget.clone()),
- dst_lg_k,
- );
+ new_array.merge_array_with_downsample(old_gadget.values(),
dst_lg_k);
}
_ => {
- unreachable!("gadget mode changed unexpectedly; should
never be Array4/Array6")
+ unreachable!("gadget mode changed unexpectedly; should
never be Array4/Array6");
}
}
@@ -186,7 +181,7 @@ impl HllUnion {
merge_array_into_array8(dst_array, dst_lg_k, src_mode,
src_lg_k);
}
_ => {
- unreachable!("gadget mode changed unexpectedly; should
never be Array4/Array6")
+ unreachable!("gadget mode changed unexpectedly; should
never be Array4/Array6");
}
}
}
@@ -249,6 +244,29 @@ impl HllUnion {
}
}
+ /// Serializes the union's result as an [`HllType::Hll8`] sketch.
+ ///
+ /// Produces the same bytes as `to_sketch(HllType::Hll8).serialize()`
without copying an
+ /// intermediate sketch. The image retains the effective `lg_k` and
estimate, but not the
+ /// union's configured maximum `lg_k`. It can be read with
[`HllSketch::deserialize`].
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::hll::HllSketch;
+ /// use datasketches::hll::HllUnion;
+ ///
+ /// let mut union = HllUnion::new(12).unwrap();
+ /// union.update_value("apple");
+ /// let mut partial = HllSketch::deserialize(&union.serialize()).unwrap();
+ /// partial.update("banana");
+ /// union.update(&partial);
+ /// assert!((union.estimate() - 2.0).abs() < 0.01);
+ /// ```
+ pub fn serialize(&self) -> Vec<u8> {
+ self.gadget.serialize()
+ }
+
/// Returns the union's current effective `lg_k`.
pub fn lg_config_k(&self) -> u8 {
self.gadget.lg_config_k()
@@ -468,7 +486,7 @@ fn merge_array46_same_lgk(dst: &mut Array8, num_registers:
usize, get_value: imp
dst.set_register(slot, val);
}
}
- dst.rebuild_estimator_from_registers();
+ dst.invalidate_estimator();
}
/// Merging independent register histories invalidates the HIP accumulator.
@@ -506,7 +524,7 @@ fn merge_array46_with_downsample(
}
}
}
- dst.rebuild_estimator_from_registers();
+ dst.invalidate_estimator();
}
/// Multiple source registers map to each destination register via masking.
@@ -586,17 +604,17 @@ fn copy_or_downsample(src_mode: &Mode, src_lg_k: u8,
tgt_lg_k: u8) -> Array8 {
let estimate_state = get_array_estimate_state(src_mode);
let mut result = if src_lg_k <= tgt_lg_k {
- let mut result = Array8::new(src_lg_k);
-
match src_mode {
- Mode::Array8(src) => {
- result.merge_array_same_lgk(src.values());
- }
+ Mode::Array8(src) => src.clone(),
Mode::Array6(src) => {
+ let mut result = Array8::new(src_lg_k);
copy_array46_via_coupons(&mut result, src.num_registers(),
|slot| src.get(slot));
+ result
}
Mode::Array4(src) => {
+ let mut result = Array8::new(src_lg_k);
copy_array46_via_coupons(&mut result, src.num_registers(),
|slot| src.get(slot));
+ result
}
Mode::List { .. } | Mode::Set { .. } => {
unreachable!(
@@ -604,8 +622,6 @@ fn copy_or_downsample(src_mode: &Mode, src_lg_k: u8,
tgt_lg_k: u8) -> Array8 {
);
}
}
-
- result
} else {
let mut result = Array8::new(tgt_lg_k);
merge_array_with_downsample(&mut result, tgt_lg_k, src_mode, src_lg_k);
diff --git a/tests-integration/tests/hll_test/union.rs
b/tests-integration/tests/hll_test/union.rs
index c61a171..5f807d8 100644
--- a/tests-integration/tests/hll_test/union.rs
+++ b/tests-integration/tests/hll_test/union.rs
@@ -745,3 +745,116 @@ fn
test_downsampling_single_hll_input_preserves_estimate() {
assert_eq!(union.estimate(), sketch.estimate(), "{hll_type:?}
estimate");
}
}
+
+#[test]
+fn test_copied_hll8_input_preserves_subsequent_updates() {
+ for lg_max_k in [10, 12] {
+ for merged in [false, true] {
+ let mut source = make_hll_sketch(HllType::Hll8, 10, 0, 2_000);
+ if merged {
+ let mut union = HllUnion::new(10).unwrap();
+ union.update(&source);
+ union.update(&make_hll_sketch(HllType::Hll8, 10, 1_000,
3_000));
+ source = union.to_sketch(HllType::Hll8);
+ }
+ let mut union = HllUnion::new(lg_max_k).unwrap();
+ union.update(&source);
+ let mut expected = source.clone();
+
+ // Copying must retain both the estimate history and the caches
used by later updates.
+ for value in 2_000..5_000_u64 {
+ union.update_value(value);
+ expected.update(value);
+ }
+ let result = union.to_sketch(HllType::Hll8);
+ assert_same_estimate_and_bounds(&result, &expected);
+ assert_eq!(result.serialize(), expected.serialize());
+ assert_eq!(union.lg_config_k(), source.lg_config_k());
+ }
+ }
+}
+
+#[test]
+fn test_union_query_timing_does_not_change_mixed_updates() {
+ let mut queried = HllUnion::new(12).unwrap();
+ let mut deferred = queried.clone();
+ let inputs = [
+ (HllType::Hll8, 12),
+ (HllType::Hll4, 12),
+ (HllType::Hll6, 14),
+ (HllType::Hll8, 10),
+ (HllType::Hll4, 8),
+ ];
+ for (index, (hll_type, lg_k)) in inputs.into_iter().enumerate() {
+ let start = index as u64 * 10_000;
+ let source = make_hll_sketch(hll_type, lg_k, start, start + 5_000);
+ queried.update(&source);
+ deferred.update(&source);
+ assert!(!deferred.is_empty());
+
+ // Queries refresh one accumulator between merges; the other keeps
accepting updates.
+ assert_same_estimate_and_bounds(
+ &queried.to_sketch(HllType::Hll8),
+ &queried.to_sketch(HllType::Hll4),
+ );
+ let restored = HllSketch::deserialize(&queried.serialize()).unwrap();
+ assert_eq!(restored.composite_estimate(),
queried.composite_estimate());
+ for value in start + 5_000..start + 5_100 {
+ queried.update_value(value);
+ deferred.update_value(value);
+ }
+ }
+
+ assert_eq!(queried.serialize(), deferred.serialize());
+ assert_same_estimate_and_bounds(
+ &queried.to_sketch(HllType::Hll8),
+ &deferred.to_sketch(HllType::Hll8),
+ );
+
+ // A copied result can be merged again before either its source or the
copy is queried.
+ let source = make_hll_sketch(HllType::Hll8, 8, 50_000, 55_000);
+ deferred.update(&source);
+ let result = deferred.to_sketch(HllType::Hll8);
+ let mut copied = HllUnion::new(12).unwrap();
+ copied.update(&result);
+ for value in 55_000..56_000_u64 {
+ copied.update_value(value);
+ deferred.update_value(value);
+ }
+ assert_eq!(copied.serialize(), deferred.serialize());
+}
+
+#[test]
+fn test_union_supports_shared_queries_after_dense_merges() {
+ let mut union = HllUnion::new(12).unwrap();
+ for index in 0..3 {
+ union.update(&make_hll_sketch(
+ HllType::Hll8,
+ 12,
+ index * 5_000,
+ (index + 1) * 5_000,
+ ));
+ }
+ let expected = union.to_sketch(HllType::Hll8);
+ let bytes = expected.serialize();
+ let barrier = std::sync::Barrier::new(4);
+
+ std::thread::scope(|scope| {
+ for _ in 0..4 {
+ scope.spawn(|| {
+ barrier.wait();
+ assert_eq!(union.estimate(), expected.estimate());
+ assert_eq!(union.composite_estimate(),
expected.composite_estimate());
+ assert_eq!(
+ union.lower_bound(NumStdDev::Two),
+ expected.lower_bound(NumStdDev::Two)
+ );
+ assert_eq!(
+ union.upper_bound(NumStdDev::Two),
+ expected.upper_bound(NumStdDev::Two)
+ );
+ assert_eq!(union.serialize(), bytes);
+ });
+ }
+ });
+}
diff --git a/tests-integration/tests/serde_tests/hll.rs
b/tests-integration/tests/serde_tests/hll.rs
index 6f4485b..ed0dd41 100644
--- a/tests-integration/tests/serde_tests/hll.rs
+++ b/tests-integration/tests/serde_tests/hll.rs
@@ -21,6 +21,7 @@ use std::path::PathBuf;
use datasketches::hash::value::natural_extend;
use datasketches::hll::HllSketch;
use datasketches::hll::HllType;
+use datasketches::hll::HllUnion;
use googletest::assert_that;
use googletest::prelude::all;
use googletest::prelude::ge;
@@ -30,6 +31,40 @@ use googletest::prelude::near;
use crate::serialization_test_data;
+#[test]
+fn union_serialization_preserves_result_and_subsequent_updates() {
+ for hll_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
+ for count in [0, 4, 100, 10_000_u64] {
+ let mut source = HllSketch::new(12, hll_type).unwrap();
+ for value in 0..count {
+ source.update(value);
+ }
+ for lg_max_k in [8, 12, 14] {
+ let mut union = HllUnion::new(lg_max_k).unwrap();
+ union.update(&source);
+ let bytes = union.serialize();
+ assert_eq!(bytes, union.to_sketch(HllType::Hll8).serialize());
+
+ let mut restored = HllSketch::deserialize(&bytes).unwrap();
+ assert_eq!(restored.target_type(), HllType::Hll8);
+ assert_eq!(restored.lg_config_k(), union.lg_config_k());
+ assert_eq!(restored.estimate(), union.estimate());
+
+ for value in count..count + 1_000 {
+ union.update_value(value);
+ restored.update(value);
+ }
+ assert_eq!(union.to_sketch(HllType::Hll8), restored);
+
+ union.reset();
+ let empty =
HllSketch::deserialize(&union.serialize()).unwrap();
+ assert!(empty.is_empty());
+ assert_eq!(empty.lg_config_k(), lg_max_k);
+ }
+ }
+ }
+}
+
fn test_sketch_file(path: PathBuf, expected_cardinality: usize, expected_lg_k:
u8) {
let expected = expected_cardinality as f64;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]