You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/10/23 04:24:45 UTC
(datafusion) branch gh-readonly-queue/main/pr-26191-a5ca29189d1fe5459ee700adf9620db6058b6abc created (now bcb33e2787)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-26191-a5ca29189d1fe5459ee700adf9620db6058b6abc
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at bcb33e2787 perf: unroll PrimitiveArray hashing for the no-null path (#26191)
This branch includes the following new commits:
new bcb33e2787 perf: unroll PrimitiveArray hashing for the no-null path (#26191)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: perf: unroll PrimitiveArray hashing for the no-null path (#26191)
Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-26191-a5ca29189d1fe5459ee700adf9620db6058b6abc
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit bcb33e27871c0a65e3eaef20345c450f8c0f646c
Author: RIchard Baah <13...@users.noreply.github.com>
AuthorDate: Fri Oct 23 03:29:40 2026 +0000
perf: unroll PrimitiveArray hashing for the no-null path (#26191)
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and
enhancements and this helps us generate change logs for our releases.
You can link an issue to this PR using the GitHub syntax. For example
`Closes #123` indicates that this PR will close issue #123.
-->
- Closes None, see similar PR
https://github.com/apache/datafusion/pull/26159.
## Rationale for this change
The no-null branch of `hash_array_primitive` is a tight `zip` over
`hashes_buffer` and `array.values()`. For `PrimitiveArray<Int64>` and
friends
the whole hash is a handful of cycles, so the serialization imposed by
one
scalar iteration per row shows up as a measurable per-batch cost.
<!--
Why are you proposing this change? If this is already explained clearly
in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand
your changes and offer better suggestions for fixes.
Please explain the problem you are trying to solve in terms of the
user-visible
behavior, rather than the implementation.
For example, "The code in `foo.rs` doesn't handle nulls" is a symptom of
the
implementation. "COUNT(DISTINCT) returns wrong results when the column
contains
nulls" is the user-visible problem.
-->
## What changes are included in this PR?
Replace the two scalar loops with two small helpers that batch
independent
hashes before storing:
- `hash_prim_fresh_dense`: single-column case (`rehash == false`), **16
rows
per iteration**. Each lane only reads `values[row]`, so lane count can
go
wide before register pressure matters.
- `hash_prim_rehash_dense`: multi-column case (`rehash == true`), **8
rows
per iteration**. Each lane holds both `prev_hash` and `value` live;
widening past 8 spilled registers in the multi-column case.
Both use `std::array::from_fn::<LANES>` to gather + hash into a
temporary
array, then store the whole batch, keeps the independent hash chains in
flight so the pipeline isn't serialized on store-to-load deps. A scalar
tail handles rows beyond the last `LANES`-aligned boundary.
<!--
There is no need to duplicate the description in the issue here, but it
is sometimes worth providing a summary of the individual changes in this
PR.
-->
## What is the testing strategy for this PR?
Existing `hash_utils::tests`
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
Briefly describe how this PR is tested, and point to the specific tests
you added. For example: 'This new feature is covered by the
`sqllogictest` cases added in `foo.slt`'.
If this PR does not add tests, explain why. For example, if the change
is already covered by existing tests, please mention it.
You should also check the `codecov` bot reply on this PR to confirm the
changed code is exercised.
-->
## Are there any user-facing changes?
no
<!--
If there are user-facing changes then we may require documentation to be
updated before approving the PR.
If there are any breaking changes to public APIs, please add the `api
change` label.
-->
---------
Co-authored-by: Jay Zhan <ja...@gmail.com>
---
datafusion/common/src/hash_utils.rs | 57 +++++++++++++++++++++++++++++++------
1 file changed, 49 insertions(+), 8 deletions(-)
diff --git a/datafusion/common/src/hash_utils.rs b/datafusion/common/src/hash_utils.rs
index f7a8b037fb..181cde28f9 100644
--- a/datafusion/common/src/hash_utils.rs
+++ b/datafusion/common/src/hash_utils.rs
@@ -321,15 +321,9 @@ fn hash_array_primitive<T>(
if array.null_count() == 0 {
if rehash {
- for (hash, &value) in hashes_buffer.iter_mut().zip(array.values().iter()) {
- let mut hasher = random_state.seeded_state(*hash).build_hasher();
- value.hash_write(&mut hasher);
- *hash = hasher.finish();
- }
+ hash_prim_rehash_dense(array.values(), hashes_buffer, random_state);
} else {
- for (hash, &value) in hashes_buffer.iter_mut().zip(array.values().iter()) {
- *hash = value.hash_one(random_state);
- }
+ hash_prim_fresh_dense(array.values(), hashes_buffer, random_state);
}
} else if rehash {
for i in array.nulls().unwrap().valid_indices() {
@@ -346,6 +340,53 @@ fn hash_array_primitive<T>(
}
}
+/// Overwrite each slot with `value.hash_one(state)`, 16 rows per iteration.
+/// Gathering + hashing a whole lane batch before storing keeps the independent
+/// hashes in flight so the pipeline isn't serialized on store-to-load deps.
+#[cfg(not(feature = "force_hash_collisions"))]
+#[inline(always)]
+fn hash_prim_fresh_dense<N, S>(values: &[N], hashes: &mut [u64], state: &S)
+where
+ N: HashValue + Copy,
+ S: HashState,
+{
+ const LANES: usize = 16;
+ let (value_chunks, value_tail) = values.as_chunks::<LANES>();
+ let (hash_chunks, hash_tail) = hashes.as_chunks_mut::<LANES>();
+ for (h, v) in hash_chunks.iter_mut().zip(value_chunks) {
+ *h = v.map(|value| value.hash_one(state));
+ }
+ for (h, v) in hash_tail.iter_mut().zip(value_tail) {
+ *h = v.hash_one(state);
+ }
+}
+
+/// Fold `prev_hash` + `value` into a new hash, 8 rows per iteration. 8 is
+/// narrower than `hash_prim_fresh_dense` because each lane holds both `prev` and
+/// `value` live; widening past 8 spilled registers in the multi-column case.
+#[cfg(not(feature = "force_hash_collisions"))]
+#[inline(always)]
+fn hash_prim_rehash_dense<N, S>(values: &[N], hashes: &mut [u64], state: &S)
+where
+ N: HashValue + Copy,
+ S: HashState,
+{
+ const LANES: usize = 8;
+ let rehash_one = |prev_hash: u64, value: N| {
+ let mut hasher = state.seeded_state(prev_hash).build_hasher();
+ value.hash_write(&mut hasher);
+ hasher.finish()
+ };
+ let (value_chunks, value_tail) = values.as_chunks::<LANES>();
+ let (hash_chunks, hash_tail) = hashes.as_chunks_mut::<LANES>();
+ for (h, v) in hash_chunks.iter_mut().zip(value_chunks) {
+ *h = std::array::from_fn(|lane| rehash_one(h[lane], v[lane]));
+ }
+ for (h, &v) in hash_tail.iter_mut().zip(value_tail) {
+ *h = rehash_one(*h, v);
+ }
+}
+
/// Hashes one array into the `hashes_buffer`
/// If `rehash==true` this combines the previous hash value in the buffer
/// with the new hash using `combine_hashes`
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org