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]