Skip to content

Commit 3a3bfc5

Browse files
xudong963claude
andcommitted
perf: fix dictionary hash regression by removing hasher type param from hot loop
The #[inline(never)] hash_dictionary_inner carried a C: ChildHashing type parameter, causing different monomorphization for the RandomState path vs original code. This regressed dictionary_utf8_int32 by ~15%. Restructure: separate "hash dict values" (differs per hasher) from "scatter hashes to keys" (shared hot loop). The new hash_dictionary_scatter takes dict_hashes: &[u64] with no hasher parameter, so both paths call the exact same monomorphization. Co-Authored-By: Claude Opus 4.6 <[email protected]>
1 parent 87812d2 commit 3a3bfc5

1 file changed

Lines changed: 66 additions & 37 deletions

File tree

‎datafusion/common/src/hash_utils.rs‎

Lines changed: 66 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -777,32 +777,30 @@ fn hash_generic_byte_view_array_with_hasher<T: ByteViewType, S: BuildHasher>(
777777
}
778778
}
779779

780-
/// Hash dictionary array with compile-time specialization for null handling.
780+
/// Scatter pre-computed dictionary value hashes to key positions.
781781
///
782-
/// Uses const generics to eliminate runtim branching in the hot loop:
782+
/// Uses const generics to eliminate runtime branching in the hot loop:
783783
/// - `HAS_NULL_KEYS`: Whether to check for null dictionary keys
784784
/// - `HAS_NULL_VALUES`: Whether to check for null dictionary values
785785
/// - `MULTI_COL`: Whether to combine with existing hash (true) or initialize (false)
786+
///
787+
/// Dictionary value hashing is done by the caller (`hash_dictionary` /
788+
/// `hash_dictionary_with_child_hashing`) so this function has no hasher
789+
/// type parameter — both the RandomState and custom-hasher paths call the
790+
/// exact same monomorphization, preserving codegen quality.
786791
#[cfg(not(feature = "force_hash_collisions"))]
787792
#[inline(never)]
788-
fn hash_dictionary_inner<
793+
fn hash_dictionary_scatter<
789794
K: ArrowDictionaryKeyType,
790-
C: ChildHashing + ?Sized,
791795
const HAS_NULL_KEYS: bool,
792796
const HAS_NULL_VALUES: bool,
793797
const MULTI_COL: bool,
794798
>(
795799
array: &DictionaryArray<K>,
796-
child_hashing: &C,
800+
dict_hashes: &[u64],
797801
hashes_buffer: &mut [u64],
798-
) -> Result<()> {
799-
// Hash each dictionary value once, and then use that computed
800-
// hash for each key value to avoid a potentially expensive
801-
// redundant hashing for large dictionary elements (e.g. strings)
802+
) {
802803
let dict_values = array.values();
803-
let mut dict_hashes = vec![0; dict_values.len()];
804-
child_hashing.create_hashes([dict_values], &mut dict_hashes)?;
805-
806804
if HAS_NULL_KEYS {
807805
for (hash, key) in hashes_buffer.iter_mut().zip(array.keys().iter()) {
808806
if let Some(key) = key {
@@ -828,66 +826,97 @@ fn hash_dictionary_inner<
828826
}
829827
}
830828
}
831-
Ok(())
832829
}
833830

