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 bea0e95 perf(cpc): serialize bit-matrix unions without intermediate
sketch (#353)
bea0e95 is described below
commit bea0e958e9cbd47bbac83c3447f7a6ec8c821d87
Author: tison <[email protected]>
AuthorDate: Thu Nov 12 09:25:51 2026 +0800
perf(cpc): serialize bit-matrix unions without intermediate sketch (#353)
---
CHANGELOG.md | 2 +-
benchmarks/cpc/serde.rs | 11 +-
datasketches/src/cpc/compression.rs | 133 +++++++++++++-------
datasketches/src/cpc/serialization.rs | 101 +++++++++++++++
datasketches/src/cpc/sketch.rs | 75 ++----------
datasketches/src/cpc/union.rs | 196 ++++++++++++++++++++++++++++--
tests-integration/tests/cpc_test/union.rs | 118 ++++++++++++++++++
7 files changed, 522 insertions(+), 114 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 910b81d..ce4e41e 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -13,7 +13,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 low-cardinality `CpcUnion` inputs, 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`,
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 `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.
### Performance improvements
diff --git a/benchmarks/cpc/serde.rs b/benchmarks/cpc/serde.rs
index 4259705..5ff3c0e 100644
--- a/benchmarks/cpc/serde.rs
+++ b/benchmarks/cpc/serde.rs
@@ -75,8 +75,15 @@ pub fn register(runner: &mut Runner) {
deserialize(b, items)
});
}
- // Reuse each union for repeated serialization: empty, sparse, and
bit-matrix results.
- for &(items, rounds) in &[(0_u64, 4_000_000), (20_000_u64, 500),
(80_000_u64, 200)] {
+ // Reuse each union for repeated serialization across empty, sparse,
hybrid, pinned, and
+ // sliding union results.
+ for &(items, rounds) in &[
+ (0_u64, 4_000_000),
+ (20_000_u64, 500),
+ (80_000_u64, 200),
+ (400_000_u64, 500),
+ (2_500_000_u64, 400),
+ ] {
runner.compare(
&format!("cpc::serde::serialize_union/{items:?}"),
rounds,
diff --git a/datasketches/src/cpc/compression.rs
b/datasketches/src/cpc/compression.rs
index 71b65ff..e8643f3 100644
--- a/datasketches/src/cpc/compression.rs
+++ b/datasketches/src/cpc/compression.rs
@@ -15,8 +15,6 @@
// specific language governing permissions and limitations
// under the License.
-use std::cmp::Ordering;
-
use crate::codec::SketchBytes;
use crate::cpc::compression_data::DECODING_TABLES_FOR_HIGH_ENTROPY_BYTE;
use crate::cpc::compression_data::ENCODING_TABLES_FOR_HIGH_ENTROPY_BYTE;
@@ -24,44 +22,77 @@ use
crate::cpc::compression_data::LENGTH_LIMITED_UNARY_DECODING_TABLE65;
use crate::cpc::compression_data::LENGTH_LIMITED_UNARY_ENCODING_TABLE65;
use crate::error::Error;
-pub fn encode_pairs(pairs: &[u32], lg_k: u8, output: &mut SketchBytes) ->
usize {
- let num_pairs = pairs.len() as u32;
- let num_base_bits =
- golomb_choose_number_of_base_bits((1 << lg_k) + num_pairs,
u64::from(num_pairs));
- let mut bits = BitWriter::new(output);
- let golomb_lo_mask = (1 << num_base_bits) - 1;
- let mut predicted_row_index = 0;
- let mut predicted_col_index = 0;
+pub struct PairEncoder<'a> {
+ bits: BitWriter<'a>,
+ num_base_bits: u8,
+ golomb_lo_mask: u32,
+ predicted_row_index: u32,
+ predicted_col_index: u32,
+}
- for &row_col in pairs {
+impl<'a> PairEncoder<'a> {
+ pub fn new(num_pairs: u32, lg_k: u8, output: &'a mut SketchBytes) -> Self {
+ let num_base_bits = golomb_choose_number_of_base_bits(
+ (1u64 << lg_k) + u64::from(num_pairs),
+ u64::from(num_pairs),
+ );
+ Self {
+ bits: BitWriter::new(output),
+ num_base_bits,
+ golomb_lo_mask: (1 << num_base_bits) - 1,
+ predicted_row_index: 0,
+ predicted_col_index: 0,
+ }
+ }
+
+ #[inline(always)]
+ pub fn write_pair(&mut self, row_col: u32) {
let row_index = row_col >> 6;
let col_index = row_col & 63;
- if row_index != predicted_row_index {
- predicted_col_index = 0;
+ if row_index != self.predicted_row_index {
+ self.predicted_col_index = 0;
}
- assert!(row_index >= predicted_row_index);
- assert!(col_index >= predicted_col_index);
+ assert!(row_index >= self.predicted_row_index);
+ assert!(col_index >= self.predicted_col_index);
- let y_delta = row_index - predicted_row_index;
- let x_delta = col_index - predicted_col_index;
- predicted_row_index = row_index;
- predicted_col_index = col_index + 1;
+ let y_delta = row_index - self.predicted_row_index;
+ let x_delta = col_index - self.predicted_col_index;
+ self.predicted_row_index = row_index;
+ self.predicted_col_index = col_index + 1;
let code_info = LENGTH_LIMITED_UNARY_ENCODING_TABLE65[x_delta as
usize];
- bits.write(u64::from(code_info & 0xfff), (code_info >> 12) as u8);
- bits.write_unary(u64::from(y_delta >> num_base_bits));
- bits.write(u64::from(y_delta & golomb_lo_mask), num_base_bits);
+ self.bits
+ .write(u64::from(code_info & 0xfff), (code_info >> 12) as u8);
+ self.bits
+ .write_unary(u64::from(y_delta >> self.num_base_bits));
+ self.bits
+ .write(u64::from(y_delta & self.golomb_lo_mask),
self.num_base_bits);
}
- bits.pad(10u8.saturating_sub(num_base_bits));
- bits.finish()
+ pub fn finish(mut self) -> usize {
+ self.bits.pad(10u8.saturating_sub(self.num_base_bits));
+ self.bits.finish()
+ }
+}
+
+pub fn encode_pairs(pairs: &[u32], lg_k: u8, output: &mut SketchBytes) ->
usize {
+ let mut encoder = PairEncoder::new(pairs.len() as u32, lg_k, output);
+ for &row_col in pairs {
+ encoder.write_pair(row_col);
+ }
+ encoder.finish()
}
-pub fn encode_window(window: &[u8], lg_k: u8, num_coupons: u32, output: &mut
SketchBytes) -> usize {
+pub fn encode_window(
+ window: impl IntoIterator<Item = u8>,
+ lg_k: u8,
+ num_coupons: u32,
+ output: &mut SketchBytes,
+) -> usize {
let pseudo_phase = determine_pseudo_phase(lg_k, num_coupons);
let encoding_table = &ENCODING_TABLES_FOR_HIGH_ENTROPY_BYTE[pseudo_phase
as usize];
let mut bits = BitWriter::new(output);
- for &byte in window {
+ for byte in window {
let code_info = encoding_table[byte as usize];
bits.write(u64::from(code_info & 0xfff), (code_info >> 12) as u8);
}
@@ -69,6 +100,28 @@ pub fn encode_window(window: &[u8], lg_k: u8, num_coupons:
u32, output: &mut Ske
bits.finish()
}
+pub fn estimated_encoded_pair_bytes(num_pairs: u32, lg_k: u8) -> usize {
+ if num_pairs == 0 {
+ return 0;
+ }
+ let b = golomb_choose_number_of_base_bits(
+ (1u64 << lg_k) + u64::from(num_pairs),
+ u64::from(num_pairs),
+ );
+ let unary_zero_bits = (1u64 << lg_k) >> b;
+ let pair_bits = u64::from(num_pairs) * (u64::from(b) + 4);
+ let total_words = (unary_zero_bits + pair_bits + 63) >> 5;
+ (total_words as usize) * size_of::<u32>()
+}
+
+pub fn estimated_encoded_window_bytes(lg_k: u8, num_coupons: u32) -> usize {
+ let k = 1u64 << lg_k;
+ let max_steady_bits = k * 5;
+ let sparse_window_bits = k + 4 * u64::from(num_coupons);
+ let bits = max_steady_bits.min(sparse_window_bits) + 63;
+ ((bits >> 5) as usize) * size_of::<u32>()
+}
+
struct BitWriter<'a> {
output: &'a mut SketchBytes,
buffer: u64,
@@ -77,6 +130,7 @@ struct BitWriter<'a> {
}
impl<'a> BitWriter<'a> {
+ #[inline]
fn new(output: &'a mut SketchBytes) -> Self {
Self {
output,
@@ -86,12 +140,14 @@ impl<'a> BitWriter<'a> {
}
}
+ #[inline]
fn write(&mut self, value: u64, count: u8) {
self.buffer |= value << self.buffered_bits;
self.buffered_bits += count;
self.flush_full_word();
}
+ #[inline]
fn write_unary(&mut self, value: u64) {
let mut remaining = value;
while remaining >= 16 {
@@ -101,11 +157,13 @@ impl<'a> BitWriter<'a> {
self.write(1 << remaining, (remaining + 1) as u8);
}
+ #[inline]
fn pad(&mut self, count: u8) {
self.buffered_bits += count;
self.flush_full_word();
}
+ #[inline]
fn flush_full_word(&mut self) {
if self.buffered_bits >= 32 {
self.output.write_u32_le(self.buffer as u32);
@@ -115,6 +173,7 @@ impl<'a> BitWriter<'a> {
}
}
+ #[inline]
fn finish(mut self) -> usize {
if self.buffered_bits > 0 {
debug_assert!(self.buffered_bits < 32);
@@ -131,7 +190,10 @@ pub fn decode_pairs(data: &[u8], num_pairs: u32, lg_k: u8)
-> Result<Vec<u32>, E
}
let k = 1 << lg_k;
let mut pairs = vec![0; num_pairs as usize];
- let num_base_bits = golomb_choose_number_of_base_bits(k + num_pairs,
num_pairs as u64);
+ let num_base_bits = golomb_choose_number_of_base_bits(
+ (1u64 << lg_k) + u64::from(num_pairs),
+ u64::from(num_pairs),
+ );
let mut bits = BitReader::new(data);
let golomb_lo_mask = (1 << num_base_bits) - 1;
let mut predicted_row_index = 0u32;
@@ -307,10 +369,10 @@ pub fn determine_pseudo_phase(lg_k: u8, num_coupons: u32)
-> u8 {
}
/// Returns an integer that is between zero and ceil(log_2(k)) - 1, inclusive.
-fn golomb_choose_number_of_base_bits(k: u32, count: u64) -> u8 {
+fn golomb_choose_number_of_base_bits(k: u64, count: u64) -> u8 {
debug_assert!(k > 0);
debug_assert!(count > 0);
- let quotient = ((k as u64) - count) / count; // integer division
+ let quotient = (k - count) / count; // integer division
if quotient == 0 {
0
} else {
@@ -320,18 +382,7 @@ fn golomb_choose_number_of_base_bits(k: u32, count: u64)
-> u8 {
fn floor_log2_of_long(x: u64) -> u8 {
debug_assert!(x > 0);
- let mut p = 0u8;
- let mut y = 1u64;
- loop {
- match u64::cmp(&y, &x) {
- Ordering::Equal => return p,
- Ordering::Greater => return p - 1,
- Ordering::Less => {
- p += 1;
- y <<= 1;
- }
- }
- }
+ (u64::BITS - 1 - x.leading_zeros()) as u8
}
#[cfg(test)]
diff --git a/datasketches/src/cpc/serialization.rs
b/datasketches/src/cpc/serialization.rs
index 36d25d3..46aa5ed 100644
--- a/datasketches/src/cpc/serialization.rs
+++ b/datasketches/src/cpc/serialization.rs
@@ -15,6 +15,12 @@
// specific language governing permissions and limitations
// under the License.
+use crate::codec::SketchBytes;
+use crate::codec::family::Family;
+use crate::cpc::compression::encode_window;
+use crate::cpc::compression::estimated_encoded_pair_bytes;
+use crate::cpc::compression::estimated_encoded_window_bytes;
+
pub const SERIAL_VERSION: u8 = 1;
pub const FLAG_COMPRESSED: u8 = 1;
pub const FLAG_HAS_HIP: u8 = 2;
@@ -46,3 +52,98 @@ pub fn make_preamble_ints(
}
preamble_ints
}
+
+pub fn serialize_compressed<W, F>(
+ lg_k: u8,
+ seed_hash: u16,
+ first_interesting_column: u8,
+ num_coupons: u32,
+ hip: Option<(f64, f64)>,
+ window: Option<W>,
+ table_num_entries: u32,
+ encode_table: F,
+) -> Vec<u8>
+where
+ W: IntoIterator<Item = u8>,
+ F: FnOnce(&mut SketchBytes) -> usize,
+{
+ let has_hip = hip.is_some();
+ let has_window = window.is_some();
+ let has_table = table_num_entries > 0;
+ let preamble_ints = make_preamble_ints(num_coupons, has_hip, has_table,
has_window);
+ let header_bytes = usize::from(preamble_ints) * size_of::<u32>();
+ let payload_bytes = if num_coupons == 0 {
+ 0
+ } else {
+ let window_bytes = if has_window {
+ estimated_encoded_window_bytes(lg_k, num_coupons)
+ } else {
+ 0
+ };
+ window_bytes + estimated_encoded_pair_bytes(table_num_entries, lg_k)
+ };
+
+ let mut bytes = SketchBytes::with_capacity(header_bytes + payload_bytes);
+ bytes.write_u8(preamble_ints);
+ bytes.write_u8(SERIAL_VERSION);
+ bytes.write_u8(Family::CPC.id);
+ bytes.write_u8(lg_k);
+ bytes.write_u8(first_interesting_column);
+ let flags = (1 << FLAG_COMPRESSED)
+ | (u8::from(has_hip) << FLAG_HAS_HIP)
+ | (u8::from(has_table) << FLAG_HAS_TABLE)
+ | (u8::from(has_window) << FLAG_HAS_WINDOW);
+ bytes.write_u8(flags);
+ bytes.write_u16_le(seed_hash);
+
+ if num_coupons == 0 {
+ return bytes.into_bytes();
+ }
+
+ bytes.write_u32_le(num_coupons);
+ let mut words_offset = 12;
+ if has_table && has_window {
+ // if there is no window it is the same as number of coupons
+ bytes.write_u32_le(table_num_entries);
+ words_offset += 4;
+ // HIP values can be in two different places in the sequence of fields
+ // this is the first HIP decision point
+ if let Some((kxp, hip_est_accum)) = hip {
+ bytes.write_f64_le(kxp);
+ bytes.write_f64_le(hip_est_accum);
+ words_offset += 16;
+ }
+ }
+ let table_words_offset = words_offset;
+ if has_table {
+ bytes.write_u32_le(0);
+ words_offset += 4;
+ }
+ let window_words_offset = words_offset;
+ if has_window {
+ bytes.write_u32_le(0);
+ }
+ // this is the second HIP decision point
+ if !(has_table && has_window) {
+ if let Some((kxp, hip_est_accum)) = hip {
+ bytes.write_f64_le(kxp);
+ bytes.write_f64_le(hip_est_accum);
+ }
+ }
+
+ let window_words = window.map(|w| encode_window(w, lg_k, num_coupons, &mut
bytes));
+ let table_words = has_table.then(|| encode_table(&mut bytes));
+
+ let mut out = bytes.into_bytes();
+ if let Some(table_words) = table_words {
+ debug_assert!(table_words <= u32::MAX as usize);
+ out[table_words_offset..table_words_offset + 4]
+ .copy_from_slice(&(table_words as u32).to_le_bytes());
+ }
+ if let Some(window_words) = window_words {
+ debug_assert!(window_words <= u32::MAX as usize);
+ out[window_words_offset..window_words_offset + 4]
+ .copy_from_slice(&(window_words as u32).to_le_bytes());
+ }
+ out
+}
diff --git a/datasketches/src/cpc/sketch.rs b/datasketches/src/cpc/sketch.rs
index a2ca362..931a5af 100644
--- a/datasketches/src/cpc/sketch.rs
+++ b/datasketches/src/cpc/sketch.rs
@@ -18,7 +18,6 @@
use std::fmt;
use std::hash::Hash;
-use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::assert::ensure_preamble_longs_in;
use crate::codec::assert::ensure_serial_version_is;
@@ -34,7 +33,6 @@ use crate::cpc::compression::decode_pairs;
use crate::cpc::compression::decode_window;
use crate::cpc::compression::determine_pseudo_phase;
use crate::cpc::compression::encode_pairs;
-use crate::cpc::compression::encode_window;
use crate::cpc::compression_data::COLUMN_PERMUTATIONS_FOR_DECODING;
use crate::cpc::compression_data::COLUMN_PERMUTATIONS_FOR_ENCODING;
use crate::cpc::determine_correct_offset;
@@ -50,6 +48,7 @@ use crate::cpc::serialization::FLAG_HAS_TABLE;
use crate::cpc::serialization::FLAG_HAS_WINDOW;
use crate::cpc::serialization::SERIAL_VERSION;
use crate::cpc::serialization::make_preamble_ints;
+use crate::cpc::serialization::serialize_compressed;
use crate::error::Error;
use crate::error::ErrorKind;
use crate::hash::DEFAULT_UPDATE_SEED;
@@ -489,7 +488,6 @@ impl CpcSketch {
/// The serialized data can be read by other DataSketches implementations.
pub fn serialize(&self) -> Vec<u8> {
let flavor = self.flavor();
- let has_hip = !self.merge_flag;
let has_window = matches!(flavor, Flavor::Pinned | Flavor::Sliding);
let mut pairs = match flavor {
Flavor::Empty => vec![],
@@ -558,64 +556,22 @@ impl CpcSketch {
};
pairs.sort_unstable();
- let table_num_entries = pairs.len() as u32;
- let mut payload = SketchBytes::with_capacity(if self.is_empty() { 0 }
else { 256 });
- let window_words = has_window.then(|| {
- encode_window(
- &self.sliding_window,
- self.lg_k,
- self.num_coupons,
- &mut payload,
- )
- });
- let table_words =
- (!pairs.is_empty()).then(|| encode_pairs(&pairs, self.lg_k, &mut
payload));
- let payload = payload.into_bytes();
-
- let has_table = table_words.is_some();
- let preamble_ints = make_preamble_ints(self.num_coupons, has_hip,
has_table, has_window);
- let mut bytes = SketchBytes::with_capacity(40 + payload.len());
- bytes.write_u8(preamble_ints);
- bytes.write_u8(SERIAL_VERSION);
- bytes.write_u8(Family::CPC.id);
- bytes.write_u8(self.lg_k);
- bytes.write_u8(self.first_interesting_column);
- let flags = (1 << FLAG_COMPRESSED)
- | (if has_hip { 1 } else { 0 } << FLAG_HAS_HIP)
- | (if has_table { 1 } else { 0 } << FLAG_HAS_TABLE)
- | (if has_window { 1 } else { 0 } << FLAG_HAS_WINDOW);
- bytes.write_u8(flags);
debug_assert_eq!(
self.seed_hash,
compute_seed_hash(self.seed, ErrorKind::InvalidArgument).unwrap()
);
- bytes.write_u16_le(self.seed_hash);
- if !self.is_empty() {
- bytes.write_u32_le(self.num_coupons);
- if has_table && has_window {
- // if there is no window it is the same as number of coupons
- bytes.write_u32_le(table_num_entries);
- // HIP values can be in two different places in the sequence
of fields
- // this is the first HIP decision point
- if has_hip {
- self.write_hip(&mut bytes);
- }
- }
- if let Some(table_words) = table_words {
- debug_assert!(table_words <= u32::MAX as usize);
- bytes.write_u32_le(table_words as u32);
- }
- if let Some(window_words) = window_words {
- debug_assert!(window_words <= u32::MAX as usize);
- bytes.write_u32_le(window_words as u32);
- }
- // this is the second HIP decision point
- if has_hip && !(has_table && has_window) {
- self.write_hip(&mut bytes);
- }
- bytes.write(&payload);
- }
- bytes.into_bytes()
+ let hip = (!self.merge_flag).then_some((self.kxp, self.hip_est_accum));
+ let window = has_window.then(|| self.sliding_window.iter().copied());
+ serialize_compressed(
+ self.lg_k,
+ self.seed_hash,
+ self.first_interesting_column,
+ self.num_coupons,
+ hip,
+ window,
+ pairs.len() as u32,
+ |bytes| encode_pairs(&pairs, self.lg_k, bytes),
+ )
}
/// Deserializes a `CpcSketch` from bytes.
@@ -891,9 +847,4 @@ impl CpcSketch {
hip_est_accum,
})
}
-
- fn write_hip(&self, bytes: &mut SketchBytes) {
- bytes.write_f64_le(self.kxp);
- bytes.write_f64_le(self.hip_est_accum);
- }
}
diff --git a/datasketches/src/cpc/union.rs b/datasketches/src/cpc/union.rs
index c7691a4..c7a40c9 100644
--- a/datasketches/src/cpc/union.rs
+++ b/datasketches/src/cpc/union.rs
@@ -59,21 +59,30 @@
//! [`CpcUnion::serialize`] borrows it directly. Its estimator state must
therefore be maintained
//! during merging, including input adoption and downsampling, rather than
repaired on export.
//!
-//! A bit matrix has no sliding window or surprise table. Both export paths
reconstruct these,
-//! along with the coupon count, window offset, and first interesting column,
through
-//! [`CpcUnion::to_sketch`]. The matrix does not preserve the stream history
needed by HIP, so
-//! the reconstructed sketch uses the merged estimator.
+//! A bit matrix has no sliding window or surprise table.
[`CpcUnion::to_sketch`] reconstructs
+//! both to return a mutable sketch, while [`CpcUnion::serialize`] streams the
window bytes and
+//! ordered coupon pairs directly from the matrix into the compressed encoder.
Neither export path
+//! has the stream history needed by HIP, so both emit the merged estimator
state.
use std::fmt;
+use std::iter::Empty;
+use crate::codec::SketchBytes;
use crate::cpc::CpcSketch;
use crate::cpc::DEFAULT_LG_K;
use crate::cpc::Flavor;
+use crate::cpc::compression::PairEncoder;
+use crate::cpc::compression::determine_pseudo_phase;
+use crate::cpc::compression_data::COLUMN_PERMUTATIONS_FOR_ENCODING;
use crate::cpc::count_bits_set_in_matrix;
use crate::cpc::determine_correct_offset;
+use crate::cpc::determine_flavor;
use crate::cpc::pair_table::PairTable;
+use crate::cpc::serialization::serialize_compressed;
use crate::error::Error;
+use crate::error::ErrorKind;
use crate::hash::DEFAULT_UPDATE_SEED;
+use crate::hash::compute_seed_hash;
/// Union operator for CPC sketches.
#[derive(Clone)]
@@ -97,7 +106,7 @@ enum UnionState {
/// A full coupon matrix, used once an input or the accumulator outgrows
sparse mode.
///
/// Row-wise OR combines coupon sets without maintaining a sketch's
compressed layout or
- /// estimator fields. Export must reconstruct that layout before it can
use the sketch encoder.
+ /// estimator fields. Export derives the window and surprise pairs from
the matrix on demand.
BitMatrix(Vec<u64>),
}
@@ -220,8 +229,8 @@ impl CpcUnion {
/// Serializes the union's result as a `CpcSketch`.
///
- /// Produces the same bytes as [`Self::to_sketch`] followed by
[`CpcSketch::serialize`],
- /// and can be faster.
+ /// Produces the same bytes as [`Self::to_sketch`] followed by
[`CpcSketch::serialize`]
+ /// without constructing an intermediate sketch.
///
/// # Examples
///
@@ -241,7 +250,7 @@ impl CpcUnion {
pub fn serialize(&self) -> Vec<u8> {
match &self.state {
UnionState::Accumulator(sketch) => sketch.serialize(),
- UnionState::BitMatrix(_) => self.to_sketch().serialize(),
+ UnionState::BitMatrix(matrix) => serialize_bit_matrix(matrix,
self.lg_k, self.seed),
}
}
@@ -477,3 +486,174 @@ fn merge_table_into_sketch(sketch: &mut CpcSketch, table:
&PairTable) {
k += stride;
}
}
+
+fn serialize_bit_matrix(matrix: &[u64], lg_k: u8, seed: u64) -> Vec<u8> {
+ let seed_hash = compute_seed_hash(seed, ErrorKind::InvalidArgument)
+ .expect("union seed was validated at construction");
+ let num_coupons = count_bits_set_in_matrix(matrix);
+ let flavor = determine_flavor(lg_k, num_coupons);
+
+ match flavor {
+ Flavor::Empty => {
+ serialize_compressed(lg_k, seed_hash, 0, 0, None,
None::<Empty<u8>>, 0, |_| 0)
+ }
+ Flavor::Sparse | Flavor::Hybrid => serialize_compressed(
+ lg_k,
+ seed_hash,
+ 0,
+ num_coupons,
+ None,
+ None::<Empty<u8>>,
+ num_coupons,
+ |bytes| encode_all_matrix_pairs(matrix, num_coupons, lg_k, bytes),
+ ),
+ Flavor::Pinned => {
+ let table_num_entries = matrix.iter().map(|&word| (word >>
8).count_ones()).sum();
+ let window = matrix.iter().map(|&word| (word & 0xFF) as u8);
+ serialize_compressed(
+ lg_k,
+ seed_hash,
+ 0,
+ num_coupons,
+ None,
+ Some(window),
+ table_num_entries,
+ |bytes| encode_pinned_matrix_pairs(matrix, table_num_entries,
lg_k, bytes),
+ )
+ }
+ Flavor::Sliding => {
+ let offset = determine_correct_offset(lg_k, num_coupons);
+ let clear_mask = (0xFFu64 << offset) ^ u64::MAX;
+ let flip_mask = (1u64 << offset) - 1;
+ let mut surprises = 0u64;
+ let mut table_num_entries = 0u32;
+ for &word in matrix {
+ let pattern = (word & clear_mask) ^ flip_mask;
+ surprises |= pattern;
+ table_num_entries += pattern.count_ones();
+ }
+ let first_interesting_column = (surprises.trailing_zeros() as
u8).min(offset);
+ let window = matrix.iter().map(|&word| ((word >> offset) & 0xFF)
as u8);
+ serialize_compressed(
+ lg_k,
+ seed_hash,
+ first_interesting_column,
+ num_coupons,
+ None,
+ Some(window),
+ table_num_entries,
+ |bytes| {
+ encode_sliding_matrix_pairs(
+ matrix,
+ lg_k,
+ num_coupons,
+ offset,
+ clear_mask,
+ flip_mask,
+ table_num_entries,
+ bytes,
+ )
+ },
+ )
+ }
+ }
+}
+
+/// Streams all set `(row, col)` bits in ascending row-major order.
+fn encode_all_matrix_pairs(
+ matrix: &[u64],
+ num_pairs: u32,
+ lg_k: u8,
+ bytes: &mut SketchBytes,
+) -> usize {
+ let mut encoder = PairEncoder::new(num_pairs, lg_k, bytes);
+ for (row, &word) in matrix.iter().enumerate() {
+ let row_prefix = (row as u32) << 6;
+ let mut pattern = word;
+ while pattern != 0 {
+ let col = pattern.trailing_zeros();
+ pattern &= pattern - 1;
+ encoder.write_pair(row_prefix | col);
+ }
+ }
+ encoder.finish()
+}
+
+/// Streams post-window `(row, col - 8)` surprise bits (`col >= 8`) in
ascending row-major order.
+fn encode_pinned_matrix_pairs(
+ matrix: &[u64],
+ num_pairs: u32,
+ lg_k: u8,
+ bytes: &mut SketchBytes,
+) -> usize {
+ let mut encoder = PairEncoder::new(num_pairs, lg_k, bytes);
+ for (row, &word) in matrix.iter().enumerate() {
+ let row_prefix = (row as u32) << 6;
+ let mut shifted = word >> 8;
+ while shifted != 0 {
+ let reduced_col = shifted.trailing_zeros();
+ shifted &= shifted - 1;
+ encoder.write_pair(row_prefix | reduced_col);
+ }
+ }
+ encoder.finish()
+}
+
+/// Streams sliding-flavor surprise pairs row by row, sorting permuted columns
within each row.
+fn encode_sliding_matrix_pairs(
+ matrix: &[u64],
+ lg_k: u8,
+ num_coupons: u32,
+ offset: u8,
+ clear_mask: u64,
+ flip_mask: u64,
+ num_pairs: u32,
+ bytes: &mut SketchBytes,
+) -> usize {
+ debug_assert!(offset <= 56);
+ let pseudo_phase = determine_pseudo_phase(lg_k, num_coupons);
+ let permutation = &COLUMN_PERMUTATIONS_FOR_ENCODING[pseudo_phase as usize];
+ let col_shift = 56 - offset;
+ let mut encoder = PairEncoder::new(num_pairs, lg_k, bytes);
+ let mut row_cols = [0u8; 56];
+
+ for (row, &word) in matrix.iter().enumerate() {
+ let mut pattern = (word & clear_mask) ^ flip_mask;
+ if pattern == 0 {
+ continue;
+ }
+
+ let row_prefix = (row as u32) << 6;
+ let first_col = pattern.trailing_zeros() as u8;
+ pattern &= pattern - 1;
+ let first_perm = permutation[((first_col + col_shift) & 63) as usize];
+ if pattern == 0 {
+ encoder.write_pair(row_prefix | u32::from(first_perm));
+ continue;
+ }
+
+ row_cols[0] = first_perm;
+ let mut len = 1;
+ while pattern != 0 {
+ let col = pattern.trailing_zeros() as u8;
+ pattern &= pattern - 1;
+ row_cols[len] = permutation[((col + col_shift) & 63) as usize];
+ len += 1;
+ }
+
+ // Rows are visited in ascending order; only permuted columns within
this row need sorting.
+ for i in 1..len {
+ let key = row_cols[i];
+ let mut j = i;
+ while j > 0 && row_cols[j - 1] > key {
+ row_cols[j] = row_cols[j - 1];
+ j -= 1;
+ }
+ row_cols[j] = key;
+ }
+ for &perm_col in &row_cols[..len] {
+ encoder.write_pair(row_prefix | u32::from(perm_col));
+ }
+ }
+ encoder.finish()
+}
diff --git a/tests-integration/tests/cpc_test/union.rs
b/tests-integration/tests/cpc_test/union.rs
index 963d0ee..9a30ec5 100644
--- a/tests-integration/tests/cpc_test/union.rs
+++ b/tests-integration/tests/cpc_test/union.rs
@@ -179,3 +179,121 @@ fn test_lg_k_too_large_returns_error() {
let error = CpcSketch::new(27).unwrap_err();
assert_eq!(error.kind(), ErrorKind::InvalidArgument);
}
+
+#[test]
+fn test_union_serialize_all_flavors_and_subsequent_merges() {
+ const SEED: u64 = 0x5eed_cafe;
+
+ // Covers Empty, Sparse, Hybrid, Pinned (without and with post-window
surprises), and Sliding
+ // across MIN_LG_K = 4 and lg_k = 8, spanning multiple window offsets and
permutation phases.
+ let cases: &[(u8, &[u64])] = &[
+ (4, &[0, 1, 3, 12, 40, 120, 500]),
+ (8, &[0, 10, 60, 180, 1_500, 3_000, 12_000, 50_000]),
+ ];
+
+ let mut saw_window_only = false;
+ let mut saw_window_and_table = false;
+ for &(lg_k, counts) in cases {
+ for &num_values in counts {
+ let mut union = CpcUnion::with_seed(lg_k, SEED).unwrap();
+ if num_values > 0 {
+ let split = num_values / 2;
+ let mut left = CpcSketch::with_seed(lg_k, SEED).unwrap();
+ for value in 0..split {
+ left.update(value);
+ }
+ let mut right = CpcSketch::with_seed(lg_k, SEED).unwrap();
+ for value in split..num_values {
+ right.update(value);
+ }
+ union.update(&left).unwrap();
+ union.update(&right).unwrap();
+ }
+
+ let bytes = union.serialize();
+ let expected_sketch = union.to_sketch();
+ assert_eq!(
+ bytes,
+ expected_sketch.serialize(),
+ "mismatch at lg_k={lg_k}, n={num_values}"
+ );
+
+ let flags = bytes[5];
+ let has_table = flags & (1 << 3) != 0;
+ let has_window = flags & (1 << 4) != 0;
+ if has_window && !has_table {
+ saw_window_only = true;
+ }
+ if has_window && has_table {
+ saw_window_and_table = true;
+ }
+
+ assert_eq!(
+ CpcSketch::deserialize(&bytes).unwrap_err().kind(),
+ ErrorKind::InvalidData
+ );
+ let decoded = CpcSketch::deserialize_with_seed(&bytes,
SEED).unwrap();
+ assert_eq!(decoded.lg_k(), expected_sketch.lg_k());
+ assert_eq!(decoded.is_empty(), expected_sketch.is_empty());
+ assert_eq!(decoded.estimate(), expected_sketch.estimate());
+
+ // Decoded union image must merge cleanly into downstream unions.
+ let mut extra = CpcSketch::with_seed(lg_k, SEED).unwrap();
+ for value in num_values..(num_values + 64) {
+ extra.update(value);
+ }
+
+ let mut downstream_from_bytes = CpcUnion::with_seed(lg_k,
SEED).unwrap();
+ downstream_from_bytes.update(&decoded).unwrap();
+ downstream_from_bytes.update(&extra).unwrap();
+
+ let mut downstream_from_sketch = CpcUnion::with_seed(lg_k,
SEED).unwrap();
+ downstream_from_sketch.update(&expected_sketch).unwrap();
+ downstream_from_sketch.update(&extra).unwrap();
+
+ assert_eq!(
+ downstream_from_bytes.serialize(),
+ downstream_from_sketch.to_sketch().serialize()
+ );
+ }
+ }
+
+ assert!(
+ saw_window_only,
+ "expected a pinned bit-matrix case without surprise table"
+ );
+ assert!(
+ saw_window_and_table,
+ "expected windowed bit-matrix cases with surprise table"
+ );
+}
+
+#[test]
+fn test_union_serialize_mixed_lg_k_downsampling_across_bit_matrix_flavors() {
+ let mut union = CpcUnion::new(11).unwrap();
+
+ // Progress through Sparse -> Hybrid -> Pinned -> Sliding while mixing
wider and narrower lg_k
+ // inputs so both source folding and bit-matrix downsampling are exercised
before serializing.
+ for (lg_k, range) in [
+ (12_u8, 0_u64..80),
+ (10, 40..450),
+ (11, 300..900),
+ (9, 500..2_200),
+ (10, 1_800..4_500),
+ (8, 2_000..15_000),
+ ] {
+ let mut sketch = CpcSketch::new(lg_k).unwrap();
+ for value in range {
+ sketch.update(value);
+ }
+ union.update(&sketch).unwrap();
+
+ let bytes = union.serialize();
+ let expected = union.to_sketch();
+ assert_eq!(bytes, expected.serialize());
+
+ let decoded = CpcSketch::deserialize(&bytes).unwrap();
+ assert_eq!(decoded.lg_k(), union.lg_k());
+ assert_eq!(decoded.estimate(), expected.estimate());
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]