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 a3de7e9 perf(cpc): reuse the source matrix for the first sliding
merge (#387)
a3de7e9 is described below
commit a3de7e96dd482a61c15e62c6875405f83b368ea8
Author: tison <[email protected]>
AuthorDate: Thu Nov 19 15:20:42 2026 +0800
perf(cpc): reuse the source matrix for the first sliding merge (#387)
---
CHANGELOG.md | 4 +++
benchmarks/cpc/mod.rs | 2 ++
benchmarks/cpc/union.rs | 47 +++++++++++++++++++++++++++++++
datasketches/src/cpc/union.rs | 8 ++++++
tests-integration/tests/cpc_test/union.rs | 16 +++++++++++
5 files changed, 77 insertions(+)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 289c576..8ec0535 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -8,6 +8,10 @@ All significant changes to this project will be documented in
this file.
* Add `DensitySketch`, `Kernel`, `GaussianKernel`, `DensityValue`, and
`DensitySketchIter` behind the `density` feature for streaming kernel density
estimation and coreset construction over multidimensional `f32` and `f64`
vectors, with custom kernel support, merging, iteration, and cross-language
serialization.
+### 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.
+
### Bug fixes
* `HllSketch::serialize` and `HllUnion::serialize` now set the compact flag in
serialized `HllType::Hll6` and `HllType::Hll8` HLL-mode headers, matching the
compact wire format expected by cross-language DataSketches readers;
deserialization continues to accept images with or without the flag.
diff --git a/benchmarks/cpc/mod.rs b/benchmarks/cpc/mod.rs
index 32c8b7f..7c950ee 100644
--- a/benchmarks/cpc/mod.rs
+++ b/benchmarks/cpc/mod.rs
@@ -16,9 +16,11 @@
// under the License.
mod serde;
+mod union;
mod update;
pub fn register(runner: &mut benchmarks::Runner) {
serde::register(runner);
+ union::register(runner);
update::register(runner);
}
diff --git a/benchmarks/cpc/union.rs b/benchmarks/cpc/union.rs
new file mode 100644
index 0000000..478b772
--- /dev/null
+++ b/benchmarks/cpc/union.rs
@@ -0,0 +1,47 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::hint::black_box;
+
+use benchmarks::Bencher;
+use benchmarks::Runner;
+use datasketches::cpc::CpcSketch;
+use datasketches::cpc::CpcUnion;
+
+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);
+ }
+
+ bencher.bench_local(|| {
+ let mut union = CpcUnion::new(lg_k).unwrap();
+ union.update(black_box(&source)).unwrap();
+ union
+ });
+}
+
+pub fn register(runner: &mut Runner) {
+ for (lg_k, rounds) in [(11, 230_000), (14, 26_000)] {
+ runner.case(
+ format!("cpc::union::empty_from_sliding/{lg_k}"),
+ rounds,
+ |b| empty_from_sliding(b, lg_k),
+ );
+ }
+}
diff --git a/datasketches/src/cpc/union.rs b/datasketches/src/cpc/union.rs
index c7a40c9..94b04e4 100644
--- a/datasketches/src/cpc/union.rs
+++ b/datasketches/src/cpc/union.rs
@@ -280,6 +280,14 @@ impl CpcUnion {
// if source is past SPARSE mode, make sure that union is a bitMatrix.
if flavor > Flavor::Sparse {
if let UnionState::Accumulator(old_sketch) = &self.state {
+ if flavor == Flavor::Sliding && old_sketch.is_empty() &&
self.lg_k == sketch.lg_k()
+ {
+ // At equal precision, each source row is already the
result of OR with
+ // the corresponding zero row in the empty union.
+ self.state =
UnionState::BitMatrix(sketch.build_bit_matrix());
+ return Ok(());
+ }
+
// convert the accumulator to a bit matrix
let bit_matrix = old_sketch.build_bit_matrix();
self.state = UnionState::BitMatrix(bit_matrix);
diff --git a/tests-integration/tests/cpc_test/union.rs
b/tests-integration/tests/cpc_test/union.rs
index 9a30ec5..a9bc6a8 100644
--- a/tests-integration/tests/cpc_test/union.rs
+++ b/tests-integration/tests/cpc_test/union.rs
@@ -104,6 +104,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);
+ }
+
+ 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]
fn test_reduce_k_empty() {
let mut sketch = CpcSketch::new(11).unwrap();
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]