mbutrovich commented on code in PR #7691:
URL: https://github.com/apache/datafusion-comet/pull/7691#discussion_r4635745766
##########
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:
Thanks, switched to the copy. For murmur3's 256-byte chunk the copy stays
inline: 8 `vmovups` pairs on x86-64-v3 and 8 `ldp`/`stp q` pairs on
Neoverse-N1. The restore then runs 7 or 8 instructions per null row, where the
save and restore loops took about 18. For xxhash64's 512-byte chunk the copy
becomes a `memcpy` call on both targets, so the x86 and Neoverse runs should
include an xxhash64 case before the threshold is final.
--
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]