2010YOUY01 commented on code in PR #23816:
URL: https://github.com/apache/datafusion/pull/23816#discussion_r3772221474
##########
datafusion/functions-aggregate/src/hyperloglog.rs:
##########
@@ -70,107 +99,182 @@ impl<T> HyperLogLog<T>
where
T: Hash + ?Sized,
{
- /// Creates a new, empty HyperLogLog.
+ /// Creates a new, empty HyperLogLog with the default precision (14).
pub fn new() -> Self {
- let registers = [0; NUM_REGISTERS];
- Self::new_with_registers(registers)
+ Self::with_precision(DEFAULT_HLL_P)
}
- /// Creates a HyperLogLog from already populated registers
- /// note that this method should not be invoked in untrusted environment
- /// because the internal structure of registers are not examined.
- pub(crate) fn new_with_registers(registers: [u8; NUM_REGISTERS]) -> Self {
+ /// Creates a new, empty HyperLogLog with the given precision `p`.
+ ///
+ /// The number of registers is `2^p`. Supported range:
`HLL_P_MIN..=DEFAULT_HLL_P`.
+ #[inline(always)]
+ pub fn with_precision(p: usize) -> Self {
+ assert!(
+ (HLL_P_MIN..=DEFAULT_HLL_P).contains(&p),
+ "HLL precision must be in {HLL_P_MIN}..={DEFAULT_HLL_P}, got {p}",
+ );
+ let q = 64 - p;
+ let p_mask = ((1_usize << p) as u64) - 1;
Self {
- registers,
+ p,
+ q,
+ p_mask,
phantom: PhantomData,
+ registers: [0u8; 1 << DEFAULT_HLL_P],
}
}
- /// The HLL hash state is shared through `datafusion_common::hash_utils`
- /// so sketches remain compatible across accumulators.
+ /// Creates a HyperLogLog from already populated registers.
+ ///
+ /// The precision is inferred from the register slice length, which must be
+ /// a power of two in the range `2^HLL_P_MIN..=2^DEFAULT_HLL_P`.
+ ///
+ /// Note that this method should not be invoked in an untrusted environment
+ /// because the internal structure of registers is not examined.
+ pub(crate) fn from_registers(v: &[u8]) -> Self {
+ let len = v.len();
+ assert!(
+ len.is_power_of_two(),
+ "register slice length must be a power of two, got {len}",
+ );
+ let p = len.ilog2() as usize;
+ assert!(
+ (HLL_P_MIN..=DEFAULT_HLL_P).contains(&p),
+ "inferred precision {p} is outside {HLL_P_MIN}..={DEFAULT_HLL_P}",
+ );
+ let q = 64 - p;
+ let p_mask = (len as u64) - 1;
+ let mut registers = [0u8; 1 << DEFAULT_HLL_P];
+ registers[..len].copy_from_slice(v);
+ Self {
+ p,
+ q,
+ p_mask,
+ phantom: PhantomData,
+ registers,
+ }
+ }
+
+ /// The precision of this sketch.
#[inline]
- fn hash_value(&self, obj: &T) -> u64 {
- HLL_HASH_STATE.hash_one(obj)
+ pub(crate) fn precision(&self) -> usize {
+ self.p
+ }
+
+ /// Heap bytes used by the register buffer (not captured by `size_of_val`).
+ /// Always 0 — registers are stored inline in the struct.
+ pub(crate) fn register_heap_size(&self) -> usize {
+ 0
}
/// Adds an element to the HyperLogLog.
+ #[cfg(test)]
pub fn add(&mut self, obj: &T) {
- let hash = self.hash_value(obj);
+ let hash = HLL_HASH_STATE.hash_one(obj);
self.add_hashed(hash);
}
/// Adds a pre-computed hash value directly to the HyperLogLog.
///
/// The hash should be computed using [`HLL_HASH_STATE`], the same hasher
used
/// by [`Self::add`].
- #[inline]
+ #[inline(always)]
pub(crate) fn add_hashed(&mut self, hash: u64) {
- let index = (hash & HLL_P_MASK) as usize;
- let p = ((hash >> HLL_P) | (1_u64 << HLL_Q)).trailing_zeros() + 1;
- self.registers[index] = self.registers[index].max(p as u8);
+ self.for_each_hash(std::iter::once(hash));
Review Comment:
Creating multiple utilities to implement this function seem unnecessary,
could we inline all the logic like the previous implementation
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
