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


##########
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>(
+    values: &[T],
+    nulls: &NullBuffer,
+    hashes: &mut [H],
+    hash: impl Fn(T, H) -> H,
+) {
+    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 {
+            for i in set_bits(valid) {
+                hashes[i] = hash(values[i], hashes[i]);
+            }
+            continue;
+        }
+        // The check above leaves at most `64 - MIN_VALID_FOR_DENSE` null rows.
+        let mut kept = [H::default(); 64 - MIN_VALID_FOR_DENSE as usize];

Review Comment:
   The dense branch walks the null bits twice (save, then restore) and sizes 
`kept` from `MIN_VALID_FOR_DENSE`. Copying the whole chunk first needs one walk 
and no `H: Default` bound:
   
   ```rust
   let previous = *hashes;
   for (h, &v) in hashes.iter_mut().zip(values) {
       *h = hash(v, *h);
   }
   for i in set_bits(!valid) {
       hashes[i] = previous[i];
   }
   ```
   
   The copy is 256 or 512 bytes and vectorizes. I timed the chunk loop on its 
own (int32 murmur3, 8192 rows, random nulls, M-series Mac, `-C 
target-cpu=native`). This is a local micro-benchmark, not the `hash_nulls` 
bench. This PR against the copy: 1.85 vs 1.87 us at 10% nulls, 2.18 vs 1.91 us 
at 25%, 4.29 vs 3.08 us at 50%, 5.10 vs 3.60 us at 60%, and 3.49 vs 2.58 us at 
75%. A cheaper dense chunk moves the break-even toward fewer valid rows, so the 
threshold sweep would need to run after this change.



##########
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:
   This safe `pub(crate)` function relies on `values`, `nulls` and `hashes` 
having the same length. If `hashes` is longer, its extra rows are silently left 
alone, which is the failure #7687 added the length check for. The check in 
`create_hashes_internal!` guarantees it today. A `debug_assert_eq!` on the 
three lengths here would keep it true for a future caller.



##########
native/spark-expr/src/hash_funcs/utils.rs:
##########
@@ -1499,3 +1558,131 @@ mod tests {
         }
     }
 }
+
+#[cfg(test)]
+mod null_chunk_tests {

Review Comment:
   `utils.rs` already has a `#[cfg(test)] mod tests` (line 1356), so these 
tests can go there instead of a second test module. `MIN_VALID_FOR_DENSE` can 
then drop `pub(super)`, since only this file uses it and a child module can 
read private items.



##########
native/spark-expr/benches/hash_nulls.rs:
##########
@@ -0,0 +1,129 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! Benchmarks hashing fixed-width columns with nulls, the case shuffle hash 
partitioning hits on
+//! nullable keys such as TPC-DS foreign keys.
+
+use arrow::array::{ArrayRef, Float64Array, Int32Array, Int64Array};
+use arrow::buffer::NullBuffer;
+use criterion::{criterion_group, criterion_main, Criterion};
+use datafusion::common::ScalarValue;
+use datafusion::physical_plan::ColumnarValue;
+use datafusion_comet_spark_expr::murmur3::create_murmur3_hashes;
+use datafusion_comet_spark_expr::spark_xxhash64;
+use std::hint::black_box;
+use std::sync::Arc;
+
+const NUM_ROWS: usize = 8192;
+
+/// Null percentages, from TPC-DS-like to nearly all null.
+const SWEEP: [u32; 11] = [3, 10, 25, 50, 60, 70, 75, 80, 85, 90, 99];
+
+/// Pseudo-random values from a fixed-seed xorshift, so runs are comparable.
+fn xorshift(seed: u64) -> impl FnMut() -> u64 {
+    let mut x = seed;
+    move || {
+        x ^= x << 13;
+        x ^= x >> 7;
+        x ^= x << 17;
+        x
+    }
+}
+
+/// Each row is null with probability `null_fraction`, independently.
+fn random_nulls(null_fraction: f64) -> NullBuffer {
+    let mut next = xorshift(0x2545_f491_4f6c_dd1d);
+    NullBuffer::from(
+        (0..NUM_ROWS)
+            .map(|_| (next() as f64 / u64::MAX as f64) >= null_fraction)
+            .collect::<Vec<_>>(),
+    )
+}
+
+/// Every tenth row is null, a pattern the branch predictor learns.
+fn stride_nulls() -> NullBuffer {

Review Comment:
   `is_null(i, 0.1)` in `benches/common/mod.rs` builds this same 
every-tenth-row pattern, and most benches in this crate pull that module in. 
`common::i32_array(NUM_ROWS, 0.1, ...)` can replace `stride_nulls` here.



##########
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:
   This compares Comet with itself. The files under 
`sql-tests/expressions/hash/` all have fewer than 64 rows, so no SQL test 
reaches a full chunk today. A SQL file with a CTAS over `range(200)` that nulls 
rows in these patterns and selects `hash(i)`, `hash(l)`, `hash(d)`, 
`xxhash64(d)` and `xxhash64(i, d)` would check both loops against Spark. A 
float argument keeps `xxhash64` on Comet's kernel at the default seed 
(`args_compatible_with_spark_xxhash64`), and the `-0.0` and NaN rows fit in the 
same table. `hash_fixed_width_with_nulls_matches_per_row` still covers the 
sliced offsets, so this test could be replaced by that file.



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