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 1d2d406 refactor(hll): simplify coupon serialization and
documentation (#291)
1d2d406 is described below
commit 1d2d406f81f85a44c2c3e89c4d8b9d2d9b4cefb9
Author: tison <[email protected]>
AuthorDate: Mon Oct 5 14:47:30 2026 +0800
refactor(hll): simplify coupon serialization and documentation (#291)
---
datasketches/src/hll/array4.rs | 100 +++-----------
datasketches/src/hll/array6.rs | 69 +---------
datasketches/src/hll/array8.rs | 123 ++---------------
datasketches/src/hll/aux_map.rs | 67 ++--------
datasketches/src/hll/composite_interpolation.rs | 23 +---
datasketches/src/hll/container.rs | 19 +--
datasketches/src/hll/coupon_mapping.rs | 7 +-
datasketches/src/hll/cubic_interpolation.rs | 23 +---
datasketches/src/hll/estimator.rs | 136 ++++---------------
datasketches/src/hll/harmonic_numbers.rs | 35 +----
datasketches/src/hll/hash_set.rs | 56 ++------
datasketches/src/hll/list.rs | 49 +------
datasketches/src/hll/mod.rs | 108 ++++-----------
datasketches/src/hll/serialization.rs | 34 +----
datasketches/src/hll/sketch.rs | 105 +++++++--------
datasketches/src/hll/union.rs | 171 +++++++++++-------------
16 files changed, 257 insertions(+), 868 deletions(-)
diff --git a/datasketches/src/hll/array4.rs b/datasketches/src/hll/array4.rs
index 2380e00..1a13059 100644
--- a/datasketches/src/hll/array4.rs
+++ b/datasketches/src/hll/array4.rs
@@ -15,11 +15,6 @@
// specific language governing permissions and limitations
// under the License.
-//! HyperLogLog Array4 mode - 4-bit packed representation with exception
handling
-//!
-//! Array4 stores HLL register values using 4 bits per slot (2 slots per byte).
-//! When values exceed 4 bits after cur_min offset, they're stored in an
auxiliary hash map.
-
use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::assert::insufficient_data;
@@ -58,18 +53,16 @@ impl AuxFormat {
}
}
-/// Core Array4 data structure - stores 4-bit values efficiently
+/// Registers stored as four-bit offsets from their current minimum.
#[derive(Debug, Clone, PartialEq)]
pub struct Array4 {
lg_config_k: u8,
- /// Packed 4-bit values: 2 values per byte
- /// Even slots use low nibble, odd slots use high nibble
+ /// Even slots occupy the low nibble; odd slots occupy the high nibble.
bytes: Box<[u8]>,
- /// Current minimum value offset (optimization to delay aux map creation)
cur_min: u8,
- /// Count of slots at exactly cur_min (when 0, increment cur_min)
+ /// When this reaches zero, the offset must increase until it reaches the
new minimum.
num_at_cur_min: u32,
- /// Exception table for values >= 15 after cur_min offset
+ /// Every `AUX_TOKEN` nibble has an entry here containing the absolute
register value.
aux_map: Option<AuxMap>,
estimator: Estimator,
}
@@ -88,49 +81,35 @@ impl Array4 {
}
}
- /// Get raw 4-bit value from slot (not adjusted for cur_min)
#[inline]
fn get_raw(&self, slot: u32) -> u8 {
debug_assert!(slot >> 1 < self.bytes.len() as u32);
let byte = self.bytes[(slot >> 1) as usize];
- if slot & 1 == 0 {
- byte & 15 // low nibble for even slots
- } else {
- byte >> 4 // high nibble for odd slots
- }
+ if slot & 1 == 0 { byte & 15 } else { byte >> 4 }
}
- /// Get the actual value at a slot (adjusted for cur_min and aux_map)
- ///
- /// Returns the true register value:
- /// * If raw < 15: value = cur_min + raw
- /// * If raw == 15 (AUX_TOKEN): value is in aux_map
pub fn get(&self, slot: u32) -> u8 {
let raw = self.get_raw(slot);
if raw < AUX_TOKEN {
self.cur_min + raw
} else {
- // Value is in aux_map
self.aux_map
.as_ref()
.and_then(|map| map.get(slot))
- .unwrap_or(self.cur_min) // Fallback (shouldn't happen)
+ .unwrap_or(self.cur_min)
}
}
- /// Get the number of registers (K = 2^lg_config_k)
pub fn num_registers(&self) -> usize {
1 << self.lg_config_k
}
- /// Returns the estimate state independently from register-derived cached
values.
pub fn estimate_state(&self) -> EstimateState {
self.estimator.estimate_state()
}
- /// Set raw 4-bit value in slot
#[inline]
fn put_raw(&mut self, slot: u32, value: u8) {
debug_assert!(value <= AUX_TOKEN);
@@ -139,9 +118,9 @@ impl Array4 {
let byte_idx = (slot >> 1) as usize;
let old_byte = self.bytes[byte_idx];
self.bytes[byte_idx] = if slot & 1 == 0 {
- (old_byte & 0xF0) | (value & 0x0F) // set low nibble
+ (old_byte & 0xF0) | (value & 0x0F)
} else {
- (old_byte & 0x0F) | (value << 4) // set high nibble
+ (old_byte & 0x0F) | (value << 4)
};
}
@@ -150,7 +129,6 @@ impl Array4 {
let slot = coupon.slot() & mask;
let new_value = coupon.value();
- // Quick rejection: if new value <= cur_min, no update needed
if new_value <= self.cur_min {
return;
}
@@ -162,7 +140,6 @@ impl Array4 {
return;
}
- // Get actual old value (might be in aux map)
let old_value = if raw_stored < AUX_TOKEN {
lower_bound
} else {
@@ -177,26 +154,22 @@ impl Array4 {
return;
}
- // Update HIP and KxQ registers via estimator
self.estimator
.update(self.lg_config_k, old_value, new_value);
let shifted_new = new_value - self.cur_min;
- // Four cases based on old/new exception status
match (raw_stored, shifted_new) {
- // Case 1: Both old and new are exceptions
(AUX_TOKEN, shifted) if shifted >= AUX_TOKEN => {
self.aux_map
.as_mut()
.expect("aux_map should be initialized since stored value
is AUX_TOKEN")
.replace(slot, new_value);
}
- // Case 2: Old is exception, new is not (impossible without
cur_min change)
+ // Registers only increase here; an exception cannot disappear
until cur_min changes.
(AUX_TOKEN, _) => {
unreachable!("AUX_TOKEN present with non-exception new value");
}
- // Case 3: Old not exception, new is exception
(_, shifted) if shifted >= AUX_TOKEN => {
self.put_raw(slot, AUX_TOKEN);
let aux = self
@@ -204,13 +177,11 @@ impl Array4 {
.get_or_insert_with(|| AuxMap::new(self.lg_config_k));
aux.insert(slot, new_value);
}
- // Case 4: Neither is exception
_ => {
self.put_raw(slot, shifted_new);
}
}
- // Handle cur_min adjustment
if old_value == self.cur_min {
self.num_at_cur_min -= 1;
while self.num_at_cur_min == 0 {
@@ -219,17 +190,13 @@ impl Array4 {
}
}
- /// Increment cur_min and adjust all values
- ///
- /// This is called when no slots remain at cur_min value.
- /// All stored values are decremented by 1, and exceptions
- /// that fall back into the 4-bit range are moved from aux map.
+ /// Requires no registers at `cur_min`. Raising the offset makes some
auxiliary values
+ /// fit in the nibbles again; the logical register values must stay
unchanged.
fn shift_to_bigger_cur_min(&mut self) {
let new_cur_min = self.cur_min + 1;
let k = 1 << self.lg_config_k;
let mut num_at_new = 0;
- // Decrement all stored values in the main array
for slot in 0..k {
let raw = self.get_raw(slot);
debug_assert_ne!(raw, 0, "value cannot be 0 when shifting
cur_min");
@@ -258,7 +225,6 @@ impl Array4 {
if new_shifted < AUX_TOKEN {
self.put_raw(slot, new_shifted);
} else {
- // Still an exception
let aux = new_aux.get_or_insert_with(||
AuxMap::new(self.lg_config_k));
aux.insert(slot, old_actual_val);
}
@@ -270,14 +236,11 @@ impl Array4 {
self.num_at_cur_min = num_at_new;
}
- /// Returns the current cardinality estimate.
pub fn estimate(&self) -> f64 {
- // Array4 tracks cur_min and num_at_cur_min dynamically
self.estimator
.estimate(self.lg_config_k, self.cur_min, self.num_at_cur_min)
}
- /// Get upper bound for cardinality estimate
pub fn upper_bound(&self, num_std_dev: NumStdDev) -> f64 {
self.estimator.upper_bound(
self.lg_config_k,
@@ -287,7 +250,6 @@ impl Array4 {
)
}
- /// Get lower bound for cardinality estimate
pub fn lower_bound(&self, num_std_dev: NumStdDev) -> f64 {
self.estimator.lower_bound(
self.lg_config_k,
@@ -297,19 +259,14 @@ impl Array4 {
)
}
- /// Restores estimate state after copying or transforming the same logical
sketch.
pub fn restore_estimate_state(&mut self, state: EstimateState) {
self.estimator.restore_estimate_state(state);
}
- /// Check if the sketch is empty (all slots are zero)
pub fn is_empty(&self) -> bool {
self.num_at_cur_min == (1 << self.lg_config_k) && self.cur_min == 0
}
- /// Deserialize Array4 from HLL mode bytes
- ///
- /// Expects full HLL preamble (40 bytes) followed by packed 4-bit data and
optional aux map.
pub fn deserialize(
mut cursor: SketchSlice,
cur_min: u8,
@@ -318,16 +275,14 @@ impl Array4 {
ooo: bool,
) -> Result<Self, Error> {
let k = 1usize << lg_config_k;
- let num_bytes = 1usize << (lg_config_k - 1); // k/2 bytes for 4-bit
packing
+ let num_bytes = 1usize << (lg_config_k - 1);
- // Read estimator values from preamble
let hip_accum = cursor
.read_f64_le()
.map_err(insufficient_data("hip_accum"))?;
let kxq0 = cursor.read_f64_le().map_err(insufficient_data("kxq0"))?;
let kxq1 = cursor.read_f64_le().map_err(insufficient_data("kxq1"))?;
- // Read num_at_cur_min and aux_count
let num_at_cur_min = cursor
.read_u32_le()
.map_err(insufficient_data("num_at_cur_min"))?;
@@ -364,13 +319,11 @@ impl Array4 {
));
}
- // Read packed 4-bit byte array
let mut data = vec![0u8; num_bytes];
cursor
.read_exact(&mut data)
.map_err(insufficient_data("data"))?;
- // Read aux map if present
let mut aux_map = None;
if aux_count > 0 {
let mut aux = AuxMap::new(lg_config_k);
@@ -414,13 +367,10 @@ impl Array4 {
})
}
- /// Serialize Array4 to bytes
- ///
- /// Produces full HLL preamble (40 bytes) followed by packed 4-bit data
and optional aux map.
+ /// Writes packed registers followed by compact auxiliary entries.
pub fn serialize(&self, lg_config_k: u8) -> Vec<u8> {
- let num_bytes = 1 << (lg_config_k - 1); // k/2 bytes for 4-bit packing
+ let num_bytes = 1 << (lg_config_k - 1);
- // Collect aux map entries if present
let aux_entries: Vec<(u32, u8)> = if let Some(aux) = &self.aux_map {
aux.iter().collect()
} else {
@@ -431,43 +381,32 @@ impl Array4 {
let total_size = HLL_PREAMBLE_SIZE + num_bytes + (aux_count as usize *
COUPON_SIZE_BYTES);
let mut bytes = SketchBytes::with_capacity(total_size);
- // Write standard header
bytes.write_u8(HLL_PREINTS);
bytes.write_u8(SERIAL_VERSION);
bytes.write_u8(Family::HLL.id);
bytes.write_u8(lg_config_k);
- bytes.write_u8(0); // unused for HLL mode
+ bytes.write_u8(0); // lg_arr is unused for compact auxiliary storage.
- // Write flags.
- // COMPACT_FLAG_MASK is always set: aux map entries are written as a
compact sequential
- // list of populated entries only.
let mut flags = COMPACT_FLAG_MASK;
if self.estimator.uses_composite_estimate() {
flags |= OUT_OF_ORDER_FLAG_MASK;
}
bytes.write_u8(flags);
- // Write cur_min
bytes.write_u8(self.cur_min);
- // Mode byte: HLL mode with HLL4 type
bytes.write_u8(encode_mode_byte(CUR_MODE_HLL, TGT_HLL4));
- // Write estimator values
bytes.write_f64_le(self.estimator.hip_accum());
bytes.write_f64_le(self.estimator.kxq0());
bytes.write_f64_le(self.estimator.kxq1());
- // Write num_at_cur_min
bytes.write_u32_le(self.num_at_cur_min);
- // Write aux_count
bytes.write_u32_le(aux_count);
- // Write packed 4-bit byte array
bytes.write(&self.bytes);
- // Write aux map entries if present
for (slot, value) in aux_entries.iter().copied() {
bytes.write_u32_le(Coupon::pack(slot, value).raw());
}
@@ -512,7 +451,6 @@ mod tests {
// Both values should be stored in the same byte
assert_eq!(data.bytes[0], 0x75); // 0111_0101 = 7 << 4 | 5
- // Test multiple slots
data.put_raw(2, 15);
data.put_raw(3, 3);
assert_eq!(data.get_raw(2), 15);
@@ -523,24 +461,18 @@ mod tests {
fn test_hip_estimator_basic() {
let mut arr = Array4::new(10); // 1024 buckets
- // Initially estimate should be 0
assert_eq!(arr.estimate(), 0.0);
- // Add some unique values to different slots
for i in 0..10_000u32 {
arr.update(Coupon::from_value(i));
}
- // Estimate should be positive and roughly in the ballpark
- // (not exact, but should be non-zero and not NaN/Inf)
let estimate = arr.estimate();
assert_that!(estimate, gt(0.0));
assert_that!(estimate, is_finite());
assert_that!(estimate, lt(100_000.0));
- // Rough sanity check: with 100 updates to different slots,
- // estimate should be in a reasonable range (very loose bounds)
assert_that!(estimate, gt(1_000.0));
assert_that!(estimate, lt(100_000.0));
}
@@ -549,11 +481,9 @@ mod tests {
fn test_kxq_register_split() {
let mut arr = Array4::new(8); // 256 buckets
- // Test that values < 32 and >= 32 are handled correctly
arr.update(Coupon::pack(0, 10)); // value < 32, goes to kxq0
arr.update(Coupon::pack(1, 40)); // value >= 32, goes to kxq1
- // Verify registers were updated (not exact values, just check they
changed)
// kxq0 should have decreased (we removed a 0 and added a 10)
// Initial kxq0 = 256 (all zeros = 1.0 each)
assert_that!(arr.estimator.kxq0(), lt(256.0));
diff --git a/datasketches/src/hll/array6.rs b/datasketches/src/hll/array6.rs
index 3654bb8..a1b0032 100644
--- a/datasketches/src/hll/array6.rs
+++ b/datasketches/src/hll/array6.rs
@@ -15,12 +15,6 @@
// specific language governing permissions and limitations
// under the License.
-//! HyperLogLog Array6 mode - 6-bit packed representation
-//!
-//! Array6 stores HLL register values using 6 bits per slot, providing a range
of 0-63.
-//! This is sufficient for most HLL use cases without needing exception
handling or
-//! cur_min optimization like Array4.
-
use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::assert::insufficient_data;
@@ -38,15 +32,13 @@ use crate::hll::serialization::SERIAL_VERSION;
use crate::hll::serialization::TGT_HLL6;
use crate::hll::serialization::encode_mode_byte;
-const VAL_MASK_6: u16 = 0x3F; // 6 bits: 0b0011_1111
+const VAL_MASK_6: u16 = 0x3F;
-/// Core Array6 data structure - stores 6-bit values with cross-byte packing
+/// Registers packed into consecutive six-bit fields.
#[derive(Debug, Clone, PartialEq)]
pub struct Array6 {
lg_config_k: u8,
- /// Packed 6-bit values, may cross byte boundaries
bytes: Box<[u8]>,
- /// Count of slots with value 0
num_zeros: u32,
estimator: Estimator,
}
@@ -64,41 +56,30 @@ impl Array6 {
}
}
- /// Get value from a slot (6-bit value)
- ///
- /// Uses 16-bit window reads to handle values crossing byte boundaries.
#[inline]
fn get_raw(&self, slot: u32) -> u8 {
let start_bit = slot * 6;
- let byte_idx = (start_bit >> 3) as usize; // Divide by 8
- let shift = (start_bit & 7) as u8; // Mod 8
+ let byte_idx = (start_bit >> 3) as usize;
+ let shift = (start_bit & 7) as u8;
- // Read 2 bytes as u16 (little-endian)
let two_bytes = u16::from_le_bytes([self.bytes[byte_idx],
self.bytes[byte_idx + 1]]);
- // Extract 6 bits at the shift position
((two_bytes >> shift) & VAL_MASK_6) as u8
}
- /// Get the unpacked 6-bit value (0-63) at the given slot
#[inline]
pub fn get(&self, slot: u32) -> u8 {
self.get_raw(slot)
}
- /// Get the number of registers (K = 2^lg_config_k)
pub fn num_registers(&self) -> usize {
1 << self.lg_config_k
}
- /// Returns the estimate state independently from register-derived cached
values.
pub fn estimate_state(&self) -> EstimateState {
self.estimator.estimate_state()
}
- /// Set value in a slot (6-bit value)
- ///
- /// Uses read-modify-write on 16-bit window to preserve surrounding bits.
#[inline]
fn put_raw(&mut self, slot: u32, value: u8) {
debug_assert!(value <= 63, "6-bit value must be 0-63");
@@ -107,22 +88,17 @@ impl Array6 {
let byte_idx = (start_bit >> 3) as usize;
let shift = (start_bit & 0x7) as u8;
- // Read current 2 bytes
let mut two_bytes = u16::from_le_bytes([self.bytes[byte_idx],
self.bytes[byte_idx + 1]]);
- // Clear the 6-bit slot
two_bytes &= !(VAL_MASK_6 << shift);
- // Insert new value
two_bytes |= ((value as u16) & VAL_MASK_6) << shift;
- // Write back
let bytes_out = two_bytes.to_le_bytes();
self.bytes[byte_idx] = bytes_out[0];
self.bytes[byte_idx + 1] = bytes_out[1];
}
- /// Update with a coupon
pub fn update(&mut self, coupon: Coupon) {
let mask = (1 << self.lg_config_k) - 1;
let slot = coupon.slot() & mask;
@@ -131,51 +107,40 @@ impl Array6 {
let old_value = self.get_raw(slot);
if new_value > old_value {
- // Update HIP and KxQ registers via estimator
self.estimator
.update(self.lg_config_k, old_value, new_value);
- // Update the slot
self.put_raw(slot, new_value);
- // Track num_zeros (count of slots with value 0)
if old_value == 0 {
self.num_zeros -= 1;
}
}
}
- /// Returns the current cardinality estimate.
pub fn estimate(&self) -> f64 {
// Array6 doesn't use cur_min (always 0), so num_at_cur_min = num_zeros
self.estimator.estimate(self.lg_config_k, 0, self.num_zeros)
}
- /// Get upper bound for cardinality estimate
pub fn upper_bound(&self, num_std_dev: NumStdDev) -> f64 {
self.estimator
.upper_bound(self.lg_config_k, 0, self.num_zeros, num_std_dev)
}
- /// Get lower bound for cardinality estimate
pub fn lower_bound(&self, num_std_dev: NumStdDev) -> f64 {
self.estimator
.lower_bound(self.lg_config_k, 0, self.num_zeros, num_std_dev)
}
- /// Restores estimate state after copying or transforming the same logical
sketch.
pub fn restore_estimate_state(&mut self, state: EstimateState) {
self.estimator.restore_estimate_state(state);
}
- /// Check if the sketch is empty (all slots are zero)
pub fn is_empty(&self) -> bool {
self.num_zeros == (1 << self.lg_config_k)
}
- /// Deserialize Array6 from HLL mode bytes
- ///
- /// Expects full HLL preamble (40 bytes) followed by packed 6-bit data.
pub fn deserialize_registers(
mut cursor: SketchSlice,
lg_config_k: u8,
@@ -184,7 +149,6 @@ impl Array6 {
let k = 1 << lg_config_k;
let num_bytes = num_bytes_for_k(k);
- // Read estimator values from preamble
let hip_accum = cursor
.read_f64_le()
.map_err(insufficient_data("hip_accum"))?;
@@ -211,7 +175,6 @@ impl Array6 {
));
}
- // Read packed byte array from offset HLL_BYTE_ARR_START
let mut data = vec![0u8; num_bytes];
cursor
.read_exact(&mut data)
@@ -227,23 +190,18 @@ impl Array6 {
})
}
- /// Serialize Array6 to bytes
- ///
- /// Produces full HLL preamble (40 bytes) followed by packed 6-bit data.
pub fn serialize(&self, lg_config_k: u8) -> Vec<u8> {
let k = 1 << lg_config_k;
let num_bytes = num_bytes_for_k(k);
let total_size = HLL_PREAMBLE_SIZE + num_bytes;
let mut bytes = SketchBytes::with_capacity(total_size);
- // Write standard header
bytes.write_u8(HLL_PREINTS);
bytes.write_u8(SERIAL_VERSION);
bytes.write_u8(Family::HLL.id);
bytes.write_u8(lg_config_k);
bytes.write_u8(0); // unused for HLL mode
- // Write flags
let mut flags = 0u8;
if self.estimator.uses_composite_estimate() {
flags |= OUT_OF_ORDER_FLAG_MASK;
@@ -253,10 +211,8 @@ impl Array6 {
// cur_min is always 0 for Array6
bytes.write_u8(0);
- // Mode byte: HLL mode with HLL6 type
bytes.write_u8(encode_mode_byte(CUR_MODE_HLL, TGT_HLL6));
- // Write estimator values
bytes.write_f64_le(self.estimator.hip_accum());
bytes.write_f64_le(self.estimator.kxq0());
bytes.write_f64_le(self.estimator.kxq1());
@@ -267,7 +223,6 @@ impl Array6 {
// Write aux_count (always 0 for Array6)
bytes.write_u32_le(0);
- // Write packed byte array
bytes.write(&self.bytes);
bytes.into_bytes()
@@ -279,10 +234,8 @@ impl Array6 {
}
}
-/// Calculate number of bytes needed for k slots with 6 bits each
fn num_bytes_for_k(k: u32) -> usize {
- // k slots * 6 bits = k * 6/8 bytes = k * 3/4 bytes
- // Add 1 for 16-bit window read safety
+ // The final register's 16-bit read/write window needs one padding byte.
(((k * 3) >> 2) + 1) as usize
}
@@ -298,10 +251,8 @@ mod tests {
#[test]
fn test_num_bytes_calculation() {
- // k=16 slots: 16 * 6 bits = 96 bits = 12 bytes
assert_eq!(num_bytes_for_k(16), (16 * 3 / 4) + 1);
- // k=1024: 1024 * 6 bits = 6144 bits = 768 bytes
assert_eq!(num_bytes_for_k(1024), (1024 * 3 / 4) + 1);
}
@@ -309,7 +260,6 @@ mod tests {
fn test_get_set_raw() {
let mut arr = Array6::new(4); // 16 slots
- // Test various 6-bit values across different slots
arr.put_raw(0, 0);
arr.put_raw(1, 1);
arr.put_raw(2, 31);
@@ -320,7 +270,6 @@ mod tests {
assert_eq!(arr.get_raw(2), 31);
assert_eq!(arr.get_raw(3), 63);
- // Test that values don't interfere with each other
arr.put_raw(5, 42);
assert_eq!(arr.get_raw(5), 42);
assert_eq!(arr.get_raw(3), 63); // Earlier value unchanged
@@ -338,7 +287,6 @@ mod tests {
fn test_boundary_crossing() {
let mut arr = Array6::new(8); // 256 slots
- // Test values that will cross byte boundaries
// Slot 1: starts at bit 6 (crosses byte 0/1 boundary)
arr.put_raw(1, 0b111111);
assert_eq!(arr.get_raw(1), 63);
@@ -351,7 +299,6 @@ mod tests {
arr.put_raw(3, 0b110011);
assert_eq!(arr.get_raw(3), 51);
- // Verify no interference
assert_eq!(arr.get_raw(1), 63);
assert_eq!(arr.get_raw(2), 42);
assert_eq!(arr.get_raw(3), 51);
@@ -361,21 +308,17 @@ mod tests {
fn test_hip_estimator() {
let mut arr = Array6::new(10); // 1024 buckets
- // Initially estimate should be 0
assert_eq!(arr.estimate(), 0.0);
- // Add some unique values using real coupon hashing
for i in 0..10_000u32 {
arr.update(Coupon::from_value(i));
}
let estimate = arr.estimate();
- // Sanity checks
assert_that!(estimate, gt(0.0));
assert_that!(estimate, is_finite());
- // Rough bounds for 10K unique items (very loose)
assert_that!(estimate, gt(1_000.0));
assert_that!(estimate, lt(100_000.0));
}
@@ -384,7 +327,6 @@ mod tests {
fn test_full_range() {
let mut arr = Array6::new(6); // 64 slots
- // Test all possible 6-bit values (0-63)
for val in 0..64u8 {
arr.put_raw(val as u32, val);
}
@@ -398,7 +340,6 @@ mod tests {
fn test_kxq_register_split() {
let mut arr = Array6::new(8); // 256 buckets
- // Test that values < 32 and >= 32 are handled correctly
arr.update(Coupon::pack(0, 10)); // value < 32, goes to kxq0
arr.update(Coupon::pack(1, 40)); // value >= 32, goes to kxq1
diff --git a/datasketches/src/hll/array8.rs b/datasketches/src/hll/array8.rs
index e28c724..a2f60aa 100644
--- a/datasketches/src/hll/array8.rs
+++ b/datasketches/src/hll/array8.rs
@@ -15,11 +15,6 @@
// specific language governing permissions and limitations
// under the License.
-//! HyperLogLog Array8 mode - 8-bit (1 byte per slot) representation
-//!
-//! Array8 is the simplest HLL array implementation, storing one byte per slot.
-//! This provides the maximum value range (0-255) with no bit-packing
complexity.
-
use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::assert::insufficient_data;
@@ -37,13 +32,11 @@ use crate::hll::serialization::SERIAL_VERSION;
use crate::hll::serialization::TGT_HLL8;
use crate::hll::serialization::encode_mode_byte;
-/// Core Array8 data structure - one byte per slot, no packing
+/// Registers stored one per byte.
#[derive(Debug, Clone, PartialEq)]
pub struct Array8 {
lg_config_k: u8,
- /// Direct byte array: bytes[slot] = value
bytes: Box<[u8]>,
- /// Count of slots with value 0
num_zeros: u32,
estimator: Estimator,
}
@@ -60,23 +53,16 @@ impl Array8 {
}
}
- /// Get value from a slot
- ///
- /// Direct array access - no bit manipulation required.
#[inline]
pub fn get(&self, slot: u32) -> u8 {
self.bytes[slot as usize]
}
- /// Set value in a slot
- ///
- /// Direct array write - no bit manipulation required.
#[inline]
fn put(&mut self, slot: u32, value: u8) {
self.bytes[slot as usize] = value;
}
- /// Update with a coupon
pub fn update(&mut self, coupon: Coupon) {
let mask = (1 << self.lg_config_k) - 1;
let slot = coupon.slot() & mask;
@@ -85,88 +71,64 @@ impl Array8 {
let old_value = self.get(slot);
if new_value > old_value {
- // Update HIP and KxQ registers via estimator
self.estimator
.update(self.lg_config_k, old_value, new_value);
- // Update the slot
self.put(slot, new_value);
- // Track num_zeros (count of slots with value 0)
if old_value == 0 {
self.num_zeros -= 1;
}
}
}
- /// Returns the current cardinality estimate.
pub fn estimate(&self) -> f64 {
// Array8 doesn't use cur_min (always 0), so num_at_cur_min = num_zeros
self.estimator.estimate(self.lg_config_k, 0, self.num_zeros)
}
- /// Get upper bound for cardinality estimate
pub fn upper_bound(&self, num_std_dev: NumStdDev) -> f64 {
self.estimator
.upper_bound(self.lg_config_k, 0, self.num_zeros, num_std_dev)
}
- /// Get lower bound for cardinality estimate
pub fn lower_bound(&self, num_std_dev: NumStdDev) -> f64 {
self.estimator
.lower_bound(self.lg_config_k, 0, self.num_zeros, num_std_dev)
}
- /// Check if the sketch is empty (all slots are zero)
pub fn is_empty(&self) -> bool {
self.num_zeros == (1 << self.lg_config_k)
}
- /// Get read access to register values (one byte per register)
pub fn values(&self) -> &[u8] {
&self.bytes
}
- /// Get the number of registers (K = 2^lg_config_k)
pub fn num_registers(&self) -> usize {
1 << self.lg_config_k
}
- /// Returns the estimate state independently from register-derived cached
values.
pub fn estimate_state(&self) -> EstimateState {
self.estimator.estimate_state()
}
- /// Restores estimate state after copying or transforming the same logical
sketch.
pub fn restore_estimate_state(&mut self, state: EstimateState) {
self.estimator.restore_estimate_state(state);
}
- /// Directly set a register value
- ///
- /// This bypasses the normal update path and directly modifies the
register.
- /// Caller must call rebuild_estimator_from_registers() after all
modifications.
+ /// Bypasses estimator updates. Call `rebuild_estimator_from_registers`
after all writes.
pub fn set_register(&mut self, slot: usize, value: u8) {
self.bytes[slot] = value;
}
- /// Rebuild estimator state from current register values
- ///
- /// Recomputes num_zeros, kxq0, and kxq1, then switches to composite
estimation.
- /// Should be called after bulk register modifications.
+ /// Rebuilds register-derived caches and invalidates HIP after bulk writes.
pub fn rebuild_estimator_from_registers(&mut self) {
self.rebuild_cached_values();
self.estimator.invalidate_hip();
}
- /// Merge another Array8 with the same lg_k
- ///
- /// Performs register-by-register max merge. HIP is invalidated because
the register update
- /// order is unavailable.
- ///
- /// # Panics
- ///
- /// Panics if src length doesn't match self length (different lg_k).
+ /// Merges registers and invalidates HIP because their update order is
unavailable.
pub fn merge_array_same_lgk(&mut self, src: &[u8]) {
assert_eq!(
src.len(),
@@ -182,22 +144,8 @@ impl Array8 {
self.estimator.invalidate_hip();
}
- /// Merge an array with larger lg_k (downsampling)
- ///
- /// When merging a source with lg_k > dst lg_k, multiple source registers
- /// map to each destination register using the masking operation:
- /// `dst_slot = src_slot & ((1 << dst_lg_k) - 1)`
- ///
- /// The destination takes the max of all source values that map to it.
- ///
- /// # Parameters
- ///
- /// * `src`: Source register values (length must be 2^src_lg_k)
- /// * `src_lg_k`: Log2 of source register count
- ///
- /// # Panics
- ///
- /// Panics if src_lg_k <= self.lg_config_k (not downsampling).
+ /// Register values come from a separate hash word, so folding slot
indices needs no
+ /// adjustment to the values. Merging independent histories invalidates
HIP.
pub fn merge_array_with_downsample(&mut self, src: &[u8], src_lg_k: u8) {
assert!(
src_lg_k > self.lg_config_k,
@@ -220,16 +168,10 @@ impl Array8 {
self.estimator.invalidate_hip();
}
- /// Rebuild cached values after bulk modifications
- ///
- /// Recomputes num_zeros by counting zero-valued registers.
- /// This is needed after merge operations that bypass normal update paths.
+ /// Rebuilds register-derived caches without changing the estimate state.
fn rebuild_cached_values(&mut self) {
self.num_zeros = self.bytes.iter().filter(|&&v| v == 0).count() as u32;
- // Recompute kxq values from actual register values
- // This is essential after bulk merges where registers change but
estimator isn't updated
- // incrementally
let mut kxq0_sum = 0.0;
let mut kxq1_sum = 0.0;
@@ -246,9 +188,6 @@ impl Array8 {
self.estimator.restore_kxq(kxq0_sum, kxq1_sum);
}
- /// Deserialize Array8 from HLL mode bytes
- ///
- /// Expects full HLL preamble (40 bytes) followed by k bytes of data.
pub fn deserialize_registers(
mut cursor: SketchSlice,
lg_config_k: u8,
@@ -256,7 +195,6 @@ impl Array8 {
) -> Result<Self, Error> {
let k = 1usize << lg_config_k;
- // Read estimator values from preamble
let hip_accum = cursor
.read_f64_le()
.map_err(insufficient_data("hip_accum"))?;
@@ -283,7 +221,6 @@ impl Array8 {
));
}
- // Read byte array from offset HLL_BYTE_ARR_START
let mut data = vec![0u8; k];
cursor
.read_exact(&mut data)
@@ -299,22 +236,17 @@ impl Array8 {
})
}
- /// Serialize Array8 to bytes
- ///
- /// Produces full HLL preamble (40 bytes) followed by k bytes of data.
pub fn serialize(&self, lg_config_k: u8) -> Vec<u8> {
let k = 1 << lg_config_k;
let total_size = HLL_PREAMBLE_SIZE + k as usize;
let mut bytes = SketchBytes::with_capacity(total_size);
- // Write standard header
bytes.write_u8(HLL_PREINTS);
bytes.write_u8(SERIAL_VERSION);
bytes.write_u8(Family::HLL.id);
bytes.write_u8(lg_config_k);
bytes.write_u8(0); // unused for HLL mode
- // Write flags
let mut flags = 0u8;
if self.estimator.uses_composite_estimate() {
flags |= OUT_OF_ORDER_FLAG_MASK;
@@ -324,10 +256,8 @@ impl Array8 {
// cur_min is always 0 for Array8
bytes.write_u8(0);
- // Mode byte: HLL mode with HLL8 type
bytes.write_u8(encode_mode_byte(CUR_MODE_HLL, TGT_HLL8));
- // Write estimator values
bytes.write_f64_le(self.estimator.hip_accum());
bytes.write_f64_le(self.estimator.kxq0());
bytes.write_f64_le(self.estimator.kxq1());
@@ -338,7 +268,6 @@ impl Array8 {
// Write aux_count (always 0 for Array8)
bytes.write_u32_le(0);
- // Write byte array
bytes.write(&self.bytes);
bytes.into_bytes()
@@ -364,7 +293,6 @@ mod tests {
fn test_array8_basic() {
let arr = Array8::new(10); // 1024 buckets
- // Initially all slots should be 0
assert_eq!(arr.get(0), 0);
assert_eq!(arr.get(100), 0);
assert_eq!(arr.get(1023), 0);
@@ -374,16 +302,14 @@ mod tests {
fn test_get_set() {
let mut arr = Array8::new(4); // 16 slots
- // Test all possible 8-bit values
for slot in 0..16 {
- arr.put(slot, (slot * 17) as u8); // Various values
+ arr.put(slot, (slot * 17) as u8);
}
for slot in 0..16 {
assert_eq!(arr.get(slot), (slot * 17) as u8);
}
- // Test full range (0-255)
arr.put(0, 0);
arr.put(1, 127);
arr.put(2, 255);
@@ -397,20 +323,15 @@ mod tests {
fn test_update_basic() {
let mut arr = Array8::new(4);
- // Update slot 0 with value 5
arr.update(Coupon::pack(0, 5));
assert_eq!(arr.get(0), 5);
- // Update with a smaller value (should be ignored)
arr.update(Coupon::pack(0, 3));
assert_eq!(arr.get(0), 5);
- // Update with a larger value
arr.update(Coupon::pack(0, 42));
assert_eq!(arr.get(0), 42);
- // Test value at max coupon range (63)
- // Note: Coupon::pack only stores 6 bits (0-63)
arr.update(Coupon::pack(1, 63));
assert_eq!(arr.get(1), 63);
}
@@ -419,21 +340,17 @@ mod tests {
fn test_hip_estimator() {
let mut arr = Array8::new(10); // 1024 buckets
- // Initially estimate should be 0
assert_eq!(arr.estimate(), 0.0);
- // Add some unique values using real coupon hashing
for i in 0..10_000u32 {
arr.update(Coupon::from_value(i));
}
let estimate = arr.estimate();
- // Sanity checks
assert_that!(estimate, gt(0.0));
assert_that!(estimate, is_finite());
- // Rough bounds for 10K unique items (very loose)
assert_that!(estimate, gt(1_000.0));
assert_that!(estimate, lt(100_000.0));
}
@@ -442,7 +359,6 @@ mod tests {
fn test_full_value_range() {
let mut arr = Array8::new(8); // 256 slots
- // Test all possible 8-bit values (0-255)
for val in 0..=255u8 {
arr.put(val as u32, val);
}
@@ -456,9 +372,7 @@ mod tests {
fn test_high_value_direct() {
let mut arr = Array8::new(6); // 64 slots
- // Test that Array8 CAN store full range (0-255) directly
- // Even though coupons are limited to 6 bits (0-63)
- // Direct put/get bypasses coupon encoding
+ // Direct storage accepts byte values beyond the six-bit coupon range.
let test_values = [16, 32, 64, 128, 200, 255];
for (slot, &value) in test_values.iter().enumerate() {
@@ -466,7 +380,6 @@ mod tests {
assert_eq!(arr.get(slot as u32), value);
}
- // Verify no cross-slot corruption
for (slot, &value) in test_values.iter().enumerate() {
assert_eq!(arr.get(slot as u32), value);
}
@@ -476,7 +389,6 @@ mod tests {
fn test_kxq_register_split() {
let mut arr = Array8::new(8); // 256 buckets
- // Test that values < 32 and >= 32 are handled correctly
arr.update(Coupon::pack(0, 10)); // value < 32, goes to kxq0
arr.update(Coupon::pack(1, 50)); // value >= 32, goes to kxq1
@@ -492,12 +404,10 @@ mod tests {
fn test_values_access() {
let mut arr = Array8::new(4); // 16 slots
- // Set some values
arr.put(0, 10);
arr.put(5, 25);
arr.put(15, 63);
- // Test read access via values()
let vals = arr.values();
assert_eq!(vals.len(), 16);
assert_eq!(vals[0], 10);
@@ -511,20 +421,16 @@ mod tests {
let mut dst = Array8::new(4); // 16 slots
let mut src = Array8::new(4); // 16 slots
- // Set up dst with some values
dst.put(0, 10);
dst.put(1, 20);
dst.put(2, 30);
- // Set up src with overlapping and new values
src.put(1, 15); // Smaller than dst[1]=20, should keep 20
src.put(2, 35); // Larger than dst[2]=30, should update to 35
src.put(3, 40); // New value
- // Merge src into dst
dst.merge_array_same_lgk(src.values());
- // Check results
assert_eq!(dst.get(0), 10, "dst[0] unchanged");
assert_eq!(dst.get(1), 20, "dst[1] kept max value");
assert_eq!(dst.get(2), 35, "dst[2] updated to larger value");
@@ -533,7 +439,6 @@ mod tests {
// Bulk merges require composite estimation.
assert!(dst.estimator.uses_composite_estimate());
- // Verify num_zeros updated (should be 12: 16 - 4 non-zero)
assert_eq!(dst.num_zeros, 12);
}
@@ -543,7 +448,6 @@ mod tests {
let mut dst = Array8::new(4); // 16 slots
let mut src = Array8::new(5); // 32 slots
- // Set up dst
dst.put(0, 10);
dst.put(1, 20);
@@ -553,10 +457,8 @@ mod tests {
src.put(1, 18); // maps to dst[1], max(20, 18) = 20
src.put(17, 30); // maps to dst[1], max(20, 30) = 30
- // Merge with downsampling
dst.merge_array_with_downsample(src.values(), 5);
- // Check results - dst takes max of all src slots that map to it
assert_eq!(dst.get(0), 25, "dst[0] = max(10, 15, 25)");
assert_eq!(dst.get(1), 30, "dst[1] = max(20, 18, 30)");
@@ -586,18 +488,14 @@ mod tests {
fn test_rebuild_cached_values() {
let mut arr = Array8::new(4); // 16 slots
- // Set some non-zero values
arr.put(0, 10);
arr.put(1, 20);
arr.put(2, 30);
- // Manually corrupt num_zeros
arr.num_zeros = 999;
- // Rebuild should fix it
arr.rebuild_cached_values();
- // Should be 13 zeros (16 total - 3 non-zero)
assert_eq!(arr.num_zeros, 13);
}
@@ -606,19 +504,16 @@ mod tests {
let mut dst = Array8::new(4);
let mut src = Array8::new(4);
- // Fill dst with ascending values
for i in 0..16 {
dst.put(i, i as u8);
}
- // Fill src with descending values
for i in 0..16 {
src.put(i, (15 - i) as u8);
}
dst.merge_array_same_lgk(src.values());
- // Result should be max at each position
for i in 0..16 {
let expected = (i as u8).max((15 - i) as u8);
assert_eq!(
diff --git a/datasketches/src/hll/aux_map.rs b/datasketches/src/hll/aux_map.rs
index 86339a5..5286fe9 100644
--- a/datasketches/src/hll/aux_map.rs
+++ b/datasketches/src/hll/aux_map.rs
@@ -15,22 +15,11 @@
// specific language governing permissions and limitations
// under the License.
-//! Auxiliary hash map for HLL Array4 exceptions
-//!
-//! Stores slot-value pairs for values that don't fit in the 4-bit main array.
-//! Uses open addressing with stride-based probing for collision resolution.
-
use crate::hll::Coupon;
use crate::hll::RESIZE_DENOMINATOR;
use crate::hll::RESIZE_NUMERATOR;
-/// Open-addressing hash table for exception values (values >= 15)
-///
-/// This hash map stores (slot_number, value) pairs where values have exceeded
-/// the 4-bit representation (after cur_min offset) in the main Array4.
-///
-/// Each entry is a [`Coupon`] packed as: [value (upper 6 bits) | slot_no
(lower 26 bits)].
-/// Empty entries are represented as [`Coupon::EMPTY`].
+/// Absolute register values for the `AUX_TOKEN` slots in `Array4`.
#[derive(Debug, Clone)]
pub struct AuxMap {
lg_size: u8,
@@ -41,13 +30,11 @@ pub struct AuxMap {
impl PartialEq for AuxMap {
fn eq(&self, other: &Self) -> bool {
- // Two aux maps are equal if they have the same lg_config_k
- // and the same non-empty entries (regardless of internal storage
order)
+ // Capacity and slot order do not affect the logical entries.
if self.lg_config_k != other.lg_config_k || self.count != other.count {
return false;
}
- // Collect and sort non-empty entries from both maps
let mut entries1: Vec<Coupon> = self
.entries
.iter()
@@ -68,10 +55,8 @@ impl PartialEq for AuxMap {
}
}
-/// Get lg_aux_arr_ints for a given lg_config_k
-///
-/// This determines the initial size of the auxiliary hash map
-/// based on the sketch size.
+/// Initial table sizes from DataSketches C++:
+///
<https://github.com/apache/datasketches-cpp/blob/5a055521/hll/include/HllUtil.hpp>
fn lg_aux_arr_ints(lg_config_k: u8) -> u8 {
static LG_AUX_ARR_INTS: &[u8] = &[
0, 2, 2, 2, 2, 2, 2, 3, 3, 3, // 0-9
@@ -83,7 +68,6 @@ fn lg_aux_arr_ints(lg_config_k: u8) -> u8 {
}
impl AuxMap {
- /// Create a new map with specified size
pub fn new(lg_config_k: u8) -> Self {
let lg_size = lg_aux_arr_ints(lg_config_k);
Self {
@@ -94,13 +78,11 @@ impl AuxMap {
}
}
- /// Insert a new slot-value pair
pub fn insert(&mut self, slot: u32, value: u8) {
let index = self.find(slot);
match index {
FindResult::Found(_) => {
- // Invariant: Array4 always check existence before inserting
- // a new value on the same slot.
+ // Array4 uses insert only when a slot first becomes an
exception.
unreachable!("slot {} already exists in aux map", slot);
}
FindResult::Empty(idx) => {
@@ -111,9 +93,6 @@ impl AuxMap {
}
}
- /// Get value for a slot
- ///
- /// Returns `None` if the slot is not found
pub fn get(&self, slot: u32) -> Option<u8> {
match self.find(slot) {
FindResult::Found(idx) => Some(self.entries[idx].value()),
@@ -121,24 +100,18 @@ impl AuxMap {
}
}
- /// Replace value for existing slot
pub fn replace(&mut self, slot: u32, value: u8) {
match self.find(slot) {
FindResult::Found(idx) => {
self.entries[idx] = Coupon::pack(slot, value);
}
FindResult::Empty(_) => {
- // Invariant: Array4 always check existence before replacing
- // an old value on the same slot.
+ // Every AUX_TOKEN slot must already have an entry.
unreachable!("slot {} not found in aux map", slot);
}
}
}
- /// Find slot in hash table using open addressing with stride
- ///
- /// Returns either the index where the slot is found, or the index
- /// of an empty slot where it could be inserted.
fn find(&self, slot: u32) -> FindResult {
let mask = (1 << self.lg_size) - 1;
let config_k_mask = (1 << self.lg_config_k) - 1;
@@ -157,20 +130,17 @@ impl AuxMap {
return FindResult::Found(probe as usize);
}
- // Open addressing with odd stride (guarantees full coverage)
+ // An odd stride visits every slot in a power-of-two table.
let stride = (slot >> self.lg_size) | 1;
probe = (probe + stride) & mask;
if probe == start {
- // Invariant: AuxMap::insert is responsible for
- // growing the AuxMap when a new entry is inserted
- // causing the map to be full.
+ // insert grows the table past 75% occupancy, leaving an empty
slot.
unreachable!("AuxMap full; no empty slots");
}
}
}
- /// Check if we need to grow the hash table (75% load factor)
fn check_grow(&mut self) {
let size = 1 << self.lg_size;
if (RESIZE_DENOMINATOR * self.count) > (RESIZE_NUMERATOR * size) {
@@ -178,19 +148,16 @@ impl AuxMap {
}
}
- /// Double the hash table size and rehash all entries
fn grow(&mut self) {
let new_lg_size = self.lg_size + 1;
let new_size = 1 << new_lg_size;
let new_mask = (1 << new_lg_size) - 1;
let mut new_entries = vec![Coupon::EMPTY; new_size].into_boxed_slice();
- // Rehash all entries into the larger table
for &entry in self.entries.iter() {
if !entry.is_empty() {
let slot = entry.slot();
- // Find position in new table
let mut probe = slot & new_mask;
let start_position = probe;
@@ -203,8 +170,7 @@ impl AuxMap {
let stride = (slot >> new_lg_size) | 1;
probe = (probe + stride) & new_mask;
if probe == start_position {
- // Invariant: there will always be space for all
- // `self.entries` in the `new_entries` array.
+ // Doubling capacity leaves room for every existing
entry.
unreachable!("AuxMap full; no empty slots");
}
}
@@ -215,7 +181,6 @@ impl AuxMap {
self.lg_size = new_lg_size;
}
- /// Iterate over (slot, value) pairs without consuming the map
pub fn iter(&self) -> impl Iterator<Item = (u32, u8)> + '_ {
let config_k_mask = (1 << self.lg_config_k) - 1;
self.entries.iter().filter_map(move |&entry| {
@@ -233,7 +198,6 @@ impl AuxMap {
}
}
-/// Iterator over AuxMap entries
pub struct AuxMapIter {
entries: std::vec::IntoIter<Coupon>,
config_k_mask: u32,
@@ -250,7 +214,7 @@ impl Iterator for AuxMapIter {
let value = entry.value();
return Some((slot, value));
}
- Some(_) => continue, // Skip empty entries
+ Some(_) => continue,
None => return None,
}
}
@@ -269,7 +233,6 @@ impl IntoIterator for AuxMap {
}
}
-/// Result of a find operation
enum FindResult {
Found(usize),
Empty(usize),
@@ -283,18 +246,15 @@ mod tests {
fn test_aux_map_basic_operations() {
let mut map = AuxMap::new(10);
- // Insert some values
map.insert(10, 20);
map.insert(50, 30);
map.insert(100, 40);
- // Get values
assert_eq!(map.get(10), Some(20));
assert_eq!(map.get(50), Some(30));
assert_eq!(map.get(100), Some(40));
assert_eq!(map.get(999), None);
- // Replace value
map.replace(50, 35);
assert_eq!(map.get(50), Some(35));
}
@@ -303,14 +263,11 @@ mod tests {
fn test_aux_map_growth() {
let mut map = AuxMap::new(8);
- // Insert enough to trigger resize (75% load factor)
map.insert(1, 15);
map.insert(2, 16);
map.insert(3, 17);
- // This should trigger a resize
map.insert(4, 18);
- // All values should still be accessible
assert_eq!(map.get(1), Some(15));
assert_eq!(map.get(2), Some(16));
assert_eq!(map.get(3), Some(17));
@@ -322,13 +279,13 @@ mod tests {
fn test_aux_map_duplicate_insert() {
let mut map = AuxMap::new(10);
map.insert(10, 20);
- map.insert(10, 30); // Should panic
+ map.insert(10, 30);
}
#[test]
#[should_panic(expected = "not found")]
fn test_aux_map_replace_missing() {
let mut map = AuxMap::new(10);
- map.replace(999, 20); // Should panic
+ map.replace(999, 20);
}
}
diff --git a/datasketches/src/hll/composite_interpolation.rs
b/datasketches/src/hll/composite_interpolation.rs
index e5e13e3..cf419bf 100644
--- a/datasketches/src/hll/composite_interpolation.rs
+++ b/datasketches/src/hll/composite_interpolation.rs
@@ -15,13 +15,7 @@
// specific language governing permissions and limitations
// under the License.
-//! Composite interpolation tables for HLL estimation.
-//!
-//! These tables correct raw HyperLogLog estimates when the register update
history is unavailable,
-//! such as after merging independent sketches.
-//!
-//! Currently, this module contains tables for common lg_k values (4-12). The
full C++
-//! implementation has tables for lg_k 4-21. Additional tables can be found at:
+//! Bias-correction tables for `lg_k` 4 through 21 from DataSketches C++:
//!
<https://github.com/apache/datasketches-cpp/blob/5a055521/hll/include/CompositeInterpolationXTable-internal.hpp>
const NUM_X_VALUES: usize = 257;
@@ -31,11 +25,6 @@ static Y_STRIDES: [u32; 18] = [
1, 2, 3, 5, 10, 20, 40, 80, 160, 320, 640, 1280, 2560, 5120, 10240, 20480,
40960, 81920,
];
-/// Get Y stride for a given lg_k.
-///
-/// # Panics
-///
-/// Panics if lg_k is not in range `[4, 21]`.
pub fn get_y_stride(lg_k: u8) -> u32 {
if !(4..=21).contains(&lg_k) {
panic!("lg_k must be in range [4, 21], got: {}", lg_k);
@@ -43,18 +32,10 @@ pub fn get_y_stride(lg_k: u8) -> u32 {
Y_STRIDES[(lg_k - 4) as usize]
}
-/// Get X array length (constant for all lg_k)
pub const fn get_x_arr_length() -> usize {
NUM_X_VALUES
}
-/// Get X array for a given lg_k.
-///
-/// Returns a reference to the pre-computed X values for cubic interpolation.
-///
-/// # Panics
-///
-/// Panics if lg_k is not in range `[4, 21]`.
pub fn get_x_arr(lg_k: u8) -> &'static [f64; NUM_X_VALUES] {
if !(4..=21).contains(&lg_k) {
panic!("lg_k must be in range [4, 21], got: {}", lg_k);
@@ -62,7 +43,6 @@ pub fn get_x_arr(lg_k: u8) -> &'static [f64; NUM_X_VALUES] {
&ARRAYS[(lg_k - 4) as usize]
}
-/// This is extracted from
https://github.com/apache/datasketches-cpp/blob/5a055521/hll/include/CompositeInterpolationXTable-internal.hpp#L54
static ARRAYS: [[f64; NUM_X_VALUES]; 18] = [
[
10.767999803534,
@@ -4796,7 +4776,6 @@ mod tests {
#[test]
fn test_x_arr_monotonic() {
- // X array should be strictly increasing
let x_arr = get_x_arr(8);
for i in 1..x_arr.len() {
assert_that!(x_arr[i], gt(x_arr[i - 1]), "index: {i}");
diff --git a/datasketches/src/hll/container.rs
b/datasketches/src/hll/container.rs
index e15d6bc..8f0313c 100644
--- a/datasketches/src/hll/container.rs
+++ b/datasketches/src/hll/container.rs
@@ -15,11 +15,6 @@
// specific language governing permissions and limitations
// under the License.
-//! Base container for coupon storage with cardinality estimation
-//!
-//! Provides a simple array-based storage for coupons (hash values) with
-//! cubic interpolation-based cardinality estimation and confidence bounds.
-
use crate::common::NumStdDev;
use crate::hll::COUPON_RSE;
use crate::hll::Coupon;
@@ -27,12 +22,10 @@ use crate::hll::coupon_mapping::X_ARR;
use crate::hll::coupon_mapping::Y_ARR;
use crate::hll::cubic_interpolation::using_x_and_y_tables;
-/// Container for storing coupons with basic cardinality estimation
#[derive(Debug, Clone)]
pub struct Container {
- /// Log2 of container size
lg_size: usize,
- /// Array of coupon values (Coupon::EMPTY = empty)
+ /// Empty slots contain `Coupon::EMPTY`.
pub coupons: Box<[Coupon]>,
/// Number of non-empty coupons
pub len: usize,
@@ -40,8 +33,7 @@ pub struct Container {
impl PartialEq for Container {
fn eq(&self, other: &Self) -> bool {
- // Two containers are equal if they have the same non-empty coupons
- // (regardless of order or internal storage)
+ // Capacity and slot order do not affect the logical coupon contents.
if self.len != other.len {
return false;
}
@@ -75,7 +67,6 @@ impl Container {
}
}
- /// Create container from existing coupons
pub fn from_coupons(lg_size: usize, coupons: Box<[Coupon]>, len: usize) ->
Self {
Self {
lg_size,
@@ -104,34 +95,28 @@ impl Container {
self.coupons.len()
}
- /// Get cardinality estimate using cubic interpolation
pub fn estimate(&self) -> f64 {
let len = self.len as f64;
let est = using_x_and_y_tables(&X_ARR, &Y_ARR, len);
len.max(est)
}
- /// Get upper confidence bound for cardinality estimate
pub fn upper_bound(&self, num_std_dev: NumStdDev) -> f64 {
let len = self.len as f64;
let est = using_x_and_y_tables(&X_ARR, &Y_ARR, len);
- // Upper bound: negative RSE means (1 + rse) < 1, so bound > estimate
let rse = -(num_std_dev as u8 as f64) * COUPON_RSE;
let bound = est / (1.0 + rse);
len.max(bound)
}
- /// Get lower confidence bound for cardinality estimate
pub fn lower_bound(&self, num_std_dev: NumStdDev) -> f64 {
let len = self.len as f64;
let est = using_x_and_y_tables(&X_ARR, &Y_ARR, len);
- // Lower bound: positive RSE means (1 + rse) > 1, so bound < estimate
let rse = (num_std_dev as u8 as f64) * COUPON_RSE;
let bound = est / (1.0 + rse);
len.max(bound)
}
- /// Iterate over all non-empty coupons
pub fn iter(&self) -> impl Iterator<Item = Coupon> + '_ {
self.coupons.iter().filter(|&&c| !c.is_empty()).copied()
}
diff --git a/datasketches/src/hll/coupon_mapping.rs
b/datasketches/src/hll/coupon_mapping.rs
index 1b4d687..0ee8d43 100644
--- a/datasketches/src/hll/coupon_mapping.rs
+++ b/datasketches/src/hll/coupon_mapping.rs
@@ -15,10 +15,9 @@
// specific language governing permissions and limitations
// under the License.
-//! Lookup tables for coupon-based cardinality estimation
-//!
-//! These pre-computed X and Y value pairs are used with cubic interpolation
-//! to map from the number of observed coupons to estimated cardinality.
+//! Coupon-count correction for the 26-bit slot encoding. These X/Y pairs are
used with
+//! cubic interpolation and come from DataSketches C++:
+//!
<https://github.com/apache/datasketches-cpp/blob/5a055521/hll/include/CubicInterpolation-internal.hpp>
/// X values (coupon counts) for interpolation table
pub static X_ARR: [f64; 40] = [
diff --git a/datasketches/src/hll/cubic_interpolation.rs
b/datasketches/src/hll/cubic_interpolation.rs
index e192318..440a42b 100644
--- a/datasketches/src/hll/cubic_interpolation.rs
+++ b/datasketches/src/hll/cubic_interpolation.rs
@@ -15,12 +15,9 @@
// specific language governing permissions and limitations
// under the License.
-//! Cubic interpolation utilities for cardinality estimation
-//!
-//! Implements Lagrange cubic interpolation over lookup tables to provide
-//! smooth, accurate cardinality estimates from discrete observations.
+//! Four-point Lagrange interpolation for the HLL correction tables.
+//! The X coordinates must be strictly increasing.
-/// Interpolate Y value from X using pre-computed X/Y tables
pub fn using_x_and_y_tables(x_arr: &[f64], y_arr: &[f64], x: f64) -> f64 {
debug_assert!(x_arr.len() >= 4 && x_arr.len() == y_arr.len());
@@ -28,13 +25,13 @@ pub fn using_x_and_y_tables(x_arr: &[f64], y_arr: &[f64],
x: f64) -> f64 {
debug_assert!(x >= x_arr[0] && x < x_arr[last_idx]);
if x == x_arr[last_idx] {
- return y_arr[last_idx]; // corner case
+ return y_arr[last_idx];
}
let offset = find_straddle(x_arr, x);
debug_assert!(offset < last_idx);
- // Select 4-point window based on position in array
+ // Keep the four-point window inside the table at either end.
if offset == 0 {
return interpolate_using_x_and_y_tables(x_arr, y_arr, offset, x);
}
@@ -46,7 +43,6 @@ pub fn using_x_and_y_tables(x_arr: &[f64], y_arr: &[f64], x:
f64) -> f64 {
interpolate_using_x_and_y_tables(x_arr, y_arr, offset - 1, x)
}
-/// Helper to perform cubic interpolation at offset using X/Y tables
fn interpolate_using_x_and_y_tables(x_arr: &[f64], y_arr: &[f64], offset:
usize, x: f64) -> f64 {
cubic_interpolate(
x_arr[offset],
@@ -61,7 +57,6 @@ fn interpolate_using_x_and_y_tables(x_arr: &[f64], y_arr:
&[f64], offset: usize,
)
}
-/// Interpolate Y value from X using X array and uniform Y stride
pub fn using_x_arr_and_y_stride(x_arr: &[f64], y_stride: f64, x: f64) -> f64 {
let len = x_arr.len();
debug_assert!(len >= 4);
@@ -70,7 +65,6 @@ pub fn using_x_arr_and_y_stride(x_arr: &[f64], y_stride: f64,
x: f64) -> f64 {
debug_assert!(x >= x_arr[0] && x <= x_arr[last_idx]);
if x == x_arr[last_idx] {
- // corner case
return y_stride * (last_idx as f64);
}
@@ -79,14 +73,11 @@ pub fn using_x_arr_and_y_stride(x_arr: &[f64], y_stride:
f64, x: f64) -> f64 {
debug_assert!(offset <= len_m2);
if offset == 0 {
- // corner case
return interpolate_using_x_arr_and_y_stride(x_arr, y_stride, offset,
x);
} else if offset == len_m2 {
- // corner case: offset - 2
return interpolate_using_x_arr_and_y_stride(x_arr, y_stride, offset -
2, x);
}
- // main case: offset - 1
interpolate_using_x_arr_and_y_stride(x_arr, y_stride, offset - 1, x)
}
@@ -109,7 +100,6 @@ fn interpolate_using_x_arr_and_y_stride(
)
}
-/// Cubic interpolation using the Lagrange interpolation formula.
fn cubic_interpolate(
x0: f64,
y0: f64,
@@ -139,7 +129,7 @@ fn cubic_interpolate(
term0 + term1 + term2 + term3
}
-/// Find index `i` such that x_arr[i] <= x < x_arr[i+1].
+/// Finds `i` such that `x_arr[i] <= x < x_arr[i + 1]`.
fn find_straddle(x_arr: &[f64], x: f64) -> usize {
debug_assert!(x_arr.len() >= 2);
let last_idx = x_arr.len() - 1;
@@ -148,10 +138,9 @@ fn find_straddle(x_arr: &[f64], x: f64) -> usize {
recursive_find_straddle(x_arr, 0, last_idx, x)
}
-/// Recursive helper for `find_straddle`.
fn recursive_find_straddle(x_arr: &[f64], left: usize, right: usize, x: f64)
-> usize {
debug_assert!(left < right);
- debug_assert!(x_arr[left] <= x && x < x_arr[right]); // invariant
+ debug_assert!(x_arr[left] <= x && x < x_arr[right]);
if left + 1 == right {
return left;
diff --git a/datasketches/src/hll/estimator.rs
b/datasketches/src/hll/estimator.rs
index 8897516..1a22809 100644
--- a/datasketches/src/hll/estimator.rs
+++ b/datasketches/src/hll/estimator.rs
@@ -19,6 +19,9 @@
//!
//! Sequential register updates use HIP (Historical Inverse Probability). Bulk
merges use the
//! composite estimator because register values do not retain their update
order.
+//!
+//! Estimator formulas and crossover constants follow DataSketches C++:
+//!
<https://github.com/apache/datasketches-cpp/blob/5a055521/hll/include/HllArray-internal.hpp>
use crate::common::NumStdDev;
use crate::common::inv_pow2::inv_pow2;
@@ -35,13 +38,10 @@ pub enum EstimateState {
Composite,
}
-/// Cardinality estimator shared by Array4, Array6, and Array8.
-///
-/// Sequential updates use HIP. Bulk merges use the composite estimator
because register values do
-/// not retain update order. Both modes maintain KxQ as a cache derived from
the current registers.
+/// KxQ caches the sum of `2^-register`. Splitting the sum at register value
32 preserves
+/// precision when large and small contributions coexist.
#[derive(Debug, Clone, PartialEq)]
pub struct Estimator {
- /// Estimate selected by the register history.
estimate_state: EstimateState,
/// KxQ register for values < 32 (larger inverse powers)
kxq0: f64,
@@ -50,7 +50,6 @@ pub struct Estimator {
}
impl Estimator {
- /// Creates an estimator for a sketch with 2^lg_config_k registers.
pub fn new(lg_config_k: u8) -> Self {
let k = 1 << lg_config_k;
Self {
@@ -74,22 +73,11 @@ impl Estimator {
}
}
- /// Update the estimator when a register changes from old_value to
new_value
- ///
- /// This should be called BEFORE actually updating the register in the
array.
- ///
- /// # Algorithm
- ///
- /// 1. Update the HIP accumulator when it remains valid
- /// 2. Update KxQ registers (always)
- ///
- /// The KxQ registers are split for numerical precision:
- /// * kxq0: sum of 1/2^v for v < 32
- /// * kxq1: sum of 1/2^v for v >= 32
+ /// Applies a register increase; requires `new_value > old_value`.
pub fn update(&mut self, lg_config_k: u8, old_value: u8, new_value: u8) {
let k = (1 << lg_config_k) as f64;
- // Update HIP accumulator FIRST when the register history is still
available.
+ // HIP must use the KxQ sums from before this register update.
if let EstimateState::Hip(hip_accum) = &mut self.estimate_state {
*hip_accum += k / (self.kxq0 + self.kxq1);
}
@@ -98,16 +86,13 @@ impl Estimator {
self.update_kxq(old_value, new_value);
}
- /// Update only the KxQ registers (internal helper)
fn update_kxq(&mut self, old_value: u8, new_value: u8) {
- // Subtract old value contribution
if old_value < 32 {
self.kxq0 -= inv_pow2(old_value);
} else {
self.kxq1 -= inv_pow2(old_value);
}
- // Add new value contribution
if new_value < 32 {
self.kxq0 += inv_pow2(new_value);
} else {
@@ -115,15 +100,8 @@ impl Estimator {
}
}
- /// Get the current cardinality estimate
- ///
- /// Dispatches to the estimate selected by the register history.
- ///
- /// # Arguments
- ///
- /// * `lg_config_k`: Log2 of number of registers (k)
- /// * `cur_min`: Current minimum register value (for Array4, 0 for
Array6/8)
- /// * `num_at_cur_min`: Number of registers at cur_min value
+ /// For `Array6`/`Array8`, pass zero for `cur_min` and the zero-register
count for
+ /// `num_at_cur_min`. `Array4` tracks its actual minimum and its count.
pub fn estimate(&self, lg_config_k: u8, cur_min: u8, num_at_cur_min: u32)
-> f64 {
match self.estimate_state {
EstimateState::Hip(hip_accum) => hip_accum,
@@ -133,16 +111,6 @@ impl Estimator {
}
}
- /// Get upper bound for cardinality estimate
- ///
- /// Returns the upper confidence bound for the cardinality estimate.
- ///
- /// # Arguments
- ///
- /// * `lg_config_k`: Log2 of number of registers (k)
- /// * `cur_min`: Current minimum register value (for Array4, 0 for
Array6/8)
- /// * `num_at_cur_min`: Number of registers at cur_min value
- /// * `num_std_dev`: Number of standard deviations (1, 2, or 3)
pub fn upper_bound(
&self,
lg_config_k: u8,
@@ -157,23 +125,11 @@ impl Estimator {
self.uses_composite_estimate(),
num_std_dev,
);
- // RSE is negative for upper bounds, so (1 + rse) < 1, making bound >
estimate
estimate / (1.0 + rse)
}
- /// Get lower bound for cardinality estimate
- ///
- /// Returns the lower confidence bound for the cardinality estimate.
- ///
- /// Each non-zero register requires a distinct item, so their count is a
hard floor
- /// for the lower bound. If `cur_min` is non-zero, all `k` registers are
non-zero.
- ///
- /// # Arguments
- ///
- /// * `lg_config_k`: Log2 of number of registers (k)
- /// * `cur_min`: Current minimum register value (for Array4, 0 for
Array6/8)
- /// * `num_at_cur_min`: Number of registers at cur_min value
- /// * `num_std_dev`: Number of standard deviations (1, 2, or 3)
+ /// Each nonzero register requires a distinct item, so their count is a
hard floor
+ /// for the lower bound. If `cur_min` is nonzero, all `k` registers are
nonzero.
pub fn lower_bound(
&self,
lg_config_k: u8,
@@ -194,15 +150,9 @@ impl Estimator {
} else {
config_k
};
- // RSE is positive for lower bounds, so (1 + rse) > 1, making bound <
estimate
(estimate / (1.0 + rse)).max(f64::from(num_nonzero_registers))
}
- /// Get raw HLL estimate using standard HyperLogLog formula
- ///
- /// Formula: correctionFactor * k^2 / (kxq0 + kxq1)
- ///
- /// Uses lg_k-specific correction factors for small k.
fn raw_estimate(&self, lg_config_k: u8) -> f64 {
let k = (1 << lg_config_k) as f64;
@@ -217,16 +167,12 @@ impl Estimator {
(correction_factor * k * k) / (self.kxq0 + self.kxq1)
}
- /// Get linear counting (bitmap) estimate for small cardinalities
- ///
- /// Uses harmonic numbers to estimate based on empty registers.
fn bitmap_estimate(&self, lg_config_k: u8, cur_min: u8, num_at_cur_min:
u32) -> f64 {
let k = 1 << lg_config_k;
- // Number of unhit (empty) buckets
let num_unhit = if cur_min == 0 { num_at_cur_min } else { 0 };
- // Edge case: all buckets hit
+ // Preserve the upstream fallback for a bitmap with no empty registers.
if num_unhit == 0 {
return (k as f64) * (k as f64 / 0.5).ln();
}
@@ -235,20 +181,14 @@ impl Estimator {
harmonic_numbers::bitmap_estimate(k, num_hit)
}
- /// Get composite estimate (blends raw HLL and linear counting)
- ///
- /// This estimate is used when the register update history is unavailable.
- /// It uses cubic interpolation on the raw HLL estimate, then blends
- /// with linear counting for small cardinalities.
+ /// Selects between bias-corrected HLL and bitmap estimates using their
empirical crossover.
fn composite_estimate(&self, lg_config_k: u8, cur_min: u8, num_at_cur_min:
u32) -> f64 {
let raw_estimate = self.raw_estimate(lg_config_k);
- // Get composite interpolation table
let x_arr = composite_interpolation::get_x_arr(lg_config_k);
let x_arr_len = composite_interpolation::get_x_arr_length();
let y_stride = composite_interpolation::get_y_stride(lg_config_k) as
f64;
- // Handle edge cases
if raw_estimate < x_arr[0] {
return 0.0;
}
@@ -262,7 +202,6 @@ impl Estimator {
return raw_estimate * factor;
}
- // Interpolate using cubic interpolation
let adjusted_estimate =
cubic_interpolation::using_x_arr_and_y_stride(x_arr, y_stride,
raw_estimate);
@@ -273,11 +212,9 @@ impl Estimator {
return adjusted_estimate;
}
- // Get linear counting estimate
let linear_estimate = self.bitmap_estimate(lg_config_k, cur_min,
num_at_cur_min);
- // Blend estimates based on crossover threshold
- // Use average to reduce bias from threshold comparison
+ // Comparing the average to the threshold reduces estimator-selection
bias.
let average_estimate = (adjusted_estimate + linear_estimate) / 2.0;
// Crossover thresholds (empirically determined)
@@ -296,7 +233,6 @@ impl Estimator {
}
}
- /// Get the HIP accumulator value
pub fn hip_accum(&self) -> f64 {
match self.estimate_state {
EstimateState::Hip(hip_accum) => hip_accum,
@@ -304,22 +240,18 @@ impl Estimator {
}
}
- /// Get the kxq0 register value
pub fn kxq0(&self) -> f64 {
self.kxq0
}
- /// Get the kxq1 register value
pub fn kxq1(&self) -> f64 {
self.kxq1
}
- /// Returns whether estimates are derived from registers rather than HIP
history.
pub fn uses_composite_estimate(&self) -> bool {
matches!(self.estimate_state, EstimateState::Composite)
}
- /// Returns the estimate state independently from register-derived KxQ
values.
pub fn estimate_state(&self) -> EstimateState {
self.estimate_state
}
@@ -341,27 +273,15 @@ impl Estimator {
}
}
-/// Get relative error for HLL estimates
-///
-/// This matches the implementation in datasketches-cpp HllUtil.hpp and
RelativeErrorTables.hpp
-///
-/// # Arguments
-///
-/// * `lg_config_k`: Log2 of number of registers (must be 4-21)
-/// * `upper_bound`: Whether computing upper bound (vs lower bound)
-/// * `composite`: Whether the estimate is derived from registers rather than
HIP history
-/// * `num_std_dev`: Number of standard deviations (1, 2, or 3)
-///
-/// # Returns
-///
-/// Relative error factor to apply to estimate
+/// Relative error used as `estimate / (1 + error)`: negative for upper bounds.
+/// Follows DataSketches C++ `HllUtil::getRelErr`:
+///
<https://github.com/apache/datasketches-cpp/blob/5a055521/hll/include/HllUtil.hpp>
fn relative_error(
lg_config_k: u8,
upper_bound: bool,
composite: bool,
num_std_dev: NumStdDev,
) -> f64 {
- // For lg_k > 12, use analytical formula with RSE factors
if lg_config_k > 12 {
// RSE factors from Apache DataSketches C++ implementation
// HLL_HIP_RSE_FACTOR = sqrt(ln(2)) ≈ 0.8325546
@@ -378,21 +298,19 @@ fn relative_error(
return sign * (num_std_dev as u8 as f64) * rse_factor / k.sqrt();
}
- // For lg_k <= 12, use empirically measured lookup tables.
- // Tables are indexed by: ((lg_k - 4) * 3) + (num_std_dev - 1)
+ // Small sketches use measured error quantiles rather than the asymptotic
formula.
let idx = ((lg_config_k as usize) - 4) * 3 + ((num_std_dev as usize) - 1);
- // Select the appropriate table based on estimator and bound direction.
match (composite, upper_bound) {
- (false, false) => HIP_LB[idx], // Case 0: HIP, Lower Bound
- (false, true) => HIP_UB[idx], // Case 1: HIP, Upper Bound
- (true, false) => NON_HIP_LB[idx], // Case 2: Non-HIP, Lower Bound
- (true, true) => NON_HIP_UB[idx], // Case 3: Non-HIP, Upper Bound
+ (false, false) => HIP_LB[idx],
+ (false, true) => HIP_UB[idx],
+ (true, false) => NON_HIP_LB[idx],
+ (true, true) => NON_HIP_UB[idx],
}
}
-// Relative error lookup tables from Apache DataSketches C++ implementation
-// RelativeErrorTables-internal.hpp
+// Measured quantiles, grouped by lg_k 4–12 with three standard deviations per
group.
+// Source:
https://github.com/apache/datasketches-cpp/blob/5a055521/hll/include/RelativeErrorTables-internal.hpp
/// HIP (in-order) Lower Bound errors for lg_k 4-12, std_dev 1-3
/// Q(.84134), Q(.97725), Q(.99865) quantiles
@@ -572,22 +490,18 @@ mod tests {
fn test_estimator_update() {
let mut est = Estimator::new(8); // 256 registers
- // Update from 0 to 10
est.update(8, 0, 10);
- // HIP should have increased
assert_that!(est.hip_accum(), gt(0.0));
- // kxq0 should have changed (10 < 32)
assert_that!(est.kxq0(), lt(256.0));
- assert_eq!(est.kxq1(), 0.0); // kxq1 unchanged
+ assert_eq!(est.kxq1(), 0.0);
}
#[test]
fn test_kxq_split() {
let mut est = Estimator::new(8);
- // Update to value < 32 (goes to kxq0)
est.update(8, 0, 10);
let kxq0_after_10 = est.kxq0();
let kxq1_after_10 = est.kxq1();
diff --git a/datasketches/src/hll/harmonic_numbers.rs
b/datasketches/src/hll/harmonic_numbers.rs
index 649ab22..cef22c7 100644
--- a/datasketches/src/hll/harmonic_numbers.rs
+++ b/datasketches/src/hll/harmonic_numbers.rs
@@ -15,10 +15,8 @@
// specific language governing permissions and limitations
// under the License.
-//! Harmonic number calculations for linear counting estimator
-//!
-//! Provides utilities for computing harmonic numbers used in the
-//! HLL bitmap estimator for small cardinalities.
+//! Harmonic-number approximation used by the bitmap estimator, following
DataSketches C++:
+//!
<https://github.com/apache/datasketches-cpp/blob/5a055521/hll/include/HarmonicNumbers-internal.hpp>
const NUM_EXACT: usize = 25;
const EULER_MASCHERONI: f64 = 0.577_215_664_901_532_9;
@@ -52,9 +50,7 @@ static EXACT_HARMONIC: [f64; NUM_EXACT] = [
1347822955.0 / 356948592.0, // H(24)
];
-/// Compute the n-th harmonic number H(n) = 1 + 1/2 + 1/3 + ... + 1/n
-///
-/// Uses exact table for small n, asymptotic expansion for large n.
+/// Computes `H(n) = 1 + 1/2 + ... + 1/n`, with `H(0) = 0`.
fn harmonic_number(n: usize) -> f64 {
if n < NUM_EXACT {
return EXACT_HARMONIC[n];
@@ -64,7 +60,7 @@ fn harmonic_number(n: usize) -> f64 {
let inv_sq = 1.0 / (x * x);
let mut sum = x.ln() + EULER_MASCHERONI + (1.0 / (2.0 * x));
- // Asymptotic expansion (appropriate for n >= 25)
+ // The cutoff at 25 and expansion through n^-8 are chosen together for f64
precision.
let mut pow = inv_sq; // n^-2
sum -= pow * (1.0 / 12.0);
@@ -80,18 +76,8 @@ fn harmonic_number(n: usize) -> f64 {
sum
}
-/// Bitmap estimator for flat random-access bit vectors (similar to Bloom
filter)
-///
-/// This is used for linear counting in the HLL composite estimator.
-///
-/// # Arguments
-///
-/// * `bit_vector_length`: Total length of bit vector (k for HLL)
-/// * `num_bits_set`: Number of bits set (non-zero registers)
-///
-/// # Returns
-///
-/// Estimated cardinality based on coupon collector problem
+/// Expected draws needed to hit `num_bits_set` distinct slots under the
coupon collector model.
+/// Requires `num_bits_set <= bit_vector_length`.
pub fn bitmap_estimate(bit_vector_length: u32, num_bits_set: u32) -> f64 {
let k = bit_vector_length;
let num_set = num_bits_set;
@@ -113,16 +99,12 @@ mod tests {
#[test]
fn test_exact_harmonic_numbers() {
- // H(1) = 1
assert_that!(harmonic_number(1), near(1.0, 1e-10));
- // H(2) = 1 + 1/2 = 1.5
assert_that!(harmonic_number(2), near(1.5, 1e-10));
- // H(3) = 1 + 1/2 + 1/3 = 11/6
assert_that!(harmonic_number(3), near(11.0 / 6.0, 1e-10));
- // H(10) should be exact from table
let expected = 1.0
+ 1.0 / 2.0
+ 1.0 / 3.0
@@ -143,20 +125,17 @@ mod tests {
let h_n = harmonic_number(n);
let approx = (n as f64).ln() + EULER_MASCHERONI + 1.0 / (2.0 * n as
f64);
- // Should be close (within 0.1%)
assert_that!(h_n, near(approx, h_n * 0.001));
}
#[test]
fn test_bitmap_estimate_empty() {
- // No bits set = estimate should be near 0
let est = bitmap_estimate(1024, 0);
assert_that!(est, near(0.0, 1e-6));
}
#[test]
fn test_bitmap_estimate_full() {
- // All bits set = should estimate large value
let k = 1024;
let est = bitmap_estimate(k, k);
@@ -170,11 +149,9 @@ mod tests {
#[test]
fn test_bitmap_estimate_half() {
- // Half bits set
let k = 1024;
let est = bitmap_estimate(k, k / 2);
- // Should be between 0 and k * H(k)
assert_that!(est, gt(0.0));
assert_that!(est, lt(k as f64 * harmonic_number(k as usize)));
}
diff --git a/datasketches/src/hll/hash_set.rs b/datasketches/src/hll/hash_set.rs
index dd2f5be..d78be7c 100644
--- a/datasketches/src/hll/hash_set.rs
+++ b/datasketches/src/hll/hash_set.rs
@@ -15,11 +15,6 @@
// specific language governing permissions and limitations
// under the License.
-//! Hash set for storing unique coupons with linear probing
-//!
-//! Uses open addressing with a custom stride function to handle collisions.
-//! Provides better performance than List when many coupons are stored.
-
use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::assert::insufficient_data;
@@ -36,7 +31,6 @@ use crate::hll::serialization::SERIAL_VERSION;
use crate::hll::serialization::SET_PREAMBLE_SIZE;
use crate::hll::serialization::encode_mode_byte;
-/// Hash set for efficient coupon storage with collision handling
#[derive(Debug, Clone, PartialEq)]
pub struct HashSet {
container: Container,
@@ -56,33 +50,27 @@ impl HashSet {
}
}
- /// Insert coupon into hash set, ignoring duplicates
pub fn update(&mut self, coupon: Coupon) {
let mask = (1 << self.container.lg_size()) - 1;
- // Initial probe position from low bits of coupon
let mut probe = coupon.raw() & mask;
let starting_position = probe;
loop {
let slot = &mut self.container.coupons[probe as usize];
if slot.is_empty() {
- // Found empty slot, insert new coupon
*slot = coupon;
self.container.len += 1;
break;
} else if *slot == coupon {
- // Duplicate found, nothing to do
break;
}
- // Collision: compute stride and probe next position
- // Stride is always odd to ensure all slots are visited
+ // An odd stride visits every slot in a power-of-two table.
let stride = ((coupon.raw() & KEY_MASK_26) >>
self.container.lg_size()) | 1;
probe = (probe + stride) & mask;
if probe == starting_position {
- // Invariant: the caller (HllSketch) is responsible for
- // growing / upgrading the HashSet when it's full
+ // HllSketch must grow or promote the set before it runs out
of empty slots.
unreachable!("HashSet full; no empty slots");
}
}
@@ -92,7 +80,6 @@ impl HashSet {
&self.container
}
- /// Deserialize a HashSet from bytes
pub fn deserialize(
mut cursor: SketchSlice,
lg_arr: usize,
@@ -120,8 +107,7 @@ impl HashSet {
}
if compact {
- // Compact mode: only couponCount coupons are stored
- // Create a new hash set and insert coupons one by one
+ // Compact images omit empty slots, so probe positions must be
rebuilt.
let mut hash_set = HashSet::new(lg_arr);
for i in 0..coupon_count {
let coupon = cursor.read_u32_le().map_err(|error| {
@@ -135,8 +121,7 @@ impl HashSet {
}
Ok(hash_set)
} else {
- // Non-compact mode: full hash table with empty slots
- // Read entire hash table including empty slots
+ // Updatable images contain the probe positions; preserve their
table layout.
let mut coupons = vec![Coupon::EMPTY; array_size];
for (i, coupon) in coupons.iter_mut().enumerate() {
let raw = cursor.read_u32_le().map_err(|error| {
@@ -161,51 +146,30 @@ impl HashSet {
}
}
- /// Serialize a HashSet to bytes
+ /// Serializes occupied coupons in compact format.
pub fn serialize(&self, lg_config_k: u8, hll_type: HllType) -> Vec<u8> {
- let compact = true; // Always use compact format
let coupon_count = self.container.len();
let lg_arr = self.container.lg_size();
-
- // Compute size
- let array_size = if compact { coupon_count } else { 1 << lg_arr };
- let total_size = SET_PREAMBLE_SIZE + (array_size * 4);
+ let total_size = SET_PREAMBLE_SIZE + (coupon_count * size_of::<u32>());
let mut bytes = SketchBytes::with_capacity(total_size);
- // Write preamble
bytes.write_u8(HASH_SET_PREINTS);
bytes.write_u8(SERIAL_VERSION);
bytes.write_u8(Family::HLL.id);
bytes.write_u8(lg_config_k);
bytes.write_u8(lg_arr as u8);
- // Write flags
- let mut flags = 0u8;
- if compact {
- flags |= COMPACT_FLAG_MASK;
- }
- bytes.write_u8(flags);
+ bytes.write_u8(COMPACT_FLAG_MASK);
- // Write unused byte
- bytes.write_u8(0);
+ bytes.write_u8(0); // Unused state byte in Set mode.
- // Write mode byte: SET mode with target HLL type
bytes.write_u8(encode_mode_byte(CUR_MODE_SET, hll_type as u8));
- // Write coupon count
bytes.write_u32_le(coupon_count as u32);
- // Write coupons
- if compact {
- for coupon in self.container.iter() {
- bytes.write_u32_le(coupon.raw());
- }
- } else {
- // Non-compact mode: write entire hash table
- for coupon in self.container.coupons.iter().copied() {
- bytes.write_u32_le(coupon.raw());
- }
+ for coupon in self.container.iter() {
+ bytes.write_u32_le(coupon.raw());
}
bytes.into_bytes()
diff --git a/datasketches/src/hll/list.rs b/datasketches/src/hll/list.rs
index 47370fa..748b187 100644
--- a/datasketches/src/hll/list.rs
+++ b/datasketches/src/hll/list.rs
@@ -15,11 +15,6 @@
// specific language governing permissions and limitations
// under the License.
-//! Simple list for storing unique coupons in order
-//!
-//! Provides sequential storage with linear search for duplicates.
-//! Efficient for small numbers of coupons before transitioning to HashSet.
-
use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::family::Family;
@@ -35,7 +30,6 @@ use crate::hll::serialization::LIST_PREINTS;
use crate::hll::serialization::SERIAL_VERSION;
use crate::hll::serialization::encode_mode_byte;
-/// List for sequential coupon storage with duplicate detection
#[derive(Debug, Clone, PartialEq)]
pub struct List {
container: Container,
@@ -55,16 +49,13 @@ impl List {
}
}
- /// Insert coupon into list, ignoring duplicates
pub fn update(&mut self, coupon: Coupon) {
for value in self.container.coupons.iter_mut() {
if value.is_empty() {
- // Found empty slot, insert new coupon
*value = coupon;
self.container.len += 1;
break;
} else if *value == coupon {
- // Duplicate found, nothing to do
break;
}
}
@@ -74,7 +65,6 @@ impl List {
&self.container
}
- /// Deserialize a List from bytes
pub fn deserialize(
mut cursor: SketchSlice,
lg_arr: usize,
@@ -82,10 +72,8 @@ impl List {
empty: bool,
compact: bool,
) -> Result<Self, Error> {
- // Always allocate the full-sized array (1 << lg_arr) so Coupon::EMPTY
sentinel
- // slots are available for future update() calls. In compact format
only
- // coupon_count values are stored on disk, but memory must hold the
full capacity
- // so the linear scan in update() can find an empty slot to insert
into.
+ // Compact images omit empty slots. Restore the full capacity so
future updates
+ // can insert into an empty slot before the list promotes.
let array_size = 1usize << lg_arr;
if coupon_count > array_size {
return Err(Error::deserial(format!(
@@ -109,7 +97,6 @@ impl List {
}
}
- // Read coupons into the front of the full-sized array; remaining
slots stay Coupon::EMPTY.
let mut coupons = vec![Coupon::EMPTY; array_size];
if !empty && coupon_count > 0 {
for (i, coupon) in coupons.iter_mut().take(read_count).enumerate()
{
@@ -126,55 +113,33 @@ impl List {
})
}
- /// Serialize a List to bytes
+ /// Serializes occupied coupons in compact format.
pub fn serialize(&self, lg_config_k: u8, hll_type: HllType) -> Vec<u8> {
- let compact = true; // Always use compact format
let empty = self.container.is_empty();
let coupon_count = self.container.len();
let lg_arr = self.container.lg_size();
-
- // Compute size
- let array_size = if compact { coupon_count } else { 1 << lg_arr };
- let total_size = LIST_PREAMBLE_SIZE + (array_size * 4);
+ let total_size = LIST_PREAMBLE_SIZE + (coupon_count *
size_of::<u32>());
let mut bytes = SketchBytes::with_capacity(total_size);
- // Write preamble
bytes.write_u8(LIST_PREINTS);
bytes.write_u8(SERIAL_VERSION);
bytes.write_u8(Family::HLL.id);
bytes.write_u8(lg_config_k);
bytes.write_u8(lg_arr as u8);
- // Write flags
- let mut flags = 0u8;
+ let mut flags = COMPACT_FLAG_MASK;
if empty {
flags |= EMPTY_FLAG_MASK;
}
- if compact {
- flags |= COMPACT_FLAG_MASK;
- }
bytes.write_u8(flags);
- // Write count
bytes.write_u8(coupon_count as u8);
- // Write mode byte: LIST mode with target HLL type
bytes.write_u8(encode_mode_byte(CUR_MODE_LIST, hll_type as u8));
- // Write coupons (only non-empty ones if compact)
- if !empty {
- let mut write_idx = 0;
- for coupon in self.container.coupons.iter().copied() {
- if compact && coupon.is_empty() {
- continue; // Skip empty coupons in compact mode
- }
- bytes.write_u32_le(coupon.raw());
- write_idx += 1;
- if write_idx >= array_size {
- break;
- }
- }
+ for coupon in self.container.iter().take(coupon_count) {
+ bytes.write_u32_le(coupon.raw());
}
bytes.into_bytes()
diff --git a/datasketches/src/hll/mod.rs b/datasketches/src/hll/mod.rs
index 1304ee0..fdec977 100644
--- a/datasketches/src/hll/mod.rs
+++ b/datasketches/src/hll/mod.rs
@@ -15,64 +15,14 @@
// specific language governing permissions and limitations
// under the License.
-//! HyperLogLog sketch implementation for cardinality estimation.
+//! HyperLogLog sketches for estimating the number of distinct values.
//!
-//! This module provides a probabilistic data structure for estimating the
cardinality
-//! (number of distinct elements) of large datasets with high accuracy and low
memory usage.
+//! Use [`HllSketch`] to collect values and [`HllUnion`] to combine sketches.
+//! [`HllType`] controls register storage; `lg_k` controls the register count
and accuracy.
//!
-//! # Overview
-//!
-//! HyperLogLog (HLL) sketches use hash functions to estimate cardinality in
logarithmic space.
-//! This implementation follows the Apache DataSketches specification and
supports multiple
-//! storage modes that automatically adapt based on cardinality:
-//!
-//! * **List mode**: Stores individual values for small cardinalities
-//! * **Set mode**: Uses a hash set for medium cardinalities
-//! * **HLL mode**: Uses compact arrays for large cardinalities
-//!
-//! Mode transitions are automatic and transparent to the user. Each promotion
preserves
-//! all previously observed values and maintains estimation accuracy.
-//!
-//! # Core Types
-//!
-//! The primary type for cardinality estimation is [`HllSketch`], which
maintains a single
-//! sketch and provides methods to update with new values and retrieve
cardinality estimates.
-//! For combining multiple sketches, use [`HllUnion`], which efficiently
merges sketches
-//! that may have different configurations.
-//!
-//! # HLL Types
-//!
-//! The three target HLL types are isomorphic representations of the same
registers. Given the
-//! same `lg_k` and input, they produce identical estimates and error
distributions; they trade
-//! memory layout and update performance, not statistical precision:
-//!
-//! * [`HllType::Hll4`]: 4 bits per bucket (most compact)
-//! * [`HllType::Hll6`]: 6 bits per bucket (fixed-size middle ground)
-//! * [`HllType::Hll8`]: 8 bits per bucket (largest and simplest
representation)
-//!
-//! # Union Operations
-//!
-//! The [`HllUnion`] type enables combining multiple HLL sketches into a
unified estimate.
-//! It accumulates the distinct values represented by all input sketches and
automatically handles:
-//!
-//! * Sketches with different `lg_k` configurations (resizes/downsamples as
needed)
-//! * Sketches with different target HLL types
-//!
-//! The result's accuracy is determined by its final effective `lg_k`. Merging
sketches with
-//! different configurations may reduce this value. Once reduced, it remains
lower until the union
-//! is reset. A lower effective `lg_k` widens the error distribution;
converting among HLL target
-//! types does not change accuracy.
-//!
-//! # Serialization
-//!
-//! Sketches can be serialized and deserialized while preserving all state,
including:
-//! * Current mode and HLL type
-//! * All observed values (coupons or register values)
-//! * HIP accumulator state for accurate estimation
-//! * Out-of-order flag for merged/deserialized sketches
-//!
-//! The serialization format is compatible with Apache DataSketches
implementations
-//! in Java and C++, enabling cross-platform sketch exchange.
+//! Serialized sketches are compatible with Apache DataSketches in Java and
C++.
+//! Cross-language updates must also use compatible hashing; see
+//! [`hash::value`](crate::hash::value).
//!
//! # Usage
//!
@@ -131,9 +81,10 @@ mod union;
pub use self::sketch::HllSketch;
pub use self::union::HllUnion;
-/// Target HLL type.
+/// Storage representation for HLL registers.
///
-/// See [module level documentation](self) for more details.
+/// For the same `lg_k` and input, all three types produce the same estimates.
+/// They trade memory usage against update speed.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum HllType {
/// Uses 4 bits per HLL bucket and has the smallest storage footprint.
@@ -157,19 +108,10 @@ const COUPON_RSE: f64 = COUPON_RSE_FACTOR / (1 << 13) as
f64;
const RESIZE_NUMERATOR: u32 = 3; // Resize at 3/4 = 75% load factor
const RESIZE_DENOMINATOR: u32 = 4;
-/// A coupon encodes a (slot, value) pair derived from hashing an input.
+/// A reusable hash of an input value for HLL sketches.
///
-/// Format: `[value (6 bits) << 26] | [slot (26 bits)]`
-///
-/// The slot identifies an HLL register (derived from the lower bits of the
hash),
-/// and the value represents the number of leading zeros plus one (from the
upper bits).
-///
-/// Pre-computing coupons is useful when the same logical value must be
inserted into
-/// multiple independent sketches, because the (relatively expensive) hash
step is paid
-/// only once. A common pattern is dictionary-encoded data: compute the
coupon for each
-/// term id up front, cache it, and then call
[`HllSketch::update_with_coupon`] for
-/// each per-bucket sketch rather than calling [`HllSketch::update`]
repeatedly with the
-/// decoded string.
+/// Compute a coupon once with [`Coupon::from_value`] and pass it to
+/// [`HllSketch::update_with_coupon`] on sketches with any `lg_k` or
[`HllType`].
///
/// # Examples
///
@@ -189,19 +131,17 @@ const RESIZE_DENOMINATOR: u32 = 4;
/// assert!(sketch2.estimate() >= 1.0);
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
-pub struct Coupon(u32);
+pub struct Coupon(u32); // Upper six bits: register value; lower 26 bits: slot.
impl Coupon {
/// Sentinel value indicating an empty coupon slot.
const EMPTY: Self = Coupon(0);
- /// Returns `true` if this coupon is the empty sentinel (value `0`).
#[inline(always)]
fn is_empty(self) -> bool {
self == Self::EMPTY
}
- /// Returns the raw 32-bit representation of the coupon.
#[inline(always)]
fn raw(self) -> u32 {
self.0
@@ -209,13 +149,21 @@ impl Coupon {
/// Computes the HLL coupon for a hashable value.
///
- /// You may use [`hash::value`](crate::hash::value) wrappers when another
DataSketches
+ /// Use [`hash::value`](crate::hash::value) wrappers when another
DataSketches
/// implementation requires a specific value hashing strategy.
///
- /// Hashes `value` using MurmurHash3 128-bit and packs the result into a
coupon:
- /// the low 26 bits of the low hash word become the slot index, and the
- /// leading-zero count of the high hash word (capped at 62, then plus one)
- /// becomes the 6-bit register value.
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::hll::Coupon;
+ /// use datasketches::hll::HllSketch;
+ /// use datasketches::hll::HllType;
+ ///
+ /// let coupon = Coupon::from_value("apple");
+ /// let mut sketch = HllSketch::new(10, HllType::Hll8).unwrap();
+ /// sketch.update_with_coupon(coupon);
+ /// assert!(sketch.estimate() >= 1.0);
+ /// ```
#[inline(always)]
pub fn from_value<T: Hash>(value: T) -> Self {
let mut hasher = MurmurHash3X64128::default();
@@ -224,25 +172,23 @@ impl Coupon {
let addr26 = lo as u32 & KEY_MASK_26;
let lz = hi.leading_zeros();
+ // Register values must fit in six bits; zero is reserved for empty
slots.
let capped = lz.min(62);
let value = capped + 1;
Coupon((value << KEY_BITS_26) | addr26)
}
- /// Pack a slot index and register value into a coupon.
#[inline(always)]
fn pack(slot: u32, value: u8) -> Self {
Coupon(((value as u32) << KEY_BITS_26) | (slot & KEY_MASK_26))
}
- /// Extract the slot index (low 26 bits).
#[inline(always)]
fn slot(self) -> u32 {
self.0 & KEY_MASK_26
}
- /// Extract the register value (upper 6 bits).
#[inline(always)]
fn value(self) -> u8 {
(self.0 >> KEY_BITS_26) as u8
diff --git a/datasketches/src/hll/serialization.rs
b/datasketches/src/hll/serialization.rs
index cacb6cb..166753e 100644
--- a/datasketches/src/hll/serialization.rs
+++ b/datasketches/src/hll/serialization.rs
@@ -15,15 +15,11 @@
// specific language governing permissions and limitations
// under the License.
-//! Binary serialization format constants for HLL sketches
-//!
-//! This module contains all constants related to the Apache DataSketches
-//! binary serialization format, shared across all sketch modes.
+//! HLL wire-format constants. Preamble lengths ending in `PREINTS` count
32-bit words;
+//! those ending in `PREAMBLE_SIZE` count bytes.
-/// Current serialization version
pub const SERIAL_VERSION: u8 = 1;
-/// Flag indicating sketch is empty (no values inserted)
pub const EMPTY_FLAG_MASK: u8 = 4;
/// Flag indicating compact coupon or HLL4 auxiliary storage.
///
@@ -32,64 +28,40 @@ pub const COMPACT_FLAG_MASK: u8 = 8;
/// Flag indicating that HIP history is unavailable and composite estimation
is required.
pub const OUT_OF_ORDER_FLAG_MASK: u8 = 16;
-/// Preamble size for LIST mode (8 bytes = 2 ints)
pub const LIST_PREINTS: u8 = 2;
-/// Preamble size for SET mode (12 bytes = 3 ints)
pub const HASH_SET_PREINTS: u8 = 3;
-/// Preamble size for HLL mode (40 bytes = 10 ints)
pub const HLL_PREINTS: u8 = 10;
-/// Total size of LIST preamble in bytes
pub const LIST_PREAMBLE_SIZE: usize = 8;
-/// Total size of SET preamble in bytes
pub const SET_PREAMBLE_SIZE: usize = 12;
-/// Total size of HLL preamble in bytes
pub const HLL_PREAMBLE_SIZE: usize = 40;
-/// Extract current mode from mode byte (low 2 bits)
-///
-/// Returns: 0 = LIST, 1 = SET, 2 = HLL
#[inline]
pub fn extract_cur_mode(mode_byte: u8) -> u8 {
mode_byte & 0x3
}
-/// Extract target HLL type from mode byte (bits 2-3)
-///
-/// Returns: 0 = HLL4, 1 = HLL6, 2 = HLL8
#[inline]
pub fn extract_tgt_hll_type(mode_byte: u8) -> u8 {
(mode_byte >> 2) & 0x3
}
-/// Encode mode byte from current mode and target type
-///
-/// # Arguments
-///
-/// * `cur_mode`: 0 = LIST, 1 = SET, 2 = HLL
-/// * `tgt_type`: 0 = HLL4, 1 = HLL6, 2 = HLL8
+/// The mode byte stores `CUR_MODE_*` in bits 0–1 and `TGT_HLL*` in bits 2–3.
#[inline]
pub fn encode_mode_byte(cur_mode: u8, tgt_type: u8) -> u8 {
(cur_mode & 0x3) | ((tgt_type & 0x3) << 2)
}
-/// Current mode: LIST
pub const CUR_MODE_LIST: u8 = 0;
-/// Current mode: SET
pub const CUR_MODE_SET: u8 = 1;
-/// Current mode: HLL
pub const CUR_MODE_HLL: u8 = 2;
-/// Target type: HLL4 (4-bit packed)
pub const TGT_HLL4: u8 = 0;
-/// Target type: HLL6 (6-bit packed)
pub const TGT_HLL6: u8 = 1;
-/// Target type: HLL8 (8-bit unpacked)
pub const TGT_HLL8: u8 = 2;
-/// Size of a single coupon in bytes (u32)
pub const COUPON_SIZE_BYTES: usize = 4;
diff --git a/datasketches/src/hll/sketch.rs b/datasketches/src/hll/sketch.rs
index bef4fbb..437062f 100644
--- a/datasketches/src/hll/sketch.rs
+++ b/datasketches/src/hll/sketch.rs
@@ -15,11 +15,6 @@
// specific language governing permissions and limitations
// under the License.
-//! HyperLogLog sketch implementation
-//!
-//! This module provides the main [`HllSketch`] struct, which is the primary
interface
-//! for creating and using HLL sketches for cardinality estimation.
-
use std::fmt;
use std::hash::Hash;
@@ -68,15 +63,9 @@ pub struct HllSketch {
}
impl HllSketch {
- /// Creates a new HLL sketch.
- ///
- /// # Arguments
+ /// Creates an empty sketch with `2^lg_config_k` registers and the
requested [`HllType`].
///
- /// * `lg_config_k`: The `lg_k` value in `[4, 21]`, which controls the
number of buckets.
- /// * `lg_k = 4`: 16 buckets, ~26% relative error.
- /// * `lg_k = 12`: 4096 buckets, ~1.6% relative error (common choice).
- /// * `lg_k = 21`: 2M buckets, ~0.4% relative error.
- /// * `hll_type`: Target HLL array type (`Hll4`, `Hll6`, or `Hll8`).
+ /// Increasing `lg_config_k` uses more memory and reduces estimation error.
///
/// # Errors
///
@@ -106,29 +95,15 @@ impl HllSketch {
})
}
- /// Create an HLL sketch directly from a Mode
- ///
- /// This is used internally (e.g., by union operations) to construct
- /// sketches in specific modes without going through List mode first.
- ///
- /// # Arguments
- ///
- /// * `lg_config_k`: Log2 of the number of buckets (K)
- /// * `mode`: The mode to initialize the sketch with
pub(super) fn from_mode(lg_config_k: u8, mode: Mode) -> Self {
Self { lg_config_k, mode }
}
- /// Get the current mode of the sketch
pub(super) fn mode(&self) -> &Mode {
&self.mode
}
- /// Get mutable access to the current mode
- ///
- /// # Safety
- ///
- /// Caller must maintain internal invariants (num_zeros, estimator state).
+ /// Callers must keep register-derived caches and estimate state
consistent with the mode.
pub(super) fn mode_mut(&mut self) -> &mut Mode {
&mut self.mode
}
@@ -162,16 +137,11 @@ impl HllSketch {
/// Updates the sketch with a value.
///
- /// Accepts any type that implements [`Hash`]. The value is hashed and
converted to
- /// an internal coupon, which is then inserted into the sketch.
- ///
/// You may use [`hash::value`](crate::hash::value) wrappers when another
DataSketches
/// implementation requires a specific value hashing strategy.
///
- /// If you need to insert the same logical value into multiple sketches,
consider
- /// pre-computing the coupon with [`Coupon::from_value`] and calling
- /// [`update_with_coupon`](Self::update_with_coupon) on each sketch to
avoid
- /// redundant hashing.
+ /// To reuse the hash across sketches, see [`Coupon`] and
+ /// [`update_with_coupon`](Self::update_with_coupon).
///
/// # Examples
///
@@ -192,15 +162,7 @@ impl HllSketch {
self.update_with_coupon(Coupon::from_value(value));
}
- /// Updates the sketch with a pre-computed [`Coupon`].
- ///
- /// A [`Coupon`] encodes both the HLL bucket index (low 26 bits) and the
register
- /// value (high 6 bits) derived from hashing an input. Accepting a
pre-computed
- /// coupon makes it possible to pay the hashing cost once and fan the
result out to
- /// many independent sketches — see [`Coupon`] for a worked example.
- ///
- /// All internal bookkeeping, including representation transitions and
estimator state updates,
- /// is handled automatically.
+ /// Updates the sketch with a precomputed [`Coupon`], without hashing the
input again.
///
/// # Examples
///
@@ -209,9 +171,9 @@ impl HllSketch {
/// use datasketches::hll::HllSketch;
/// use datasketches::hll::HllType;
///
- /// let c = Coupon::from_value("apple");
+ /// let coupon = Coupon::from_value("apple");
/// let mut sketch = HllSketch::new(10, HllType::Hll8).unwrap();
- /// sketch.update_with_coupon(c);
+ /// sketch.update_with_coupon(coupon);
/// assert!(sketch.estimate() >= 1.0);
/// ```
pub fn update_with_coupon(&mut self, coupon: Coupon) {
@@ -254,8 +216,11 @@ impl HllSketch {
/// use datasketches::hll::HllType;
///
/// let mut sketch = HllSketch::new(10, HllType::Hll8).unwrap();
- /// sketch.update("apple");
- /// assert!(sketch.estimate() >= 1.0);
+ /// for value in ["apple", "banana", "apple"] {
+ /// sketch.update(value);
+ /// }
+ /// let estimate = sketch.estimate();
+ /// assert!((estimate - 2.0).abs() < 0.01);
/// ```
pub fn estimate(&self) -> f64 {
match &self.mode {
@@ -267,9 +232,22 @@ impl HllSketch {
}
}
- /// Returns the upper confidence bound for the cardinality estimate.
+ /// Returns the upper confidence bound for `num_std_dev` standard
deviations.
///
- /// The bound is based on the requested number of standard deviations.
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::common::NumStdDev;
+ /// use datasketches::hll::HllSketch;
+ /// use datasketches::hll::HllType;
+ ///
+ /// let mut sketch = HllSketch::new(10, HllType::Hll8).unwrap();
+ /// for value in 0..10_000 {
+ /// sketch.update(value);
+ /// }
+ /// let upper = sketch.upper_bound(NumStdDev::Two);
+ /// assert!(upper >= sketch.estimate());
+ /// ```
pub fn upper_bound(&self, num_std_dev: NumStdDev) -> f64 {
match &self.mode {
Mode::List { list, .. } =>
list.container().upper_bound(num_std_dev),
@@ -280,9 +258,22 @@ impl HllSketch {
}
}
- /// Returns the lower confidence bound for the cardinality estimate.
+ /// Returns the lower confidence bound for `num_std_dev` standard
deviations.
+ ///
+ /// # Examples
///
- /// The bound is based on the requested number of standard deviations.
+ /// ```
+ /// use datasketches::common::NumStdDev;
+ /// use datasketches::hll::HllSketch;
+ /// use datasketches::hll::HllType;
+ ///
+ /// let mut sketch = HllSketch::new(10, HllType::Hll8).unwrap();
+ /// for value in 0..10_000 {
+ /// sketch.update(value);
+ /// }
+ /// let lower = sketch.lower_bound(NumStdDev::Two);
+ /// assert!(lower <= sketch.estimate());
+ /// ```
pub fn lower_bound(&self, num_std_dev: NumStdDev) -> f64 {
match &self.mode {
Mode::List { list, .. } =>
list.container().lower_bound(num_std_dev),
@@ -311,12 +302,11 @@ impl HllSketch {
///
/// let bytes = sketch.serialize();
/// let decoded = HllSketch::deserialize(&bytes).unwrap();
- /// assert!(decoded.estimate() >= 1.0);
+ /// assert_eq!(decoded.estimate(), sketch.estimate());
/// ```
pub fn deserialize(bytes: &[u8]) -> Result<HllSketch, Error> {
let mut cursor = SketchSlice::new(bytes);
- // Read and validate preamble
let preamble_ints = cursor
.read_u8()
.map_err(insufficient_data("preamble_ints"))?;
@@ -335,13 +325,10 @@ impl HllSketch {
let state = cursor.read_u8().map_err(insufficient_data("state"))?;
let mode_byte = cursor.read_u8().map_err(insufficient_data("mode"))?;
- // Verify family ID
Family::HLL.validate_id(family_id)?;
- // Verify serialization version
ensure_serial_version_is(SERIAL_VERSION, serial_version)?;
- // Verify lg_k range (4-21 are valid)
if !(4..=21).contains(&lg_config_k) {
return Err(Error::deserial(format!(
"lg_k must be in [4; 21], got {lg_config_k}",
@@ -361,7 +348,7 @@ impl HllSketch {
let compact = (flags & COMPACT_FLAG_MASK) != 0;
let ooo = (flags & OUT_OF_ORDER_FLAG_MASK) != 0;
- // Deserialize based on mode
+ // Each mode reader starts after the shared eight-byte header.
let mode =
match extract_cur_mode(mode_byte) {
CUR_MODE_LIST => {
@@ -451,7 +438,7 @@ impl HllSketch {
}
}
- /// Returns the estimated size of the sketch in bytes.
+ /// Returns the estimated memory usage in bytes, including owned heap
allocations.
pub fn estimated_size(&self) -> usize {
let heap_size = match &self.mode {
Mode::List { list, .. } => list.container().estimated_size(),
diff --git a/datasketches/src/hll/union.rs b/datasketches/src/hll/union.rs
index eb98382..f16cebc 100644
--- a/datasketches/src/hll/union.rs
+++ b/datasketches/src/hll/union.rs
@@ -15,19 +15,6 @@
// specific language governing permissions and limitations
// under the License.
-//! HyperLogLog Union for combining multiple HLL sketches
-//!
-//! The HLL Union allows combining multiple HLL sketches into a single unified
-//! sketch, enabling set union operations for cardinality estimation.
-//!
-//! # Overview
-//!
-//! The union maintains an internal "gadget" sketch that accumulates the union
-//! of all input sketches. It can handle sketches with:
-//! * Different lg_k values (automatically resizes as needed)
-//! * Different modes (List, Set, Array4/6/8)
-//! * Different target HLL types
-
use std::hash::Hash;
use crate::common::NumStdDev;
@@ -43,9 +30,6 @@ use crate::hll::mode::Mode;
/// An HLL union for combining multiple HLL sketches.
///
-/// The union accumulates the distinct values represented by all input
sketches and automatically
-/// handles sketches with different configurations.
-///
/// Merging sketches with different configurations may reduce the union's
effective `lg_k`. Once
/// reduced, it remains lower until [`reset`](Self::reset), so estimates and
bounds reflect the
/// reduced register count. The requested [`HllType`] changes only the result
representation, not
@@ -54,19 +38,15 @@ use crate::hll::mode::Mode;
/// See the [module level documentation](super) for more.
#[derive(Debug, Clone)]
pub struct HllUnion {
- /// Maximum lg_k that this union can handle
lg_max_k: u8,
- /// Internal sketch that accumulates the union
+ /// Array modes always use `Array8`; packed results are produced by
`to_sketch`.
gadget: HllSketch,
}
impl HllUnion {
- /// Creates a new HLL union.
- ///
- /// # Arguments
+ /// Creates an empty union with a maximum of `2^lg_max_k` registers.
///
- /// * `lg_max_k`: Maximum `lg_k` in `[4, 21]`. This determines the maximum
precision the union
- /// can handle. Input sketches with a larger `lg_k` are downsampled.
+ /// Input sketches with a larger `lg_k` are downsampled.
///
/// # Errors
///
@@ -81,39 +61,32 @@ impl HllUnion {
/// let mut union = HllUnion::new(10).unwrap();
/// union.update_value("apple");
/// let result = union.to_sketch(HllType::Hll8);
- /// assert_eq!(result.estimate(), 1.0);
+ /// assert!(result.estimate() >= 1.0);
/// ```
pub fn new(lg_max_k: u8) -> Result<Self, Error> {
- // Start with an empty gadget at lg_max_k using Hll8
let gadget = HllSketch::new(lg_max_k, HllType::Hll8)?;
Ok(Self { lg_max_k, gadget })
}
- /// Updates the union with a hashable value.
- ///
- /// This accepts any type that implements `Hash`. The value is hashed
- /// and converted to a coupon, which is then inserted into the sketch.
+ /// Updates the union with a value, using the same hashing as
[`HllSketch::update`].
///
/// # Examples
///
/// ```
- /// use datasketches::hll::HllType;
/// use datasketches::hll::HllUnion;
///
/// let mut union = HllUnion::new(10).unwrap();
/// union.update_value("apple");
- /// let result = union.to_sketch(HllType::Hll8);
- /// assert_eq!(result.estimate(), 1.0);
+ /// assert!(union.estimate() >= 1.0);
/// ```
pub fn update_value<T: Hash>(&mut self, value: T) {
self.gadget.update(value);
}
- /// Updates the union with another sketch.
+ /// Merges a sketch into the union, accepting any [`HllType`] and `lg_k`.
///
- /// The input is merged while accommodating different `lg_k`
configurations and target HLL
- /// types. The union's effective `lg_k` may decrease as a result.
+ /// The union's effective `lg_k` may decrease. Empty sketches have no
effect.
///
/// # Examples
///
@@ -152,7 +125,6 @@ impl HllUnion {
}
}
- /// Update union from a List or Set mode sketch
fn update_from_list_or_set(
&mut self,
sketch: &HllSketch,
@@ -160,23 +132,18 @@ impl HllUnion {
src_lg_k: u8,
dst_lg_k: u8,
) {
- // Fast path: If gadget is empty and lg_k matches, directly copy as
HLL_8
if self.gadget.is_empty() && src_lg_k == dst_lg_k {
self.gadget = if sketch.target_type() == HllType::Hll8 {
sketch.clone()
} else {
- // Convert to Hll8 by changing target type
convert_coupon_mode_to_hll8(src_mode, src_lg_k)
};
} else {
- // Regular path: merge coupons into gadget
merge_coupons_into_gadget(&mut self.gadget, src_mode);
}
}
- /// Update union from an Array mode sketch
fn update_from_array(&mut self, src_mode: &Mode, src_lg_k: u8, dst_lg_k:
u8) {
- // Fast path: If gadget is empty, just copy/downsample source
if self.gadget.is_empty() {
let new_array = copy_or_downsample(src_mode, src_lg_k,
self.lg_max_k);
let final_lg_k = new_array.num_registers().trailing_zeros() as u8;
@@ -193,10 +160,8 @@ impl HllUnion {
}
}
- /// Merge an array source into an array gadget
fn merge_array_into_array_gadget(&mut self, src_mode: &Mode, src_lg_k: u8,
dst_lg_k: u8) {
if src_lg_k < dst_lg_k {
- // Source has lower precision - must downsize gadget
let mut new_array = Array8::new(src_lg_k);
match self.gadget.mode() {
@@ -216,7 +181,6 @@ impl HllUnion {
merge_array_same_lgk(&mut new_array, src_mode);
self.gadget = HllSketch::from_mode(src_lg_k,
Mode::Array8(new_array));
} else {
- // Standard merge: src_lg_k >= dst_lg_k
match self.gadget.mode_mut() {
Mode::Array8(dst_array) => {
merge_array_into_array8(dst_array, dst_lg_k, src_mode,
src_lg_k);
@@ -228,7 +192,6 @@ impl HllUnion {
}
}
- /// Promote gadget from List/Set to Array and merge array source
fn promote_gadget_and_merge_array(&mut self, src_mode: &Mode, src_lg_k:
u8) {
let mut new_array = copy_or_downsample(src_mode, src_lg_k,
self.lg_max_k);
@@ -239,14 +202,9 @@ impl HllUnion {
self.gadget = HllSketch::from_mode(final_lg_k,
Mode::Array8(new_array));
}
- /// Returns the union result as a new sketch.
- ///
- /// The returned sketch uses the specified target HLL type. If the
requested type differs from
- /// the current representation, the result is converted.
- ///
- /// # Arguments
+ /// Returns an independent sketch with the requested [`HllType`].
///
- /// * `hll_type`: Target HLL type for the result sketch (`Hll4`, `Hll6`,
or `Hll8`).
+ /// The result retains the union's effective `lg_k` and cardinality
estimate.
///
/// # Examples
///
@@ -257,7 +215,8 @@ impl HllUnion {
/// let mut union = HllUnion::new(10).unwrap();
/// union.update_value("apple");
/// let result = union.to_sketch(HllType::Hll6);
- /// assert!(result.estimate() >= 1.0);
+ /// assert_eq!(result.target_type(), HllType::Hll6);
+ /// assert_eq!(result.estimate(), union.estimate());
/// ```
pub fn to_sketch(&self, hll_type: HllType) -> HllSketch {
let gadget_type = self.gadget.target_type();
@@ -305,40 +264,94 @@ impl HllUnion {
self.gadget.is_empty()
}
- /// Resets the union to its initial empty state.
+ /// Clears the union and restores its configured maximum `lg_k`.
+ ///
+ /// # Examples
///
- /// This clears all accumulated data so the union can be reused.
+ /// ```
+ /// use datasketches::hll::HllSketch;
+ /// use datasketches::hll::HllType;
+ /// use datasketches::hll::HllUnion;
+ ///
+ /// let mut sketch = HllSketch::new(10, HllType::Hll8).unwrap();
+ /// for value in 0..10_000 {
+ /// sketch.update(value);
+ /// }
+ /// let mut union = HllUnion::new(12).unwrap();
+ /// union.update(&sketch);
+ /// assert_eq!(union.lg_config_k(), 10);
+ ///
+ /// union.reset();
+ /// assert!(union.is_empty());
+ /// assert_eq!(union.lg_config_k(), 12);
+ /// ```
pub fn reset(&mut self) {
self.gadget = HllSketch::new(self.lg_max_k, HllType::Hll8).unwrap();
}
/// Returns the union's current cardinality estimate.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::hll::HllUnion;
+ ///
+ /// let mut union = HllUnion::new(10).unwrap();
+ /// for value in ["apple", "banana", "apple"] {
+ /// union.update_value(value);
+ /// }
+ /// let estimate = union.estimate();
+ /// assert!((estimate - 2.0).abs() < 0.01);
+ /// ```
pub fn estimate(&self) -> f64 {
self.gadget.estimate()
}
- /// Returns the upper confidence bound for the union's cardinality
estimate.
+ /// Returns the upper confidence bound for `num_std_dev` standard
deviations.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::common::NumStdDev;
+ /// use datasketches::hll::HllUnion;
///
- /// The bound is based on the requested number of standard deviations.
+ /// let mut union = HllUnion::new(10).unwrap();
+ /// for value in 0..10_000 {
+ /// union.update_value(value);
+ /// }
+ /// let upper = union.upper_bound(NumStdDev::Two);
+ /// assert!(upper >= union.estimate());
+ /// ```
pub fn upper_bound(&self, num_std_dev: NumStdDev) -> f64 {
self.gadget.upper_bound(num_std_dev)
}
- /// Returns the lower confidence bound for the union's cardinality
estimate.
+ /// Returns the lower confidence bound for `num_std_dev` standard
deviations.
+ ///
+ /// # Examples
///
- /// The bound is based on the requested number of standard deviations.
+ /// ```
+ /// use datasketches::common::NumStdDev;
+ /// use datasketches::hll::HllUnion;
+ ///
+ /// let mut union = HllUnion::new(10).unwrap();
+ /// for value in 0..10_000 {
+ /// union.update_value(value);
+ /// }
+ /// let lower = union.lower_bound(NumStdDev::Two);
+ /// assert!(lower <= union.estimate());
+ /// ```
pub fn lower_bound(&self, num_std_dev: NumStdDev) -> f64 {
self.gadget.lower_bound(num_std_dev)
}
- /// Returns the estimated size of the union in bytes.
+ /// Returns the estimated memory usage in bytes, including owned heap
allocations.
pub fn estimated_size(&self) -> usize {
// The gadget's inline size is already covered by size_of::<Self>().
size_of::<Self>() - size_of::<HllSketch>() +
self.gadget.estimated_size()
}
}
-/// Convert a coupon mode (List or Set) to Hll8 target type
fn convert_coupon_mode_to_hll8(src_mode: &Mode, src_lg_k: u8) -> HllSketch {
match src_mode {
Mode::List { list, .. } => HllSketch::from_mode(
@@ -359,10 +372,6 @@ fn convert_coupon_mode_to_hll8(src_mode: &Mode, src_lg_k:
u8) -> HllSketch {
}
}
-/// Merge coupons from a List or Set mode into the gadget
-///
-/// Iterates over all coupons in the source and updates the gadget.
-/// The gadget handles mode transitions automatically (List → Set → Array).
fn merge_coupons_into_gadget(gadget: &mut HllSketch, src_mode: &Mode) {
match src_mode {
Mode::List { list, .. } => {
@@ -383,7 +392,6 @@ fn merge_coupons_into_gadget(gadget: &mut HllSketch,
src_mode: &Mode) {
}
}
-/// Merge coupons from a List or Set mode into an Array8
fn merge_coupons_into_mode(dst: &mut Array8, src_mode: &Mode) {
match src_mode {
Mode::List { list, .. } => {
@@ -404,12 +412,7 @@ fn merge_coupons_into_mode(dst: &mut Array8, src_mode:
&Mode) {
}
}
-/// Merge an HLL array into an Array8
-///
-/// Handles merging from Array4, Array6, or Array8 sources. Dispatches based
on lg_k:
-/// * Same lg_k: optimized bulk merge
-/// * src lg_k > dst lg_k: downsample src into dst
-/// * src lg_k < dst lg_k: handled by caller (requires gadget replacement)
+/// The caller must downsize the destination first if the source has a smaller
`lg_k`.
fn merge_array_into_array8(dst_array8: &mut Array8, dst_lg_k: u8, src_mode:
&Mode, src_lg_k: u8) {
assert!(
src_lg_k >= dst_lg_k,
@@ -425,7 +428,6 @@ fn merge_array_into_array8(dst_array8: &mut Array8,
dst_lg_k: u8, src_mode: &Mod
}
}
-/// Extract estimate state from an array mode.
fn get_array_estimate_state(mode: &Mode) -> EstimateState {
match mode {
Mode::Array8(src) => src.estimate_state(),
@@ -439,7 +441,6 @@ fn get_array_estimate_state(mode: &Mode) -> EstimateState {
}
}
-/// Merge Array4/Array6 into Array8 by iterating registers
fn merge_array46_same_lgk(dst: &mut Array8, num_registers: usize, get_value:
impl Fn(u32) -> u8) {
for slot in 0..num_registers {
let val = get_value(slot as u32);
@@ -451,9 +452,7 @@ fn merge_array46_same_lgk(dst: &mut Array8, num_registers:
usize, get_value: imp
dst.rebuild_estimator_from_registers();
}
-/// Merge arrays with same lg_k
-///
-/// Takes the max of corresponding registers. HIP accumulator is invalidated
by the merge.
+/// Merging independent register histories invalidates the HIP accumulator.
fn merge_array_same_lgk(dst: &mut Array8, src_mode: &Mode) {
match src_mode {
Mode::Array8(src) => {
@@ -471,7 +470,6 @@ fn merge_array_same_lgk(dst: &mut Array8, src_mode: &Mode) {
}
}
-/// Merge Array4/Array6 into Array8 with downsampling
fn merge_array46_with_downsample(
dst: &mut Array8,
dst_lg_k: u8,
@@ -492,10 +490,8 @@ fn merge_array46_with_downsample(
dst.rebuild_estimator_from_registers();
}
-/// Merge arrays with downsampling (src lg_k > dst lg_k)
-///
/// Multiple source registers map to each destination register via masking.
-/// HIP accumulator is invalidated by the merge.
+/// Merging independent register histories invalidates the HIP accumulator.
fn merge_array_with_downsample(dst: &mut Array8, dst_lg_k: u8, src_mode:
&Mode, src_lg_k: u8) {
assert!(
src_lg_k > dst_lg_k,
@@ -520,10 +516,8 @@ fn merge_array_with_downsample(dst: &mut Array8, dst_lg_k:
u8, src_mode: &Mode,
}
}
-/// Convert Array8 to a different HLL type
-///
-/// Creates a new sketch with the requested type by copying register values
-/// from the Array8 source. Preserves the estimate state.
+/// Changing representation preserves the estimate state; replaying registers
alone would change
+/// HIP.
fn convert_array8_to_type(src: &Array8, lg_config_k: u8, target_type: HllType)
-> HllSketch {
let estimate_state = src.estimate_state();
match target_type {
@@ -558,7 +552,6 @@ fn convert_array8_to_type(src: &Array8, lg_config_k: u8,
target_type: HllType) -
}
}
-/// Copy Array4/Array6 registers into Array8 by converting to coupons
fn copy_array46_via_coupons(dst: &mut Array8, num_registers: usize, get_value:
impl Fn(u32) -> u8) {
for slot in 0..num_registers {
let val = get_value(slot as u32);
@@ -569,10 +562,7 @@ fn copy_array46_via_coupons(dst: &mut Array8,
num_registers: usize, get_value: i
}
}
-/// Copy or downsample a source array to create a new Array8
-///
-/// Directly copies if src_lg_k <= tgt_lg_k, downsamples otherwise.
-/// The source estimate state carries over because the result represents the
same logical sketch.
+/// Preserves the source estimate state because the result represents the same
logical sketch.
fn copy_or_downsample(src_mode: &Mode, src_lg_k: u8, tgt_lg_k: u8) -> Array8 {
let estimate_state = get_array_estimate_state(src_mode);
@@ -598,7 +588,6 @@ fn copy_or_downsample(src_mode: &Mode, src_lg_k: u8,
tgt_lg_k: u8) -> Array8 {
result
} else {
- // Downsample from src to tgt
let mut result = Array8::new(tgt_lg_k);
merge_array_with_downsample(&mut result, tgt_lg_k, src_mode, src_lg_k);
result
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