834-
/// Hash the values in a dictionary array
831+
/// Dispatch to the correct `hash_dictionary_scatter` variant based on
832+
/// null presence and multi-column mode.
835833
#[cfg(not(feature = "force_hash_collisions"))]
836-
fn hash_dictionary<K: ArrowDictionaryKeyType>(
834+
fn dispatch_dictionary_scatter<K: ArrowDictionaryKeyType>(
837835
array: &DictionaryArray<K>,
838-
child_hashing: &impl ChildHashing,
836+
dict_hashes: &[u64],
839837
hashes_buffer: &mut [u64],
840838
multi_col: bool,
841-
) -> Result<()> {
839+
) {
842840
let has_null_keys = array.keys().null_count() != 0;
843841
let has_null_values = array.values().null_count() != 0;
844842

845-
// Dispatcher based on null presence and multi-column mode
846-
// Should reduce branching within hot loops
847843
match (has_null_keys, has_null_values, multi_col) {
848-
(false, false, false) => hash_dictionary_inner::<K, _, false, false, false>(
844+
(false, false, false) => hash_dictionary_scatter::<K, false, false, false>(
849845
array,
850-
child_hashing,
846+
dict_hashes,
851847
hashes_buffer,
852848
),
853-
(false, false, true) => hash_dictionary_inner::<K, _, false, false, true>(
849+
(false, false, true) => hash_dictionary_scatter::<K, false, false, true>(
854850
array,
855-
child_hashing,
851+
dict_hashes,
856852
hashes_buffer,
857853
),
858-
(false, true, false) => hash_dictionary_inner::<K, _, false, true, false>(
854+
(false, true, false) => hash_dictionary_scatter::<K, false, true, false>(
859855
array,
860-
child_hashing,
856+
dict_hashes,
861857
hashes_buffer,
862858
),
863-
(false, true, true) => hash_dictionary_inner::<K, _, false, true, true>(
859+
(false, true, true) => hash_dictionary_scatter::<K, false, true, true>(
864860
array,
865-
child_hashing,
861+
dict_hashes,
866862
hashes_buffer,
867863
),
868-
(true, false, false) => hash_dictionary_inner::<K, _, true, false, false>(
864+
(true, false, false) => hash_dictionary_scatter::<K, true, false, false>(
869865
array,
870-
child_hashing,
866+
dict_hashes,
871867
hashes_buffer,
872868
),
873-
(true, false, true) => hash_dictionary_inner::<K, _, true, false, true>(
869+
(true, false, true) => hash_dictionary_scatter::<K, true, false, true>(
874870
array,
875-
child_hashing,
871+
dict_hashes,
876872
hashes_buffer,
877873
),
878-
(true, true, false) => hash_dictionary_inner::<K, _, true, true, false>(
874+
(true, true, false) => hash_dictionary_scatter::<K, true, true, false>(
879875
array,
880-
child_hashing,
876+
dict_hashes,
881877
hashes_buffer,
882878
),
883-
(true, true, true) => hash_dictionary_inner::<K, _, true, true, true>(
879+
(true, true, true) => hash_dictionary_scatter::<K, true, true, true>(
884880
array,
885-
child_hashing,
881+
dict_hashes,
886882
hashes_buffer,
887883
),
888884
}
889885
}
890886

887+
/// Hash the values in a dictionary array using the default RandomState path.
888+
#[cfg(not(feature = "force_hash_collisions"))]
889+
fn hash_dictionary<K: ArrowDictionaryKeyType>(
890+
array: &DictionaryArray<K>,
891+
random_state: &RandomState,
892+
hashes_buffer: &mut [u64],
893+
multi_col: bool,
894+
) -> Result<()> {
895+
// Hash each dictionary value once, and then use that computed
896+
// hash for each key value to avoid a potentially expensive
897+
// redundant hashing for large dictionary elements (e.g. strings)
898+
let dict_values = array.values();
899+
let mut dict_hashes = vec![0; dict_values.len()];
900+
create_hashes([dict_values], random_state, &mut dict_hashes)?;
901+
dispatch_dictionary_scatter(array, &dict_hashes, hashes_buffer, multi_col);
902+
Ok(())
903+
}
904+
905+
/// Hash the values in a dictionary array using a custom hasher.
906+
#[cfg(not(feature = "force_hash_collisions"))]
907+
fn hash_dictionary_with_child_hashing<K: ArrowDictionaryKeyType>(
908+
array: &DictionaryArray<K>,
909+
child_hashing: &impl ChildHashing,
910+
hashes_buffer: &mut [u64],
911+
multi_col: bool,
912+
) -> Result<()> {
913+
let dict_values = array.values();
914+
let mut dict_hashes = vec![0; dict_values.len()];
915+
child_hashing.create_hashes([dict_values], &mut dict_hashes)?;
916+
dispatch_dictionary_scatter(array, &dict_hashes, hashes_buffer, multi_col);
917+
Ok(())
918+
}
919+
891920
#[cfg(not(feature = "force_hash_collisions"))]
892921
fn hash_struct_array(
893922
array: &StructArray,
@@ -1345,7 +1374,7 @@ fn hash_single_array(
13451374
hash_array(&array, random_state, hashes_buffer, rehash)
13461375
}
13471376
DataType::Dictionary(_, _) => downcast_dictionary_array! {
1348-
array => hash_dictionary(array, &child_hashing, hashes_buffer, rehash)?,
1377+
array => hash_dictionary(array, random_state, hashes_buffer, rehash)?,
13491378
_ => unreachable!()
13501379
}
13511380
DataType::Struct(_) => {
@@ -1421,7 +1450,7 @@ fn hash_single_array_with_hasher<S: BuildHasher>(
14211450
hash_array_with_hasher(&array, hash_builder, hashes_buffer, rehash)
14221451
}
14231452
DataType::Dictionary(_, _) => downcast_dictionary_array! {
1424-
array => hash_dictionary(array, &child_hashing, hashes_buffer, rehash)?,
1453+
array => hash_dictionary_with_child_hashing(array, &child_hashing, hashes_buffer, rehash)?,
14251454
_ => unreachable!()
14261455
}
14271456
DataType::Struct(_) => {

0 commit comments

Comments
 (0)