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 e112e78  perf(cpc): merge coupon rows in contiguous blocks (#388)
e112e78 is described below

commit e112e786259b1aee0e247dad747279c6e8d6ed94
Author: tison <[email protected]>
AuthorDate: Thu Nov 19 16:52:18 2026 +0800

    perf(cpc): merge coupon rows in contiguous blocks (#388)
---
 CHANGELOG.md                              |  3 +-
 benchmarks/cpc/union.rs                   | 62 +++++++++++++++++++++++++++++--
 datasketches/src/cpc/union.rs             | 44 +++++++---------------
 tests-integration/tests/cpc_test/union.rs | 27 ++++++++------
 4 files changed, 88 insertions(+), 48 deletions(-)

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 8ec0535..fb67c46 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -10,7 +10,8 @@ All significant changes to this project will be documented in 
this file.
 
 ### Performance improvements
 
-* `CpcUnion::update` uses less time and temporary memory when the first 
nonempty input is a Sliding sketch at the union's effective precision.
+* `CpcUnion::update` is faster when merging sketches that contain many 
distinct values relative to their configured precision, including when the 
sketches have different precisions.
+* An empty `CpcUnion` can merge a high-cardinality sketch faster and with less 
temporary memory when the sketch's `lg_k` is less than or equal to the union's. 
For example, the first merge saves 16 KiB of temporary memory for a sketch of 
65,536 distinct values when both use `lg_k = 11`.
 
 ### Bug fixes
 
diff --git a/benchmarks/cpc/union.rs b/benchmarks/cpc/union.rs
index 478b772..d2dfcb1 100644
--- a/benchmarks/cpc/union.rs
+++ b/benchmarks/cpc/union.rs
@@ -22,12 +22,17 @@ use benchmarks::Runner;
 use datasketches::cpc::CpcSketch;
 use datasketches::cpc::CpcUnion;
 
+fn partial(lg_k: u8, first: u64, items: u64) -> CpcSketch {
+    let mut sketch = CpcSketch::new(lg_k).unwrap();
+    for value in first..first + items {
+        sketch.update(value);
+    }
+    sketch
+}
+
 fn empty_from_sliding(bencher: Bencher, lg_k: u8) {
     // Reuse one Sliding input across rounds so each fresh union measures its 
first merge.
-    let mut source = CpcSketch::new(lg_k).unwrap();
-    for value in 0..(32_u64 << lg_k) {
-        source.update(value);
-    }
+    let source = partial(lg_k, 0, 32_u64 << lg_k);
 
     bencher.bench_local(|| {
         let mut union = CpcUnion::new(lg_k).unwrap();
@@ -36,6 +41,41 @@ fn empty_from_sliding(bencher: Bencher, lg_k: u8) {
     });
 }
 
+fn merge_partials(bencher: Bencher, src_lg_k: u8, dst_lg_k: u8) {
+    let k = 1_u64 << src_lg_k;
+    // Uneven partitions produce sparse, hybrid, pinned, and sliding inputs in 
the same union.
+    let mut first = 0;
+    let partials = [k / 64, k / 4, 2 * k, 32 * k].map(|items| {
+        let sketch = partial(src_lg_k, first, items);
+        first += items;
+        sketch
+    });
+    bencher.bench_local(|| {
+        let mut union = CpcUnion::new(dst_lg_k).unwrap();
+        for sketch in black_box(&partials) {
+            union.update(sketch).unwrap();
+        }
+        union
+    });
+}
+
+fn merge_serialized_partials(bencher: Bencher, items_per_partition: u64) {
+    const LG_K: u8 = 21;
+    // A distributed group receives encoded partial states and emits an 
encoded result.
+    let partials: Vec<_> = (0..4)
+        .map(|i| partial(LG_K, i * items_per_partition, 
items_per_partition).serialize())
+        .collect();
+    bencher.bench_local(|| {
+        let mut union = CpcUnion::new(LG_K).unwrap();
+        for bytes in black_box(&partials) {
+            union
+                .update(&CpcSketch::deserialize(bytes).unwrap())
+                .unwrap();
+        }
+        union.to_sketch().serialize()
+    });
+}
+
 pub fn register(runner: &mut Runner) {
     for (lg_k, rounds) in [(11, 230_000), (14, 26_000)] {
         runner.case(
@@ -44,4 +84,18 @@ pub fn register(runner: &mut Runner) {
             |b| empty_from_sliding(b, lg_k),
         );
     }
+    for (src_lg_k, dst_lg_k, rounds) in [(11, 11, 100_000), (14, 11, 11_000)] {
+        runner.case(
+            format!("cpc::union::merge_partials/{src_lg_k}_into_{dst_lg_k}"),
+            rounds,
+            |b| merge_partials(b, src_lg_k, dst_lg_k),
+        );
+    }
+    for (items, rounds) in [(4_096, 550), (262_144, 13)] {
+        runner.case(
+            format!("cpc::union::merge_serialized_partials/lg21/{items}"),
+            rounds,
+            |b| merge_serialized_partials(b, items),
+        );
+    }
 }
diff --git a/datasketches/src/cpc/union.rs b/datasketches/src/cpc/union.rs
index 94b04e4..d89b70c 100644
--- a/datasketches/src/cpc/union.rs
+++ b/datasketches/src/cpc/union.rs
@@ -343,13 +343,9 @@ impl CpcUnion {
                 if matches!(flavor, Flavor::Hybrid | Flavor::Pinned) {
                     // [Case C] Hybrid, bitMatrix valid, accumulator == null
                     // [Case C] Pinned, bitMatrix valid, accumulator == null
-                    or_window_into_matrix(
-                        old_matrix,
-                        self.lg_k,
-                        &sketch.sliding_window,
-                        sketch.window_offset,
-                        sketch.lg_k(),
-                    );
+                    // Hybrid and Pinned windows occupy columns 0 through 7.
+                    debug_assert_eq!(sketch.window_offset, 0);
+                    or_rows_into_matrix(old_matrix, &sketch.sliding_window);
                     or_table_into_matrix(old_matrix, self.lg_k, 
sketch.surprising_value_table());
                     return Ok(());
                 }
@@ -359,7 +355,7 @@ impl CpcUnion {
                 // Instead, we convert it to a bitMatrix that can be ORed into 
the destination.
                 assert_eq!(flavor, Flavor::Sliding);
                 let src_matrix = sketch.build_bit_matrix();
-                or_matrix_into_matrix(old_matrix, self.lg_k, &src_matrix, 
sketch.lg_k());
+                or_rows_into_matrix(old_matrix, &src_matrix);
             }
         }
         Ok(())
@@ -394,7 +390,7 @@ impl CpcUnion {
             UnionState::BitMatrix(matrix) => {
                 let new_k = 1 << new_lg_k;
                 let mut new_matrix = vec![0; new_k];
-                or_matrix_into_matrix(&mut new_matrix, new_lg_k, matrix, 
self.lg_k);
+                or_rows_into_matrix(&mut new_matrix, matrix);
                 self.lg_k = new_lg_k;
                 self.state = UnionState::BitMatrix(new_matrix);
             }
@@ -427,21 +423,6 @@ impl fmt::Debug for CpcUnion {
     }
 }
 
-fn or_window_into_matrix(
-    dst_matrix: &mut [u64],
-    dst_lg_k: u8,
-    src_window: &[u8],
-    src_offset: u8,
-    src_lg_k: u8,
-) {
-    assert!(dst_lg_k <= src_lg_k);
-    let dst_mask = (1 << dst_lg_k) - 1; // downsamples when dst_lg_k < src_lg_k
-    let src_k = 1 << src_lg_k;
-    for src_row in 0..src_k {
-        dst_matrix[src_row & dst_mask] |= (src_window[src_row] as u64) << 
src_offset;
-    }
-}
-
 fn or_table_into_matrix(dst_matrix: &mut [u64], dst_lg_k: u8, src_table: 
&PairTable) {
     let dst_mask = (1 << dst_lg_k) - 1; // downsamples when dst_lg_k < src_lg_k
     let slots = src_table.slots();
@@ -455,13 +436,14 @@ fn or_table_into_matrix(dst_matrix: &mut [u64], dst_lg_k: 
u8, src_table: &PairTa
     }
 }
 
-fn or_matrix_into_matrix(dst_matrix: &mut [u64], dst_lg_k: u8, src_matrix: 
&[u64], src_lg_k: u8) {
-    assert!(dst_lg_k <= src_lg_k);
-    let dst_mask = (1 << dst_lg_k) - 1; // downsamples when dst_lg_k < src_lg_k
-    let src_k = 1 << src_lg_k;
-    for src_row in 0..src_k {
-        let dst_row = src_row & dst_mask;
-        dst_matrix[dst_row] |= src_matrix[src_row];
+fn or_rows_into_matrix<T: Copy + Into<u64>>(dst: &mut [u64], src: &[T]) {
+    // Folding keeps the low row bits, so every destination-sized block maps 
to the same rows.
+    let blocks = src.chunks_exact(dst.len());
+    debug_assert!(blocks.remainder().is_empty());
+    for block in blocks {
+        for (row, &bits) in dst.iter_mut().zip(block) {
+            *row |= bits.into();
+        }
     }
 }
 
diff --git a/tests-integration/tests/cpc_test/union.rs 
b/tests-integration/tests/cpc_test/union.rs
index a9bc6a8..baff1d3 100644
--- a/tests-integration/tests/cpc_test/union.rs
+++ b/tests-integration/tests/cpc_test/union.rs
@@ -105,19 +105,22 @@ fn test_sliding_union_matches_single_sketch() {
 }
 
 #[test]
-fn first_sliding_merge_folds_a_higher_precision_source() {
-    let mut wide = CpcSketch::new(10).unwrap();
-    let mut narrow = CpcSketch::new(8).unwrap();
-    for value in 0..32_768 {
-        wide.update(value);
-        narrow.update(value);
-    }
+fn union_folds_wider_coupon_rows_to_the_destination_precision() {
+    // Exercise a Hybrid, Pinned, and Sliding source with four rows per 
destination row.
+    for items in [256, 2_048, 32_768] {
+        let mut wide = CpcSketch::new(10).unwrap();
+        let mut narrow = CpcSketch::new(8).unwrap();
+        for value in 0..items {
+            wide.update(value);
+            narrow.update(value);
+        }
 
-    let mut folded = CpcUnion::new(8).unwrap();
-    folded.update(&wide).unwrap();
-    let mut direct = CpcUnion::new(8).unwrap();
-    direct.update(&narrow).unwrap();
-    assert_eq!(folded.serialize(), direct.serialize());
+        let mut folded = CpcUnion::new(8).unwrap();
+        folded.update(&wide).unwrap();
+        let mut direct = CpcUnion::new(8).unwrap();
+        direct.update(&narrow).unwrap();
+        assert_eq!(folded.serialize(), direct.serialize());
+    }
 }
 
 #[test]


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to