|
| 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