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 4987426 feat(hll,theta): support target HllType in
HllUnion::serialize and add ThetaUnion::serialize_compressed (#369)
4987426 is described below
commit 498742694821984cccadd97c3acff451afdf3e9c
Author: tison <[email protected]>
AuthorDate: Sun Nov 15 19:09:32 2026 +0800
feat(hll,theta): support target HllType in HllUnion::serialize and add
ThetaUnion::serialize_compressed (#369)
---
CHANGELOG.md | 2 +-
benchmarks/hll/serde.rs | 55 ++--
datasketches/src/hll/array4.rs | 44 +---
datasketches/src/hll/array6.rs | 46 +---
datasketches/src/hll/array8.rs | 207 +++++++++++++--
datasketches/src/hll/serialization.rs | 42 +++
datasketches/src/hll/union.rs | 292 +++++++++------------
.../src/thetafamily/theta/serialization.rs | 90 +++++++
datasketches/src/thetafamily/theta/sketch.rs | 88 +------
datasketches/src/thetafamily/theta/union.rs | 42 ++-
tests-integration/tests/hll_test/union.rs | 37 ++-
tests-integration/tests/serde_tests/hll.rs | 176 ++++++++++++-
tests-integration/tests/serde_tests/theta.rs | 95 +++++++
13 files changed, 830 insertions(+), 386 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index a6414f7..cebd4c3 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -19,7 +19,7 @@ All significant changes to this project will be documented in
this file.
### New features
-* Add `CpcUnion::serialize`, `HllUnion::serialize`, `ThetaUnion::serialize`,
and `TupleUnion::serialize` to encode union results without calling
`to_sketch`. Direct serialization avoids intermediate sketch allocations for
`HllUnion` and `CpcUnion`, writes an `HllType::Hll8` image at the union's
effective `lg_k` for `HllUnion`, and encodes `TupleUnion` summaries without
requiring `Clone` or cloning heap-backed summaries.
+* Add `CpcUnion::serialize`, `HllUnion::serialize`, `ThetaUnion::serialize`,
`ThetaUnion::serialize_compressed`, and `TupleUnion::serialize` to encode union
results without calling `to_sketch`. Direct serialization avoids intermediate
sketch allocations for `HllUnion` and `CpcUnion`, lets `HllUnion::serialize`
target any `HllType` (`Hll4`, `Hll6`, or `Hll8`) at the union's effective
`lg_k`, supports v4 compressed output via `ThetaUnion::serialize_compressed`,
and encodes `TupleUnion` sum [...]
* Add `XorFilter`, `XorFilterBuilder`, and `XorFilterType` behind the `xor`
feature for immutable membership queries on values or precomputed hashes.
Filters support 8-, 16-, and 32-bit fingerprints and can be serialized for
later queries.
### Improvements
diff --git a/benchmarks/hll/serde.rs b/benchmarks/hll/serde.rs
index de9fa35..d193703 100644
--- a/benchmarks/hll/serde.rs
+++ b/benchmarks/hll/serde.rs
@@ -30,35 +30,42 @@ fn union(rows: u64) -> HllUnion {
union
}
-fn serialize_union(bencher: Bencher, rows: u64) {
+fn serialize_union(bencher: Bencher, rows: u64, hll_type: HllType, direct:
bool) {
let union = union(rows);
- bencher.bench_local(|| black_box(&union).serialize());
-}
-
-fn serialize_union_via_sketch(bencher: Bencher, rows: u64) {
- let union = union(rows);
- bencher.bench_local(||
black_box(&union).to_sketch(HllType::Hll8).serialize());
+ if direct {
+ bencher.bench_local(|| black_box(&union).serialize(hll_type));
+ } else {
+ bencher.bench_local(||
black_box(&union).to_sketch(hll_type).serialize());
+ }
}
pub fn register(runner: &mut Runner) {
- let cases = &[
- (0, 15_000_000),
- (4, 12_000_000),
- (100, 2_000_000),
- (80_000, 90_000),
+ let targets = [
+ ("hll4", HllType::Hll4, 500),
+ ("hll6", HllType::Hll6, 600),
+ ("hll8", HllType::Hll8, 50_000),
];
- for &(rows, rounds) in cases {
- runner.case(
- format!("hll::serde::serialize_union/{rows:?}"),
- rounds,
- |b| serialize_union(b, rows),
- );
- }
- for &(rows, rounds) in cases {
- runner.case(
- format!("hll::serde::serialize_union_via_sketch/{rows:?}"),
- rounds,
- |b| serialize_union_via_sketch(b, rows),
+ let sparse_cases = [(0, 10_000_000), (4, 8_000_000), (100, 1_500_000)];
+ for &(label, hll_type, dense_rounds) in &targets {
+ for &(rows, rounds) in &sparse_cases {
+ runner.compare(
+ &format!("hll::serde::serialize_union/{label}/{rows:?}"),
+ rounds,
+ &[
+ ("via_sketch", &|b| serialize_union(b, rows, hll_type,
false)),
+ ("direct", &|b| serialize_union(b, rows, hll_type, true)),
+ ],
+ );
+ }
+ runner.compare(
+ &format!("hll::serde::serialize_union/{label}/80000"),
+ dense_rounds,
+ &[
+ ("via_sketch", &|b| {
+ serialize_union(b, 80_000, hll_type, false)
+ }),
+ ("direct", &|b| serialize_union(b, 80_000, hll_type, true)),
+ ],
);
}
}
diff --git a/datasketches/src/hll/array4.rs b/datasketches/src/hll/array4.rs
index 4190a3f..28daa80 100644
--- a/datasketches/src/hll/array4.rs
+++ b/datasketches/src/hll/array4.rs
@@ -18,24 +18,18 @@
use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::assert::insufficient_data;
-use crate::codec::family::Family;
use crate::common::NumStdDev;
use crate::error::Error;
use crate::hll::Coupon;
+use crate::hll::HllType;
use crate::hll::aux_map::AuxMap;
use crate::hll::estimator::EstimateState;
use crate::hll::estimator::Estimator;
-use crate::hll::serialization::COMPACT_FLAG_MASK;
use crate::hll::serialization::COUPON_SIZE_BYTES;
-use crate::hll::serialization::CUR_MODE_HLL;
use crate::hll::serialization::HLL_PREAMBLE_SIZE;
-use crate::hll::serialization::HLL_PREINTS;
-use crate::hll::serialization::OUT_OF_ORDER_FLAG_MASK;
-use crate::hll::serialization::SERIAL_VERSION;
-use crate::hll::serialization::TGT_HLL4;
-use crate::hll::serialization::encode_mode_byte;
+use crate::hll::serialization::write_hll_preamble;
-const AUX_TOKEN: u8 = 15;
+pub const AUX_TOKEN: u8 = 15;
#[derive(Clone, Copy)]
pub enum AuxFormat {
@@ -386,29 +380,15 @@ impl Array4 {
let total_size = HLL_PREAMBLE_SIZE + num_bytes + (aux_count as usize *
COUPON_SIZE_BYTES);
let mut bytes = SketchBytes::with_capacity(total_size);
- bytes.write_u8(HLL_PREINTS);
- bytes.write_u8(SERIAL_VERSION);
- bytes.write_u8(Family::HLL.id);
- bytes.write_u8(lg_config_k);
- bytes.write_u8(0); // lg_arr is unused for compact auxiliary storage.
-
- let mut flags = COMPACT_FLAG_MASK;
- if self.estimator.uses_composite_estimate() {
- flags |= OUT_OF_ORDER_FLAG_MASK;
- }
- bytes.write_u8(flags);
-
- bytes.write_u8(self.cur_min);
-
- bytes.write_u8(encode_mode_byte(CUR_MODE_HLL, TGT_HLL4));
-
- bytes.write_f64_le(self.estimator.hip_accum());
- bytes.write_f64_le(self.estimator.kxq0());
- bytes.write_f64_le(self.estimator.kxq1());
-
- bytes.write_u32_le(self.num_at_cur_min);
-
- bytes.write_u32_le(aux_count);
+ write_hll_preamble(
+ &mut bytes,
+ lg_config_k,
+ HllType::Hll4,
+ self.cur_min,
+ self.num_at_cur_min,
+ aux_count,
+ &self.estimator,
+ );
bytes.write(&self.bytes);
diff --git a/datasketches/src/hll/array6.rs b/datasketches/src/hll/array6.rs
index 636da15..b1fe163 100644
--- a/datasketches/src/hll/array6.rs
+++ b/datasketches/src/hll/array6.rs
@@ -18,19 +18,14 @@
use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::assert::insufficient_data;
-use crate::codec::family::Family;
use crate::common::NumStdDev;
use crate::error::Error;
use crate::hll::Coupon;
+use crate::hll::HllType;
use crate::hll::estimator::EstimateState;
use crate::hll::estimator::Estimator;
-use crate::hll::serialization::CUR_MODE_HLL;
use crate::hll::serialization::HLL_PREAMBLE_SIZE;
-use crate::hll::serialization::HLL_PREINTS;
-use crate::hll::serialization::OUT_OF_ORDER_FLAG_MASK;
-use crate::hll::serialization::SERIAL_VERSION;
-use crate::hll::serialization::TGT_HLL6;
-use crate::hll::serialization::encode_mode_byte;
+use crate::hll::serialization::write_hll_preamble;
const VAL_MASK_6: u16 = 0x3F;
@@ -201,32 +196,15 @@ impl Array6 {
let total_size = HLL_PREAMBLE_SIZE + num_bytes;
let mut bytes = SketchBytes::with_capacity(total_size);
- bytes.write_u8(HLL_PREINTS);
- bytes.write_u8(SERIAL_VERSION);
- bytes.write_u8(Family::HLL.id);
- bytes.write_u8(lg_config_k);
- bytes.write_u8(0); // unused for HLL mode
-
- let mut flags = 0u8;
- if self.estimator.uses_composite_estimate() {
- flags |= OUT_OF_ORDER_FLAG_MASK;
- }
- bytes.write_u8(flags);
-
- // cur_min is always 0 for Array6
- bytes.write_u8(0);
-
- bytes.write_u8(encode_mode_byte(CUR_MODE_HLL, TGT_HLL6));
-
- bytes.write_f64_le(self.estimator.hip_accum());
- bytes.write_f64_le(self.estimator.kxq0());
- bytes.write_f64_le(self.estimator.kxq1());
-
- // Write num_at_cur_min (num_zeros for Array6)
- bytes.write_u32_le(self.num_zeros);
-
- // Write aux_count (always 0 for Array6)
- bytes.write_u32_le(0);
+ write_hll_preamble(
+ &mut bytes,
+ lg_config_k,
+ HllType::Hll6,
+ 0,
+ self.num_zeros,
+ 0,
+ &self.estimator,
+ );
bytes.write(&self.bytes);
@@ -239,7 +217,7 @@ impl Array6 {
}
}
-fn num_bytes_for_k(k: u32) -> usize {
+pub fn num_bytes_for_k(k: u32) -> usize {
// The final register's 16-bit read/write window needs one padding byte.
(((k * 3) >> 2) + 1) as usize
}
diff --git a/datasketches/src/hll/array8.rs b/datasketches/src/hll/array8.rs
index 6586104..f45fdae 100644
--- a/datasketches/src/hll/array8.rs
+++ b/datasketches/src/hll/array8.rs
@@ -20,19 +20,17 @@ use std::sync::OnceLock;
use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::assert::insufficient_data;
-use crate::codec::family::Family;
use crate::common::NumStdDev;
use crate::error::Error;
use crate::hll::Coupon;
+use crate::hll::HllType;
+use crate::hll::array4::AUX_TOKEN;
+use crate::hll::array6::num_bytes_for_k;
use crate::hll::estimator::EstimateState;
use crate::hll::estimator::Estimator;
-use crate::hll::serialization::CUR_MODE_HLL;
+use crate::hll::serialization::COUPON_SIZE_BYTES;
use crate::hll::serialization::HLL_PREAMBLE_SIZE;
-use crate::hll::serialization::HLL_PREINTS;
-use crate::hll::serialization::OUT_OF_ORDER_FLAG_MASK;
-use crate::hll::serialization::SERIAL_VERSION;
-use crate::hll::serialization::TGT_HLL8;
-use crate::hll::serialization::encode_mode_byte;
+use crate::hll::serialization::write_hll_preamble;
/// Registers stored one per byte.
#[derive(Debug, Clone)]
@@ -300,38 +298,102 @@ impl Array8 {
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 k = 1usize << lg_config_k;
+ let total_size = HLL_PREAMBLE_SIZE + k;
let mut bytes = SketchBytes::with_capacity(total_size);
- bytes.write_u8(HLL_PREINTS);
- bytes.write_u8(SERIAL_VERSION);
- bytes.write_u8(Family::HLL.id);
- bytes.write_u8(lg_config_k);
- bytes.write_u8(0); // unused for HLL mode
+ write_hll_preamble(
+ &mut bytes,
+ lg_config_k,
+ HllType::Hll8,
+ 0,
+ estimation.num_zeros,
+ 0,
+ &estimation.estimator,
+ );
+
+ bytes.write(&self.bytes);
- let mut flags = 0u8;
- if estimation.estimator.uses_composite_estimate() {
- flags |= OUT_OF_ORDER_FLAG_MASK;
+ bytes.into_bytes()
+ }
+
+ pub fn serialize_as(&self, lg_config_k: u8, hll_type: HllType) -> Vec<u8> {
+ match hll_type {
+ HllType::Hll4 => self.serialize_as_hll4(lg_config_k),
+ HllType::Hll6 => self.serialize_as_hll6(lg_config_k),
+ HllType::Hll8 => self.serialize(lg_config_k),
}
- bytes.write_u8(flags);
+ }
- // cur_min is always 0 for Array8
+ fn serialize_as_hll6(&self, lg_config_k: u8) -> Vec<u8> {
+ let estimation = self.estimation();
+ let k = 1u32 << lg_config_k;
+ let num_bytes = num_bytes_for_k(k);
+ let total_size = HLL_PREAMBLE_SIZE + num_bytes;
+ let mut bytes = SketchBytes::with_capacity(total_size);
+
+ write_hll_preamble(
+ &mut bytes,
+ lg_config_k,
+ HllType::Hll6,
+ 0,
+ estimation.num_zeros,
+ 0,
+ &estimation.estimator,
+ );
+
+ for chunk in self.bytes.chunks_exact(4) {
+ let v0 = chunk[0].min(63);
+ let v1 = chunk[1].min(63);
+ let v2 = chunk[2].min(63);
+ let v3 = chunk[3].min(63);
+ bytes.write(&[v0 | (v1 << 6), (v1 >> 2) | (v2 << 4), (v2 >> 4) |
(v3 << 2)]);
+ }
+ // Array6 reads and writes 16-bit windows and expects one trailing
padding byte.
bytes.write_u8(0);
- bytes.write_u8(encode_mode_byte(CUR_MODE_HLL, TGT_HLL8));
+ bytes.into_bytes()
+ }
+
+ fn serialize_as_hll4(&self, lg_config_k: u8) -> Vec<u8> {
+ let estimation = self.estimation();
+ let k = 1usize << lg_config_k;
- bytes.write_f64_le(estimation.estimator.hip_accum());
- bytes.write_f64_le(estimation.estimator.kxq0());
- bytes.write_f64_le(estimation.estimator.kxq1());
+ let cur_min = self.bytes.iter().copied().min().unwrap_or(0);
+ let mut num_at_cur_min = 0u32;
+ let mut aux_count = 0usize;
+ for &val in &self.bytes {
+ num_at_cur_min += u32::from(val == cur_min);
+ aux_count += usize::from(val - cur_min >= AUX_TOKEN);
+ }
- // Write num_at_cur_min (num_zeros for Array8)
- bytes.write_u32_le(estimation.num_zeros);
+ let num_bytes = k >> 1;
+ let total_size = HLL_PREAMBLE_SIZE + num_bytes + (aux_count *
COUPON_SIZE_BYTES);
+ let mut bytes = SketchBytes::with_capacity(total_size);
- // Write aux_count (always 0 for Array8)
- bytes.write_u32_le(0);
+ write_hll_preamble(
+ &mut bytes,
+ lg_config_k,
+ HllType::Hll4,
+ cur_min,
+ num_at_cur_min,
+ aux_count as u32,
+ &estimation.estimator,
+ );
- bytes.write(&self.bytes);
+ for pair in self.bytes.chunks_exact(2) {
+ let lo = (pair[0] - cur_min).min(AUX_TOKEN);
+ let hi = (pair[1] - cur_min).min(AUX_TOKEN);
+ bytes.write_u8(lo | (hi << 4));
+ }
+
+ if aux_count > 0 {
+ for (slot, &val) in self.bytes.iter().enumerate() {
+ if val - cur_min >= AUX_TOKEN {
+ bytes.write_u32_le(Coupon::pack(slot as u32, val).raw());
+ }
+ }
+ }
bytes.into_bytes()
}
@@ -600,4 +662,93 @@ mod tests {
);
}
}
+
+ #[test]
+ fn test_serialize_as_hll6_matches_array6_bytes() {
+ use crate::hll::HllSketch;
+
+ for lg_k in [4u8, 6, 8] {
+ let k = 1usize << lg_k;
+ let mut arr8 = Array8::new(lg_k);
+ let mut arr6 = crate::hll::array6::Array6::new(lg_k);
+ for slot in 0..k {
+ let val = ((slot * 7) % 64) as u8;
+ if val > 0 {
+ let coupon = Coupon::pack(slot as u32, val);
+ arr8.update(coupon);
+ arr6.update(coupon);
+ }
+ }
+ assert_eq!(arr8.serialize_as(lg_k, HllType::Hll6),
arr6.serialize(lg_k));
+
+ // Composite / out-of-order mode matches too.
+ arr8.invalidate_estimator();
+ arr6.restore_estimate_state(EstimateState::Composite);
+ assert_eq!(arr8.serialize_as(lg_k, HllType::Hll6),
arr6.serialize(lg_k));
+
+ let decoded = HllSketch::deserialize(&arr8.serialize_as(lg_k,
HllType::Hll6)).unwrap();
+ assert_eq!(decoded.estimate(), arr6.estimate());
+ assert_eq!(decoded.composite_estimate(),
arr6.composite_estimate());
+ }
+ }
+
+ #[test]
+ fn test_serialize_as_hll4_handles_shifted_cur_min_and_multi_aux() {
+ use crate::hll::HllSketch;
+ use crate::hll::array4::Array4;
+
+ let lg_k = 4u8;
+ let k = 1usize << lg_k;
+ let mut arr8 = Array8::new(lg_k);
+ let mut arr4 = Array4::new(lg_k);
+
+ // Set cur_min = 5, boundary delta 14 (slot 2 -> 19), and three
exceptions (slots 1, 7, 15).
+ let values = [5u8, 20, 19, 6, 5, 12, 8, 25, 9, 5, 18, 7, 11, 14, 15,
63];
+ assert_eq!(values.len(), k);
+ for (slot, &val) in values.iter().enumerate() {
+ let coupon = Coupon::pack(slot as u32, val);
+ arr8.update(coupon);
+ arr4.update(coupon);
+ }
+
+ let direct_bytes = arr8.serialize_as(lg_k, HllType::Hll4);
+ assert_eq!(direct_bytes[6], 5); // cur_min == 5
+ assert_eq!(
+ u32::from_le_bytes(direct_bytes[36..40].try_into().unwrap()),
+ 3
+ );
+
+ let decoded = HllSketch::deserialize(&direct_bytes).unwrap();
+ let expected = HllSketch::from_mode(lg_k,
crate::hll::mode::Mode::Array4(arr4.clone()));
+ assert_eq!(decoded, expected);
+ assert_eq!(decoded.estimate(), expected.estimate());
+ assert_eq!(decoded.composite_estimate(),
expected.composite_estimate());
+ for std_dev in [NumStdDev::One, NumStdDev::Two, NumStdDev::Three] {
+ assert_eq!(decoded.lower_bound(std_dev),
expected.lower_bound(std_dev));
+ assert_eq!(decoded.upper_bound(std_dev),
expected.upper_bound(std_dev));
+ }
+
+ // Composite / out-of-order state matches too.
+ arr8.invalidate_estimator();
+ arr4.restore_estimate_state(EstimateState::Composite);
+ let direct_ooo = arr8.serialize_as(lg_k, HllType::Hll4);
+ let decoded_ooo = HllSketch::deserialize(&direct_ooo).unwrap();
+ let expected_ooo = HllSketch::from_mode(lg_k,
crate::hll::mode::Mode::Array4(arr4));
+ assert_eq!(decoded_ooo, expected_ooo);
+ assert_eq!(decoded_ooo.estimate(), expected_ooo.estimate());
+ assert_eq!(
+ decoded_ooo.composite_estimate(),
+ expected_ooo.composite_estimate()
+ );
+ for std_dev in [NumStdDev::One, NumStdDev::Two, NumStdDev::Three] {
+ assert_eq!(
+ decoded_ooo.lower_bound(std_dev),
+ expected_ooo.lower_bound(std_dev)
+ );
+ assert_eq!(
+ decoded_ooo.upper_bound(std_dev),
+ expected_ooo.upper_bound(std_dev)
+ );
+ }
+ }
}
diff --git a/datasketches/src/hll/serialization.rs
b/datasketches/src/hll/serialization.rs
index 166753e..c982aad 100644
--- a/datasketches/src/hll/serialization.rs
+++ b/datasketches/src/hll/serialization.rs
@@ -18,6 +18,11 @@
//! HLL wire-format constants. Preamble lengths ending in `PREINTS` count
32-bit words;
//! those ending in `PREAMBLE_SIZE` count bytes.
+use crate::codec::SketchBytes;
+use crate::codec::family::Family;
+use crate::hll::HllType;
+use crate::hll::estimator::Estimator;
+
pub const SERIAL_VERSION: u8 = 1;
pub const EMPTY_FLAG_MASK: u8 = 4;
@@ -65,3 +70,40 @@ pub const TGT_HLL6: u8 = 1;
pub const TGT_HLL8: u8 = 2;
pub const COUPON_SIZE_BYTES: usize = 4;
+
+pub fn write_hll_preamble(
+ bytes: &mut SketchBytes,
+ lg_config_k: u8,
+ hll_type: HllType,
+ cur_min: u8,
+ num_at_cur_min: u32,
+ aux_count: u32,
+ estimator: &Estimator,
+) {
+ let (tgt_type, compact) = match hll_type {
+ HllType::Hll4 => (TGT_HLL4, true),
+ HllType::Hll6 => (TGT_HLL6, false),
+ HllType::Hll8 => (TGT_HLL8, false),
+ };
+
+ bytes.write_u8(HLL_PREINTS);
+ bytes.write_u8(SERIAL_VERSION);
+ bytes.write_u8(Family::HLL.id);
+ bytes.write_u8(lg_config_k);
+ bytes.write_u8(0); // unused in HLL6/HLL8 and compact HLL4
+
+ let mut flags = if compact { COMPACT_FLAG_MASK } else { 0 };
+ if estimator.uses_composite_estimate() {
+ flags |= OUT_OF_ORDER_FLAG_MASK;
+ }
+ bytes.write_u8(flags);
+ bytes.write_u8(cur_min);
+ bytes.write_u8(encode_mode_byte(CUR_MODE_HLL, tgt_type));
+
+ bytes.write_f64_le(estimator.hip_accum());
+ bytes.write_f64_le(estimator.kxq0());
+ bytes.write_f64_le(estimator.kxq1());
+
+ bytes.write_u32_le(num_at_cur_min);
+ bytes.write_u32_le(aux_count);
+}
diff --git a/datasketches/src/hll/union.rs b/datasketches/src/hll/union.rs
index 202e6f8..f5b9634 100644
--- a/datasketches/src/hll/union.rs
+++ b/datasketches/src/hll/union.rs
@@ -26,6 +26,7 @@ use crate::hll::HllType;
use crate::hll::array4::Array4;
use crate::hll::array6::Array6;
use crate::hll::array8::Array8;
+use crate::hll::container::Container;
use crate::hll::estimator::EstimateState;
use crate::hll::mode::Mode;
@@ -129,37 +130,51 @@ impl HllUnion {
let src_lg_k = sketch.lg_config_k();
let dst_lg_k = self.gadget.lg_config_k();
- let src_mode = sketch.mode();
- match src_mode {
- Mode::List { .. } | Mode::Set { .. } => {
- self.update_from_list_or_set(sketch, src_mode, src_lg_k,
dst_lg_k);
+ match sketch.mode() {
+ Mode::List { list, .. } => {
+ if self.gadget.is_empty() && src_lg_k == dst_lg_k {
+ self.gadget = HllSketch::from_mode(
+ src_lg_k,
+ Mode::List {
+ list: list.clone(),
+ hll_type: HllType::Hll8,
+ },
+ );
+ } else {
+ for coupon in list.container().iter() {
+ self.gadget.update_with_coupon(coupon);
+ }
+ }
}
- Mode::Array4(_) | Mode::Array6(_) | Mode::Array8(_) => {
- self.update_from_array(src_mode, src_lg_k, dst_lg_k);
+ Mode::Set { set, .. } => {
+ if self.gadget.is_empty() && src_lg_k == dst_lg_k {
+ self.gadget = HllSketch::from_mode(
+ src_lg_k,
+ Mode::Set {
+ set: set.clone(),
+ hll_type: HllType::Hll8,
+ },
+ );
+ } else {
+ for coupon in set.container().iter() {
+ self.gadget.update_with_coupon(coupon);
+ }
+ }
+ }
+ Mode::Array4(src) => {
+ self.update_from_array(ArrayMode::Array4(src), src_lg_k,
dst_lg_k);
+ }
+ Mode::Array6(src) => {
+ self.update_from_array(ArrayMode::Array6(src), src_lg_k,
dst_lg_k);
+ }
+ Mode::Array8(src) => {
+ self.update_from_array(ArrayMode::Array8(src), src_lg_k,
dst_lg_k);
}
}
}
- fn update_from_list_or_set(
- &mut self,
- sketch: &HllSketch,
- src_mode: &Mode,
- src_lg_k: u8,
- dst_lg_k: u8,
- ) {
- if self.gadget.is_empty() && src_lg_k == dst_lg_k {
- self.gadget = if sketch.target_type() == HllType::Hll8 {
- sketch.clone()
- } else {
- convert_coupon_mode_to_hll8(src_mode, src_lg_k)
- };
- } else {
- merge_coupons_into_gadget(&mut self.gadget, src_mode);
- }
- }
-
- fn update_from_array(&mut self, src_mode: &Mode, src_lg_k: u8, dst_lg_k:
u8) {
+ fn update_from_array(&mut self, src_mode: ArrayMode<'_>, src_lg_k: u8,
dst_lg_k: u8) {
if self.gadget.is_empty() {
let new_array = copy_or_downsample(src_mode, src_lg_k,
self.lg_max_k);
let final_lg_k = new_array.num_registers().trailing_zeros() as u8;
@@ -167,52 +182,33 @@ impl HllUnion {
return;
}
- let is_gadget_array = matches!(self.gadget.mode(), Mode::Array8(_));
-
- if is_gadget_array {
- self.merge_array_into_array_gadget(src_mode, src_lg_k, dst_lg_k);
- } else {
- self.promote_gadget_and_merge_array(src_mode, src_lg_k);
- }
- }
-
- fn merge_array_into_array_gadget(&mut self, src_mode: &Mode, src_lg_k: u8,
dst_lg_k: u8) {
- if src_lg_k < dst_lg_k {
- let mut new_array = Array8::new(src_lg_k);
-
- match self.gadget.mode() {
- Mode::Array8(old_gadget) => {
- new_array.merge_array_with_downsample(old_gadget.values(),
dst_lg_k);
- }
- _ => {
- unreachable!("gadget mode changed unexpectedly; should
never be Array4/Array6");
- }
+ let lg_max_k = self.lg_max_k;
+ match self.gadget.mode_mut() {
+ Mode::List { list, .. } => {
+ let next =
+ promote_coupons_and_merge_array(src_mode, src_lg_k,
lg_max_k, list.container());
+ self.gadget = next;
}
-
- merge_array_same_lgk(&mut new_array, src_mode);
- self.gadget = HllSketch::from_mode(src_lg_k,
Mode::Array8(new_array));
- } else {
- match self.gadget.mode_mut() {
- Mode::Array8(dst_array) => {
+ Mode::Set { set, .. } => {
+ let next =
+ promote_coupons_and_merge_array(src_mode, src_lg_k,
lg_max_k, set.container());
+ self.gadget = next;
+ }
+ Mode::Array8(dst_array) => {
+ if src_lg_k < dst_lg_k {
+ let mut new_array = Array8::new(src_lg_k);
+ new_array.merge_array_with_downsample(dst_array.values(),
dst_lg_k);
+ merge_array_same_lgk(&mut new_array, src_mode);
+ self.gadget = HllSketch::from_mode(src_lg_k,
Mode::Array8(new_array));
+ } else {
merge_array_into_array8(dst_array, dst_lg_k, src_mode,
src_lg_k);
}
- _ => {
- unreachable!("gadget mode changed unexpectedly; should
never be Array4/Array6");
- }
}
+ Mode::Array4(_) => unreachable!("HllUnion gadget should never be
in Array4 mode"),
+ Mode::Array6(_) => unreachable!("HllUnion gadget should never be
in Array6 mode"),
}
}
- fn promote_gadget_and_merge_array(&mut self, src_mode: &Mode, src_lg_k:
u8) {
- let mut new_array = copy_or_downsample(src_mode, src_lg_k,
self.lg_max_k);
-
- let old_gadget_mode = self.gadget.mode();
- merge_coupons_into_mode(&mut new_array, old_gadget_mode);
-
- let final_lg_k = new_array.num_registers().trailing_zeros() as u8;
- self.gadget = HllSketch::from_mode(final_lg_k,
Mode::Array8(new_array));
- }
-
/// Returns an independent sketch with the requested [`HllType`].
///
/// The result retains the union's effective `lg_k` and cardinality
estimate.
@@ -254,33 +250,46 @@ impl HllUnion {
Mode::Array8(array8) => {
convert_array8_to_type(array8, self.gadget.lg_config_k(),
hll_type)
}
- Mode::Array4(_) | Mode::Array6(_) => {
- unreachable!("gadget mode changed unexpectedly; should never
be Array4/Array6")
- }
+ Mode::Array4(_) => unreachable!("HllUnion gadget should never be
in Array4 mode"),
+ Mode::Array6(_) => unreachable!("HllUnion gadget should never be
in Array6 mode"),
}
}
- /// Serializes the union's result as an [`HllType::Hll8`] sketch.
+ /// Serializes the union's result as an [`HllSketch`] with the requested
[`HllType`].
///
- /// 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`].
+ /// Produces an equivalent sketch to [`Self::to_sketch`] followed by
[`HllSketch::serialize`]
+ /// without allocating or cloning an intermediate sketch. For
[`HllType::Hll6`],
+ /// [`HllType::Hll8`], coupon modes, and [`HllType::Hll4`] with at most
one auxiliary entry,
+ /// the output matches `to_sketch(hll_type).serialize()` byte-for-byte;
for [`HllType::Hll4`]
+ /// with multiple auxiliary entries, auxiliary entries are written in
ascending slot order
+ /// rather than hash-table order.
+ ///
+ /// 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::HllType;
/// use datasketches::hll::HllUnion;
///
/// let mut union = HllUnion::new(12).unwrap();
/// union.update_value("apple");
- /// let mut partial = HllSketch::deserialize(&union.serialize()).unwrap();
+ /// let mut partial =
HllSketch::deserialize(&union.serialize(HllType::Hll8)).unwrap();
/// partial.update("banana");
/// union.update(&partial);
/// assert!((union.estimate() - 2.0).abs() < 0.01);
/// ```
- pub fn serialize(&self) -> Vec<u8> {
- self.gadget.serialize()
+ pub fn serialize(&self, hll_type: HllType) -> Vec<u8> {
+ let lg_config_k = self.gadget.lg_config_k();
+ match self.gadget.mode() {
+ Mode::List { list, .. } => list.serialize(lg_config_k, hll_type),
+ Mode::Set { set, .. } => set.serialize(lg_config_k, hll_type),
+ Mode::Array8(arr) => arr.serialize_as(lg_config_k, hll_type),
+ Mode::Array4(_) => unreachable!("HllUnion gadget should never be
in Array4 mode"),
+ Mode::Array6(_) => unreachable!("HllUnion gadget should never be
in Array6 mode"),
+ }
}
/// Returns the union's current effective `lg_k`.
@@ -405,68 +414,44 @@ impl HllUnion {
}
}
-fn convert_coupon_mode_to_hll8(src_mode: &Mode, src_lg_k: u8) -> HllSketch {
- match src_mode {
- Mode::List { list, .. } => HllSketch::from_mode(
- src_lg_k,
- Mode::List {
- list: list.clone(),
- hll_type: HllType::Hll8,
- },
- ),
- Mode::Set { set, .. } => HllSketch::from_mode(
- src_lg_k,
- Mode::Set {
- set: set.clone(),
- hll_type: HllType::Hll8,
- },
- ),
- _ => unreachable!("convert_coupon_mode_to_hll8 called with non-coupon
mode"),
- }
+#[derive(Clone, Copy)]
+enum ArrayMode<'a> {
+ Array4(&'a Array4),
+ Array6(&'a Array6),
+ Array8(&'a Array8),
}
-fn merge_coupons_into_gadget(gadget: &mut HllSketch, src_mode: &Mode) {
- match src_mode {
- Mode::List { list, .. } => {
- for coupon in list.container().iter() {
- gadget.update_with_coupon(coupon);
- }
- }
- Mode::Set { set, .. } => {
- for coupon in set.container().iter() {
- gadget.update_with_coupon(coupon);
- }
- }
- Mode::Array4(_) | Mode::Array6(_) | Mode::Array8(_) => {
- unreachable!(
- "merge_coupons_into_gadget called with array mode; array modes
should use merge_array_into_array8"
- );
+impl ArrayMode<'_> {
+ fn estimate_state(self) -> EstimateState {
+ match self {
+ Self::Array4(src) => src.estimate_state(),
+ Self::Array6(src) => src.estimate_state(),
+ Self::Array8(src) => src.estimate_state(),
}
}
}
-fn merge_coupons_into_mode(dst: &mut Array8, src_mode: &Mode) {
- match src_mode {
- Mode::List { list, .. } => {
- for coupon in list.container().iter() {
- dst.update(coupon);
- }
- }
- Mode::Set { set, .. } => {
- for coupon in set.container().iter() {
- dst.update(coupon);
- }
- }
- Mode::Array4(_) | Mode::Array6(_) | Mode::Array8(_) => {
- unreachable!(
- "merge_coupons_into_mode called with array mode; array modes
should use copy_or_downsample"
- );
- }
+fn promote_coupons_and_merge_array(
+ src_mode: ArrayMode<'_>,
+ src_lg_k: u8,
+ lg_max_k: u8,
+ coupons: &Container,
+) -> HllSketch {
+ let mut new_array = copy_or_downsample(src_mode, src_lg_k, lg_max_k);
+ for coupon in coupons.iter() {
+ new_array.update(coupon);
}
+ let final_lg_k = new_array.num_registers().trailing_zeros() as u8;
+ HllSketch::from_mode(final_lg_k, Mode::Array8(new_array))
}
/// The caller must downsize the destination first if the source has a smaller
`lg_k`.
-fn merge_array_into_array8(dst_array8: &mut Array8, dst_lg_k: u8, src_mode:
&Mode, src_lg_k: u8) {
+fn merge_array_into_array8(
+ dst_array8: &mut Array8,
+ dst_lg_k: u8,
+ src_mode: ArrayMode<'_>,
+ src_lg_k: u8,
+) {
assert!(
src_lg_k >= dst_lg_k,
"merge_array_into_array8 requires src_lg_k >= dst_lg_k (got src={},
dst={})",
@@ -481,19 +466,6 @@ fn merge_array_into_array8(dst_array8: &mut Array8,
dst_lg_k: u8, src_mode: &Mod
}
}
-fn get_array_estimate_state(mode: &Mode) -> EstimateState {
- match mode {
- Mode::Array8(src) => src.estimate_state(),
- Mode::Array6(src) => src.estimate_state(),
- Mode::Array4(src) => src.estimate_state(),
- Mode::List { .. } | Mode::Set { .. } => {
- unreachable!(
- "get_array_estimate_state called with non-array mode; List/Set
not supported"
- );
- }
- }
-}
-
fn merge_array46_same_lgk(dst: &mut Array8, num_registers: usize, get_value:
impl Fn(u32) -> u8) {
for slot in 0..num_registers {
let val = get_value(slot as u32);
@@ -506,20 +478,17 @@ fn merge_array46_same_lgk(dst: &mut Array8,
num_registers: usize, get_value: imp
}
/// Merging independent register histories invalidates the HIP accumulator.
-fn merge_array_same_lgk(dst: &mut Array8, src_mode: &Mode) {
+fn merge_array_same_lgk(dst: &mut Array8, src_mode: ArrayMode<'_>) {
match src_mode {
- Mode::Array8(src) => {
+ ArrayMode::Array8(src) => {
dst.merge_array_same_lgk(src.values());
}
- Mode::Array6(src) => {
+ ArrayMode::Array6(src) => {
merge_array46_same_lgk(dst, src.num_registers(), |slot|
src.get(slot));
}
- Mode::Array4(src) => {
+ ArrayMode::Array4(src) => {
merge_array46_same_lgk(dst, src.num_registers(), |slot|
src.get(slot));
}
- _ => {
- unreachable!("merge_array_same_lgk called with non-array mode;
List/Set not supported")
- }
}
}
@@ -545,7 +514,12 @@ fn merge_array46_with_downsample(
/// Multiple source registers map to each destination register via masking.
/// Merging independent register histories invalidates the HIP accumulator.
-fn merge_array_with_downsample(dst: &mut Array8, dst_lg_k: u8, src_mode:
&Mode, src_lg_k: u8) {
+fn merge_array_with_downsample(
+ dst: &mut Array8,
+ dst_lg_k: u8,
+ src_mode: ArrayMode<'_>,
+ src_lg_k: u8,
+) {
assert!(
src_lg_k > dst_lg_k,
"merge_array_with_downsample requires src_lg_k > dst_lg_k (got src={},
dst={})",
@@ -554,18 +528,15 @@ fn merge_array_with_downsample(dst: &mut Array8,
dst_lg_k: u8, src_mode: &Mode,
);
match src_mode {
- Mode::Array8(src) => {
+ ArrayMode::Array8(src) => {
dst.merge_array_with_downsample(src.values(), src_lg_k);
}
- Mode::Array6(src) => {
+ ArrayMode::Array6(src) => {
merge_array46_with_downsample(dst, dst_lg_k, src.num_registers(),
|slot| src.get(slot));
}
- Mode::Array4(src) => {
+ ArrayMode::Array4(src) => {
merge_array46_with_downsample(dst, dst_lg_k, src.num_registers(),
|slot| src.get(slot));
}
- _ => unreachable!(
- "merge_array_with_downsample called with non-array mode; List/Set
not supported"
- ),
}
}
@@ -616,27 +587,22 @@ fn copy_array46_via_coupons(dst: &mut Array8,
num_registers: usize, get_value: i
}
/// Preserves the source estimate state because the result represents the same
logical sketch.
-fn copy_or_downsample(src_mode: &Mode, src_lg_k: u8, tgt_lg_k: u8) -> Array8 {
- let state = get_array_estimate_state(src_mode);
+fn copy_or_downsample(src_mode: ArrayMode<'_>, src_lg_k: u8, tgt_lg_k: u8) ->
Array8 {
+ let state = src_mode.estimate_state();
let mut result = if src_lg_k <= tgt_lg_k {
match src_mode {
- Mode::Array8(src) => src.clone(),
- Mode::Array6(src) => {
+ ArrayMode::Array8(src) => src.clone(),
+ ArrayMode::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) => {
+ ArrayMode::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!(
- "copy_or_downsample called with non-array mode; List/Set
not supported"
- );
- }
}
} else {
let mut result = Array8::new(tgt_lg_k);
diff --git a/datasketches/src/thetafamily/theta/serialization.rs
b/datasketches/src/thetafamily/theta/serialization.rs
index a36c5bd..8ff151a 100644
--- a/datasketches/src/thetafamily/theta/serialization.rs
+++ b/datasketches/src/thetafamily/theta/serialization.rs
@@ -73,3 +73,93 @@ pub(super) fn serialize_compact_uncompressed<E: SketchEntry>(
}
bytes.into_bytes()
}
+
+pub(super) fn serialize_compact_compressed<E: SketchEntry>(
+ state: &CompactSketchState<E>,
+) -> Vec<u8> {
+ if is_suitable_for_compression(state) {
+ serialize_v4(state)
+ } else {
+ serialize_compact_uncompressed(state)
+ }
+}
+
+fn is_suitable_for_compression<E: SketchEntry>(state: &CompactSketchState<E>)
-> bool {
+ let num_retained = state.retained_entries().len();
+ state.is_ordered() && num_retained != 0 && (num_retained != 1 ||
state.is_estimation_mode())
+}
+
+fn serialize_v4<E: SketchEntry>(state: &CompactSketchState<E>) -> Vec<u8> {
+ let entries = state.retained_entries();
+ let pre_longs = if state.is_estimation_mode() { 2u8 } else { 1u8 };
+ let entry_bits = compute_entry_bits(entries);
+ let num_entries_bytes = num_entries_bytes(entries.len());
+
+ // Pre-size exactly: preamble longs (8 bytes each) + num_entries_bytes +
packed bits.
+ let compressed_bits = entry_bits as usize * entries.len();
+ let compressed_bytes = compressed_bits.div_ceil(8);
+ let out_bytes = (pre_longs as usize * 8) + (num_entries_bytes as usize) +
compressed_bytes;
+ let mut bytes = SketchBytes::with_capacity(out_bytes);
+
+ bytes.write_u8(pre_longs);
+ bytes.write_u8(COMPRESSED_SERIAL_VERSION);
+ bytes.write_u8(Family::THETA.id);
+ bytes.write_u8(entry_bits);
+ bytes.write_u8(num_entries_bytes);
+
+ let mut flags = 0u8;
+ flags |= FLAGS_IS_READ_ONLY;
+ flags |= FLAGS_IS_COMPACT;
+ flags |= FLAGS_IS_ORDERED;
+ bytes.write_u8(flags);
+
+ bytes.write_u16_le(state.seed_hash());
+ if state.is_estimation_mode() {
+ bytes.write_u64_le(state.theta());
+ }
+
+ let mut n = entries.len() as u32;
+ for _ in 0..num_entries_bytes {
+ bytes.write_u8((n & 0xff) as u8);
+ n >>= 8;
+ }
+
+ let bits = u32::from(entry_bits);
+ let mut acc = 0u128;
+ let mut acc_bits = 0u32;
+ let mut previous = 0u64;
+ for entry in entries {
+ let hash = entry.hash();
+ acc = (acc << bits) | u128::from(hash - previous);
+ previous = hash;
+ acc_bits += bits;
+ if acc_bits >= 64 {
+ acc_bits -= 64;
+ bytes.write(&((acc >> acc_bits) as u64).to_be_bytes());
+ }
+ }
+ if acc_bits > 0 {
+ let tail = ((acc << (64 - acc_bits)) as u64).to_be_bytes();
+ bytes.write(&tail[..acc_bits.div_ceil(8) as usize]);
+ }
+
+ bytes.into_bytes()
+}
+
+fn compute_entry_bits<E: SketchEntry>(entries: &[E]) -> u8 {
+ let mut previous = 0u64;
+ let mut ored = 0u64;
+ for entry in entries {
+ let hash = entry.hash();
+ let delta = hash - previous;
+ ored |= delta;
+ previous = hash;
+ }
+ (64 - ored.leading_zeros()) as u8
+}
+
+fn num_entries_bytes(num_entries: usize) -> u8 {
+ let n = num_entries as u32;
+ let bits = u32::BITS - n.leading_zeros();
+ bits.div_ceil(8) as u8
+}
diff --git a/datasketches/src/thetafamily/theta/sketch.rs
b/datasketches/src/thetafamily/theta/sketch.rs
index 3088406..c8a43ab 100644
--- a/datasketches/src/thetafamily/theta/sketch.rs
+++ b/datasketches/src/thetafamily/theta/sketch.rs
@@ -25,7 +25,6 @@ use std::hash::Hash;
use std::iter::FusedIterator;
use std::slice;
-use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::assert::ensure_preamble_longs_in_range;
use crate::codec::assert::insufficient_data;
@@ -48,10 +47,8 @@ use crate::thetafamily::common::KeySketch;
use crate::thetafamily::common::SketchEntry;
use crate::thetafamily::common::binomial_bounds;
use crate::thetafamily::common::constants::DEFAULT_LG_K;
-use crate::thetafamily::common::constants::FLAGS_IS_COMPACT;
use crate::thetafamily::common::constants::FLAGS_IS_EMPTY;
use crate::thetafamily::common::constants::FLAGS_IS_ORDERED;
-use crate::thetafamily::common::constants::FLAGS_IS_READ_ONLY;
use crate::thetafamily::common::constants::MAX_THETA;
use crate::thetafamily::common::hash_table::SketchHashTable;
use crate::thetafamily::common::hash_table::SketchHashTableIter;
@@ -591,17 +588,7 @@ impl CompactThetaSketch {
///
/// Falls back to [`serialize`](Self::serialize) when compression is not
applicable.
pub fn serialize_compressed(&self) -> Vec<u8> {
- if self.is_suitable_for_compression() {
- self.serialize_v4()
- } else {
- self.serialize()
- }
- }
-
- fn is_suitable_for_compression(&self) -> bool {
- self.is_ordered()
- && self.num_retained() != 0
- && (self.num_retained() != 1 || self.is_estimation_mode())
+ serialization::serialize_compact_compressed(&self.compact_state)
}
/// Serializes this sketch into the uncompressed compact Theta format.
@@ -613,79 +600,6 @@ impl CompactThetaSketch {
serialization::serialize_compact_uncompressed(&self.compact_state)
}
- fn serialize_v4(&self) -> Vec<u8> {
- let retained_hashes = self.retained_hashes();
- let pre_longs = if self.is_estimation_mode() { 2u8 } else { 1u8 };
- let entry_bits = Self::compute_entry_bits(retained_hashes);
- let num_entries_bytes = Self::num_entries_bytes(retained_hashes.len());
-
- // Pre-size exactly: preamble longs (8 bytes each) + num_entries_bytes
+ packed bits.
- let compressed_bits = entry_bits as usize * retained_hashes.len();
- let compressed_bytes = compressed_bits.div_ceil(8);
- let out_bytes = (pre_longs as usize * 8) + (num_entries_bytes as
usize) + compressed_bytes;
- let mut bytes = SketchBytes::with_capacity(out_bytes);
-
- bytes.write_u8(pre_longs);
- bytes.write_u8(serialization::COMPRESSED_SERIAL_VERSION);
- bytes.write_u8(Family::THETA.id);
- bytes.write_u8(entry_bits);
- bytes.write_u8(num_entries_bytes);
-
- let mut flags = 0u8;
- flags |= FLAGS_IS_READ_ONLY;
- flags |= FLAGS_IS_COMPACT;
- flags |= FLAGS_IS_ORDERED;
- bytes.write_u8(flags);
-
- bytes.write_u16_le(self.seed_hash());
- if self.is_estimation_mode() {
- bytes.write_u64_le(self.theta64());
- }
-
- let mut n = retained_hashes.len() as u32;
- for _ in 0..num_entries_bytes {
- bytes.write_u8((n & 0xff) as u8);
- n >>= 8;
- }
-
- let bits = u32::from(entry_bits);
- let mut acc = 0u128;
- let mut acc_bits = 0u32;
- let mut previous = 0u64;
- for &entry in retained_hashes {
- acc = (acc << bits) | u128::from(entry - previous);
- previous = entry;
- acc_bits += bits;
- if acc_bits >= 64 {
- acc_bits -= 64;
- bytes.write(&((acc >> acc_bits) as u64).to_be_bytes());
- }
- }
- if acc_bits > 0 {
- let tail = ((acc << (64 - acc_bits)) as u64).to_be_bytes();
- bytes.write(&tail[..acc_bits.div_ceil(8) as usize]);
- }
-
- bytes.into_bytes()
- }
-
- fn compute_entry_bits(entries: &[u64]) -> u8 {
- let mut previous = 0u64;
- let mut ored = 0u64;
- for &entry in entries {
- let delta = entry - previous;
- ored |= delta;
- previous = entry;
- }
- (64 - ored.leading_zeros()) as u8
- }
-
- fn num_entries_bytes(num_entries: usize) -> u8 {
- let n = num_entries as u32;
- let bits = u32::BITS - n.leading_zeros();
- bits.div_ceil(8) as u8
- }
-
/// Deserializes a compact Theta sketch using the default seed.
///
/// Also accepts data serialized by other DataSketches implementations.
diff --git a/datasketches/src/thetafamily/theta/union.rs
b/datasketches/src/thetafamily/theta/union.rs
index ecac475..efd9187 100644
--- a/datasketches/src/thetafamily/theta/union.rs
+++ b/datasketches/src/thetafamily/theta/union.rs
@@ -65,14 +65,50 @@ impl ThetaUnion {
/// Serializes this union result into the uncompressed compact Theta
format.
///
- /// Produces the same bytes as `self.to_sketch(ordered).serialize()`. When
`ordered` is `true`,
- /// retained hashes are sorted. Otherwise they may be unordered; empty
results and exact
- /// singletons always use their canonical encoding.
+ /// The result is the same as [`Self::to_sketch`] followed by
+ /// [`CompactThetaSketch::serialize`]: the same retained hashes, theta,
and seed hash, and
+ /// identical bytes when `ordered` is `true`
(`to_sketch(true).serialize()`). When `ordered` is
+ /// `false`, retained hashes may appear in a different order. Empty
results and exact singletons
+ /// always use their canonical encoding.
pub fn serialize(&self, ordered: bool) -> Vec<u8> {
let state = self.state.to_compact_hash_state(ordered);
serialization::serialize_compact_uncompressed(&state)
}
+ /// Serializes this union result in compressed compact Theta format if
applicable.
+ ///
+ /// Produces the same bytes as
`self.to_sketch(true).serialize_compressed()`. Compressed
+ /// serialization requires ordered entries, so retained hashes are sorted
ascending. Falls back
+ /// to uncompressed canonical encoding for empty sketches, zero-entry
estimation sketches, and
+ /// exact singletons.
+ ///
+ /// The serialized data can be read by other DataSketches implementations
via
+ /// [`CompactThetaSketch::deserialize`] or
[`CompactThetaSketch::deserialize_with_seed`].
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::theta::CompactThetaSketch;
+ /// use datasketches::theta::ThetaSketchBuilder;
+ /// use datasketches::theta::ThetaUnionBuilder;
+ ///
+ /// let mut sketch =
ThetaSketchBuilder::default().lg_k(12).build().unwrap();
+ /// for value in 0..100 {
+ /// sketch.update(value);
+ /// }
+ ///
+ /// let mut union = ThetaUnionBuilder::default().lg_k(12).build().unwrap();
+ /// union.update(&sketch).unwrap();
+ ///
+ /// let bytes = union.serialize_compressed();
+ /// let restored = CompactThetaSketch::deserialize(&bytes).unwrap();
+ /// assert_eq!(restored.num_retained(), 100);
+ /// ```
+ pub fn serialize_compressed(&self) -> Vec<u8> {
+ let state = self.state.to_compact_hash_state(true);
+ serialization::serialize_compact_compressed(&state)
+ }
+
/// Resets the union to its empty state.
pub fn reset(&mut self) {
self.state.reset();
diff --git a/tests-integration/tests/hll_test/union.rs
b/tests-integration/tests/hll_test/union.rs
index e02f240..56c4e44 100644
--- a/tests-integration/tests/hll_test/union.rs
+++ b/tests-integration/tests/hll_test/union.rs
@@ -784,7 +784,7 @@ fn test_union_query_timing_does_not_change_mixed_updates() {
&queried.to_sketch(HllType::Hll8),
&queried.to_sketch(HllType::Hll4),
);
- let restored = HllSketch::deserialize(&queried.serialize()).unwrap();
+ let restored =
HllSketch::deserialize(&queried.serialize(HllType::Hll8)).unwrap();
assert_eq!(restored.composite_estimate(),
queried.composite_estimate());
for value in start + 5_000..start + 5_100 {
queried.update_value(value);
@@ -792,7 +792,10 @@ fn test_union_query_timing_does_not_change_mixed_updates()
{
}
}
- assert_eq!(queried.serialize(), deferred.serialize());
+ assert_eq!(
+ queried.serialize(HllType::Hll8),
+ deferred.serialize(HllType::Hll8)
+ );
assert_same_estimate_and_bounds(
&queried.to_sketch(HllType::Hll8),
&deferred.to_sketch(HllType::Hll8),
@@ -808,7 +811,10 @@ fn test_union_query_timing_does_not_change_mixed_updates()
{
copied.update_value(value);
deferred.update_value(value);
}
- assert_eq!(copied.serialize(), deferred.serialize());
+ assert_eq!(
+ copied.serialize(HllType::Hll8),
+ deferred.serialize(HllType::Hll8)
+ );
}
#[test]
@@ -822,25 +828,36 @@ fn
test_union_supports_shared_queries_after_dense_merges() {
(index + 1) * 5_000,
));
}
- let expected = union.to_sketch(HllType::Hll8);
- let bytes = expected.serialize();
+ let expected_hll8 = union.to_sketch(HllType::Hll8);
+ let bytes_hll8 = expected_hll8.serialize();
+ let expected_hll6 = union.to_sketch(HllType::Hll6);
+ let bytes_hll6 = expected_hll6.serialize();
+ let expected_hll4 = union.to_sketch(HllType::Hll4);
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.estimate(), expected_hll8.estimate());
+ assert_eq!(
+ union.composite_estimate(),
+ expected_hll8.composite_estimate()
+ );
assert_eq!(
union.lower_bound(NumStdDev::Two),
- expected.lower_bound(NumStdDev::Two)
+ expected_hll8.lower_bound(NumStdDev::Two)
);
assert_eq!(
union.upper_bound(NumStdDev::Two),
- expected.upper_bound(NumStdDev::Two)
+ expected_hll8.upper_bound(NumStdDev::Two)
+ );
+ assert_eq!(union.serialize(HllType::Hll8), bytes_hll8);
+ assert_eq!(union.serialize(HllType::Hll6), bytes_hll6);
+ assert_eq!(
+
HllSketch::deserialize(&union.serialize(HllType::Hll4)).unwrap(),
+ expected_hll4
);
- assert_eq!(union.serialize(), bytes);
});
}
});
diff --git a/tests-integration/tests/serde_tests/hll.rs
b/tests-integration/tests/serde_tests/hll.rs
index ed0dd41..8aed0b1 100644
--- a/tests-integration/tests/serde_tests/hll.rs
+++ b/tests-integration/tests/serde_tests/hll.rs
@@ -18,6 +18,7 @@
use std::fs;
use std::path::PathBuf;
+use datasketches::common::NumStdDev;
use datasketches::hash::value::natural_extend;
use datasketches::hll::HllSketch;
use datasketches::hll::HllType;
@@ -42,7 +43,7 @@ fn
union_serialization_preserves_result_and_subsequent_updates() {
for lg_max_k in [8, 12, 14] {
let mut union = HllUnion::new(lg_max_k).unwrap();
union.update(&source);
- let bytes = union.serialize();
+ let bytes = union.serialize(HllType::Hll8);
assert_eq!(bytes, union.to_sketch(HllType::Hll8).serialize());
let mut restored = HllSketch::deserialize(&bytes).unwrap();
@@ -57,10 +58,177 @@ fn
union_serialization_preserves_result_and_subsequent_updates() {
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);
+ for target_type in [HllType::Hll4, HllType::Hll6,
HllType::Hll8] {
+ let empty =
HllSketch::deserialize(&union.serialize(target_type)).unwrap();
+ assert!(empty.is_empty());
+ assert_eq!(empty.target_type(), target_type);
+ assert_eq!(empty.lg_config_k(), lg_max_k);
+ }
+ }
+ }
+ }
+}
+
+fn assert_union_matches_sketch(
+ union: &HllUnion,
+ target_type: HllType,
+ check_bytes_when_single_aux: bool,
+) {
+ let bytes = union.serialize(target_type);
+ let expected = union.to_sketch(target_type);
+ if check_bytes_when_single_aux {
+ let dense_offset = 40 + (1usize << (union.lg_config_k() - 1));
+ let single_or_no_aux =
+ target_type != HllType::Hll4 || bytes.len() <= dense_offset +
size_of::<u32>();
+ if single_or_no_aux {
+ assert_eq!(
+ bytes,
+ expected.serialize(),
+ "byte mismatch for target_type={target_type:?}, lg_k={}",
+ union.lg_config_k()
+ );
+ }
+ }
+
+ let restored = HllSketch::deserialize(&bytes).unwrap();
+ assert_eq!(restored.target_type(), target_type);
+ assert_eq!(restored.lg_config_k(), expected.lg_config_k());
+ assert_eq!(restored.is_empty(), expected.is_empty());
+ assert_eq!(restored, expected);
+ assert_eq!(restored.estimate(), expected.estimate());
+ assert_eq!(restored.composite_estimate(), expected.composite_estimate());
+ assert_eq!(restored.estimate(), union.estimate());
+ assert_eq!(restored.composite_estimate(), union.composite_estimate());
+ for num_std_dev in [NumStdDev::One, NumStdDev::Two, NumStdDev::Three] {
+ assert_eq!(
+ restored.lower_bound(num_std_dev),
+ expected.lower_bound(num_std_dev)
+ );
+ assert_eq!(
+ restored.upper_bound(num_std_dev),
+ expected.upper_bound(num_std_dev)
+ );
+ assert_eq!(
+ restored.lower_bound(num_std_dev),
+ union.lower_bound(num_std_dev)
+ );
+ assert_eq!(
+ restored.upper_bound(num_std_dev),
+ union.upper_bound(num_std_dev)
+ );
+ }
+}
+
+#[test]
+fn union_serialization_handles_all_modes_and_target_types() {
+ for count in [0, 4, 100, 10_000_u64] {
+ let mut union = HllUnion::new(12).unwrap();
+ for value in 0..count {
+ union.update_value(value);
+ }
+ for target_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
+ assert_union_matches_sketch(&union, target_type, true);
+ }
+ }
+}
+
+#[test]
+fn union_serialization_cold_and_warm_composite_states_match() {
+ let build_composite_union = || {
+ let mut union = HllUnion::new(12).unwrap();
+ for (start, end) in [(0_u64, 3_000), (3_000, 6_000)] {
+ let mut sketch = HllSketch::new(12, HllType::Hll8).unwrap();
+ for value in start..end {
+ sketch.update(value);
}
+ union.update(&sketch);
+ }
+ union
+ };
+
+ for target_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
+ // Cold: serialize before calling any estimate or to_sketch on this
union.
+ let cold_union = build_composite_union();
+ let cold_bytes = cold_union.serialize(target_type);
+
+ // Warm: populate lazy estimator cache before serializing.
+ let warm_union = build_composite_union();
+ let _ = warm_union.composite_estimate();
+ let warm_bytes = warm_union.serialize(target_type);
+
+ assert_eq!(cold_bytes, warm_bytes);
+ assert_union_matches_sketch(&cold_union, target_type, true);
+ }
+}
+
+#[test]
+fn union_serialization_handles_downsampled_unions() {
+ // Single-sketch downsample keeps HIP mode.
+ let mut wide = HllSketch::new(14, HllType::Hll8).unwrap();
+ for value in 0..10_000_u64 {
+ wide.update(value);
+ }
+ let mut hip_downsampled = HllUnion::new(10).unwrap();
+ hip_downsampled.update(&wide);
+ assert_eq!(hip_downsampled.lg_config_k(), 10);
+ for target_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
+ assert_union_matches_sketch(&hip_downsampled, target_type, true);
+ }
+
+ // Multi-sketch downsample merges into dense OOO Array8 at the smaller
lg_k.
+ let mut narrow = HllSketch::new(8, HllType::Hll4).unwrap();
+ for value in 10_000..15_000_u64 {
+ narrow.update(value);
+ }
+ let mut ooo_downsampled = HllUnion::new(12).unwrap();
+ ooo_downsampled.update(&wide);
+ ooo_downsampled.update(&narrow);
+ assert_eq!(ooo_downsampled.lg_config_k(), 8);
+ for target_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
+ assert_union_matches_sketch(&ooo_downsampled, target_type, true);
+ }
+}
+
+#[test]
+fn union_serialization_hll4_handles_shifted_cur_min_and_multi_aux() {
+ // Keys verified at lg_k = 4 to hit distinct slots with register value >=
22.
+ const HIGH_VALUE_KEYS: [u64; 4] = [503_824, 2_048_382, 2_144_141,
9_410_086];
+
+ let mut direct_union = HllUnion::new(4).unwrap();
+ for value in 0..200_u64 {
+ direct_union.update_value(value);
+ }
+ for value in HIGH_VALUE_KEYS {
+ direct_union.update_value(value);
+ }
+
+ let mut merged_left = HllSketch::new(4, HllType::Hll8).unwrap();
+ for value in 0..200_u64 {
+ merged_left.update(value);
+ }
+ let mut merged_right = HllSketch::new(4, HllType::Hll8).unwrap();
+ for value in HIGH_VALUE_KEYS {
+ merged_right.update(value);
+ }
+ let mut merged_union = HllUnion::new(4).unwrap();
+ merged_union.update(&merged_left);
+ merged_union.update(&merged_right);
+
+ for union in [&direct_union, &merged_union] {
+ let hll4_bytes = union.serialize(HllType::Hll4);
+ let expected_hll4_bytes = union.to_sketch(HllType::Hll4).serialize();
+ let dense_end = 40 + (1usize << (4 - 1));
+ assert!(hll4_bytes[6] > 0, "expected shifted cur_min > 0");
+ assert!(
+ (hll4_bytes.len() - dense_end) / size_of::<u32>() >= 2,
+ "expected at least 2 aux exceptions"
+ );
+ // Preamble and packed nibbles must match bit-for-bit; only aux coupon
order may differ.
+ assert_eq!(hll4_bytes[..dense_end], expected_hll4_bytes[..dense_end]);
+ assert_eq!(hll4_bytes.len(), expected_hll4_bytes.len());
+
+ for target_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
+ assert_union_matches_sketch(union, target_type, target_type !=
HllType::Hll4);
}
}
}
diff --git a/tests-integration/tests/serde_tests/theta.rs
b/tests-integration/tests/serde_tests/theta.rs
index b22301e..4073d0f 100644
--- a/tests-integration/tests/serde_tests/theta.rs
+++ b/tests-integration/tests/serde_tests/theta.rs
@@ -415,3 +415,98 @@ fn union_serialization_matches_compact_result() {
}
}
}
+
+#[test]
+fn union_compressed_serialization_matches_compact_result() {
+ for (lg_k, rows, probability, mixed_precision) in [
+ (5, 0, 1.0, false),
+ (5, 1, 1.0, false),
+ (5, 12, 1.0, false),
+ (5, 40, 1.0, false),
+ (5, 64, 0.5, false),
+ (5, 64, 1e-12, false),
+ (5, 64, 1.0, true),
+ (8, 5_000, 1.0, false),
+ ] {
+ let seed = 123;
+ let mut input = ThetaSketchBuilder::default()
+ .lg_k(8)
+ .seed(seed)
+ .sampling_probability(probability)
+ .build()
+ .unwrap();
+ for value in 0..rows {
+ input.update(value);
+ }
+ let mut union = ThetaUnionBuilder::default()
+ .lg_k(lg_k)
+ .seed(seed)
+ .build()
+ .unwrap();
+
+ let empty_compressed = union.serialize_compressed();
+ assert_eq!(
+ empty_compressed,
+ union.to_sketch(true).serialize_compressed()
+ );
+ assert_eq!(empty_compressed, union.serialize(true));
+ assert_eq!(empty_compressed[1], 3);
+
+ union.update(&input).unwrap();
+ if mixed_precision {
+ let mut other = ThetaSketchBuilder::default()
+ .lg_k(5)
+ .seed(seed)
+ .build()
+ .unwrap();
+ for value in 32..96 {
+ other.update(value);
+ }
+ union.update(&other.compact(true)).unwrap();
+ }
+
+ let compressed = union.serialize_compressed();
+ let expected_sketch = union.to_sketch(true);
+ assert_eq!(
+ compressed,
+ expected_sketch.serialize_compressed(),
+ "lg_k={lg_k}, rows={rows}, probability={probability},
mixed={mixed_precision}",
+ );
+
+ let num_retained = expected_sketch.num_retained();
+ if num_retained == 0 || (num_retained == 1 &&
!expected_sketch.is_estimation_mode()) {
+ assert_eq!(compressed[1], 3);
+ assert_eq!(compressed, union.serialize(true));
+ } else {
+ assert_eq!(compressed[1], 4);
+ assert!(compressed.len() <= union.serialize(true).len());
+ }
+
+ let restored = CompactThetaSketch::deserialize_with_seed(&compressed,
seed).unwrap();
+ assert_eq!(restored.is_empty(), expected_sketch.is_empty());
+ assert_eq!(
+ restored.is_estimation_mode(),
+ expected_sketch.is_estimation_mode()
+ );
+ assert_eq!(restored.is_ordered(), expected_sketch.is_ordered());
+ assert_eq!(restored.theta(), expected_sketch.theta());
+ assert_eq!(restored.estimate(), expected_sketch.estimate());
+ assert_eq!(
+ restored
+ .iter()
+ .map(|entry| entry.hash())
+ .collect::<Vec<_>>(),
+ expected_sketch
+ .iter()
+ .map(|entry| entry.hash())
+ .collect::<Vec<_>>(),
+ );
+ assert_eq!(restored.serialize_compressed(), compressed);
+
+ union.reset();
+ assert_eq!(
+ union.serialize_compressed(),
+ union.to_sketch(true).serialize_compressed()
+ );
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]