alamb commented on code in PR #19374:
URL: https://github.com/apache/datafusion/pull/19374#discussion_r2628891528
##########
datafusion/common/src/hash_utils.rs:
##########
@@ -787,9 +903,6 @@ mod tests {
}
}
- // same logical values should hash to the same hash value
Review Comment:
This fails after this PR because the values of the binary view no longer
match the same value as if the corresponding bytes are hashed -- for small
strings the entire u128 is hashed even if the string is short (like 'F')
##########
datafusion/common/src/hash_utils.rs:
##########
@@ -269,6 +269,127 @@ fn hash_array<T>(
}
}
+/// Hash a StringView or BytesView array
+///
+/// Templated to optimize inner loop based on presence of nulls and external
buffers.
+///
+/// HAS_NULLS: do we have to check null in the inner loop
+/// HAS_BUFFERS: if true, array has external buffers; if false, all strings
are inlined/ less then 12 bytes
+/// REHASH: if true, combining with existing hash, otherwise initializing
+#[inline(never)]
+fn hash_string_view_array_inner<
+ T: ByteViewType,
+ const HAS_NULLS: bool,
+ const HAS_BUFFERS: bool,
+ const REHASH: bool,
+>(
+ array: &GenericByteViewArray<T>,
+ random_state: &RandomState,
+ hashes_buffer: &mut [u64],
+) {
+ assert_eq!(
+ hashes_buffer.len(),
+ array.len(),
+ "hashes_buffer and array should be of equal length"
+ );
+
+ let buffers = array.data_buffers();
+ let view_bytes = |view_len: u32, view: u128| {
+ let view = ByteView::from(view);
+ let offset = view.offset as usize;
+ // SAFETY: view is a valid view as it came from the array
+ unsafe {
+ let data = buffers.get_unchecked(view.buffer_index as usize);
+ data.get_unchecked(offset..offset + view_len as usize)
+ }
+ };
+
+ let hashes_and_views = hashes_buffer.iter_mut().zip(array.views().iter());
+ for (i, (hash, &v)) in hashes_and_views.enumerate() {
+ if HAS_NULLS && array.is_null(i) {
+ continue;
+ }
+ let view_len = v as u32;
+ // all views are inlined, no need to access external buffers
+ if !HAS_BUFFERS || view_len <= 12 {
+ if REHASH {
+ *hash = combine_hashes(v.hash_one(random_state), *hash);
+ } else {
+ *hash = v.hash_one(random_state);
+ }
+ continue;
+ }
+ // view is not inlined, so we need to hash the bytes as well
+ let value = view_bytes(view_len, v);
+ if REHASH {
+ *hash = combine_hashes(value.hash_one(random_state), *hash);
+ } else {
+ *hash = value.hash_one(random_state);
+ }
+ }
+}
+
+/// Builds hash values for array views and writes them into `hashes_buffer`
+/// If `rehash==true` this combines the previous hash value in the buffer
+/// with the new hash using `combine_hashes`
+#[cfg(not(feature = "force_hash_collisions"))]
+fn hash_generic_byte_view_array<T: ByteViewType>(
+ array: &GenericByteViewArray<T>,
+ random_state: &RandomState,
+ hashes_buffer: &mut [u64],
+ rehash: bool,
+) {
+ // instantiate the correct version based on presence of nulls and external
buffers
+ match (
+ array.null_count() != 0,
+ !array.data_buffers().is_empty(),
+ rehash,
+ ) {
+ // no nulls or buffers ==> hash the inlined views directly
+ // don't call the inner function as Rust seems better able to inline
this simpler code (2-3% faster)
+ (false, false, false) => {
Review Comment:
This is the key "innovation" -- make different specialized versions of the
hashing function taking advantage of known null ness and buffers
--
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]
