Repository navigation
Commit da89c7c
authored
array_sort / array_has: monomorphize per native type instead of per Arrow type (reduce binary size) (apache#24823)
## Which issue does this PR close?
- Part of apache#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).1 parent 80ae9e5 commit da89c7c
4 files changed
Lines changed: 168 additions & 123 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
22 | 22 | | |
23 | 23 | | |
24 | 24 | | |
| 25 | + | |
25 | 26 | | |
26 | 27 | | |
27 | 28 | | |
| |||
119 | 120 | | |
120 | 121 | | |
121 | 122 | | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
122 | 139 | | |
123 | | - | |
124 | | - | |
| 140 | + | |
| 141 | + | |
125 | 142 | | |
126 | 143 | | |
127 | 144 | | |
| |||
149 | 166 | | |
150 | 167 | | |
151 | 168 | | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
| 174 | + | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
| 182 | + | |
| 183 | + | |
152 | 184 | | |
153 | 185 | | |
154 | 186 | | |
| |||
174 | 206 | | |
175 | 207 | | |
176 | 208 | | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
177 | 223 | | |
178 | 224 | | |
179 | 225 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
18 | 18 | | |
19 | 19 | | |
20 | 20 | | |
21 | | - | |
22 | | - | |
23 | | - | |
| 21 | + | |
| 22 | + | |
24 | 23 | | |
25 | 24 | | |
26 | 25 | | |
| |||
359 | 358 | | |
360 | 359 | | |
361 | 360 | | |
362 | | - | |
| 361 | + | |
363 | 362 | | |
364 | 363 | | |
365 | 364 | | |
| |||
371 | 370 | | |
372 | 371 | | |
373 | 372 | | |
374 | | - | |
375 | | - | |
| 373 | + | |
| 374 | + | |
| 375 | + | |
| 376 | + | |
| 377 | + | |
376 | 378 | | |
377 | 379 | | |
378 | 380 | | |
379 | | - | |
380 | | - | |
| 381 | + | |
| 382 | + | |
381 | 383 | | |
382 | 384 | | |
383 | 385 | | |
384 | 386 | | |
385 | 387 | | |
386 | | - | |
| 388 | + | |
387 | 389 | | |
388 | 390 | | |
389 | 391 | | |
390 | 392 | | |
391 | 393 | | |
392 | | - | |
| 394 | + | |
393 | 395 | | |
394 | 396 | | |
395 | 397 | | |
| |||
430 | 432 | | |
431 | 433 | | |
432 | 434 | | |
433 | | - | |
434 | | - | |
435 | | - | |
| 435 | + | |
| 436 | + | |
| 437 | + | |
| 438 | + | |
| 439 | + | |
| 440 | + | |
| 441 | + | |
| 442 | + | |
436 | 443 | | |
437 | 444 | | |
438 | | - | |
439 | | - | |
440 | | - | |
441 | | - | |
442 | | - | |
| 445 | + | |
443 | 446 | | |
444 | | - | |
445 | | - | |
446 | 447 | | |
447 | | - | |
| 448 | + | |
448 | 449 | | |
449 | 450 | | |
450 | 451 | | |
| |||
461 | 462 | | |
462 | 463 | | |
463 | 464 | | |
464 | | - | |
| 465 | + | |
465 | 466 | | |
466 | 467 | | |
467 | 468 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
21 | 21 | | |
22 | 22 | | |
23 | 23 | | |
| 24 | + | |
24 | 25 | | |
25 | 26 | | |
26 | 27 | | |
| |||
263 | 264 | | |
264 | 265 | | |
265 | 266 | | |
266 | | - | |
| 267 | + | |
267 | 268 | | |
268 | 269 | | |
269 | 270 | | |
| |||
285 | 286 | | |
286 | 287 | | |
287 | 288 | | |
288 | | - | |
289 | | - | |
290 | | - | |
| 289 | + | |
| 290 | + | |
| 291 | + | |
291 | 292 | | |
292 | 293 | | |
293 | 294 | | |
294 | | - | |
295 | | - | |
| 295 | + | |
| 296 | + | |
296 | 297 | | |
297 | 298 | | |
298 | 299 | | |
| |||
0 commit comments