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]

Reply via email to