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: [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]
