NoahKusaba opened a new pull request, #2363:
URL: https://github.com/apache/datafusion-ballista/pull/2363
# Which issue does this PR close?
Closes #.
# Rationale for this change
This is a vibe-port of the same change in DataFusion's `BatchPartitioner`
(apache/datafusion#21900), where it measured up to 1.16x on TPC-H sf10. The
type
is private to `datafusion-physical-plan`, so it cannot be reused directly.
--> Also verified by eye to ensure it makes sense.
@Dandandan cc
# What changes are included in this PR?
`StrengthReducedU64` is built once per task and threaded into
`compute_partition_indices`, replacing the per-row `%`. Partition assignment
is
unchanged. `try_new` now rejects a zero output partition count, which
previously
would have divided by zero.
AI Benchmark:
8192 rows/batch, 200 batches, hash on an int64 key, release, best of 15 —
timing all of `compute_partition_indices` (hash + index build):
| partitions | before | after | speedup | path |
|---|---|---|---|---|
| 16 | 46.44 µs | 25.79 µs | 1.80x | mask |
| 64 | 52.22 µs | 23.76 µs | 2.20x | mask |
| 100 | 46.06 µs | 25.90 µs | 1.78x | reciprocal |
| 200 | 46.49 µs | 25.06 µs | 1.86x | reciprocal |
| 400 | 47.90 µs | 25.95 µs | 1.85x | reciprocal |
| 800 | 52.06 µs | 32.39 µs | 1.61x | reciprocal |
### Scope of the speedup
The 1.8–2.2x above is for `compute_partition_indices` in isolation. That
function
is one phase of writing a shuffle, so the effect on the write step as a
whole is
smaller. Phase split, 50 batches x 8192 lineitem-shaped rows, LZ4, best of 8:
| phase | 64 parts | 200 parts | 400 parts |
|---|---|---|---|
| bucket (hash + index build) | 11.8% | 10.0% | 10.5% |
| interleave + view compaction | 45.1% | 42.6% | 39.6% |
| IPC encode + LZ4 | 43.1% | 47.4% | 50.0% |
| total | 22.6 ms | 33.8 ms | 36.6 ms |
Only the first row is touched by this PR; the rest is untouched. Applying the
measured phase speedup to that share:
| partitions | phase speedup | write-step sp
|---|---|---|
| 64 | 2.20x | 1.07x |
| 200 | 1.86x | 1.05x |
| 400 | 1.85x | 1.05x |
So roughly **5-7% off the shuffle write stepry wall
clock, since the write step is itself only part of a query. For comparison,
apache/datafusion#21900 made the same changef the
work and landed at up to 1.16x on TPC-H sf10.
# Are these changes tested?
Ported the tests over:
`strength_reduced_u64_remainder_matches_modulo` checks the reduced form
against `%` for 25 divisors × 21 boundary values plus a 10,000-value
pseudo-random sweep per divisor;
`strength_reduced_u64_partition_indices_matches_modulo` checks the production
entry point against a plain `%` loop on both paths. The existing
`compute_partition_indices_matches_batch_partitioner` drift test against
DataFusion's `BatchPartitioner` still passes unchanged.
# Are there any user-facing changes?
no
--
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]
