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]