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]