Skip to content

Commit 0b2e638

Browse files
committed
refactor(hll): bind estimation state to owned registers
Keep dense registers and their estimation state in a single HllArray owner. Queries resolve statistics from that owner's registers, and bulk mutations invalidate statistics before writing, including when an input iterator panics partway through a merge. Select statistics storage by register representation. HLL4 and HLL6 maintain KxQ eagerly and use their existing zero-count metadata; only HLL8 uses OnceLock for deferred reconstruction. This restores the 88-byte HllSketch layout on aarch64 without changing the serialized representation. Route dense coupon batches directly to their stable register representation instead of dispatching through the sketch mode for each coupon. Cover HIP restoration, occupied-register bounds, and interrupted bulk writes at the owning-array boundary.
1 parent 6eb6363 commit 0b2e638

8 files changed

Lines changed: 722 additions & 768 deletions

File tree

‎datasketches/src/hll/array.rs‎

Lines changed: 333 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,333 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
use std::fmt::Debug;
19+
use std::sync::OnceLock;
20+
21+
use crate::common::NumStdDev;
22+
use crate::hll::Coupon;
23+
use crate::hll::array8::Registers8;
24+
use crate::hll::estimator::EstimateState;
25+
use crate::hll::estimator::Kxq;
26+
use crate::hll::estimator::RegisterStatistics;
27+
use crate::hll::estimator::relative_error;
28+
29+
/// A dense sketch's registers and the estimation state derived from those same registers.
30+
///
31+
/// All register mutations pass through this owner, so a caller cannot query statistics for
32+
/// a different register array or forget to invalidate statistics after a bulk merge.
33+
#[derive(Debug, Clone)]
34+
pub struct HllArray<R: Registers> {
35+
registers: R,
36+
state: EstimateState,
37+
statistics: R::Statistics,
38+
}
39+
40+
/// Physical register storage and the statistics maintenance it supports.
41+
pub trait Registers: Debug + Clone + PartialEq {
42+
type Statistics: StatisticsStorage;
43+
fn new(lg_config_k: u8) -> Self;
44+
fn lg_config_k(&self) -> u8;
45+
fn get(&self, slot: u32) -> u8;
46+
fn values(&self) -> impl Iterator<Item = u8>;
47+
fn num_zeros(&self) -> u32;
48+
fn is_empty(&self) -> bool;
49+
fn update(&mut self, coupon: Coupon) -> Option<(u8, u8)>;
50+
}
51+
52+
/// Eager sums for packed storage, or deferred statistics for bulk-mergeable storage.
53+
pub trait StatisticsStorage: Debug + Clone {
54+
fn from_serialized(kxq: Kxq, num_zeros: u32) -> Self;
55+
fn resolve(&self, registers: &impl Registers) -> RegisterStatistics;
56+
fn update(&mut self, state: &mut EstimateState, lg_config_k: u8, old: u8, new: u8);
57+
fn cached_num_zeros(&self) -> Option<u32> {
58+
None
59+
}
60+
}
61+
62+
impl StatisticsStorage for Kxq {
63+
fn from_serialized(kxq: Kxq, _: u32) -> Self {
64+
kxq
65+
}
66+
67+
fn resolve(&self, registers: &impl Registers) -> RegisterStatistics {
68+
RegisterStatistics {
69+
num_zeros: registers.num_zeros(),
70+
kxq: *self,
71+
}
72+
}
73+
74+
#[inline]
75+
fn update(&mut self, state: &mut EstimateState, lg_config_k: u8, old: u8, new: u8) {
76+
state.update(lg_config_k, self, old, new);
77+
}
78+
}
79+
80+
impl StatisticsStorage for OnceLock<RegisterStatistics> {
81+
fn from_serialized(kxq: Kxq, num_zeros: u32) -> Self {
82+
OnceLock::from(RegisterStatistics { num_zeros, kxq })
83+
}
84+
85+
fn resolve(&self, registers: &impl Registers) -> RegisterStatistics {
86+
*self.get_or_init(|| RegisterStatistics::from_registers(registers.values()))
87+
}
88+
89+
#[inline]
90+
fn update(&mut self, state: &mut EstimateState, lg_config_k: u8, old: u8, new: u8) {
91+
if let Some(statistics) = self.get_mut() {
92+
state.update(lg_config_k, &mut statistics.kxq, old, new);
93+
statistics.num_zeros -= u32::from(old == 0);
94+
} else {
95+
debug_assert_eq!(*state, EstimateState::Composite);
96+
}
97+
}
98+
99+
fn cached_num_zeros(&self) -> Option<u32> {
100+
self.get().map(|statistics| statistics.num_zeros)
101+
}
102+
}
103+
104+
impl<R: Registers> PartialEq for HllArray<R> {
105+
fn eq(&self, other: &Self) -> bool {
106+
self.registers == other.registers
107+
&& self.state == other.state
108+
&& self.statistics() == other.statistics()
109+
}
110+
}
111+
112+
impl<R: Registers> HllArray<R> {
113+
pub fn new(lg_config_k: u8) -> Self {
114+
Self::from_serialized(
115+
R::new(lg_config_k),
116+
0.0,
117+
(1 << lg_config_k) as f64,
118+
0.0,
119+
1 << lg_config_k,
120+
false,
121+
)
122+
}
123+
124+
pub fn from_serialized(
125+
registers: R,
126+
hip_accum: f64,
127+
kxq0: f64,
128+
kxq1: f64,
129+
num_zeros: u32,
130+
out_of_order: bool,
131+
) -> Self {
132+
Self {
133+
registers,
134+
state: EstimateState::from_serialized(hip_accum, out_of_order),
135+
statistics: R::Statistics::from_serialized(
136+
Kxq {
137+
low: kxq0,
138+
high: kxq1,
139+
},
140+
num_zeros,
141+
),
142+
}
143+
}
144+
145+
/// Returns storage for read-only encoding and representation-specific inspection.
146+
pub fn registers(&self) -> &R {
147+
&self.registers
148+
}
149+
150+
pub fn lg_config_k(&self) -> u8 {
151+
self.registers.lg_config_k()
152+
}
153+
154+
pub fn num_registers(&self) -> usize {
155+
1 << self.lg_config_k()
156+
}
157+
158+
pub fn get(&self, slot: u32) -> u8 {
159+
self.registers.get(slot)
160+
}
161+
162+
pub fn estimate_state(&self) -> EstimateState {
163+
self.state
164+
}
165+
166+
pub fn statistics(&self) -> RegisterStatistics {
167+
self.statistics.resolve(&self.registers)
168+
}
169+
170+
#[inline]
171+
pub fn update(&mut self, coupon: Coupon) {
172+
if let Some((old, new)) = self.registers.update(coupon) {
173+
self.statistics
174+
.update(&mut self.state, self.registers.lg_config_k(), old, new);
175+
}
176+
}
177+
178+
pub fn restore_estimate_state(&mut self, state: EstimateState) {
179+
if let EstimateState::Hip(_) = state {
180+
// Resuming HIP requires current sums before the next scalar update.
181+
self.statistics();
182+
}
183+
self.state = state;
184+
}
185+
186+
pub fn estimate(&self) -> f64 {
187+
match self.state {
188+
EstimateState::Hip(value) => value,
189+
EstimateState::Composite => self.composite_estimate(),
190+
}
191+
}
192+
193+
pub fn composite_estimate(&self) -> f64 {
194+
self.statistics().composite_estimate(self.lg_config_k())
195+
}
196+
197+
pub fn upper_bound(&self, num_std_dev: NumStdDev) -> f64 {
198+
let rse = relative_error(
199+
self.lg_config_k(),
200+
true,
201+
self.state.uses_composite_estimate(),
202+
num_std_dev,
203+
);
204+
self.estimate() / (1.0 + rse)
205+
}
206+
207+
pub fn lower_bound(&self, num_std_dev: NumStdDev) -> f64 {
208+
let statistics = self.statistics();
209+
let estimate = match self.state {
210+
EstimateState::Hip(value) => value,
211+
EstimateState::Composite => statistics.composite_estimate(self.lg_config_k()),
212+
};
213+
let rse = relative_error(
214+
self.lg_config_k(),
215+
false,
216+
self.state.uses_composite_estimate(),
217+
num_std_dev,
218+
);
219+
(estimate / (1.0 + rse)).max(f64::from((1 << self.lg_config_k()) - statistics.num_zeros))
220+
}
221+
222+
pub fn is_empty(&self) -> bool {
223+
match self.statistics.cached_num_zeros() {
224+
Some(num_zeros) => num_zeros == (1 << self.lg_config_k()),
225+
// Do not rebuild statistics just to answer emptiness between bulk merges.
226+
None => self.registers.is_empty(),
227+
}
228+
}
229+
}
230+
231+
impl HllArray<Registers8> {
232+
pub fn values(&self) -> &[u8] {
233+
self.registers.as_slice()
234+
}
235+
236+
fn invalidate(&mut self) {
237+
self.state = EstimateState::Composite;
238+
self.statistics.take();
239+
}
240+
241+
pub fn merge_registers(&mut self, values: impl Iterator<Item = (usize, u8)>) {
242+
// Invalidate before consuming the iterator so a panic cannot leave stale statistics.
243+
self.invalidate();
244+
self.registers.merge_registers(values);
245+
}
246+
247+
pub fn merge_array_same_lgk(&mut self, src: &[u8]) {
248+
assert_eq!(
249+
src.len(),
250+
self.num_registers(),
251+
"Source and destination must have same lg_k"
252+
);
253+
self.invalidate();
254+
self.registers.merge_same_lgk(src);
255+
}
256+
257+
pub fn merge_array_with_downsample(&mut self, src: &[u8], src_lg_k: u8) {
258+
assert!(
259+
src_lg_k > self.lg_config_k(),
260+
"Source lg_k must be greater than destination lg_k for downsampling"
261+
);
262+
assert_eq!(
263+
src.len(),
264+
1 << src_lg_k,
265+
"Source length must match 2^src_lg_k"
266+
);
267+
self.invalidate();
268+
self.registers.merge_with_downsample(src);
269+
}
270+
}
271+
272+
#[cfg(test)]
273+
mod tests {
274+
use super::*;
275+
use crate::hll::array4::Registers4;
276+
use crate::hll::array6::Registers6;
277+
use crate::hll::array8::Array8;
278+
279+
#[test]
280+
fn lower_bounds_respect_occupied_registers_in_every_representation() {
281+
fn check<R: Registers>() {
282+
let mut array = HllArray::<R>::new(4);
283+
for slot in 0..8 {
284+
array.update(Coupon::pack(slot, 1));
285+
}
286+
assert_eq!(array.lower_bound(NumStdDev::Three), 8.0);
287+
for slot in 8..16 {
288+
array.update(Coupon::pack(slot, 1));
289+
}
290+
assert_eq!(array.lower_bound(NumStdDev::Three), 16.0);
291+
}
292+
check::<Registers4>();
293+
check::<Registers6>();
294+
check::<Registers8>();
295+
}
296+
297+
#[test]
298+
fn restored_hip_supports_updates_after_deferred_reconstruction() {
299+
let mut eager = Array8::new(4);
300+
for (slot, value) in [(0, 4), (1, 32), (2, 63)] {
301+
eager.update(Coupon::pack(slot, value));
302+
}
303+
let history = eager.estimate_state();
304+
let mut deferred = eager.clone();
305+
// Merging zero registers leaves the data unchanged but discards update history.
306+
deferred.merge_array_same_lgk(&[0; 16]);
307+
deferred.restore_estimate_state(history);
308+
for (slot, value) in [(3, 2), (0, 33), (3, 5)] {
309+
eager.update(Coupon::pack(slot, value));
310+
deferred.update(Coupon::pack(slot, value));
311+
}
312+
assert_eq!(deferred.estimate(), eager.estimate());
313+
assert_eq!(deferred.serialize(), eager.serialize());
314+
}
315+
316+
#[test]
317+
fn interrupted_bulk_merge_cannot_leave_stale_statistics() {
318+
let mut array = Array8::new(4);
319+
array.update(Coupon::pack(0, 1));
320+
let mut expected = array.clone();
321+
expected.merge_registers(std::iter::once((1, 5)));
322+
323+
let result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
324+
array.merge_registers((1..3).map(|slot| {
325+
assert_eq!(slot, 1, "interrupted register input");
326+
(slot, 5)
327+
}));
328+
}));
329+
assert!(result.is_err());
330+
assert_eq!(array.estimate(), expected.estimate());
331+
assert_eq!(array.serialize(), expected.serialize());
332+
}
333+
}

0 commit comments

Comments
 (0)