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 ba90d43 perf(theta,tuple): gather hashes and bucket-sort entries on
compaction (#344)
ba90d43 is described below
commit ba90d4365646d55cd566c95f865f1aa39ab86b07
Author: David Cromberge <[email protected]>
AuthorDate: Wed Nov 11 17:59:10 2026 +0200
perf(theta,tuple): gather hashes and bucket-sort entries on compaction
(#344)
Co-authored-by: Claude Opus 5.5 <[email protected]>
Co-authored-by: tison <[email protected]>
---
CHANGELOG.md | 1 +
datasketches/src/thetafamily/common/a_not_b.rs | 24 +---
datasketches/src/thetafamily/common/hash_table.rs | 72 ++++++++---
.../src/thetafamily/common/intersection.rs | 14 +++
.../src/thetafamily/common/jaccard_similarity.rs | 6 +
datasketches/src/thetafamily/common/mod.rs | 16 ++-
.../src/thetafamily/common/sketch_state.rs | 136 +++++++++++++++++++++
datasketches/src/thetafamily/common/union.rs | 57 ++++++---
datasketches/src/thetafamily/theta/hash_table.rs | 6 +
datasketches/src/thetafamily/theta/intersection.rs | 8 +-
datasketches/src/thetafamily/theta/sketch.rs | 26 +++-
datasketches/src/thetafamily/theta/union.rs | 8 +-
datasketches/src/thetafamily/tuple/hash_table.rs | 7 ++
datasketches/src/thetafamily/tuple/sketch.rs | 12 ++
tests-integration/tests/theta_test/a_not_b.rs | 14 ++-
tests-integration/tests/theta_test/intersection.rs | 18 +--
tests-integration/tests/theta_test/sketch.rs | 92 ++++++++++----
tests-integration/tests/theta_test/union.rs | 50 ++++++++
tests-integration/tests/tuple_test/a_not_b.rs | 27 ++--
tests-integration/tests/tuple_test/intersection.rs | 19 ++-
tests-integration/tests/tuple_test/sketch.rs | 25 +++-
tests-integration/tests/tuple_test/union.rs | 19 ++-
22 files changed, 529 insertions(+), 128 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 8a3fc88..53d8fb6 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -23,6 +23,7 @@ All significant changes to this project will be documented in
this file.
* Compressed `CompactThetaSketch` serialization and deserialization are faster.
* Tuple sketch serialization and deserialization are faster.
* `ThetaANotB` and `TupleANotB` are faster when either input is unordered.
+* Compacting Theta and Tuple sketches and producing ordered union,
intersection, and A-not-B results are faster.
## v0.6.0 (2026-10-29)
diff --git a/datasketches/src/thetafamily/common/a_not_b.rs
b/datasketches/src/thetafamily/common/a_not_b.rs
index 7c01b40..cab8e58 100644
--- a/datasketches/src/thetafamily/common/a_not_b.rs
+++ b/datasketches/src/thetafamily/common/a_not_b.rs
@@ -19,6 +19,7 @@ use std::collections::HashSet;
use std::hash::BuildHasher;
use std::hash::Hasher;
+use crate::common::random::random_u64;
use crate::error::Error;
use crate::error::ErrorKind;
use crate::hash::check_seed_hash;
@@ -129,17 +130,8 @@ where
return Ok(CompactSketchState::empty(seed_hash));
}
- let mut entries = entries;
- if ordered && !a_ordered && entries.len() > 1 {
- entries.sort_unstable_by_key(SketchEntry::hash);
- }
- let out_ordered = ordered || a_ordered || (entries.len() == 1 && theta ==
MAX_THETA);
-
- Ok(CompactSketchState::non_empty(
- entries,
- theta,
- seed_hash,
- out_ordered,
+ Ok(CompactSketchState::compact(
+ entries, theta, seed_hash, a_ordered, ordered,
))
}
@@ -182,12 +174,8 @@ where
} => (seed_hash, theta, ordered),
};
- let mut entries: Vec<S::Entry> = sketch.entries().collect();
- if ordered && !input_ordered && entries.len() > 1 {
- entries.sort_unstable_by_key(SketchEntry::hash);
- }
- let out_ordered = ordered || input_ordered || (entries.len() == 1 && theta
== MAX_THETA);
- CompactSketchState::non_empty(entries, theta, seed_hash, out_ordered)
+ let entries = sketch.entries().collect();
+ CompactSketchState::compact(entries, theta, seed_hash, input_ordered,
ordered)
}
const FOLD_MULTIPLIER: u64 = 0x9E37_79B9_7F4A_7C15;
@@ -209,7 +197,7 @@ struct FoldHashState(u64);
impl FoldHashState {
#[inline]
fn new() -> Self {
- Self(crate::common::random::random_u64())
+ Self(random_u64())
}
}
diff --git a/datasketches/src/thetafamily/common/hash_table.rs
b/datasketches/src/thetafamily/common/hash_table.rs
index 35c5106..9403d64 100644
--- a/datasketches/src/thetafamily/common/hash_table.rs
+++ b/datasketches/src/thetafamily/common/hash_table.rs
@@ -16,6 +16,7 @@
// under the License.
use std::hash::Hash;
+use std::iter::FusedIterator;
use std::slice;
use crate::common::ResizeFactor;
@@ -30,20 +31,39 @@ use crate::thetacommon::constants::MIN_LG_K;
use crate::thetacommon::constants::STRIDE_MASK;
use crate::thetacommon::sketch_state::CompactSketchState;
-pub struct SketchHashTableIter<'a, E>(slice::Iter<'a, Option<E>>);
+pub struct SketchHashTableIter<'a, E> {
+ iter: slice::Iter<'a, Option<E>>,
+ remaining: usize,
+}
impl<'a, E> Iterator for SketchHashTableIter<'a, E> {
type Item = &'a E;
+ #[inline]
fn next(&mut self) -> Option<Self::Item> {
- self.0.find_map(Option::as_ref)
+ if self.remaining == 0 {
+ return None;
+ }
+ let entry = self.iter.find_map(Option::as_ref)?;
+ self.remaining -= 1;
+ Some(entry)
}
+ #[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
- (0, self.0.size_hint().1)
+ (self.remaining, Some(self.remaining))
}
}
+impl<E> ExactSizeIterator for SketchHashTableIter<'_, E> {
+ #[inline]
+ fn len(&self) -> usize {
+ self.remaining
+ }
+}
+
+impl<E> FusedIterator for SketchHashTableIter<'_, E> {}
+
/// Generic hash-table mechanics shared by Theta and Tuple sketches.
///
/// The entry type supplies the retained hash and any sketch-specific payload.
The table owns all
@@ -287,7 +307,10 @@ where
/// Get iterator over retained entries.
pub fn iter_entries(&self) -> SketchHashTableIter<'_, E> {
- SketchHashTableIter(self.entries.iter())
+ SketchHashTableIter {
+ iter: self.entries.iter(),
+ remaining: self.num_retained,
+ }
}
/// Creates compact state for a sketch known by its owner to be non-empty.
@@ -295,19 +318,42 @@ where
where
E: Clone,
{
- let mut retained_entries: Vec<E> =
self.iter_entries().cloned().collect();
- let ordered = ordered || (retained_entries.len() == 1 &&
self.retention_theta == MAX_THETA);
- if ordered && retained_entries.len() > 1 {
- retained_entries.sort_unstable_by_key(SketchEntry::hash);
- }
- CompactSketchState::non_empty(
+ let retained_entries = self.iter_entries().cloned().collect();
+ CompactSketchState::compact(
retained_entries,
self.retention_theta,
self.seed_hash,
+ false,
ordered,
)
}
+ /// Creates compact hash state for a Theta sketch or operator known to be
non-empty.
+ #[cfg(feature = "theta")]
+ pub fn to_non_empty_compact_hashes(&self, ordered: bool) ->
CompactSketchState<u64> {
+ let hashes = self.retained_hashes();
+ CompactSketchState::compact(hashes, self.retention_theta,
self.seed_hash, false, ordered)
+ }
+
+ /// Returns retained hashes in table order.
+ #[cfg(feature = "theta")]
+ pub fn retained_hashes(&self) -> Vec<u64> {
+ if self.num_retained * 16 <= self.entries.len() {
+ return self.iter_entries().map(SketchEntry::hash).collect();
+ }
+
+ let mut hashes = vec![0u64; self.num_retained + 1];
+ let mut len = 0;
+ for slot in &self.entries {
+ let hash = slot.as_ref().map_or(0, SketchEntry::hash);
+ hashes[len] = hash;
+ len += usize::from(hash != 0);
+ }
+ debug_assert_eq!(len, self.num_retained);
+ hashes.truncate(len);
+ hashes
+ }
+
/// Get log2 of nominal size.
pub fn lg_nom_size(&self) -> u8 {
self.lg_nom_size
@@ -406,10 +452,8 @@ where
let k = 1usize << self.lg_nom_size;
// Select the k-th smallest entry as new theta and keep the lesser
entries.
- let mut retained: Vec<E> = std::mem::take(&mut self.entries)
- .into_iter()
- .flatten()
- .collect();
+ let mut retained = Vec::with_capacity(self.num_retained);
+ retained.extend(std::mem::take(&mut
self.entries).into_iter().flatten());
let kth_hash = {
let (_lesser, kth, _greater) =
retained.select_nth_unstable_by_key(k, |e| e.hash());
kth.hash()
diff --git a/datasketches/src/thetafamily/common/intersection.rs
b/datasketches/src/thetafamily/common/intersection.rs
index 535beba..6b03629 100644
--- a/datasketches/src/thetafamily/common/intersection.rs
+++ b/datasketches/src/thetafamily/common/intersection.rs
@@ -254,4 +254,18 @@ where
}
}
}
+
+ /// Returns the current intersection as canonical compact hash state.
+ #[cfg(feature = "theta")]
+ pub fn to_compact_hash_state(&self, ordered: bool) ->
Option<CompactSketchState<u64>> {
+ match self.result_state {
+ IntersectionResultState::Uninitialized => None,
+ IntersectionResultState::Empty => {
+ Some(CompactSketchState::empty(self.table.seed_hash()))
+ }
+ IntersectionResultState::NonEmpty => {
+ Some(self.table.to_non_empty_compact_hashes(ordered))
+ }
+ }
+ }
}
diff --git a/datasketches/src/thetafamily/common/jaccard_similarity.rs
b/datasketches/src/thetafamily/common/jaccard_similarity.rs
index 6c37bec..2d16331 100644
--- a/datasketches/src/thetafamily/common/jaccard_similarity.rs
+++ b/datasketches/src/thetafamily/common/jaccard_similarity.rs
@@ -32,6 +32,7 @@ use crate::thetacommon::intersection::IntersectionMergePolicy;
use crate::thetacommon::intersection::IntersectionState;
use crate::thetacommon::sketch_state::CompactSketchState;
use crate::thetacommon::sketch_state::ThetaFamilySketchMetadata;
+use crate::thetacommon::sketch_state::sort_copy_by_hash;
use crate::thetacommon::union::UnionMergePolicy;
use crate::thetacommon::union::UnionState;
@@ -113,9 +114,14 @@ struct KeyEntry {
}
impl SketchEntry for KeyEntry {
+ #[inline]
fn hash(&self) -> u64 {
self.hash
}
+
+ fn sort_by_hash(entries: &mut Vec<Self>) {
+ sort_copy_by_hash(entries);
+ }
}
#[derive(Clone, Copy, Debug)]
diff --git a/datasketches/src/thetafamily/common/mod.rs
b/datasketches/src/thetafamily/common/mod.rs
index 12d5d91..acf8ceb 100644
--- a/datasketches/src/thetafamily/common/mod.rs
+++ b/datasketches/src/thetafamily/common/mod.rs
@@ -28,21 +28,33 @@ pub(super) mod union;
pub use self::jaccard_similarity::JaccardSimilarity;
-/// Minimal entry behavior required by the shared hash table and set
operations.
-pub(super) trait SketchEntry {
+/// Minimal entry behavior required by the shared hash table, compaction, and
set operations.
+pub(super) trait SketchEntry: Sized {
fn hash(&self) -> u64;
+
+ fn sort_by_hash(entries: &mut Vec<Self>);
}
impl SketchEntry for u64 {
+ #[inline]
fn hash(&self) -> u64 {
*self
}
+
+ fn sort_by_hash(entries: &mut Vec<Self>) {
+ sketch_state::sort_copy_by_hash(entries);
+ }
}
impl<E: SketchEntry> SketchEntry for &E {
+ #[inline]
fn hash(&self) -> u64 {
E::hash(self)
}
+
+ fn sort_by_hash(entries: &mut Vec<Self>) {
+ sketch_state::sort_copy_by_hash(entries);
+ }
}
pub(super) trait KeySketch: Copy {
diff --git a/datasketches/src/thetafamily/common/sketch_state.rs
b/datasketches/src/thetafamily/common/sketch_state.rs
index 44928c0..c04c724 100644
--- a/datasketches/src/thetafamily/common/sketch_state.rs
+++ b/datasketches/src/thetafamily/common/sketch_state.rs
@@ -15,6 +15,7 @@
// specific language governing permissions and limitations
// under the License.
+use crate::thetacommon::SketchEntry;
use crate::thetacommon::constants::MAX_THETA;
/// Observable metadata consumed by shared Theta-family set operations.
@@ -67,6 +68,34 @@ impl<E> CompactSketchState<E> {
}
}
+ /// Canonicalizes and optionally sorts retained entries for a non-empty
compact sketch.
+ ///
+ /// Exact singletons (`len == 1` at `MAX_THETA`) are always marked ordered
to match their
+ /// single-word canonical encoding. When ordering is requested and
`retained_entries` are not
+ /// already ordered, entries are sorted ascending by hash.
+ pub fn compact(
+ mut retained_entries: Vec<E>,
+ theta: u64,
+ seed_hash: u16,
+ already_ordered: bool,
+ ordered: bool,
+ ) -> Self
+ where
+ E: SketchEntry,
+ {
+ let ordered =
+ ordered || already_ordered || (retained_entries.len() == 1 &&
theta == MAX_THETA);
+ if ordered && !already_ordered && retained_entries.len() > 1 {
+ E::sort_by_hash(&mut retained_entries);
+ }
+ Self::NonEmpty {
+ retained_entries,
+ theta,
+ seed_hash,
+ ordered,
+ }
+ }
+
pub fn theta(&self) -> u64 {
match self {
Self::Empty { .. } => MAX_THETA,
@@ -144,3 +173,110 @@ impl<E> CompactSketchState<E> {
}
}
}
+
+const MIN_BUCKET_SORT_LEN: usize = 256;
+const MAX_BUCKET_LEN: u32 = 32;
+
+/// Sorts uniform 64-bit MurmurHash3 entries in ascending hash order using a
single top-bit bucket
+/// pass followed by a linear insertion pass, falling back to
`sort_unstable_by_key` for small or
+/// skewed inputs.
+fn with_bucket_starts<E: SketchEntry>(
+ entries: &mut Vec<E>,
+ scatter: impl FnOnce(&mut Vec<E>, &mut [u32], u32, usize),
+) {
+ let len = entries.len();
+ if len < MIN_BUCKET_SORT_LEN {
+ if len > 1 {
+ entries.sort_unstable_by_key(SketchEntry::hash);
+ }
+ return;
+ }
+
+ // The highest set bit of the bitwise OR equals the highest set bit of the
maximum hash,
+ // avoiding a branch-dependent max reduction before computing the top-bit
bucket shift.
+ let bits = entries.iter().fold(0u64, |acc, entry| acc | entry.hash());
+ let lg_buckets = len.ilog2();
+ let num_buckets = 1usize << lg_buckets;
+ let mask = num_buckets - 1;
+ let shift = (u64::BITS - bits.leading_zeros()).saturating_sub(lg_buckets);
+
+ let mut heap_starts;
+ let mut stack_10;
+ let mut stack_12;
+ let starts: &mut [u32] = if lg_buckets <= 10 {
+ stack_10 = [0u32; (1 << 10) + 1];
+ &mut stack_10[..=num_buckets]
+ } else if lg_buckets <= 12 {
+ stack_12 = [0u32; (1 << 12) + 1];
+ &mut stack_12[..=num_buckets]
+ } else {
+ heap_starts = vec![0u32; num_buckets + 1];
+ &mut heap_starts
+ };
+
+ for entry in entries.iter() {
+ starts[((entry.hash() >> shift) as usize & mask) + 1] += 1;
+ }
+ let mut largest = 0u32;
+ for i in 1..starts.len() {
+ largest = largest.max(starts[i]);
+ starts[i] += starts[i - 1];
+ }
+ if largest > MAX_BUCKET_LEN {
+ entries.sort_unstable_by_key(SketchEntry::hash);
+ return;
+ }
+
+ scatter(entries, starts, shift, mask);
+}
+
+pub fn sort_copy_by_hash<E: SketchEntry + Copy>(entries: &mut Vec<E>) {
+ with_bucket_starts(entries, |entries, starts, shift, mask| {
+ let len = entries.len();
+ let mut sorted = vec![entries[0]; len];
+ for &entry in entries.iter() {
+ let next = &mut starts[(entry.hash() >> shift) as usize & mask];
+ sorted[*next as usize] = entry;
+ *next += 1;
+ }
+ for i in 1..len {
+ let entry = sorted[i];
+ let hash = entry.hash();
+ let mut j = i;
+ while j > 0 && sorted[j - 1].hash() > hash {
+ sorted[j] = sorted[j - 1];
+ j -= 1;
+ }
+ sorted[j] = entry;
+ }
+ *entries = sorted;
+ });
+}
+
+#[cfg(feature = "tuple")]
+pub fn sort_niche_by_hash<E: SketchEntry>(entries: &mut Vec<E>) {
+ const {
+ assert!(
+ size_of::<Option<E>>() == size_of::<E>() &&
align_of::<Option<E>>() == align_of::<E>(),
+ "niche bucket sort requires Option<E> to match E in size and
alignment",
+ );
+ }
+ with_bucket_starts(entries, |entries, starts, shift, mask| {
+ let len = entries.len();
+ let mut sorted: Vec<Option<E>> = std::iter::repeat_with(||
None).take(len).collect();
+ for entry in std::mem::take(entries) {
+ let next = &mut starts[(entry.hash() >> shift) as usize & mask];
+ sorted[*next as usize] = Some(entry);
+ *next += 1;
+ }
+ let mut sorted: Vec<E> =
sorted.into_iter().map(Option::unwrap).collect();
+ for i in 1..len {
+ let mut j = i;
+ while j > 0 && sorted[j - 1].hash() > sorted[j].hash() {
+ sorted.swap(j - 1, j);
+ j -= 1;
+ }
+ }
+ *entries = sorted;
+ });
+}
diff --git a/datasketches/src/thetafamily/common/union.rs
b/datasketches/src/thetafamily/common/union.rs
index b9e5d1d..5d53862 100644
--- a/datasketches/src/thetafamily/common/union.rs
+++ b/datasketches/src/thetafamily/common/union.rs
@@ -21,7 +21,6 @@ use crate::error::ErrorKind;
use crate::hash::check_seed_hash;
use crate::thetacommon::EntrySketch;
use crate::thetacommon::SketchEntry;
-use crate::thetacommon::constants::MAX_THETA;
use crate::thetacommon::hash_table::SketchHashTable;
use crate::thetacommon::sketch_state::CompactSketchState;
use crate::thetacommon::sketch_state::ThetaFamilySketchMetadata;
@@ -116,25 +115,52 @@ where
let Some(theta) = self.result_theta else {
return CompactSketchState::empty(self.table.seed_hash());
};
- let entries = self.retained_entries(theta).cloned().collect();
+ let entries = self.collect_retained_entries(theta, Clone::clone);
self.finish_compaction(entries, theta, ordered)
}
+ /// Returns the union as canonical compact hash state.
+ #[cfg(feature = "theta")]
+ pub fn to_compact_hash_state(&self, ordered: bool) ->
CompactSketchState<u64> {
+ let Some(theta) = self.result_theta else {
+ return CompactSketchState::empty(self.table.seed_hash());
+ };
+ let hashes = if theta >= self.table.retention_theta() {
+ self.table.retained_hashes()
+ } else {
+ self.table
+ .iter_entries()
+ .map(SketchEntry::hash)
+ .filter(|&hash| hash < theta)
+ .collect()
+ };
+ self.finish_compaction(hashes, theta, ordered)
+ }
+
/// Returns the union as canonical compact-sketch state that borrows the
retained entries.
#[cfg(feature = "tuple")]
pub fn to_borrowed_compact_sketch_state(&self, ordered: bool) ->
CompactSketchState<&E> {
let Some(theta) = self.result_theta else {
return CompactSketchState::empty(self.table.seed_hash());
};
- let entries = self.retained_entries(theta).collect();
+ let entries = self.collect_retained_entries(theta, |entry| entry);
self.finish_compaction(entries, theta, ordered)
}
- fn retained_entries(&self, theta: u64) -> impl Iterator<Item = &E> {
- let all_retained = theta >= self.table.retention_theta();
- self.table
- .iter_entries()
- .filter(move |entry| all_retained || entry.hash() < theta)
+ fn collect_retained_entries<'a, T>(
+ &'a self,
+ theta: u64,
+ map: impl FnMut(&'a E) -> T,
+ ) -> Vec<T> {
+ if theta >= self.table.retention_theta() {
+ self.table.iter_entries().map(map).collect()
+ } else {
+ self.table
+ .iter_entries()
+ .filter(|entry| entry.hash() < theta)
+ .map(map)
+ .collect()
+ }
}
fn finish_compaction<T: SketchEntry>(
@@ -147,17 +173,18 @@ where
let nominal_num = 1usize << self.table.lg_nom_size();
if retained_entries.len() > nominal_num {
let (_, kth, _) =
- retained_entries.select_nth_unstable_by_key(nominal_num,
|entry| entry.hash());
+ retained_entries.select_nth_unstable_by_key(nominal_num,
SketchEntry::hash);
theta = kth.hash();
retained_entries.truncate(nominal_num);
}
- let ordered = ordered || (retained_entries.len() == 1 && theta ==
MAX_THETA);
- if ordered {
- retained_entries.sort_unstable_by_key(SketchEntry::hash);
- }
-
- CompactSketchState::non_empty(retained_entries, theta,
self.table.seed_hash(), ordered)
+ CompactSketchState::compact(
+ retained_entries,
+ theta,
+ self.table.seed_hash(),
+ false,
+ ordered,
+ )
}
/// Reset the union to its initial state.
diff --git a/datasketches/src/thetafamily/theta/hash_table.rs
b/datasketches/src/thetafamily/theta/hash_table.rs
index 2ffb399..cc69cb1 100644
--- a/datasketches/src/thetafamily/theta/hash_table.rs
+++ b/datasketches/src/thetafamily/theta/hash_table.rs
@@ -20,6 +20,7 @@ use std::num::NonZeroU64;
use crate::thetacommon::SketchEntry;
use crate::thetacommon::hash_table::SketchHashTable;
+use crate::thetacommon::sketch_state::sort_copy_by_hash;
/// Specific hash table for theta sketch
///
@@ -32,6 +33,7 @@ pub type ThetaHashTable = SketchHashTable<ThetaEntry>;
/// A retained entry in a Theta sketch.
#[derive(Debug, Clone, Copy)]
+#[repr(transparent)]
pub struct ThetaEntry {
hash: NonZeroU64,
}
@@ -55,6 +57,10 @@ impl SketchEntry for ThetaEntry {
fn hash(&self) -> u64 {
self.hash.get()
}
+
+ fn sort_by_hash(entries: &mut Vec<Self>) {
+ sort_copy_by_hash(entries);
+ }
}
impl ThetaHashTable {
diff --git a/datasketches/src/thetafamily/theta/intersection.rs
b/datasketches/src/thetafamily/theta/intersection.rs
index 137891d..133c5a7 100644
--- a/datasketches/src/thetafamily/theta/intersection.rs
+++ b/datasketches/src/thetafamily/theta/intersection.rs
@@ -91,11 +91,7 @@ impl ThetaIntersection {
/// If `ordered` is `true`, retained hashes are sorted in ascending order.
pub fn to_sketch(&self, ordered: bool) -> Option<CompactThetaSketch> {
self.state
- .to_compact_sketch_state(ordered)
- .map(|compact_state| {
- CompactThetaSketch::from_compact_state(
- compact_state.map_retained_entries(|entry| entry.hash()),
- )
- })
+ .to_compact_hash_state(ordered)
+ .map(CompactThetaSketch::from_compact_state)
}
}
diff --git a/datasketches/src/thetafamily/theta/sketch.rs
b/datasketches/src/thetafamily/theta/sketch.rs
index 26918ac..40d9025 100644
--- a/datasketches/src/thetafamily/theta/sketch.rs
+++ b/datasketches/src/thetafamily/theta/sketch.rs
@@ -21,6 +21,7 @@
//! for cardinality estimation.
use std::hash::Hash;
+use std::iter::FusedIterator;
use std::slice;
use crate::codec::SketchBytes;
@@ -104,6 +105,17 @@ impl Iterator for ThetaSketchIter<'_> {
}
}
+impl ExactSizeIterator for ThetaSketchIter<'_> {
+ fn len(&self) -> usize {
+ match self {
+ Self::Mutable(iter) => iter.len(),
+ Self::Compact(iter) => iter.len(),
+ }
+ }
+}
+
+impl FusedIterator for ThetaSketchIter<'_> {}
+
impl<'a> ThetaSketchView<'a> {
/// Returns the 16-bit seed hash.
pub fn seed_hash(&self) -> u16 {
@@ -352,9 +364,8 @@ impl ThetaSketch {
debug_assert_eq!(self.num_retained(), 0);
CompactSketchState::empty(self.seed_hash())
} else {
- self.table.to_non_empty_compact_state(ordered)
- }
- .map_retained_entries(|entry| entry.hash());
+ self.table.to_non_empty_compact_hashes(ordered)
+ };
CompactThetaSketch::from_compact_state(compact_state)
}
@@ -1127,8 +1138,13 @@ mod tests {
fn assert_theta_and_compact_equivalent_ordered(theta: &ThetaSketch,
ordered: bool) {
let compact = theta.compact(ordered);
assert_theta_and_compact_equivalent(theta, &compact);
- if compact.num_retained() > 1 {
- assert_eq!(compact.is_ordered(), ordered);
+ let expected_ordered = ordered
+ || compact.is_empty()
+ || (compact.num_retained() == 1 && !compact.is_estimation_mode());
+ assert_eq!(compact.is_ordered(), expected_ordered);
+ if compact.is_ordered() {
+ let entries: Vec<u64> = compact.iter().map(|entry|
entry.hash()).collect();
+ assert_eq!(entries, sorted_theta_entries(theta));
}
}
diff --git a/datasketches/src/thetafamily/theta/union.rs
b/datasketches/src/thetafamily/theta/union.rs
index a8f21fa..eee30de 100644
--- a/datasketches/src/thetafamily/theta/union.rs
+++ b/datasketches/src/thetafamily/theta/union.rs
@@ -53,11 +53,7 @@ impl ThetaUnion {
/// Returns this union as a compact sketch.
pub fn to_sketch(&self, ordered: bool) -> CompactThetaSketch {
- let compact_state = self
- .state
- .to_compact_sketch_state(ordered)
- .map_retained_entries(|entry| entry.hash());
- CompactThetaSketch::from_compact_state(compact_state)
+
CompactThetaSketch::from_compact_state(self.state.to_compact_hash_state(ordered))
}
/// Serializes this union result into the uncompressed compact Theta
format.
@@ -66,7 +62,7 @@ impl ThetaUnion {
/// retained hashes are sorted. Otherwise they may be unordered; empty
results and exact
/// singletons always use their canonical encoding.
pub fn serialize(&self, ordered: bool) -> Vec<u8> {
- let state = self.state.to_compact_sketch_state(ordered);
+ let state = self.state.to_compact_hash_state(ordered);
serialization::serialize_compact_uncompressed(&state)
}
diff --git a/datasketches/src/thetafamily/tuple/hash_table.rs
b/datasketches/src/thetafamily/tuple/hash_table.rs
index 1e84959..2929317 100644
--- a/datasketches/src/thetafamily/tuple/hash_table.rs
+++ b/datasketches/src/thetafamily/tuple/hash_table.rs
@@ -21,6 +21,7 @@ use std::num::NonZeroU64;
use crate::thetacommon::SketchEntry;
use crate::thetacommon::hash_table::SketchHashTable;
use crate::thetacommon::intersection::IntersectionMergePolicy;
+use crate::thetacommon::sketch_state::sort_niche_by_hash;
use crate::thetacommon::union::UnionMergePolicy;
use crate::tuple::SummaryCombinePolicy;
@@ -46,6 +47,7 @@ impl<S> TupleEntry<S> {
}
/// Returns the hash used as this entry's key.
+ #[inline]
pub fn hash(&self) -> u64 {
self.hash.get()
}
@@ -64,9 +66,14 @@ impl<S> TupleEntry<S> {
pub type TupleHashTable<S> = SketchHashTable<TupleEntry<S>>;
impl<S> SketchEntry for TupleEntry<S> {
+ #[inline]
fn hash(&self) -> u64 {
self.hash.get()
}
+
+ fn sort_by_hash(entries: &mut Vec<Self>) {
+ sort_niche_by_hash(entries);
+ }
}
impl<S> TupleHashTable<S> {
diff --git a/datasketches/src/thetafamily/tuple/sketch.rs
b/datasketches/src/thetafamily/tuple/sketch.rs
index e62e269..c529083 100644
--- a/datasketches/src/thetafamily/tuple/sketch.rs
+++ b/datasketches/src/thetafamily/tuple/sketch.rs
@@ -23,6 +23,7 @@
//! implementations.
use std::hash::Hash;
+use std::iter::FusedIterator;
use std::slice;
use crate::codec::SketchSlice;
@@ -112,6 +113,17 @@ impl<'a, S> Iterator for TupleSketchIter<'a, S> {
}
}
+impl<S> ExactSizeIterator for TupleSketchIter<'_, S> {
+ fn len(&self) -> usize {
+ match self {
+ Self::Mutable(iter) => iter.len(),
+ Self::Compact(iter) => iter.len(),
+ }
+ }
+}
+
+impl<S> FusedIterator for TupleSketchIter<'_, S> {}
+
impl<S> Clone for TupleSketchView<'_, S> {
fn clone(&self) -> Self {
*self
diff --git a/tests-integration/tests/theta_test/a_not_b.rs
b/tests-integration/tests/theta_test/a_not_b.rs
index c4734b8..f7b2ab2 100644
--- a/tests-integration/tests/theta_test/a_not_b.rs
+++ b/tests-integration/tests/theta_test/a_not_b.rs
@@ -191,16 +191,20 @@ fn test_exact_superset_b_returns_empty() {
#[test]
fn test_result_ordering() {
- let a = sketch_with_range(0, 64);
+ let a = sketch_with_range(0, 1_000);
let empty = ThetaSketchBuilder::default().build().unwrap();
let a_not_b = ThetaANotB::default();
- let r = a_not_b.compute(&a, &empty, true).unwrap();
- assert!(r.is_ordered());
+ let ordered = a_not_b.compute(&a, &empty, true).unwrap();
+ let unordered = a_not_b.compute(&a, &empty, false).unwrap();
+ assert!(ordered.is_ordered());
+ assert!(!unordered.is_ordered());
- let r = a_not_b.compute(&a, &empty, false).unwrap();
- assert!(!r.is_ordered());
+ let mut expected: Vec<u64> = unordered.iter().map(|entry|
entry.hash()).collect();
+ expected.sort_unstable();
+ let actual: Vec<u64> = ordered.iter().map(|entry| entry.hash()).collect();
+ assert_eq!(actual, expected);
}
#[test]
diff --git a/tests-integration/tests/theta_test/intersection.rs
b/tests-integration/tests/theta_test/intersection.rs
index 5cab864..28aa8e7 100644
--- a/tests-integration/tests/theta_test/intersection.rs
+++ b/tests-integration/tests/theta_test/intersection.rs
@@ -119,16 +119,20 @@ fn test_terminal_empty_state_ignores_future_updates() {
}
#[test]
-fn test_to_sketch_unordered_is_not_ordered() {
- let mut a = ThetaSketchBuilder::default().build().unwrap();
- for i in 0..64 {
- a.update(i);
- }
+fn test_result_ordering() {
+ let a = sketch_with_range(0, 1_000);
let mut i = ThetaIntersection::default();
i.update(&a).unwrap();
- let r = i.to_sketch(false).unwrap();
- assert!(!r.is_ordered());
+ let unordered = i.to_sketch(false).unwrap();
+ let ordered = i.to_sketch(true).unwrap();
+ assert!(!unordered.is_ordered());
+ assert!(ordered.is_ordered());
+
+ let mut expected: Vec<u64> = unordered.iter().map(|entry|
entry.hash()).collect();
+ expected.sort_unstable();
+ let actual: Vec<u64> = ordered.iter().map(|entry| entry.hash()).collect();
+ assert_eq!(actual, expected);
}
#[test]
diff --git a/tests-integration/tests/theta_test/sketch.rs
b/tests-integration/tests/theta_test/sketch.rs
index b900ab1..83e3877 100644
--- a/tests-integration/tests/theta_test/sketch.rs
+++ b/tests-integration/tests/theta_test/sketch.rs
@@ -167,6 +167,75 @@ fn test_reset() {
assert_eq!(sketch.upper_bound(NumStdDev::One), 0.0);
}
+#[test]
+fn test_compact_ordering_and_canonical_states() {
+ let empty = ThetaSketchBuilder::default().build().unwrap();
+ for ordered in [false, true] {
+ let compact = empty.compact(ordered);
+ assert!(compact.is_empty());
+ assert!(compact.is_ordered());
+ assert_eq!(compact.num_retained(), 0);
+ }
+
+ let mut exact_singleton = ThetaSketchBuilder::default().build().unwrap();
+ exact_singleton.update(42u64);
+ assert!(exact_singleton.compact(false).is_ordered());
+ assert!(exact_singleton.compact(true).is_ordered());
+
+ let retained_value = (0u64..)
+ .find(|candidate| {
+ let mut sketch = ThetaSketchBuilder::default()
+ .sampling_probability(0.5)
+ .build()
+ .unwrap();
+ sketch.update(*candidate);
+ sketch.num_retained() == 1
+ })
+ .expect("failed to find a value retained under p = 0.5");
+ let mut sampled_singleton = ThetaSketchBuilder::default()
+ .sampling_probability(0.5)
+ .build()
+ .unwrap();
+ sampled_singleton.update(retained_value);
+ assert!(!sampled_singleton.compact(false).is_ordered());
+ assert!(sampled_singleton.compact(true).is_ordered());
+
+ for (lg_k, n, p) in [
+ (12, 2, 1.0),
+ (12, 1_000, 1.0),
+ (5, 1_000, 1.0),
+ (12, 20_000, 1.0),
+ (12, 20_000, 0.1),
+ (14, 50_000, 1.0),
+ ] {
+ let mut sketch = ThetaSketchBuilder::default()
+ .lg_k(lg_k)
+ .sampling_probability(p)
+ .build()
+ .unwrap();
+ for i in 0..n {
+ sketch.update(i as u64);
+ }
+ let mut expected: Vec<u64> = sketch.iter().map(|entry|
entry.hash()).collect();
+ expected.sort_unstable();
+
+ let ordered = sketch.compact(true);
+ assert!(ordered.is_ordered());
+ assert_eq!(ordered.theta64(), sketch.theta64());
+ assert_eq!(ordered.seed_hash(), sketch.seed_hash());
+ let ordered_hashes: Vec<u64> = ordered.iter().map(|entry|
entry.hash()).collect();
+ assert_eq!(ordered_hashes, expected);
+
+ let unordered = sketch.compact(false);
+ assert!(!unordered.is_ordered());
+ assert_eq!(unordered.theta64(), sketch.theta64());
+ assert_eq!(unordered.seed_hash(), sketch.seed_hash());
+ let mut unordered_hashes: Vec<u64> = unordered.iter().map(|entry|
entry.hash()).collect();
+ unordered_hashes.sort_unstable();
+ assert_eq!(unordered_hashes, expected);
+ }
+}
+
#[test]
fn test_iterator() {
let mut sketch = ThetaSketchBuilder::default().lg_k(12).build().unwrap();
@@ -269,29 +338,6 @@ fn test_bounds_with_sampling() {
assert_that!(estimate, le(upper_bound));
}
-#[test]
-fn test_bounds_all_num_std_devs() {
- let mut sketch = ThetaSketchBuilder::default().lg_k(12).build().unwrap();
- for i in 0..10000 {
- sketch.update(i);
- }
-
- // Test all valid NumStdDev values work correctly
- // These no longer return Result, so we just verify they return valid
values
- let lb1 = sketch.lower_bound(NumStdDev::One);
- let lb2 = sketch.lower_bound(NumStdDev::Two);
- let lb3 = sketch.lower_bound(NumStdDev::Three);
- let ub1 = sketch.upper_bound(NumStdDev::One);
- let ub2 = sketch.upper_bound(NumStdDev::Two);
- let ub3 = sketch.upper_bound(NumStdDev::Three);
-
- // Verify the bounds are properly ordered
- assert_that!(lb3, le(lb2));
- assert_that!(lb2, le(lb1));
- assert_that!(ub1, le(ub2));
- assert_that!(ub2, le(ub3));
-}
-
#[test]
fn test_bounds_empty_with_sampling() {
let sketch = ThetaSketchBuilder::default()
diff --git a/tests-integration/tests/theta_test/union.rs
b/tests-integration/tests/theta_test/union.rs
index d60c69a..59f17e9 100644
--- a/tests-integration/tests/theta_test/union.rs
+++ b/tests-integration/tests/theta_test/union.rs
@@ -327,7 +327,39 @@ fn test_result_ordering_forms_have_same_estimate() {
assert!(!unordered.is_ordered());
assert!(ordered.is_ordered());
+ assert_eq!(unordered.theta64(), ordered.theta64());
assert_eq!(unordered.estimate(), ordered.estimate());
+
+ let mut expected: Vec<u64> = unordered.iter().map(|entry|
entry.hash()).collect();
+ expected.sort_unstable();
+ let actual: Vec<u64> = ordered.iter().map(|entry| entry.hash()).collect();
+ assert_eq!(actual, expected);
+}
+
+#[test]
+fn test_ordered_result_sorts_clustered_deserialized_hashes() {
+ let clustered: Vec<u64> = (1..=1_000u64)
+ .rev()
+ .map(|k| (0x5AA5u64 << 48) | k)
+ .collect();
+ let mut bytes = sketch_with_range(12, 0, clustered.len() as i64)
+ .compact(false)
+ .serialize();
+ let offset = bytes.len() - clustered.len() * 8;
+ for (slot, hash) in bytes[offset..].chunks_exact_mut(8).zip(&clustered) {
+ slot.copy_from_slice(&hash.to_le_bytes());
+ }
+ let input = CompactThetaSketch::deserialize(&bytes).unwrap();
+ assert!(!input.is_ordered());
+
+ let mut union = ThetaUnionBuilder::default().lg_k(12).build().unwrap();
+ union.update(&input).unwrap();
+ let result = union.to_sketch(true);
+
+ assert!(result.is_ordered());
+ let actual: Vec<u64> = result.iter().map(|entry| entry.hash()).collect();
+ let expected: Vec<u64> = (1..=1_000u64).map(|k| (0x5AA5u64 << 48) |
k).collect();
+ assert_eq!(actual, expected);
}
#[test]
@@ -464,6 +496,24 @@ fn test_trim_to_k() {
assert_eq!(result.num_retained(), 1024);
}
+#[test]
+fn test_mixed_lg_k_union_compacts_result_storage() {
+ let large_exact = sketch_with_range(16, 0, 50_000);
+ let small_estimated = sketch_with_range(5, 0, 100_000);
+
+ let mut union = ThetaUnionBuilder::default().lg_k(16).build().unwrap();
+ union.update(&large_exact).unwrap();
+ union.update(&small_estimated).unwrap();
+
+ for ordered in [false, true] {
+ let result = union.to_sketch(ordered);
+ assert_that!(
+ result.estimated_size(),
+ le(result.num_retained().next_power_of_two().max(4) *
size_of::<u64>()),
+ );
+ }
+}
+
#[test]
fn test_builder_lg_k() {
let sketch = sketch_with_range(10, 0, 1000);
diff --git a/tests-integration/tests/tuple_test/a_not_b.rs
b/tests-integration/tests/tuple_test/a_not_b.rs
index d1e648b..941c52f 100644
--- a/tests-integration/tests/tuple_test/a_not_b.rs
+++ b/tests-integration/tests/tuple_test/a_not_b.rs
@@ -34,11 +34,15 @@ use tests_integration::MAX_THETA;
use crate::default_tuple_sketch_builder;
use crate::tuple_sketch_with_range;
-fn sorted_entries(sketch: &CompactTupleSketch<u64>) -> Vec<(u64, u64)> {
- let mut entries: Vec<_> = sketch
+fn entries(sketch: &CompactTupleSketch<u64>) -> Vec<(u64, u64)> {
+ sketch
.iter()
.map(|entry| (entry.hash(), *entry.summary()))
- .collect();
+ .collect()
+}
+
+fn sorted_entries(sketch: &CompactTupleSketch<u64>) -> Vec<(u64, u64)> {
+ let mut entries = entries(sketch);
entries.sort_unstable();
entries
}
@@ -70,10 +74,7 @@ fn accepts_mutable_and_compact_inputs() {
.compute(&a.compact(true), &b.compact(false), true)
.unwrap();
- assert_eq!(
- sorted_entries(&mutable_result),
- sorted_entries(&compact_result)
- );
+ assert_eq!(entries(&mutable_result), entries(&compact_result));
assert_eq!(mutable_result.num_retained(), 500);
}
@@ -103,14 +104,10 @@ fn input_and_result_ordering_preserve_entries() {
from_ordered_inputs.theta64()
);
assert_eq!(from_unordered_inputs.theta64(), unordered_result.theta64());
- assert_eq!(
- sorted_entries(&from_unordered_inputs),
- sorted_entries(&from_ordered_inputs)
- );
- assert_eq!(
- sorted_entries(&from_unordered_inputs),
- sorted_entries(&unordered_result)
- );
+
+ let expected = sorted_entries(&unordered_result);
+ assert_eq!(entries(&from_unordered_inputs), expected);
+ assert_eq!(entries(&from_ordered_inputs), expected);
}
#[test]
diff --git a/tests-integration/tests/tuple_test/intersection.rs
b/tests-integration/tests/tuple_test/intersection.rs
index 32a4438..7a71a31 100644
--- a/tests-integration/tests/tuple_test/intersection.rs
+++ b/tests-integration/tests/tuple_test/intersection.rs
@@ -152,12 +152,25 @@ fn only_non_empty_inputs_require_the_operator_seed() {
#[test]
fn result_ordering_follows_the_request() {
- let input = tuple_sketch_with_range(0, 100);
+ let input = tuple_sketch_with_range(0, 1_000);
let mut intersection = TupleIntersection::new(SumPolicy);
intersection.update(&input).unwrap();
- assert!(intersection.to_sketch(true).unwrap().is_ordered());
- assert!(!intersection.to_sketch(false).unwrap().is_ordered());
+ let ordered = intersection.to_sketch(true).unwrap();
+ let unordered = intersection.to_sketch(false).unwrap();
+ assert!(ordered.is_ordered());
+ assert!(!unordered.is_ordered());
+
+ let mut expected: Vec<_> = unordered
+ .iter()
+ .map(|entry| (entry.hash(), *entry.summary()))
+ .collect();
+ expected.sort_unstable();
+ let actual: Vec<_> = ordered
+ .iter()
+ .map(|entry| (entry.hash(), *entry.summary()))
+ .collect();
+ assert_eq!(actual, expected);
}
#[test]
diff --git a/tests-integration/tests/tuple_test/sketch.rs
b/tests-integration/tests/tuple_test/sketch.rs
index 194060d..096ae8b 100644
--- a/tests-integration/tests/tuple_test/sketch.rs
+++ b/tests-integration/tests/tuple_test/sketch.rs
@@ -206,17 +206,30 @@ fn assert_compact_preserves_state(
assert_eq!(compact.is_estimation_mode(), updatable.is_estimation_mode());
assert_eq!(compact.theta64(), updatable.theta64());
assert_eq!(compact.seed_hash(), updatable.seed_hash());
- assert_eq!(
- sorted_entries(compact.iter()),
- sorted_entries(updatable.iter())
- );
assert_eq!(compact.estimate(), updatable.estimate());
- assert_eq!(compact.is_ordered(), ordered);
+
+ let expected_ordered = ordered
+ || compact.is_empty()
+ || (compact.num_retained() == 1 && !compact.is_estimation_mode());
+ assert_eq!(compact.is_ordered(), expected_ordered);
+
+ let expected = sorted_entries(updatable.iter());
+ if compact.is_ordered() {
+ let actual: Vec<_> = compact
+ .iter()
+ .map(|entry| (entry.hash(), *entry.summary()))
+ .collect();
+ assert_eq!(actual, expected);
+ } else {
+ assert_eq!(sorted_entries(compact.iter()), expected);
+ }
}
#[test]
fn compact_preserves_state_in_exact_and_estimation_modes() {
- for (lg_k, num_updates, expected_estimation_mode) in [(12, 2_000, false),
(5, 5_000, true)] {
+ for (lg_k, num_updates, expected_estimation_mode) in
+ [(12, 1, false), (12, 2_000, false), (5, 5_000, true)]
+ {
let mut sketch =
default_tuple_sketch_builder().lg_k(lg_k).build().unwrap();
for key in 0..num_updates {
sketch.update(key, key + 1);
diff --git a/tests-integration/tests/tuple_test/union.rs
b/tests-integration/tests/tuple_test/union.rs
index 496838c..59e7dec 100644
--- a/tests-integration/tests/tuple_test/union.rs
+++ b/tests-integration/tests/tuple_test/union.rs
@@ -153,12 +153,25 @@ fn custom_combine_policy_controls_overlapping_summaries()
{
#[test]
fn result_ordering_follows_the_request() {
- let input = tuple_sketch_with_range(0, 100);
+ let input = tuple_sketch_with_range(0, 1_000);
let mut union = default_union_builder().build().unwrap();
union.update(&input).unwrap();
- assert!(union.to_sketch(true).is_ordered());
- assert!(!union.to_sketch(false).is_ordered());
+ let ordered = union.to_sketch(true);
+ let unordered = union.to_sketch(false);
+ assert!(ordered.is_ordered());
+ assert!(!unordered.is_ordered());
+
+ let mut expected: Vec<_> = unordered
+ .iter()
+ .map(|entry| (entry.hash(), *entry.summary()))
+ .collect();
+ expected.sort_unstable();
+ let actual: Vec<_> = ordered
+ .iter()
+ .map(|entry| (entry.hash(), *entry.summary()))
+ .collect();
+ assert_eq!(actual, expected);
}
#[test]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]