Skip to content

Commit da89c7c

Browse files
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

File tree

‎datafusion/functions-nested/benches/array_sort.rs‎

Lines changed: 48 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ use arrow::array::{ArrayRef, BooleanBufferBuilder, Int32Array, ListArray, String
2222
use arrow::buffer::{NullBuffer, OffsetBuffer};
2323
use arrow::datatypes::{DataType, Field};
2424
use criterion::{BenchmarkId, Criterion, criterion_group, criterion_main};
25+
use datafusion_common::ScalarValue;
2526
use datafusion_common::config::ConfigOptions;
2627
use datafusion_expr::{ColumnarValue, ScalarFunctionArgs, ScalarUDFImpl};
2728
use datafusion_functions_nested::sort::ArraySort;
@@ -119,9 +120,25 @@ fn create_string_list_array(num_rows: usize, elements_per_row: usize) -> ArrayRe
119120
}
120121

121122
fn invoke_array_sort(udf: &ArraySort, array: &ArrayRef) -> ColumnarValue {
123+
invoke_array_sort_with_order(udf, array, None)
124+
}
125+
126+
/// `order` is the optional second argument (`"ASC"` / `"DESC"`); `None` leaves
127+
/// `array_sort` with its default (ascending) ordering.
128+
fn invoke_array_sort_with_order(
129+
udf: &ArraySort,
130+
array: &ArrayRef,
131+
order: Option<&str>,
132+
) -> ColumnarValue {
133+
let mut args = vec![ColumnarValue::Array(Arc::clone(array))];
134+
let mut arg_fields = vec![Field::new("arr", array.data_type().clone(), true).into()];
135+
if let Some(order) = order {
136+
args.push(ColumnarValue::Scalar(ScalarValue::from(order)));
137+
arg_fields.push(Field::new("order", DataType::Utf8, true).into());
138+
}
122139
udf.invoke_with_args(ScalarFunctionArgs {
123-
args: vec![ColumnarValue::Array(Arc::clone(array))],
124-
arg_fields: vec![Field::new("arr", array.data_type().clone(), true).into()],
140+
args,
141+
arg_fields,
125142
number_rows: array.len(),
126143
return_field: Field::new("result", array.data_type().clone(), true).into(),
127144
config_options: Arc::new(ConfigOptions::default()),
@@ -149,6 +166,21 @@ fn bench_array_sort(c: &mut Criterion) {
149166
);
150167
}
151168

169+
// Same shapes, descending: `sort_row` sorts ascending and reverses, so this
170+
// measures the cost of that extra pass.
171+
for &elements_per_row in &[5, 20, 100, 1000] {
172+
let array = create_int32_list_array(NUM_ROWS, elements_per_row, false);
173+
group.bench_with_input(
174+
BenchmarkId::new("int32_desc", elements_per_row),
175+
&elements_per_row,
176+
|b, _| {
177+
b.iter(|| {
178+
black_box(invoke_array_sort_with_order(&udf, &array, Some("DESC")));
179+
});
180+
},
181+
);
182+
}
183+
152184
// Int32 with nulls in the outer list (10% null rows), single size
153185
{
154186
let array = create_int32_list_array(NUM_ROWS, 50, true);
@@ -174,6 +206,20 @@ fn bench_array_sort(c: &mut Criterion) {
174206
);
175207
}
176208

209+
for &elements_per_row in &[5, 20, 100, 1000] {
210+
let array =
211+
create_int32_list_array_with_null_elements(NUM_ROWS, elements_per_row);
212+
group.bench_with_input(
213+
BenchmarkId::new("int32_null_elements_desc", elements_per_row),
214+
&elements_per_row,
215+
|b, _| {
216+
b.iter(|| {
217+
black_box(invoke_array_sort_with_order(&udf, &array, Some("DESC")));
218+
});
219+
},
220+
);
221+
}
222+
177223
// String arrays
178224
for &elements_per_row in &[5, 20, 100, 1000] {
179225
let array = create_string_list_array(NUM_ROWS, elements_per_row);

‎datafusion/functions-nested/src/array_has.rs‎

Lines changed: 23 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -18,9 +18,8 @@
1818
//! [`ScalarUDFImpl`] definitions for array_has, array_has_all and array_has_any functions.
1919
2020
use arrow::array::{
21-
Array, ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, AsArray, BooleanArray,
22-
BooleanBufferBuilder, Datum, MAX_INLINE_VIEW_LEN, PrimitiveArray, Scalar,
23-
StringArrayType, StringViewArray,
21+
Array, ArrayRef, ArrowNativeTypeOp, AsArray, BooleanArray, BooleanBufferBuilder,
22+
Datum, MAX_INLINE_VIEW_LEN, Scalar, StringArrayType, StringViewArray,
2423
};
2524
use arrow::buffer::{BooleanBuffer, NullBuffer, OffsetBuffer};
2625
use arrow::datatypes::DataType;
@@ -359,7 +358,7 @@ fn array_has_dispatch_for_array(
359358
None
360359
} else {
361360
downcast_primitive_array! {
362-
visible_values => {
361+
visible_values, needle => {
363362
// The element-null path makes several passes over the values, so
364363
// past a large average list length the per-row `eq` kernel is
365364
// faster -- bail to it. The single-pass all-valid path has no such
@@ -371,25 +370,28 @@ fn array_has_dispatch_for_array(
371370
{
372371
None
373372
} else {
374-
Some(array_has_array_primitive(
375-
visible_values, needle, &offsets,
373+
Some(array_has_array_native(
374+
visible_values.values(),
375+
visible_values.nulls(),
376+
needle.values(),
377+
&offsets,
376378
combined_nulls.as_ref(),
377379
))
378380
}
379-
},
380-
DataType::Utf8 => Some(array_has_array_string(
381+
}
382+
(DataType::Utf8, _) => Some(array_has_array_string(
381383
visible_values.as_string::<i32>(),
382384
needle.as_string::<i32>(),
383385
&offsets,
384386
combined_nulls.as_ref(),
385387
)),
386-
DataType::LargeUtf8 => Some(array_has_array_string(
388+
(DataType::LargeUtf8, _) => Some(array_has_array_string(
387389
visible_values.as_string::<i64>(),
388390
needle.as_string::<i64>(),
389391
&offsets,
390392
combined_nulls.as_ref(),
391393
)),
392-
DataType::Utf8View => Some(array_has_array_string_view(
394+
(DataType::Utf8View, _) => Some(array_has_array_string_view(
393395
visible_values.as_string_view(),
394396
needle.as_string_view(),
395397
&offsets,
@@ -430,21 +432,20 @@ const NULL_FAST_PATH_MAX_LEN: usize = 512;
430432
/// 2. Nulls: AND the equality bitmap with validity (a null slot's value is
431433
/// arbitrary), then reduce each row to "any bit set". Chunked to bound the
432434
/// expanded needle.
433-
fn array_has_array_primitive<T: ArrowPrimitiveType>(
434-
values: &PrimitiveArray<T>,
435-
needle: &dyn Array,
435+
///
436+
/// Generic over the native type alone -- the caller's `downcast_primitive_array!`
437+
/// peels off the Arrow type -- so `Int32`, `Date32` and `Time32` share a single
438+
/// instantiation instead of getting one each.
439+
fn array_has_array_native<N: ArrowNativeTypeOp>(
440+
value_slice: &[N],
441+
element_nulls: Option<&NullBuffer>,
442+
needle_slice: &[N],
436443
offsets: &[usize],
437444
combined_nulls: Option<&NullBuffer>,
438-
) -> BooleanBuffer
439-
where
440-
T::Native: ArrowNativeTypeOp,
441-
{
442-
let needle = needle.as_primitive::<T>();
445+
) -> BooleanBuffer {
443446
let num_rows = offsets.len() - 1;
444-
let value_slice = values.values();
445-
let needle_slice = needle.values();
446447

447-
let Some(element_nulls) = values.nulls() else {
448+
let Some(element_nulls) = element_nulls else {
448449
return BooleanBuffer::collect_bool(num_rows, |i| {
449450
if combined_nulls.is_some_and(|n| n.is_null(i)) {
450451
return false;
@@ -461,7 +462,7 @@ where
461462

462463
// Case 2 (see fn doc), chunked like the all/any kernels.
463464
let mut result = BooleanBufferBuilder::new(num_rows);
464-
let mut needle_expanded: Vec<T::Native> = Vec::new();
465+
let mut needle_expanded: Vec<N> = Vec::new();
465466
for chunk_start in (0..num_rows).step_by(ROW_CONVERSION_CHUNK_SIZE) {
466467
let chunk_end = (chunk_start + ROW_CONVERSION_CHUNK_SIZE).min(num_rows);
467468
let elem_start = offsets[chunk_start];

‎datafusion/functions-nested/src/min_max.rs‎

Lines changed: 7 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ use arrow::array::{
2121
Array, ArrayRef, ArrowNativeTypeOp, ArrowPrimitiveType, AsArray, GenericListArray,
2222
OffsetSizeTrait, PrimitiveBuilder, downcast_primitive,
2323
};
24+
use arrow::buffer::NullBuffer;
2425
use arrow::datatypes::DataType;
2526
use arrow::datatypes::DataType::{LargeList, List};
2627
use datafusion_common::Result;
@@ -263,7 +264,7 @@ fn primitive_array_min_max<O: OffsetSizeTrait, T: ArrowPrimitiveType>(
263264
match len {
264265
0 => None,
265266
_ if len < ARROW_COMPUTE_THRESHOLD => {
266-
scalar_min_max::<T>(values_slice, values_nulls, start, end, is_min)
267+
scalar_min_max(values_slice, values_nulls, start, end, is_min)
267268
}
268269
_ => {
269270
let slice = values_array.slice(start, len);
@@ -285,14 +286,14 @@ fn primitive_array_min_max<O: OffsetSizeTrait, T: ArrowPrimitiveType>(
285286
/// Computes min or max for a single list row by directly scanning a slice of
286287
/// the flat values buffer.
287288
#[inline]
288-
fn scalar_min_max<T: ArrowPrimitiveType>(
289-
values_slice: &[T::Native],
290-
values_nulls: Option<&arrow::buffer::NullBuffer>,
289+
fn scalar_min_max<N: ArrowNativeTypeOp>(
290+
values_slice: &[N],
291+
values_nulls: Option<&NullBuffer>,
291292
start: usize,
292293
end: usize,
293294
is_min: bool,
294-
) -> Option<T::Native> {
295-
let mut best: Option<T::Native> = None;
295+
) -> Option<N> {
296+
let mut best: Option<N> = None;
296297
for (i, &val) in values_slice[start..end].iter().enumerate() {
297298
if let Some(nulls) = values_nulls
298299
&& !nulls.is_valid(start + i)

0 commit comments

Comments
 (0)