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]

Reply via email to