Copilot commented on code in PR #172:
URL: https://github.com/apache/datasketches-rust/pull/172#discussion_r3667238391
##########
datasketches/tests/hll_test/union.rs:
##########
@@ -415,27 +414,71 @@ fn test_union_commutativity() {
sketch_b.update(i);
}
- // Union in order A, B
- let mut union1 = HllUnion::new(12);
- union1.update(&sketch_a);
- union1.update(&sketch_b);
+ let mut union_ab = HllUnion::new(12);
+ union_ab.update(&sketch_a);
+ union_ab.update(&sketch_b);
- // Union in order B, A
- let mut union2 = HllUnion::new(12);
- union2.update(&sketch_b);
- union2.update(&sketch_a);
+ let mut union_b_then_a = HllUnion::new(12);
+ union_b_then_a.update(&sketch_b);
+ union_b_then_a.update(&sketch_a);
- let est1 = union1.estimate();
- let est2 = union2.estimate();
+ assert_eq!(union_ab.estimate(), union_b_then_a.estimate());
+}
- let relative_diff = (est1 - est2).abs() / est1.max(est2);
- assert!(
- relative_diff < 0.001,
- "Union not commutative: {} vs {} (diff: {:.4}%)",
- est1,
- est2,
- relative_diff * 100.0
- );
+fn next_power_series_point(points_per_octave: i32, current: i64) -> i64 {
+ let current = current.max(1);
+ let mut generating_index =
+ ((current as f64).log2() * f64::from(points_per_octave)).round() as
i32;
+ loop {
+ generating_index += 1;
+ let next = 2_f64
+ .powf(f64::from(generating_index) / f64::from(points_per_octave))
+ .round() as i64;
+ if next > current {
+ return next;
+ }
+ }
+}
+
+fn power_series_sketch(start: i64, points_per_octave: i32, limit: i64) ->
HllSketch {
+ let mut sketch = HllSketch::new(11, HllType::Hll8);
+ let mut value = start;
+ while value < limit {
+ sketch.update(value);
+ value = next_power_series_point(points_per_octave, value);
+ }
+ sketch
+}
+
+fn merge_estimate(sketches: &[&HllSketch; 3], order: [usize; 3]) -> f64 {
+ let mut union = HllUnion::new(11);
+ for index in order {
+ union.update(sketches[index]);
+ }
+ union.estimate()
+}
+
+#[test]
+fn test_union_merge_order_regression() {
+ // Large fractional powers of two reproduce the reference implementation's
merge-order case.
+ let points_per_octave = 1 << 17;
+ let a = power_series_sketch(1_i64 << 59, points_per_octave, 1_i64 << 60);
+ let b = power_series_sketch(1_i64 << 60, points_per_octave, 1_i64 << 61);
+ let c = power_series_sketch(1_i64 << 61, points_per_octave, 1_i64 << 62);
Review Comment:
This test performs ~3 * points_per_octave updates (≈ 393k updates at 1<<17)
plus 6 merge passes, which can noticeably increase CI runtime for the full test
suite. Consider reducing `points_per_octave` to the smallest value that still
reproduces the reference merge-order regression, or precomputing a smaller
deterministic input set that triggers the same behavior (keeping the same
assertion).
##########
datasketches/tests/hll_test/union.rs:
##########
@@ -415,27 +414,71 @@ fn test_union_commutativity() {
sketch_b.update(i);
}
- // Union in order A, B
- let mut union1 = HllUnion::new(12);
- union1.update(&sketch_a);
- union1.update(&sketch_b);
+ let mut union_ab = HllUnion::new(12);
+ union_ab.update(&sketch_a);
+ union_ab.update(&sketch_b);
- // Union in order B, A
- let mut union2 = HllUnion::new(12);
- union2.update(&sketch_b);
- union2.update(&sketch_a);
+ let mut union_b_then_a = HllUnion::new(12);
+ union_b_then_a.update(&sketch_b);
+ union_b_then_a.update(&sketch_a);
- let est1 = union1.estimate();
- let est2 = union2.estimate();
+ assert_eq!(union_ab.estimate(), union_b_then_a.estimate());
+}
- let relative_diff = (est1 - est2).abs() / est1.max(est2);
- assert!(
- relative_diff < 0.001,
- "Union not commutative: {} vs {} (diff: {:.4}%)",
- est1,
- est2,
- relative_diff * 100.0
- );
+fn next_power_series_point(points_per_octave: i32, current: i64) -> i64 {
+ let current = current.max(1);
+ let mut generating_index =
+ ((current as f64).log2() * f64::from(points_per_octave)).round() as
i32;
+ loop {
+ generating_index += 1;
+ let next = 2_f64
+ .powf(f64::from(generating_index) / f64::from(points_per_octave))
+ .round() as i64;
+ if next > current {
+ return next;
+ }
+ }
+}
Review Comment:
The `round()`-based loop can take many iterations for small `current` (e.g.,
it may repeatedly round back to the same integer), and it also relies on
floating-point behavior to eventually progress. To make this helper more robust
and easier to reason about, compute the next generating index in a way that
guarantees `next > current` without an unbounded loop (and consider explicitly
rejecting `points_per_octave <= 0` since it would lead to invalid
math/division).
##########
datasketches/tests/theta_test/a_not_b.rs:
##########
@@ -187,23 +187,23 @@ fn test_result_ordering() {
}
#[test]
-fn test_estimation_partial_overlap_unordered() {
+fn test_estimation_lower_theta_b_unordered() {
let a = sketch_with_range(0, 10000);
- let b = sketch_with_range(5000, 10000);
+ let b = sketch_with_range(5000, 25000);
let a_not_b = ThetaANotB::default();
let r = a_not_b.compute(&a, &b, true).unwrap();
- // True difference size is 5000 (keys 0..5000).
+ // B is deliberately larger so its lower theta constrains the difference.
assert!(!r.is_empty());
assert!(r.is_estimation_mode());
- assert!((r.estimate() - 5000.0).abs() <= 5000.0 * 0.02);
+ assert!((r.estimate() - 5000.0).abs() <= 5000.0 * 0.03);
Review Comment:
This test’s intent is specifically about the result being constrained by B’s
lower theta, but the assertion only checks a looser estimate tolerance (now
3%), which may allow regressions that still fall within the widened error band.
Consider adding an explicit assertion about the theta relationship being
exercised (e.g., that the result theta matches/minimizes against the inputs in
the expected way) so the test directly guards the invariant described in the
comment.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
