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]

Reply via email to