You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "jayzhan211 (via GitHub)" <gi...@apache.org> on 2026/08/31 14:29:03 UTC
[PR] array_sort / array_has: monomorphize per native type instead of per Arrow type (reduce binary size) [datafusion]
jayzhan211 opened a new pull request, #24823:
URL: https://github.com/apache/datafusion/pull/24823
## Which issue does this PR close?
- Part of https://github.com/apache/datafusion/issues/24727
## Rationale for this change
`array_sort`, `array_has` and `array_min`/`array_max` each dispatch to a kernel
that is generic over **both** the Arrow element type and the list offset width,
so each kernel is monomorphized ~64 times. The bodies only ever move and compare
native values, so most of those copies are byte-identical: `Int32`, `Date32`,
`Time32Second` and `IntervalYearMonth` all sort and compare as `i32`.
`array_sort` is the worst case, and pays for it twice over: it calls
`sort_unstable_by` with a separate ascending and descending comparator closure,
and each distinct closure type drags in its own full copy of the standard
library's `ipnsort`. That alone accounts for **437K IR lines across 7,832
instantiations — 30% of the entire crate**.
## What changes are included in this PR?
- `sort.rs`: the per-row sort kernels become generic over the native value type
rather than the Arrow type, and both sort directions route through a single
comparator. `ArrowNativeTypeOp::compare` is a total order, so a descending
sort is exactly the reverse of the ascending one — sorting one way and
reversing keeps one instantiation of the standard library's sort per native
type instead of one per (Arrow type, offset width, direction) triple.
- `sort.rs`: the row-index sort in the non-primitive path moves into a helper
free of the offset width, so it is instantiated once rather than once per
list type.
- `array_has.rs`: the primitive scan is split into a thin per-Arrow-type shim
and a native-typed kernel, so the equality scan is compiled once per native
type.
- `min_max.rs`: `scalar_min_max` becomes generic over the native type.
The kernels stay generic over `OffsetSizeTrait` deliberately. Erasing that
dimension (widening offsets to `&[usize]`) was measured and reverted: it costs
an allocation and a pass over every row, which regressed `array_sort` over
5-element lists by ~30%, and it saves only ~15K IR lines because the expensive
instantiation is keyed on the comparator closure, which never mentions the
offset width. That is also why `min_max` improves only slightly here — erasing
its offset dimension needs a zero-allocation offsets view (an enum over
`&[i32]`/`&[i64]`) to be worth doing, which is left as a follow-up.
## Code size
### 1. Generated code: `cargo llvm-lines --release -p datafusion-functions-nested --lib`
| | main | this PR | change |
| --- | ---: | ---: | ---: |
| **crate total (lines)** | 1,455,442 | 965,772 | **−489,670 (−33.6%)** |
| **crate total (copies)** | 26,832 | 18,219 | −8,613 (−32.1%) |
| `sort` module | 537,199 | 75,615 | −461,584 (−85.9%) |
| `array_has` module | 73,292 | 46,948 | −26,344 (−35.9%) |
| `min_max` module | 26,316 | 24,016 | −2,300 (−8.7%) |
The standard library's sort machinery (`core::slice::sort`, attributed to this
crate's comparators) goes from **437,623 IR lines in 7,832 instantiations to
27,851 in 579**.
### 2. Final binary size: release bench binaries
| binary | main | this PR | change |
| --- | ---: | ---: | ---: |
| `array_sort` | 6,478,112 | 6,213,728 | −264,384 (−4.1%) |
| `array_has` | 6,825,968 | 6,693,872 | −132,096 (−1.9%) |
| `array_min_max` | 7,536,608 | 7,536,608 | 0 |
## Are these changes tested?
Yes, by existing tests — this is a refactor with no behavior change:
- `cargo test -p datafusion-functions-nested --lib` — 112 tests pass
- `cargo test -p datafusion-sqllogictest --test sqllogictests -- array` — all 53
files pass
- `cargo clippy --all-targets --all-features -- -D warnings` clean
### Benchmarks
`array_sort`, `array_min_max` and `array_has`, run as base/branch pairs from
pre-built binaries so no compilation interleaves with measurement, repeated
across passes with a base-vs-base noise floor measured alongside.
No benchmark is slower beyond the noise floor. Two are consistently faster:
| benchmark | change |
| --- | ---: |
| `array_has_array_i64/found/10` | −17% |
| `array_has_array_null_patterns/i64/nulls30_found` | −6% |
Caveat on the numbers: these were measured on a laptop whose best observed
noise floor was ~2%, so differences under that are not resolvable. Everything
outside those two rows landed within ±2%.
## Are there any user-facing changes?
No. No public API or behavior changes; `array_sort` output ordering is
unchanged, including for floats (`compare` is a total order, so reversing the
ascending order reproduces the descending order exactly, `NaN` and `-0.0`
included).
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] array_sort / array_has: monomorphize per native type instead of per Arrow type (reduce binary size) [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on PR #24823:
URL: https://github.com/apache/datafusion/pull/24823#issuecomment-5495949636
Thanks @Jefffrey @alamb !
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] array_sort / array_has: monomorphize per native type instead of per Arrow type (reduce binary size) [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on PR #24823:
URL: https://github.com/apache/datafusion/pull/24823#issuecomment-5495063406
reverse benchmark added and the wrapper cleanup
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] array_sort / array_has: monomorphize per native type instead of per Arrow type (reduce binary size) [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 merged PR #24823:
URL: https://github.com/apache/datafusion/pull/24823
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] array_sort / array_has: monomorphize per native type instead of per Arrow type (reduce binary size) [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #24823:
URL: https://github.com/apache/datafusion/pull/24823#issuecomment-5480421853
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/24823?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `98.90110%` with `1 line` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 81.57%. Comparing base ([`74f4dd6`](https://app.codecov.io/gh/apache/datafusion/commit/74f4dd6fe42806cd6131628cacfdb8316234f825?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`53add10`](https://app.codecov.io/gh/apache/datafusion/commit/53add108f2b51a05c32402918999a02723939076?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 10 commits behind head on main.
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/24823?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [datafusion/functions-nested/src/sort.rs](https://app.codecov.io/gh/apache/datafusion/pull/24823?src=pr&el=tree&filepath=datafusion%2Ffunctions-nested%2Fsrc%2Fsort.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9mdW5jdGlvbnMtbmVzdGVkL3NyYy9zb3J0LnJz) | 98.55% | [1 Missing :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/24823?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #24823 +/- ##
==========================================
+ Coverage 81.53% 81.57% +0.04%
==========================================
Files 1123 1123
Lines 406102 406617 +515
Branches 406102 406617 +515
==========================================
+ Hits 331111 331718 +607
+ Misses 55628 55456 -172
- Partials 19363 19443 +80
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/24823?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] array_sort / array_has: monomorphize per native type instead of per Arrow type (reduce binary size) [datafusion]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey commented on code in PR #24823:
URL: https://github.com/apache/datafusion/pull/24823#discussion_r3900315797
##########
datafusion/functions-nested/src/sort.rs:
##########
@@ -238,99 +238,104 @@ fn sort_primitive_list<T: ArrowPrimitiveType, OffsetSize: OffsetSizeTrait>(
where
T::Native: ArrowNativeTypeOp,
{
- if prim_values.null_count() > 0 {
- sort_list_with_nulls(prim_values, list_array, field, sort_options)
- } else {
- sort_list_no_nulls(prim_values, list_array, field, sort_options)
+ let descending = sort_options.is_some_and(|o| o.descending);
+ let nulls_first = sort_options.is_none_or(|o| o.nulls_first);
+ let list_nulls = list_array.nulls();
+ let offsets = list_array.offsets();
+
+ let (values, validity) = match prim_values.nulls() {
+ Some(element_nulls) if element_nulls.null_count() > 0 => {
+ let (values, validity) = sort_rows_with_nulls(
+ prim_values.values(),
+ element_nulls,
+ offsets,
+ list_nulls,
+ descending,
+ nulls_first,
+ );
+ (values, Some(validity))
+ }
+ _ => (
+ sort_rows_no_nulls(prim_values.values(), offsets, list_nulls, descending),
+ None,
+ ),
+ };
+
+ let sorted_values = Arc::new(
+ PrimitiveArray::<T>::new(values.into(), validity)
+ .with_data_type(prim_values.data_type().clone()),
+ );
+
+ Ok(Arc::new(GenericListArray::<OffsetSize>::try_new(
+ field,
+ rebase_offsets(offsets),
+ sorted_values,
+ list_nulls.cloned(),
+ )?))
+}
+
+/// Sorts one row's values in place.
+///
+/// [`ArrowNativeTypeOp::compare`] is a total order, so a descending sort is the
+/// reverse of the ascending one. Sorting one way and reversing keeps a single
+/// instantiation of the standard library's sort per native type, instead of one
+/// per comparator closure.
+#[inline]
+fn sort_row<N: ArrowNativeTypeOp>(row: &mut [N], descending: bool) {
+ row.sort_unstable_by(|a, b| a.compare(*b));
+ if descending {
+ row.reverse();
Review Comment:
are there performance implications here? im not sure our benchmarks cover a descending case
##########
datafusion/functions-nested/src/array_has.rs:
##########
Review Comment:
we could even get rid of this thin wrapper function since its only called at one place; all it does is destructure/cast input arrays
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] array_sort / array_has: monomorphize per native type instead of per Arrow type (reduce binary size) [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #24823:
URL: https://github.com/apache/datafusion/pull/24823#issuecomment-5494797726
I also had claude compare the overall datafusion binary size before and after this PR.
My measurements suggest this trims 0.5% from the overall `datafusion-cli` binary size. Thank you @jayzhan211
```text
┌──────────────────────────────────────────────────┬───────────────────┐
│ binary │ size │
├──────────────────────────────────────────────────┼───────────────────┤
│ ~/Downloads/datafusion-cli-mergebase (4ada0dcab) │ 81,415,344 │
├──────────────────────────────────────────────────┼───────────────────┤
│ ~/Downloads/datafusion-cli-pr (53add108f) │ 81,035,392 │
├──────────────────────────────────────────────────┼───────────────────┤
│ change │ −379,952 (−0.47%) │
└──────────────────────────────────────────────────┴───────────────────┘
```
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] array_sort / array_has: monomorphize per native type instead of per Arrow type (reduce binary size) [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on code in PR #24823:
URL: https://github.com/apache/datafusion/pull/24823#discussion_r3904821073
##########
datafusion/functions-nested/src/sort.rs:
##########
@@ -238,99 +238,104 @@ fn sort_primitive_list<T: ArrowPrimitiveType, OffsetSize: OffsetSizeTrait>(
where
T::Native: ArrowNativeTypeOp,
{
- if prim_values.null_count() > 0 {
- sort_list_with_nulls(prim_values, list_array, field, sort_options)
- } else {
- sort_list_no_nulls(prim_values, list_array, field, sort_options)
+ let descending = sort_options.is_some_and(|o| o.descending);
+ let nulls_first = sort_options.is_none_or(|o| o.nulls_first);
+ let list_nulls = list_array.nulls();
+ let offsets = list_array.offsets();
+
+ let (values, validity) = match prim_values.nulls() {
+ Some(element_nulls) if element_nulls.null_count() > 0 => {
+ let (values, validity) = sort_rows_with_nulls(
+ prim_values.values(),
+ element_nulls,
+ offsets,
+ list_nulls,
+ descending,
+ nulls_first,
+ );
+ (values, Some(validity))
+ }
+ _ => (
+ sort_rows_no_nulls(prim_values.values(), offsets, list_nulls, descending),
+ None,
+ ),
+ };
+
+ let sorted_values = Arc::new(
+ PrimitiveArray::<T>::new(values.into(), validity)
+ .with_data_type(prim_values.data_type().clone()),
+ );
+
+ Ok(Arc::new(GenericListArray::<OffsetSize>::try_new(
+ field,
+ rebase_offsets(offsets),
+ sorted_values,
+ list_nulls.cloned(),
+ )?))
+}
+
+/// Sorts one row's values in place.
+///
+/// [`ArrowNativeTypeOp::compare`] is a total order, so a descending sort is the
+/// reverse of the ascending one. Sorting one way and reversing keeps a single
+/// instantiation of the standard library's sort per native type, instead of one
+/// per comparator closure.
+#[inline]
+fn sort_row<N: ArrowNativeTypeOp>(row: &mut [N], descending: bool) {
+ row.sort_unstable_by(|a, b| a.compare(*b));
+ if descending {
+ row.reverse();
Review Comment:
I didn't add a descending bench case, but I measured it locally (8192 rows, Int32, this branch vs `main`, negative = `main` faster):
| elements/row | 5 | 20 | 100 | 1000 |
|---|---|---|---|---|
| `desc` | −1.6% | −1.1% | −0.04% | −0.2% |
| `desc`, null elements | +5.6% | +7.7% | −4.1% | −1.1% |
Re-running the identical build against itself swings ±3%, so this is all noise-level — the extra `reverse()` is an O(n) pass on an O(n log n) sort. Keeping it means one `sort_unstable_by` instantiation per native type instead of one per comparator, which is the code size this PR is cutting.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org