comphead commented on code in PR #27559:
URL: https://github.com/apache/datafusion/pull/27559#discussion_r4634393669


##########
datafusion/common/src/hash_utils.rs:
##########
@@ -2981,4 +3070,97 @@ mod tests {
 
         Ok(())
     }
+
+    /// The hash of each valid row, or the previous hash for a null row.
+    #[cfg(not(feature = "force_hash_collisions"))]
+    fn primitive_hashes_per_row<T>(
+        array: &PrimitiveArray<T>,
+        previous: &[u64],
+        rehash: bool,
+    ) -> Vec<u64>
+    where
+        T: ArrowPrimitiveType<Native: HashValue>,
+    {
+        let state = RandomState::with_seed(0);
+        (0..array.len())
+            .map(|i| match (array.is_valid(i), rehash) {
+                (false, _) => previous[i],
+                (true, false) => array.value(i).hash_one(&state),
+                (true, true) => {
+                    let mut hasher = 
state.seeded_state(previous[i]).build_hasher();
+                    array.value(i).hash_write(&mut hasher);
+                    hasher.finish()
+                }
+            })
+            .collect()
+    }
+
+    #[cfg(not(feature = "force_hash_collisions"))]
+    fn check_primitive_with_nulls<T>(array: &PrimitiveArray<T>)
+    where
+        T: ArrowPrimitiveType<Native: HashValue>,
+    {
+        let state = RandomState::with_seed(0);
+        // Distinct values, so a null row that loses its previous hash shows up
+        let previous: Vec<u64> = (0..array.len() as u64).map(|i| i * 31 + 
1).collect();
+        for rehash in [false, true] {
+            let mut hashes = previous.clone();
+            hash_array_primitive(array, &state, &mut hashes, rehash);
+            let expected = primitive_hashes_per_row(array, &previous, rehash);
+            assert_eq!(
+                hashes,
+                expected,
+                "len {}, offset {}, rehash {rehash}",
+                array.len(),
+                array.offset()
+            );
+        }
+    }
+
+    #[test]
+    #[cfg(not(feature = "force_hash_collisions"))]
+    fn hash_array_primitive_with_nulls() {
+        for len in [1, 63, 64, 65, 127, 128, 129, 200] {
+            let patterns: [&dyn Fn(usize) -> bool; 5] = [
+                // One null
+                &|i| i != len / 2,
+                // Exactly `MIN_VALID_FOR_DENSE` valid rows in every 64 rows, 
the
+                // most nulls a dense chunk saves and restores
+                &|i| i % 64 >= 64 - MIN_VALID_FOR_DENSE as usize,
+                &|i| i % 3 != 0,
+                // A run of nulls longer than one 64-row chunk
+                &|i| !(1..70).contains(&i),
+                &|_| false,
+            ];
+            for valid in patterns {
+                // Offset 5 puts the validity bits off a byte boundary
+                for offset in [0, 5] {
+                    let n = offset + len;
+                    let nulls = 
NullBuffer::from((0..n).map(valid).collect::<Vec<_>>());
+                    let ints = Int64Array::new(
+                        (0..n as i64).map(|i| i * 7919 - 3).collect(),
+                        Some(nulls.clone()),
+                    );
+                    check_primitive_with_nulls(&ints.slice(offset, len));
+                    // Values past 64 bits, so a hash of a truncated value 
shows up
+                    let decimals = Decimal128Array::new(
+                        (0..n as i128).map(|i| (i << 70) - i * 7919).collect(),
+                        Some(nulls.clone()),
+                    );
+                    check_primitive_with_nulls(&decimals.slice(offset, len));
+                    let floats = Float64Array::new(

Review Comment:
   The chunk logic does not depend on the value type, and `-0.0`/NaN hashing is 
already covered by the tests near L1779 and L1902. `Int64` plus `Decimal128` 
(the wide value) cover this change, so the `Float64` case could go.



##########
datafusion/common/src/hash_utils.rs:
##########
@@ -305,23 +305,112 @@ fn hash_array_primitive<T>(
         "hashes_buffer and array should be of equal length"
     );
 
-    if array.null_count() == 0 {
+    match array.nulls().filter(|nulls| nulls.null_count() > 0) {
+        None if rehash => {
+            hash_prim_rehash_dense(array.values(), hashes_buffer, random_state)
+        }
+        None => hash_prim_fresh_dense(array.values(), hashes_buffer, 
random_state),
+        // Null rows keep their previous hash, so an all-null array, such as a
+        // column that ROLLUP or GROUPING SETS nulls out, changes nothing
+        Some(nulls) if nulls.null_count() == nulls.len() => {}
+        Some(nulls) => hash_prim_with_nulls(
+            array.values(),
+            nulls,
+            hashes_buffer,
+            random_state,
+            rehash,
+        ),
+    }
+}
+
+/// The positions of the set bits of `bits`, lowest first
+#[cfg(not(feature = "force_hash_collisions"))]
+fn set_bits(mut bits: u64) -> impl Iterator<Item = usize> {
+    std::iter::from_fn(move || {
+        (bits != 0).then(|| {
+            let i = bits.trailing_zeros() as usize;
+            bits &= bits - 1;
+            i
+        })
+    })
+}
+
+/// The fewest valid rows in a 64-row chunk for which hashing every row of the
+/// chunk and restoring its null rows costs less than hashing only its valid 
rows
+/// one at a time.
+/// The null densities in the `with_hashes` benchmark cluster around where 
random
+/// chunks cross this count, so rerun it when changing the value.
+#[cfg(not(feature = "force_hash_collisions"))]
+const MIN_VALID_FOR_DENSE: u32 = 48;
+
+/// Hashes 64 rows at a time. A chunk with at least [`MIN_VALID_FOR_DENSE`]
+/// valid rows is hashed in place with the dense loops, which have no branch 
per
+/// row, and the previous hashes of its null rows are saved before and written
+/// back after. A sparser chunk, and the last `len % 64` rows, hash only their
+/// valid rows.
+#[cfg(not(feature = "force_hash_collisions"))]
+fn hash_prim_with_nulls<N, S>(
+    values: &[N],
+    nulls: &NullBuffer,
+    hashes: &mut [u64],
+    state: &S,
+    rehash: bool,
+) where
+    N: HashValue + Copy,
+    S: HashState,
+{
+    let chunks = nulls.inner().bit_chunks();
+    let (value_chunks, value_tail) = values.as_chunks::<64>();
+    let (hash_chunks, hash_tail) = hashes.as_chunks_mut::<64>();
+    let rows = value_chunks.iter().zip(hash_chunks.iter_mut());
+    for ((values, hashes), valid) in rows.zip(chunks.iter()) {
+        if valid.count_ones() < MIN_VALID_FOR_DENSE {

Review Comment:
   From 35% random nulls up, almost every chunk takes this branch, so it does 
the same hashing as `main`'s `valid_indices()` loop. It is still slower: up to 
14% on Neoverse-V2 at 45% to 90%, and 45% on Xeon at 99% (multiple, 1.17 to 
1.69 us). That points at per-chunk overhead rather than hashing. Two 
candidates, both unmeasured:
   
   - `rehash` is a runtime flag checked in every chunk, here and in 
`hash_prim_valid`. A `const REHASH: bool` parameter, as 
`hash_string_view_array_inner` and `hash_dictionary_scatter` already use, would 
hoist it out of the loop.
   - `values[i]` and `hashes[i]` are bounds checked, while `main` used 
`value_unchecked`.
   
   If neither closes the gap, `null_count` already tells you when the average 
chunk is below the threshold, and those arrays could keep `main`'s loop. That 
gives up the clustered-null wins, so the 64-row block cases would decide it.



##########
datafusion/common/src/hash_utils.rs:
##########
@@ -2981,4 +3070,97 @@ mod tests {
 
         Ok(())
     }
+
+    /// The hash of each valid row, or the previous hash for a null row.
+    #[cfg(not(feature = "force_hash_collisions"))]
+    fn primitive_hashes_per_row<T>(

Review Comment:
   This re-implements the rehash fold that `hash_prim_valid` and 
`hash_prim_rehash_dense` already have. The no-null path could be the oracle 
instead: hash `PrimitiveArray::<T>::new(array.values().clone(), None)` into a 
copy of `previous`, then write `previous[i]` back at the null rows. That checks 
the null handling against the dense loops this PR relies on. It also removes 
this helper and the second `RandomState`.



-- 
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]

Reply via email to