You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by fr...@apache.org on 2026/04/18 08:35:37 UTC
(datasketches-rust) branch main updated: feat(hll): expose coupon fn and improve update_with_coupon docs (#116)
This is an automated email from the ASF dual-hosted git repository.
notfilippo 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 7fa974e feat(hll): expose coupon fn and improve update_with_coupon docs (#116)
7fa974e is described below
commit 7fa974ed967d423eb3da76ce9a8991d3b26a8692
Author: Filippo <12...@users.noreply.github.com>
AuthorDate: Sat Apr 18 10:35:32 2026 +0200
feat(hll): expose coupon fn and improve update_with_coupon docs (#116)
* feat(hll): expose coupon fn and improve update_with_coupon docs
Make `hll::coupon` public so callers can compute a coupon from any
hashable value without going through `HllSketch::update`. This enables
a common optimization: pre-compute coupons for dictionary-encoded data
once and fan them into multiple independent per-bucket sketches via
`update_with_coupon`, avoiding redundant hashing.
- `hll::coupon` is now `pub` with full documentation
- `HllSketch::update` cross-references `coupon` + `update_with_coupon`
- `HllSketch::update_with_coupon` gains a detailed doc comment
explaining the coupon format and the multi-sketch use case
Follows up on #113 which made `update_with_coupon` public.
* feat(hll): introduce Coupon newtype and expose update_with_coupon
Introduce a `Coupon` newtype (a 32-bit value encoding an HLL slot index
in the low 26 bits and a register value in the high 6 bits) in place of
the raw `u32` and the free functions `get_slot`, `get_value`,
`pack_coupon`, and `coupon` that existed before.
`Coupon` is now a public type with a single public constructor:
let c = Coupon::from_hash("hello");
Callers can then feed the same coupon into many independent sketches
without re-hashing:
sketch_a.update_with_coupon(c);
sketch_b.update_with_coupon(c);
This is useful for dictionary-encoded data where per-bucket HLL sketches
are maintained: compute the coupon for each term id once, cache it, and
fan it out across all relevant per-bucket sketches.
Internal helper methods (`is_empty`, `raw`, `slot`, `value`, `pack`) are
crate-private and keep the public surface minimal.
Co-authored-by: Paul Masurel <pa...@datadoghq.com>
Follows up on #113 which made `update_with_coupon` public.
---------
Co-authored-by: Paul Masurel <pa...@datadoghq.com>
---
datasketches/src/hll/array4.rs | 28 ++++-----
datasketches/src/hll/array6.rs | 19 +++----
datasketches/src/hll/array8.rs | 29 +++++-----
datasketches/src/hll/aux_map.rs | 54 ++++++++----------
datasketches/src/hll/container.rs | 24 ++++----
datasketches/src/hll/hash_set.rs | 31 +++++-----
datasketches/src/hll/list.rs | 17 +++---
datasketches/src/hll/mod.rs | 116 +++++++++++++++++++++++++++-----------
datasketches/src/hll/sketch.rs | 38 ++++++++++---
datasketches/src/hll/union.rs | 8 +--
10 files changed, 209 insertions(+), 155 deletions(-)
diff --git a/datasketches/src/hll/array4.rs b/datasketches/src/hll/array4.rs
index 9fc400d..b8e5b36 100644
--- a/datasketches/src/hll/array4.rs
+++ b/datasketches/src/hll/array4.rs
@@ -27,10 +27,8 @@ use crate::codec::assert::insufficient_data;
use crate::codec::family::Family;
use crate::common::NumStdDev;
use crate::error::Error;
+use crate::hll::Coupon;
use crate::hll::estimator::HipEstimator;
-use crate::hll::get_slot;
-use crate::hll::get_value;
-use crate::hll::pack_coupon;
use crate::hll::serialization::COUPON_SIZE_BYTES;
use crate::hll::serialization::CUR_MODE_HLL;
use crate::hll::serialization::HLL_PREAMBLE_SIZE;
@@ -130,10 +128,10 @@ impl Array4 {
};
}
- pub fn update(&mut self, coupon: u32) {
+ pub fn update(&mut self, coupon: Coupon) {
let mask = (1 << self.lg_config_k) - 1;
- let slot = get_slot(coupon) & mask;
- let new_value = get_value(coupon);
+ 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 {
@@ -341,8 +339,9 @@ impl Array4 {
"expected {aux_count} aux coupons, failed at index {i}",
))
})?;
- let slot = get_slot(coupon) & ((1 << lg_config_k) - 1);
- let value = get_value(coupon);
+ let coupon = Coupon(coupon);
+ let slot = coupon.slot() & ((1 << lg_config_k) - 1);
+ let value = coupon.value();
aux.insert(slot, value);
}
aux_map = Some(aux);
@@ -418,8 +417,7 @@ impl Array4 {
// Write aux map entries if present
for (slot, value) in aux_entries.iter().copied() {
- let coupon = pack_coupon(slot, value);
- bytes.write_u32_le(coupon);
+ bytes.write_u32_le(Coupon::pack(slot, value).raw());
}
bytes.into_bytes()
@@ -429,8 +427,7 @@ impl Array4 {
#[cfg(test)]
mod tests {
use super::*;
- use crate::hll::coupon;
- use crate::hll::pack_coupon;
+ use crate::hll::Coupon;
#[test]
fn test_get_set_raw() {
@@ -463,8 +460,7 @@ mod tests {
// Add some unique values to different slots
for i in 0..10_000u32 {
- let coupon = coupon(i);
- arr.update(coupon);
+ arr.update(Coupon::from_hash(i));
}
// Estimate should be positive and roughly in the ballpark
@@ -492,8 +488,8 @@ mod tests {
let mut arr = Array4::new(8); // 256 buckets
// Test that values < 32 and >= 32 are handled correctly
- arr.update(pack_coupon(0, 10)); // value < 32, goes to kxq0
- arr.update(pack_coupon(1, 40)); // value >= 32, goes to kxq1
+ 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)
diff --git a/datasketches/src/hll/array6.rs b/datasketches/src/hll/array6.rs
index abaf620..2aaff0a 100644
--- a/datasketches/src/hll/array6.rs
+++ b/datasketches/src/hll/array6.rs
@@ -27,9 +27,8 @@ use crate::codec::assert::insufficient_data;
use crate::codec::family::Family;
use crate::common::NumStdDev;
use crate::error::Error;
+use crate::hll::Coupon;
use crate::hll::estimator::HipEstimator;
-use crate::hll::get_slot;
-use crate::hll::get_value;
use crate::hll::serialization::CUR_MODE_HLL;
use crate::hll::serialization::HLL_PREAMBLE_SIZE;
use crate::hll::serialization::HLL_PREINTS;
@@ -124,10 +123,10 @@ impl Array6 {
}
/// Update with a coupon
- pub fn update(&mut self, coupon: u32) {
+ pub fn update(&mut self, coupon: Coupon) {
let mask = (1 << self.lg_config_k) - 1;
- let slot = get_slot(coupon) & mask;
- let new_value = get_value(coupon);
+ let slot = coupon.slot() & mask;
+ let new_value = coupon.value();
let old_value = self.get_raw(slot);
@@ -285,8 +284,7 @@ fn num_bytes_for_k(k: u32) -> usize {
#[cfg(test)]
mod tests {
use super::*;
- use crate::hll::coupon;
- use crate::hll::pack_coupon;
+ use crate::hll::Coupon;
#[test]
fn test_num_bytes_calculation() {
@@ -358,8 +356,7 @@ mod tests {
// Add some unique values using real coupon hashing
for i in 0..10_000u32 {
- let coupon = coupon(i);
- arr.update(coupon);
+ arr.update(Coupon::from_hash(i));
}
let estimate = arr.estimate();
@@ -392,8 +389,8 @@ mod tests {
let mut arr = Array6::new(8); // 256 buckets
// Test that values < 32 and >= 32 are handled correctly
- arr.update(pack_coupon(0, 10)); // value < 32, goes to kxq0
- arr.update(pack_coupon(1, 40)); // value >= 32, goes to kxq1
+ arr.update(Coupon::pack(0, 10)); // value < 32, goes to kxq0
+ arr.update(Coupon::pack(1, 40)); // value >= 32, goes to kxq1
// Initial kxq0 = 256 (all zeros = 1.0 each)
assert!(arr.estimator.kxq0() < 256.0, "kxq0 should have decreased");
diff --git a/datasketches/src/hll/array8.rs b/datasketches/src/hll/array8.rs
index 1a0f1f0..21f0d53 100644
--- a/datasketches/src/hll/array8.rs
+++ b/datasketches/src/hll/array8.rs
@@ -26,9 +26,8 @@ use crate::codec::assert::insufficient_data;
use crate::codec::family::Family;
use crate::common::NumStdDev;
use crate::error::Error;
+use crate::hll::Coupon;
use crate::hll::estimator::HipEstimator;
-use crate::hll::get_slot;
-use crate::hll::get_value;
use crate::hll::serialization::CUR_MODE_HLL;
use crate::hll::serialization::HLL_PREAMBLE_SIZE;
use crate::hll::serialization::HLL_PREINTS;
@@ -78,10 +77,10 @@ impl Array8 {
}
/// Update with a coupon
- pub fn update(&mut self, coupon: u32) {
+ pub fn update(&mut self, coupon: Coupon) {
let mask = (1 << self.lg_config_k) - 1;
- let slot = get_slot(coupon) & mask;
- let new_value = get_value(coupon);
+ let slot = coupon.slot() & mask;
+ let new_value = coupon.value();
let old_value = self.get(slot);
@@ -350,8 +349,7 @@ impl Array8 {
#[cfg(test)]
mod tests {
use super::*;
- use crate::hll::coupon;
- use crate::hll::pack_coupon;
+ use crate::hll::Coupon;
#[test]
fn test_array8_basic() {
@@ -391,20 +389,20 @@ mod tests {
let mut arr = Array8::new(4);
// Update slot 0 with value 5
- arr.update(pack_coupon(0, 5));
+ arr.update(Coupon::pack(0, 5));
assert_eq!(arr.get(0), 5);
// Update with a smaller value (should be ignored)
- arr.update(pack_coupon(0, 3));
+ arr.update(Coupon::pack(0, 3));
assert_eq!(arr.get(0), 5);
// Update with a larger value
- arr.update(pack_coupon(0, 42));
+ arr.update(Coupon::pack(0, 42));
assert_eq!(arr.get(0), 42);
// Test value at max coupon range (63)
- // Note: pack_coupon only stores 6 bits (0-63)
- arr.update(pack_coupon(1, 63));
+ // Note: Coupon::pack only stores 6 bits (0-63)
+ arr.update(Coupon::pack(1, 63));
assert_eq!(arr.get(1), 63);
}
@@ -417,8 +415,7 @@ mod tests {
// Add some unique values using real coupon hashing
for i in 0..10_000u32 {
- let coupon = coupon(i);
- arr.update(coupon);
+ arr.update(Coupon::from_hash(i));
}
let estimate = arr.estimate();
@@ -471,8 +468,8 @@ mod tests {
let mut arr = Array8::new(8); // 256 buckets
// Test that values < 32 and >= 32 are handled correctly
- arr.update(pack_coupon(0, 10)); // value < 32, goes to kxq0
- arr.update(pack_coupon(1, 50)); // value >= 32, goes to kxq1
+ arr.update(Coupon::pack(0, 10)); // value < 32, goes to kxq0
+ arr.update(Coupon::pack(1, 50)); // value >= 32, goes to kxq1
// Initial kxq0 = 256 (all zeros = 1.0 each)
assert!(arr.estimator.kxq0() < 256.0, "kxq0 should have decreased");
diff --git a/datasketches/src/hll/aux_map.rs b/datasketches/src/hll/aux_map.rs
index c4e8ca9..6e43a03 100644
--- a/datasketches/src/hll/aux_map.rs
+++ b/datasketches/src/hll/aux_map.rs
@@ -20,28 +20,22 @@
//! 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;
-use crate::hll::get_slot;
-use crate::hll::get_value;
-use crate::hll::pack_coupon;
-
-const ENTRY_EMPTY: u32 = 0;
/// 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.
///
-/// # Entry Encoding
-///
-/// Each entry is an u32 packed as: [value (upper 6 bits) | slot_no (lower 26 bits)]
-/// Empty entries are represented as 0.
+/// Each entry is a [`Coupon`] packed as: [value (upper 6 bits) | slot_no (lower 26 bits)].
+/// Empty entries are represented as [`Coupon::EMPTY`].
#[derive(Debug, Clone)]
pub struct AuxMap {
lg_size: u8,
lg_config_k: u8,
- entries: Box<[u32]>,
+ entries: Box<[Coupon]>,
count: u32,
}
@@ -54,16 +48,16 @@ impl PartialEq for AuxMap {
}
// Collect and sort non-empty entries from both maps
- let mut entries1: Vec<u32> = self
+ let mut entries1: Vec<Coupon> = self
.entries
.iter()
- .filter(|&&e| e != ENTRY_EMPTY)
+ .filter(|&&e| !e.is_empty())
.copied()
.collect();
- let mut entries2: Vec<u32> = other
+ let mut entries2: Vec<Coupon> = other
.entries
.iter()
- .filter(|&&e| e != ENTRY_EMPTY)
+ .filter(|&&e| !e.is_empty())
.copied()
.collect();
@@ -95,7 +89,7 @@ impl AuxMap {
Self {
lg_size,
lg_config_k,
- entries: vec![ENTRY_EMPTY; 1 << lg_size].into_boxed_slice(),
+ entries: vec![Coupon::EMPTY; 1 << lg_size].into_boxed_slice(),
count: 0,
}
}
@@ -110,7 +104,7 @@ impl AuxMap {
unreachable!("slot {} already exists in aux map", slot);
}
FindResult::Empty(idx) => {
- self.entries[idx] = pack_coupon(slot, value);
+ self.entries[idx] = Coupon::pack(slot, value);
self.count += 1;
self.check_grow();
}
@@ -122,7 +116,7 @@ impl AuxMap {
/// Returns `None` if the slot is not found
pub fn get(&self, slot: u32) -> Option<u8> {
match self.find(slot) {
- FindResult::Found(idx) => Some(get_value(self.entries[idx])),
+ FindResult::Found(idx) => Some(self.entries[idx].value()),
FindResult::Empty(_) => None,
}
}
@@ -131,7 +125,7 @@ impl AuxMap {
pub fn replace(&mut self, slot: u32, value: u8) {
match self.find(slot) {
FindResult::Found(idx) => {
- self.entries[idx] = pack_coupon(slot, value);
+ self.entries[idx] = Coupon::pack(slot, value);
}
FindResult::Empty(_) => {
// Invariant: Array4 always check existence before replacing
@@ -154,11 +148,11 @@ impl AuxMap {
loop {
let entry = self.entries[probe as usize];
- if entry == ENTRY_EMPTY {
+ if entry.is_empty() {
return FindResult::Empty(probe as usize);
}
- let entry_slot = get_slot(entry) & config_k_mask;
+ let entry_slot = entry.slot() & config_k_mask;
if entry_slot == slot {
return FindResult::Found(probe as usize);
}
@@ -189,19 +183,19 @@ impl AuxMap {
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![ENTRY_EMPTY; new_size].into_boxed_slice();
+ 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 != ENTRY_EMPTY {
- let slot = get_slot(entry);
+ if !entry.is_empty() {
+ let slot = entry.slot();
// Find position in new table
let mut probe = slot & new_mask;
let start_position = probe;
loop {
- if new_entries[probe as usize] == ENTRY_EMPTY {
+ if new_entries[probe as usize].is_empty() {
new_entries[probe as usize] = entry;
break;
}
@@ -225,8 +219,8 @@ impl AuxMap {
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| {
- if entry != ENTRY_EMPTY {
- Some((get_slot(entry) & config_k_mask, get_value(entry)))
+ if !entry.is_empty() {
+ Some((entry.slot() & config_k_mask, entry.value()))
} else {
None
}
@@ -236,7 +230,7 @@ impl AuxMap {
/// Iterator over AuxMap entries
pub struct AuxMapIter {
- entries: std::vec::IntoIter<u32>,
+ entries: std::vec::IntoIter<Coupon>,
config_k_mask: u32,
}
@@ -246,9 +240,9 @@ impl Iterator for AuxMapIter {
fn next(&mut self) -> Option<Self::Item> {
loop {
match self.entries.next() {
- Some(entry) if entry != ENTRY_EMPTY => {
- let slot = get_slot(entry) & self.config_k_mask;
- let value = get_value(entry);
+ Some(entry) if !entry.is_empty() => {
+ let slot = entry.slot() & self.config_k_mask;
+ let value = entry.value();
return Some((slot, value));
}
Some(_) => continue, // Skip empty entries
diff --git a/datasketches/src/hll/container.rs b/datasketches/src/hll/container.rs
index 0a99cd1..8192b04 100644
--- a/datasketches/src/hll/container.rs
+++ b/datasketches/src/hll/container.rs
@@ -22,20 +22,18 @@
use crate::common::NumStdDev;
use crate::hll::COUPON_RSE;
+use crate::hll::Coupon;
use crate::hll::coupon_mapping::X_ARR;
use crate::hll::coupon_mapping::Y_ARR;
use crate::hll::cubic_interpolation::using_x_and_y_tables;
-/// Sentinel value indicating an empty coupon slot
-pub const COUPON_EMPTY: u32 = 0;
-
/// 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 (0 = empty)
- pub coupons: Box<[u32]>,
+ /// Array of coupon values (Coupon::EMPTY = empty)
+ pub coupons: Box<[Coupon]>,
/// Number of non-empty coupons
pub len: usize,
}
@@ -48,16 +46,16 @@ impl PartialEq for Container {
return false;
}
- let mut coupons1: Vec<u32> = self
+ let mut coupons1: Vec<Coupon> = self
.coupons
.iter()
- .filter(|&&c| c != COUPON_EMPTY)
+ .filter(|&&c| !c.is_empty())
.copied()
.collect();
- let mut coupons2: Vec<u32> = other
+ let mut coupons2: Vec<Coupon> = other
.coupons
.iter()
- .filter(|&&c| c != COUPON_EMPTY)
+ .filter(|&&c| !c.is_empty())
.copied()
.collect();
@@ -72,13 +70,13 @@ impl Container {
pub fn new(lg_size: usize) -> Self {
Self {
lg_size,
- coupons: vec![COUPON_EMPTY; 1 << lg_size].into_boxed_slice(),
+ coupons: vec![Coupon::EMPTY; 1 << lg_size].into_boxed_slice(),
len: 0,
}
}
/// Create container from existing coupons
- pub fn from_coupons(lg_size: usize, coupons: Box<[u32]>, len: usize) -> Self {
+ pub fn from_coupons(lg_size: usize, coupons: Box<[Coupon]>, len: usize) -> Self {
Self {
lg_size,
coupons,
@@ -134,7 +132,7 @@ impl Container {
}
/// Iterate over all non-empty coupons
- pub fn iter(&self) -> impl Iterator<Item = u32> + '_ {
- self.coupons.iter().filter(|&&c| c != COUPON_EMPTY).copied()
+ pub fn iter(&self) -> impl Iterator<Item = Coupon> + '_ {
+ self.coupons.iter().filter(|&&c| !c.is_empty()).copied()
}
}
diff --git a/datasketches/src/hll/hash_set.rs b/datasketches/src/hll/hash_set.rs
index c04f89b..b1d2bfb 100644
--- a/datasketches/src/hll/hash_set.rs
+++ b/datasketches/src/hll/hash_set.rs
@@ -25,9 +25,9 @@ use crate::codec::SketchSlice;
use crate::codec::assert::insufficient_data;
use crate::codec::family::Family;
use crate::error::Error;
+use crate::hll::Coupon;
use crate::hll::HllType;
use crate::hll::KEY_MASK_26;
-use crate::hll::container::COUPON_EMPTY;
use crate::hll::container::Container;
use crate::hll::serialization::COMPACT_FLAG_MASK;
use crate::hll::serialization::CUR_MODE_SET;
@@ -57,28 +57,28 @@ impl HashSet {
}
/// Insert coupon into hash set, ignoring duplicates
- pub fn update(&mut self, coupon: u32) {
+ 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 & mask;
+ let mut probe = coupon.raw() & mask;
let starting_position = probe;
loop {
- let value = &mut self.container.coupons[probe as usize];
- if value == &COUPON_EMPTY {
+ let slot = &mut self.container.coupons[probe as usize];
+ if slot.is_empty() {
// Found empty slot, insert new coupon
- *value = coupon;
+ *slot = coupon;
self.container.len += 1;
break;
- } else if value == &coupon {
+ } 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
- let stride = ((coupon & KEY_MASK_26) >> self.container.lg_size()) | 1;
+ 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
@@ -114,7 +114,7 @@ impl HashSet {
"expected {coupon_count} coupons, failed at index {i}"
))
})?;
- hash_set.update(coupon);
+ hash_set.update(Coupon(coupon));
}
Ok(hash_set)
} else {
@@ -122,13 +122,14 @@ impl HashSet {
let array_size = 1 << lg_arr;
// Read entire hash table including empty slots
- let mut coupons = vec![0u32; array_size];
+ let mut coupons = vec![Coupon::EMPTY; array_size];
for (i, coupon) in coupons.iter_mut().enumerate() {
- *coupon = cursor.read_u32_le().map_err(|_| {
+ let raw = cursor.read_u32_le().map_err(|_| {
Error::insufficient_data(format!(
"expected {array_size} coupons, failed at index {i}"
))
})?;
+ *coupon = Coupon(raw);
}
Ok(Self {
@@ -179,22 +180,22 @@ impl HashSet {
// Write coupons
if compact {
// Compact mode: collect non-empty coupons and sort for deterministic output
- let mut coupons_vec: Vec<u32> = self
+ let mut coupons_vec: Vec<Coupon> = self
.container
.coupons
.iter()
- .filter(|&&c| c != 0)
+ .filter(|&&c| !c.is_empty())
.copied()
.collect();
coupons_vec.sort_unstable();
for coupon in coupons_vec.iter().copied() {
- bytes.write_u32_le(coupon);
+ 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);
+ bytes.write_u32_le(coupon.raw());
}
}
diff --git a/datasketches/src/hll/list.rs b/datasketches/src/hll/list.rs
index 5895882..1f0b3e7 100644
--- a/datasketches/src/hll/list.rs
+++ b/datasketches/src/hll/list.rs
@@ -24,8 +24,8 @@ use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::family::Family;
use crate::error::Error;
+use crate::hll::Coupon;
use crate::hll::HllType;
-use crate::hll::container::COUPON_EMPTY;
use crate::hll::container::Container;
use crate::hll::serialization::COMPACT_FLAG_MASK;
use crate::hll::serialization::CUR_MODE_LIST;
@@ -56,14 +56,14 @@ impl List {
}
/// Insert coupon into list, ignoring duplicates
- pub fn update(&mut self, coupon: u32) {
+ pub fn update(&mut self, coupon: Coupon) {
for value in self.container.coupons.iter_mut() {
- if value == &COUPON_EMPTY {
+ if value.is_empty() {
// Found empty slot, insert new coupon
*value = coupon;
self.container.len += 1;
break;
- } else if value == &coupon {
+ } else if *value == coupon {
// Duplicate found, nothing to do
break;
}
@@ -86,14 +86,15 @@ impl List {
let array_size = if compact { coupon_count } else { 1 << lg_arr };
// Read coupons
- let mut coupons = vec![0u32; array_size];
+ let mut coupons = vec![Coupon::EMPTY; array_size];
if !empty && coupon_count > 0 {
for (i, coupon) in coupons.iter_mut().enumerate() {
- *coupon = cursor.read_u32_le().map_err(|_| {
+ let raw = cursor.read_u32_le().map_err(|_| {
Error::insufficient_data(format!(
"expect {coupon_count} coupons, failed at index {i}"
))
})?;
+ *coupon = Coupon(raw);
}
}
@@ -142,10 +143,10 @@ impl List {
if !empty {
let mut write_idx = 0;
for coupon in self.container.coupons.iter().copied() {
- if compact && coupon == 0 {
+ if compact && coupon.is_empty() {
continue; // Skip empty coupons in compact mode
}
- bytes.write_u32_le(coupon);
+ bytes.write_u32_le(coupon.raw());
write_idx += 1;
if write_idx >= array_size {
break;
diff --git a/datasketches/src/hll/mod.rs b/datasketches/src/hll/mod.rs
index b3e1b36..1a3c2e3 100644
--- a/datasketches/src/hll/mod.rs
+++ b/datasketches/src/hll/mod.rs
@@ -157,52 +157,102 @@ 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;
-/// Extract slot number (low 26 bits) from coupon
-#[inline]
-fn get_slot(coupon: u32) -> u32 {
- coupon & KEY_MASK_26
-}
+/// A coupon encodes a (slot, value) pair derived from hashing an input.
+///
+/// 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.
+///
+/// # Examples
+///
+/// ```
+/// # use datasketches::hll::{HllSketch, HllType, Coupon};
+/// let c = Coupon::from_hash("hello");
+///
+/// let mut sketch1 = HllSketch::new(10, HllType::Hll8);
+/// let mut sketch2 = HllSketch::new(12, HllType::Hll8);
+/// sketch1.update_with_coupon(c);
+/// sketch2.update_with_coupon(c);
+///
+/// assert!(sketch1.estimate() >= 1.0);
+/// assert!(sketch2.estimate() >= 1.0);
+/// ```
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct Coupon(u32);
-/// Extract value (upper 6 bits) from coupon
-#[inline]
-fn get_value(coupon: u32) -> u8 {
- (coupon >> KEY_BITS_26) as u8
-}
+impl Coupon {
+ /// Sentinel value indicating an empty coupon slot.
+ const EMPTY: Self = Coupon(0);
-/// Pack slot number and value into a coupon
-///
-/// Format: [value (6 bits) << 26] | [slot (26 bits)]
-#[inline]
-fn pack_coupon(slot: u32, value: u8) -> u32 {
- ((value as u32) << KEY_BITS_26) | (slot & KEY_MASK_26)
-}
+ /// 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
+ }
-/// Generate a coupon from a hashable value.
-fn coupon<H: Hash>(v: H) -> u32 {
- let mut hasher = MurmurHash3X64128::default();
- v.hash(&mut hasher);
- let (lo, hi) = hasher.finish128();
+ /// Compute the HLL coupon for a hashable value.
+ ///
+ /// Hashes `v` 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.
+ #[inline(always)]
+ pub fn from_hash(v: impl Hash) -> Self {
+ let mut hasher = MurmurHash3X64128::default();
+ v.hash(&mut hasher);
+ let (lo, hi) = hasher.finish128();
+
+ let addr26 = lo as u32 & KEY_MASK_26;
+ let lz = hi.leading_zeros();
+ let capped = lz.min(62);
+ let value = capped + 1;
- let addr26 = lo as u32 & KEY_MASK_26;
- let lz = hi.leading_zeros();
- let capped = lz.min(62);
- let value = capped + 1;
+ Coupon((value << KEY_BITS_26) | addr26)
+ }
- (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
+ }
}
#[cfg(test)]
mod tests {
- use crate::hll::get_slot;
- use crate::hll::get_value;
- use crate::hll::pack_coupon;
+ use crate::hll::Coupon;
#[test]
fn test_pack_unpack_coupon() {
let slot = 12345u32;
let value = 42u8;
- let coupon = pack_coupon(slot, value);
- assert_eq!(get_slot(coupon), slot);
- assert_eq!(get_value(coupon), value);
+ let coupon = Coupon::pack(slot, value);
+ assert_eq!(coupon.slot(), slot);
+ assert_eq!(coupon.value(), value);
}
}
diff --git a/datasketches/src/hll/sketch.rs b/datasketches/src/hll/sketch.rs
index 58c5372..5214d46 100644
--- a/datasketches/src/hll/sketch.rs
+++ b/datasketches/src/hll/sketch.rs
@@ -28,6 +28,7 @@ use crate::codec::assert::insufficient_data;
use crate::codec::family::Family;
use crate::common::NumStdDev;
use crate::error::Error;
+use crate::hll::Coupon;
use crate::hll::HllType;
use crate::hll::RESIZE_DENOMINATOR;
use crate::hll::RESIZE_NUMERATOR;
@@ -35,7 +36,6 @@ use crate::hll::array4::Array4;
use crate::hll::array6::Array6;
use crate::hll::array8::Array8;
use crate::hll::container::Container;
-use crate::hll::coupon;
use crate::hll::hash_set::HashSet;
use crate::hll::list::List;
use crate::hll::mode::Mode;
@@ -156,10 +156,15 @@ impl HllSketch {
self.lg_config_k
}
- /// Update the sketch with a value
+ /// Update the sketch with a value.
///
- /// This accepts any type that implements `Hash`. The value is hashed
- /// and converted to a coupon, which is then inserted into the sketch.
+ /// Accepts any type that implements [`Hash`]. The value is hashed and converted to
+ /// an internal coupon, which is then inserted into the sketch.
+ ///
+ /// If you need to insert the same logical value into multiple sketches, consider
+ /// pre-computing the coupon with [`Coupon::from_hash`] and calling
+ /// [`update_with_coupon`](Self::update_with_coupon) on each sketch to avoid
+ /// redundant hashing.
///
/// # Examples
///
@@ -171,14 +176,29 @@ impl HllSketch {
/// assert!(sketch.estimate() >= 1.0);
/// ```
pub fn update<T: Hash>(&mut self, value: T) {
- let coupon = coupon(value);
- self.update_with_coupon(coupon);
+ self.update_with_coupon(Coupon::from_hash(value));
}
- /// Update the sketch with a raw coupon value
+ /// Update 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.
+ ///
+ /// Handles all internal bookkeeping, including automatic mode transitions
+ /// (List → Set → HLL array) and estimator state updates.
+ ///
+ /// # Examples
///
- /// Maintains all sketch invariants including mode transitions and estimator updates.
- pub fn update_with_coupon(&mut self, coupon: u32) {
+ /// ```
+ /// # use datasketches::hll::{HllSketch, HllType, Coupon};
+ /// let c = Coupon::from_hash("apple");
+ /// let mut sketch = HllSketch::new(10, HllType::Hll8);
+ /// sketch.update_with_coupon(c);
+ /// assert!(sketch.estimate() >= 1.0);
+ /// ```
+ pub fn update_with_coupon(&mut self, coupon: Coupon) {
match &mut self.mode {
Mode::List { list, hll_type } => {
list.update(coupon);
diff --git a/datasketches/src/hll/union.rs b/datasketches/src/hll/union.rs
index 5f3929d..9d0fd06 100644
--- a/datasketches/src/hll/union.rs
+++ b/datasketches/src/hll/union.rs
@@ -31,13 +31,13 @@
use std::hash::Hash;
use crate::common::NumStdDev;
+use crate::hll::Coupon;
use crate::hll::HllSketch;
use crate::hll::HllType;
use crate::hll::array4::Array4;
use crate::hll::array6::Array6;
use crate::hll::array8::Array8;
use crate::hll::mode::Mode;
-use crate::hll::pack_coupon;
/// An HLL Union for combining multiple HLL sketches.
///
@@ -525,7 +525,7 @@ fn convert_array8_to_type(src: &Array8, lg_config_k: u8, target_type: HllType) -
let val = src.values()[slot];
if val > 0 {
let clamped_val = val.min(63);
- let coupon = pack_coupon(slot as u32, clamped_val);
+ let coupon = Coupon::pack(slot as u32, clamped_val);
array6.update(coupon);
}
}
@@ -543,7 +543,7 @@ fn convert_array8_to_type(src: &Array8, lg_config_k: u8, target_type: HllType) -
for slot in 0..src.num_registers() {
let val = src.values()[slot];
if val > 0 {
- let coupon = pack_coupon(slot as u32, val);
+ let coupon = Coupon::pack(slot as u32, val);
array4.update(coupon);
}
}
@@ -564,7 +564,7 @@ fn copy_array46_via_coupons(dst: &mut Array8, num_registers: usize, get_value: i
for slot in 0..num_registers {
let val = get_value(slot as u32);
if val > 0 {
- let coupon = pack_coupon(slot as u32, val);
+ let coupon = Coupon::pack(slot as u32, val);
dst.update(coupon);
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org