kumarUjjawal commented on code in PR #27025:
URL: https://github.com/apache/datafusion/pull/27025#discussion_r4595621580


##########
datafusion/common/src/hash_utils.rs:
##########
@@ -544,6 +570,63 @@ fn hash_generic_byte_view_array<T: ByteViewType>(
     }
 }
 
+/// Scatters non-null dictionary hashes in independent lanes to overlap 
key-indexed loads.
+#[cfg(not(feature = "force_hash_collisions"))]
+#[inline(always)]
+fn scatter_non_null_dictionary<K: ArrowDictionaryKeyType, const MULTI_COL: 
bool>(
+    array: &DictionaryArray<K>,
+    dict_hashes: &[u64],
+    hashes: &mut [u64],
+) {
+    const LANES: usize = 8;
+    let keys = array.keys().values();
+    assert_eq!(
+        dict_hashes.len(),
+        array.values().len(),
+        "dictionary hashes must cover every dictionary value"
+    );
+    assert!(

Review Comment:
   The no-null dictionary fast path now uses `assert!(hashes.len() <= 
keys.len())`, which differs both from the dictionary null paths in the same 
function (`min(len)` at line 669, `zip` at line 700) and from every other 
hasher (`assert_eq!`).



##########
datafusion/common/src/hash_utils.rs:
##########
@@ -160,8 +180,14 @@ where
         let mut buffer = cell.try_borrow_mut()
             .map_err(|_| _internal_datafusion_err!("with_hashes cannot be 
called reentrantly on the same thread"))?;
 
-        // Ensure buffer has sufficient length, clearing old values
-        buffer.clear();
+        // A dictionary with non-null keys and values overwrites every output
+        // slot, so retain the initialized storage instead of zeroing it first.
+        let reuse_buffer = iter

Review Comment:
   The reuse gate checks nulls on the dictionary before compaction, but the 
scatter runs on the compacted dictionary. A dictionary whose only null values 
are never referenced by a key still gets cleared, even though the fast path 
would overwrite every slot.



##########
datafusion/common/src/hash_utils.rs:
##########
@@ -544,6 +570,63 @@ fn hash_generic_byte_view_array<T: ByteViewType>(
     }
 }
 
+/// Scatters non-null dictionary hashes in independent lanes to overlap 
key-indexed loads.
+#[cfg(not(feature = "force_hash_collisions"))]
+#[inline(always)]
+fn scatter_non_null_dictionary<K: ArrowDictionaryKeyType, const MULTI_COL: 
bool>(
+    array: &DictionaryArray<K>,
+    dict_hashes: &[u64],
+    hashes: &mut [u64],
+) {
+    const LANES: usize = 8;
+    let keys = array.keys().values();
+    assert_eq!(
+        dict_hashes.len(),
+        array.values().len(),
+        "dictionary hashes must cover every dictionary value"
+    );
+    assert!(
+        hashes.len() <= keys.len(),
+        "dictionary scatter requires at least one key per hash slot"
+    );
+    let keys = &keys[..hashes.len()];
+
+    let (key_chunks, key_tail) = keys.as_chunks::<LANES>();
+    let (hash_chunks, hash_tail) = hashes.as_chunks_mut::<LANES>();
+    for (keys, hashes) in key_chunks.iter().zip(hash_chunks) {
+        let gathered: [u64; LANES] = std::array::from_fn(|lane| unsafe {

Review Comment:
   `scatter_non_null_dictionary` is a safe fn that reads 
`dict_hashes.get_unchecked(key.as_usize())` with no check on the key. Its 
SAFETY comment relies on dictionary keys being in bounds, which only holds for 
validated arrays. Also, the `unsafe` block wraps the whole closure, including 
the safe `keys[lane]` index.



##########
datafusion/common/src/hash_utils.rs:
##########
@@ -160,8 +180,14 @@ where
         let mut buffer = cell.try_borrow_mut()
             .map_err(|_| _internal_datafusion_err!("with_hashes cannot be 
called reentrantly on the same thread"))?;
 
-        // Ensure buffer has sufficient length, clearing old values
-        buffer.clear();
+        // A dictionary with non-null keys and values overwrites every output
+        // slot, so retain the initialized storage instead of zeroing it first.
+        let reuse_buffer = iter

Review Comment:
   with_hashes` peeks the iterator a second time inside the TLS closure to 
compute `reuse_buffer`. It could be computed in the same `match iter.peek()` 
that already reads `required_size`.



##########
datafusion/common/src/hash_utils.rs:
##########
@@ -2570,6 +2656,123 @@ mod tests {
         assert_eq!(result, expected_hashes);
     }
 
+    #[test]
+    #[cfg(not(feature = "force_hash_collisions"))]
+    fn test_non_null_dictionary_hash_fast_path() {
+        check_non_null_dictionary_hash_fast_path::<UInt8Type>();
+        check_non_null_dictionary_hash_fast_path::<UInt16Type>();
+        check_non_null_dictionary_hash_fast_path::<Int64Type>();
+
+        let random_state = RandomState::with_seed(0);
+        let keys = vec![2, 0, 1, 2, 1, 0, 2, 0, 1, 2, 0];
+        let null_values: ArrayRef = Arc::new(
+            DictionaryArray::<Int32Type>::try_new(
+                Int32Array::from(keys),
+                Arc::new(StringArray::from(vec![Some("a"), None, Some("c")])),
+            )
+            .unwrap(),
+        );
+        let null_keys: ArrayRef = Arc::new(
+            DictionaryArray::<Int32Type>::try_new(
+                Int32Array::from(vec![
+                    Some(2),
+                    None,
+                    Some(1),
+                    Some(2),
+                    None,
+                    Some(0),
+                    Some(2),
+                    None,
+                    Some(1),
+                    Some(2),
+                    Some(0),
+                ]),
+                Arc::new(StringArray::from(vec!["a", "b", "c"])),
+            )
+            .unwrap(),
+        );
+
+        let assert_matches = |dictionary: &ArrayRef| {
+            assert!(!dictionary_overwrites_hash_buffer(dictionary.as_ref()));
+            let strings = arrow::compute::cast(dictionary, 
&DataType::Utf8).unwrap();
+            let mut expected = vec![0; dictionary.len()];
+            create_hashes([strings], &random_state, &mut expected).unwrap();
+            with_hashes([dictionary], &random_state, |hashes| {
+                assert_eq!(hashes, expected);
+                Ok(())
+            })
+            .unwrap();
+        };
+
+        assert_matches(&null_values);
+        assert_matches(&null_keys);
+    }
+
+    #[test]
+    #[cfg(feature = "force_hash_collisions")]
+    fn test_force_hash_collisions_clears_dictionary_buffer() {

Review Comment:
   `test_force_hash_collisions_clears_dictionary_buffer` only checks that a cfg 
stub hard-coded to `false` returns `false`. It never calls `with_hashes`, so it 
tests nothing about clearing the buffer.



##########
datafusion/common/src/hash_utils.rs:
##########
@@ -2570,6 +2656,123 @@ mod tests {
         assert_eq!(result, expected_hashes);
     }
 
+    #[test]
+    #[cfg(not(feature = "force_hash_collisions"))]
+    fn test_non_null_dictionary_hash_fast_path() {
+        check_non_null_dictionary_hash_fast_path::<UInt8Type>();
+        check_non_null_dictionary_hash_fast_path::<UInt16Type>();
+        check_non_null_dictionary_hash_fast_path::<Int64Type>();
+
+        let random_state = RandomState::with_seed(0);
+        let keys = vec![2, 0, 1, 2, 1, 0, 2, 0, 1, 2, 0];
+        let null_values: ArrayRef = Arc::new(
+            DictionaryArray::<Int32Type>::try_new(
+                Int32Array::from(keys),
+                Arc::new(StringArray::from(vec![Some("a"), None, Some("c")])),
+            )
+            .unwrap(),
+        );
+        let null_keys: ArrayRef = Arc::new(
+            DictionaryArray::<Int32Type>::try_new(
+                Int32Array::from(vec![
+                    Some(2),
+                    None,
+                    Some(1),
+                    Some(2),
+                    None,
+                    Some(0),
+                    Some(2),
+                    None,
+                    Some(1),
+                    Some(2),
+                    Some(0),
+                ]),
+                Arc::new(StringArray::from(vec!["a", "b", "c"])),
+            )
+            .unwrap(),
+        );
+
+        let assert_matches = |dictionary: &ArrayRef| {
+            assert!(!dictionary_overwrites_hash_buffer(dictionary.as_ref()));
+            let strings = arrow::compute::cast(dictionary, 
&DataType::Utf8).unwrap();
+            let mut expected = vec![0; dictionary.len()];
+            create_hashes([strings], &random_state, &mut expected).unwrap();
+            with_hashes([dictionary], &random_state, |hashes| {
+                assert_eq!(hashes, expected);
+                Ok(())
+            })
+            .unwrap();
+        };

Review Comment:
   The `assert_matches` test of the clearing path for null dictionaries never 
dirties the thread-local buffer itself. It only catches a missing `clear()` 
because earlier `check_non_null_dictionary_hash_fast_path` calls happened to 
leave stale data in the buffer.



##########
datafusion/common/src/hash_utils.rs:
##########
@@ -544,6 +570,63 @@ fn hash_generic_byte_view_array<T: ByteViewType>(
     }
 }
 
+/// Scatters non-null dictionary hashes in independent lanes to overlap 
key-indexed loads.
+#[cfg(not(feature = "force_hash_collisions"))]
+#[inline(always)]
+fn scatter_non_null_dictionary<K: ArrowDictionaryKeyType, const MULTI_COL: 
bool>(
+    array: &DictionaryArray<K>,
+    dict_hashes: &[u64],
+    hashes: &mut [u64],
+) {
+    const LANES: usize = 8;
+    let keys = array.keys().values();
+    assert_eq!(
+        dict_hashes.len(),
+        array.values().len(),
+        "dictionary hashes must cover every dictionary value"
+    );
+    assert!(
+        hashes.len() <= keys.len(),
+        "dictionary scatter requires at least one key per hash slot"
+    );
+    let keys = &keys[..hashes.len()];
+
+    let (key_chunks, key_tail) = keys.as_chunks::<LANES>();
+    let (hash_chunks, hash_tail) = hashes.as_chunks_mut::<LANES>();
+    for (keys, hashes) in key_chunks.iter().zip(hash_chunks) {
+        let gathered: [u64; LANES] = std::array::from_fn(|lane| unsafe {
+            let key = keys[lane];
+            // SAFETY: Dictionary keys are in bounds for values, which has the
+            // same length as dict_hashes.
+            *dict_hashes.get_unchecked(key.as_usize())
+        });
+        if MULTI_COL {

Review Comment:
   The MULTI_COL branch of the 8-lane loop calls 
`update_dictionary_hash::<MULTI_COL>`, which branches on MULTI_COL again. The 
`if MULTI_COL { .. } else { *hashes = gathered }` split plus the helper adds 
layers without changing what the code does.



##########
datafusion/common/src/hash_utils.rs:
##########
@@ -544,6 +570,63 @@ fn hash_generic_byte_view_array<T: ByteViewType>(
     }
 }
 
+/// Scatters non-null dictionary hashes in independent lanes to overlap 
key-indexed loads.
+#[cfg(not(feature = "force_hash_collisions"))]
+#[inline(always)]
+fn scatter_non_null_dictionary<K: ArrowDictionaryKeyType, const MULTI_COL: 
bool>(
+    array: &DictionaryArray<K>,
+    dict_hashes: &[u64],
+    hashes: &mut [u64],
+) {
+    const LANES: usize = 8;
+    let keys = array.keys().values();
+    assert_eq!(
+        dict_hashes.len(),
+        array.values().len(),
+        "dictionary hashes must cover every dictionary value"
+    );
+    assert!(
+        hashes.len() <= keys.len(),
+        "dictionary scatter requires at least one key per hash slot"
+    );
+    let keys = &keys[..hashes.len()];
+
+    let (key_chunks, key_tail) = keys.as_chunks::<LANES>();
+    let (hash_chunks, hash_tail) = hashes.as_chunks_mut::<LANES>();
+    for (keys, hashes) in key_chunks.iter().zip(hash_chunks) {
+        let gathered: [u64; LANES] = std::array::from_fn(|lane| unsafe {
+            let key = keys[lane];
+            // SAFETY: Dictionary keys are in bounds for values, which has the
+            // same length as dict_hashes.
+            *dict_hashes.get_unchecked(key.as_usize())
+        });
+        if MULTI_COL {
+            for (hash, dict_hash) in hashes.iter_mut().zip(gathered) {
+                update_dictionary_hash::<MULTI_COL>(hash, dict_hash);
+            }
+        } else {
+            *hashes = gathered;
+        }
+    }
+
+    for (hash, key) in hash_tail.iter_mut().zip(key_tail) {
+        // SAFETY: Dictionary keys are in bounds for values, which has the
+        // same length as dict_hashes.
+        let dict_hash = unsafe { *dict_hashes.get_unchecked(key.as_usize()) };
+        update_dictionary_hash::<MULTI_COL>(hash, dict_hash);
+    }
+}
+
+#[cfg(not(feature = "force_hash_collisions"))]
+#[inline(always)]
+fn update_dictionary_hash<const MULTI_COL: bool>(hash: &mut u64, dict_hash: 
u64) {

Review Comment:
   `update_dictionary_hash` repeats the MULTI_COL combine logic that already 
exists inline in `scatter_row` in `hash_dictionary_scatter` (lines 658-662).



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