mbutrovich commented on code in PR #7691:
URL: https://github.com/apache/datafusion-comet/pull/7691#discussion_r4635747873


##########
native/spark-expr/src/hash_funcs/utils.rs:
##########
@@ -18,6 +18,65 @@
 //! This includes utilities for hashing and murmur3 hashing.
 
 use arrow::array::Array;
+use arrow::buffer::NullBuffer;
+
+/// The positions of the set bits of `bits`, lowest first.
+#[inline]
+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 rates from 25% to 85% in the `hash_nulls` benchmark put random 
chunks around this
+/// count, so rerun them when changing the value.
+pub(super) const MIN_VALID_FOR_DENSE: u32 = 16;
+
+/// Hashes the valid rows of a fixed-width column that has nulls, 64 rows at a 
time. Null rows keep
+/// their previous hash. A chunk with at least [`MIN_VALID_FOR_DENSE`] valid 
rows is hashed in
+/// full, which vectorizes, and the previous hashes of its null rows are saved 
before and written
+/// back after. Hashing a null slot is harmless because `hash` can't fail. A 
sparser chunk, and the
+/// last `len % 64` rows, hash only their valid rows.
+#[inline]
+pub(crate) fn hash_fixed_width_with_nulls<T: Copy, H: Copy + Default>(

Review Comment:
   > A `debug_assert_eq!` on the three lengths here would keep it true for a 
future caller.
   
   Thanks. A `debug_assert_eq!` doesn't run in release builds, so a future 
caller with mismatched lengths would still skip rows or panic on `hash_tail[i]` 
there. The function now returns an internal error when the lengths differ, like 
the check in `create_hashes_internal!`, and both macro callers use `?`. 
`hash_fixed_width_with_nulls_length_mismatch_is_error` covers it.



##########
native/spark-expr/src/hash_funcs/utils.rs:
##########
@@ -1499,3 +1558,131 @@ mod tests {
         }
     }
 }
+
+#[cfg(test)]
+mod null_chunk_tests {
+    use super::{hash_fixed_width_with_nulls, MIN_VALID_FOR_DENSE};
+    use crate::hash_funcs::create_xxhash64_hashes;
+    use crate::murmur3::create_murmur3_hashes;
+    use arrow::array::{Array, ArrayRef, Float64Array, Int32Array, Int64Array};
+    use arrow::buffer::NullBuffer;
+    use std::sync::Arc;
+
+    type Pattern = Box<dyn Fn(usize) -> bool>;
+
+    /// Validity by row index, chosen to reach every path through the chunk 
loop.
+    fn patterns(len: usize) -> Vec<(&'static str, Pattern)> {
+        let min_valid = MIN_VALID_FOR_DENSE as usize;
+        vec![
+            ("one null", Box::new(move |i| i != len / 2)),
+            (
+                "MIN_VALID_FOR_DENSE valid rows per chunk",
+                Box::new(move |i| i % 64 >= 64 - min_valid),
+            ),
+            (
+                "one fewer valid row per chunk",
+                Box::new(move |i| i % 64 > 64 - min_valid),
+            ),
+            ("two thirds valid", Box::new(|i| i % 3 != 0)),
+            (
+                "null run longer than a chunk",
+                Box::new(|i| !(1..70).contains(&i)),
+            ),
+            ("all null", Box::new(|_| false)),
+        ]
+    }
+
+    #[test]
+    fn hash_fixed_width_with_nulls_matches_per_row() {
+        let hash = |value: u64, previous: u64| 
previous.wrapping_mul(0x9e37_79b9_7f4a_7c15) ^ value;
+        for len in [1, 63, 64, 65, 127, 128, 129, 200] {
+            for (name, valid) in patterns(len) {
+                // Offset 5 puts the validity bits off a byte boundary.
+                for offset in [0, 5] {
+                    let nulls = NullBuffer::from((0..offset + 
len).map(&valid).collect::<Vec<_>>())
+                        .slice(offset, len);
+                    let values: Vec<u64> = (0..len as u64).map(|i| i * 7919 + 
3).collect();
+                    // Distinct previous hashes, so a null row that loses its 
hash shows up.
+                    let previous: Vec<u64> = (0..len as u64).map(|i| i * 31 + 
1).collect();
+                    let expected: Vec<u64> = (0..len)
+                        .map(|i| {
+                            if nulls.is_valid(i) {
+                                hash(values[i], previous[i])
+                            } else {
+                                previous[i]
+                            }
+                        })
+                        .collect();
+                    let mut hashes = previous.clone();
+                    hash_fixed_width_with_nulls(&values, &nulls, &mut hashes, 
hash);
+                    assert_eq!(hashes, expected, "{name}, len {len}, offset 
{offset}");
+                }
+            }
+        }
+    }
+
+    /// Hashes each valid row on its own, as a one-row array, which never 
reaches a full chunk.
+    fn per_row<H: Copy>(
+        array: &ArrayRef,
+        previous: &[H],
+        create: impl Fn(&[ArrayRef], &mut [H]),
+    ) -> Vec<H> {
+        (0..array.len())
+            .map(|i| {
+                let mut hash = [previous[i]];
+                if array.is_valid(i) {
+                    create(&[array.slice(i, 1)], &mut hash);
+                }
+                hash[0]
+            })
+            .collect()
+    }
+
+    #[test]
+    fn create_hashes_with_nulls_matches_per_row() {

Review Comment:
   Thanks, added `hash_fixed_width_nulls.sql`. It writes one Parquet file of 
1300 rows, so each block of 256 rows is four aligned chunks with its own 
validity pattern, and the last 20 rows are a partial chunk. Two blocks have 16 
and 15 valid rows per chunk, at and one below `MIN_VALID_FOR_DENSE`. The 
`double` column has `-0.0` and NaN rows. I dropped 
`create_hashes_with_nulls_matches_per_row`.



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