comphead opened a new issue, #12368: URL: https://github.com/apache/arrow-rs/issues/12368
### Is your feature request related to a problem or challenge? `PrimitiveArray::validate_decimal_precision` returns the error for the first valid value that doesn't fit `precision`. Its loop reads the validity bit of every slot and calls `T::validate_decimal_precision` for every valid one ([`primitive_array.rs` L1708-L1723](https://github.com/apache/arrow-rs/blob/1b42833a2105efdbb757108c7d15233aa35e9bf5/arrow-array/src/array/primitive_array.rs#L1708-L1723)). The four `DecimalType::validate_decimal_precision` implementations are not `#[inline]` ([`types.rs` L1555-L1557](https://github.com/apache/arrow-rs/blob/1b42833a2105efdbb757108c7d15233aa35e9bf5/arrow-array/src/types.rs#L1555-L1557) for `Decimal128Type`), so without LTO every valid value is an out-of-line call that returns a `Result<(), ArrowError>` through memory. #12342 made `is_valid_decimal_precision` `#[inline]` and left this loop as it was. #12326 noted these implementations but did not measure them. For 8192 `Decimal128` values that fit, the loop takes 11.3 µs, and a scan of the values buffer takes 3.4 µs (measurements below). DataFusion Comet's `CheckOverflow` makes the same check on decimal arithmetic results. apache/datafusion-comet#7658 replaces its scan with one over the values buffer. Its review asked for the same scan here, so that Comet can call `validate_decimal_precision(precision).is_ok()` instead of keeping its own copy. ### Describe the solution you'd like Scan the values buffer, null slots included, and build the error only for a value that doesn't fit: ```rust let values = self.values(); let nulls = self.nulls(); let mut start = 0; while let Some(offset) = values[start..] .iter() .position(|&v| !T::is_valid_decimal_precision(v, precision)) { let index = start + offset; if nulls.is_none_or(|n| n.is_valid(index)) { return T::validate_decimal_precision(values[index], precision, self.scale()); } start = index + 1; } Ok(()) ``` The precision-below-scale check before the loop stays. A null slot can hold any value, so the scan reads a validity bit only at a value that doesn't fit, and resumes after that slot when it is null. It finds the same first valid value as the current loop, so the error does not change. For `Decimal32`, `Decimal64` and `Decimal128`, the bounds check can also shift by the precision's minimum and compare unsigned, as Comet does. That makes the `Decimal128` scan another 12% to 14% faster below. It needs either a per-type hook or a change to `is_validate_decimal_precision` and its `Decimal32` and `Decimal64` counterparts, which arrow-cast also calls. I have not measured the second option. ```rust let range = max.wrapping_sub(min) as u128; values.iter().position(|&v| v.wrapping_sub(min) as u128 > range) ``` The `decimal_overflow` bench also needs shapes whose values fit, see below. ### Describe alternatives you've considered `#[inline]` on the four `validate_decimal_precision` implementations, as #12342 did for `is_valid_decimal_precision`. Without nulls it is as fast as the scan. With nulls the loop still reads every validity bit, and the scan is 27% faster for `Decimal128` and 11% for `Decimal256`. It would also inline the per-value calls at the 190 arrow-cast call sites that #12326 counted, and #12342 found that inlining into those kernels made some casts slower until the kernels changed too. ### Additional context #### The bench doesn't reach the scan `decimal_overflow`'s `validate_decimal_precision_128` and `validate_decimal_precision_256` take 26 ns. The builders give the default `Decimal128(38, 10)` and `Decimal256(76, 10)` types, and since #12101 `validate_decimal_precision(8)` returns `Decimal precision 8 is less than scale 10` before it reads a value. Row 0 is also `i128::MAX`, so before #12101 the loop stopped at the first row. #### Measurements Built from 1b42833 on macOS aarch64 (Apple M5 Max) with rustc 1.99.1 and the default `bench` profile, which has no LTO. Each shape has 8192 values at scale 2, checked against precision 10, as in Comet's `check_overflow` bench. `nulls` makes every 17th row null, and `last row overflow` puts one value that doesn't fit in the last row. The scans are free functions in the bench file. `values_scan` is generic, as the method would be, and `shifted_scan` is the `Decimal128` form. Criterion medians of four rounds that alternated the `main` build and a build with `#[inline]` on the four `validate_decimal_precision` implementations, with `--warm-up-time 1 --measurement-time 3`. The scan columns come from the `main` build. The same functions in the other build were within 1.1%. | Type | Shape | `main` | `#[inline]` only | Scan | Scan, shifted compare | | --- | --- | ---: | ---: | ---: | ---: | | `Decimal128` | fits | 11.31 µs | 3.34 µs | 3.36 µs | 2.89 µs | | `Decimal128` | fits, nulls | 14.34 µs | 4.66 µs | 3.38 µs | 2.97 µs | | `Decimal128` | last row overflow | 11.50 µs | 3.44 µs | 3.46 µs | 3.03 µs | | `Decimal256` | fits | 13.97 µs | 6.27 µs | 6.24 µs | n/a | | `Decimal256` | fits, nulls | 16.78 µs | 7.01 µs | 6.27 µs | n/a | Before it runs, the bench checks that both scans return what `validate_decimal_precision` returns, error text included, on every shape and on an array whose null slot holds a value that doesn't fit. <details><summary>Bench additions</summary> ```rust use arrow_array::types::{Decimal128Type, DecimalType}; use arrow_array::{Array, Decimal128Array, Decimal256Array, PrimitiveArray}; use arrow_buffer::i256; use arrow_data::decimal::{MAX_DECIMAL128_FOR_EACH_PRECISION, MIN_DECIMAL128_FOR_EACH_PRECISION}; use arrow_schema::ArrowError; use criterion::*; use std::hint; // The existing `criterion_benchmark` stays as it is. /// A port of the scan into `PrimitiveArray::validate_decimal_precision`. It reads every slot of /// the values buffer, null or not, reads a validity bit only at a value that doesn't fit, and /// resumes after it when that slot is null. The first valid value that doesn't fit gets the same /// error as `main`, since `main` also returns at the first one. fn values_scan<T: DecimalType>(array: &PrimitiveArray<T>, precision: u8) -> Result<(), ArrowError> { if array.scale() > 0 && precision < array.scale() as u8 { return array.validate_decimal_precision(precision); } let values = array.values(); let nulls = array.nulls(); let mut start = 0; while let Some(offset) = values[start..] .iter() .position(|&v| !T::is_valid_decimal_precision(v, precision)) { let index = start + offset; if nulls.is_none_or(|n| n.is_valid(index)) { return T::validate_decimal_precision(values[index], precision, array.scale()); } start = index + 1; } Ok(()) } /// The same scan with Comet's bounds check: shifting by the minimum turns the two bounds checks /// into one unsigned comparison. fn shifted_scan(array: &Decimal128Array, precision: u8) -> Result<(), ArrowError> { let bounds = ( MIN_DECIMAL128_FOR_EACH_PRECISION.get(precision as usize), MAX_DECIMAL128_FOR_EACH_PRECISION.get(precision as usize), ); let (Some(&min), Some(&max)) = bounds else { return array.validate_decimal_precision(precision); }; if array.scale() > 0 && precision < array.scale() as u8 { return array.validate_decimal_precision(precision); } let range = max.wrapping_sub(min) as u128; let values = array.values(); let nulls = array.nulls(); let mut start = 0; while let Some(offset) = values[start..] .iter() .position(|&v| v.wrapping_sub(min) as u128 > range) { let index = start + offset; if nulls.is_none_or(|n| n.is_valid(index)) { return Decimal128Type::validate_decimal_precision(values[index], precision, array.scale()); } start = index + 1; } Ok(()) } const PRECISION: u8 = 10; const OVERFLOW: i128 = 1_000_000_000_000; // 10^12 doesn't fit precision 10 /// Decimal128(38, 2) values that fit precision 10, as in Comet's `check_overflow` bench. /// `null_every`: null every Nth row (0 = none). `overflow_last`: make the last row 10^12. fn shape_128(len: usize, null_every: usize, overflow_last: bool) -> Decimal128Array { (0..len) .map(|i| { if null_every != 0 && i % null_every == 0 { None } else if overflow_last && i == len - 1 { Some(OVERFLOW) } else { Some((i as i128 % 100_000) * 100) } }) .collect::<Decimal128Array>() .with_precision_and_scale(38, 2) .unwrap() } fn shape_256(len: usize, null_every: usize, overflow_last: bool) -> Decimal256Array { shape_128(len, null_every, overflow_last) .iter() .map(|v| v.map(i256::from_i128)) .collect::<Decimal256Array>() .with_precision_and_scale(76, 2) .unwrap() } fn same<T: DecimalType>(array: &PrimitiveArray<T>, extra: Option<Result<(), ArrowError>>) { let main = array.validate_decimal_precision(PRECISION).map_err(|e| e.to_string()); let scan = values_scan(array, PRECISION).map_err(|e| e.to_string()); assert_eq!(main, scan); if let Some(extra) = extra { assert_eq!(main, extra.map_err(|e| e.to_string())); } } fn scan_benchmark(c: &mut Criterion) { let len = 8192; let shapes_128 = [ ("fits", shape_128(len, 0, false)), ("fits, nulls", shape_128(len, 17, false)), ("last row overflow", shape_128(len, 0, true)), ]; let shapes_256 = [ ("fits", shape_256(len, 0, false)), ("fits, nulls", shape_256(len, 17, false)), ]; // Sanity: the prototypes return what `validate_decimal_precision` returns, and a null slot // that doesn't fit is ignored by both. for (_, a) in &shapes_128 { same(a, Some(shifted_scan(a, PRECISION))); } for (_, a) in &shapes_256 { same(a, None); } let null_slot = { let a = shape_128(len, 17, false); let mut values = a.values().to_vec(); values[17 * 3] = OVERFLOW; Decimal128Array::new(values.into(), a.nulls().cloned()) .with_precision_and_scale(38, 2) .unwrap() }; assert!(null_slot.is_null(17 * 3)); same(&null_slot, Some(shifted_scan(&null_slot, PRECISION))); assert!(values_scan(&shapes_128[2].1, PRECISION).is_err()); for (name, a) in &shapes_128 { c.bench_function(&format!("128 {name}: validate_decimal_precision"), |b| { b.iter(|| hint::black_box(hint::black_box(a).validate_decimal_precision(PRECISION))) }); c.bench_function(&format!("128 {name}: values scan"), |b| { b.iter(|| hint::black_box(values_scan(hint::black_box(a), PRECISION))) }); c.bench_function(&format!("128 {name}: shifted scan"), |b| { b.iter(|| hint::black_box(shifted_scan(hint::black_box(a), PRECISION))) }); } for (name, a) in &shapes_256 { c.bench_function(&format!("256 {name}: validate_decimal_precision"), |b| { b.iter(|| hint::black_box(hint::black_box(a).validate_decimal_precision(PRECISION))) }); c.bench_function(&format!("256 {name}: values scan"), |b| { b.iter(|| hint::black_box(values_scan(hint::black_box(a), PRECISION))) }); } } criterion_group!(benches, criterion_benchmark, scan_benchmark); criterion_main!(benches); ``` </details> #### Disassembly In the `main` bench binary, this is the loop of `PrimitiveArray<Decimal128Type>::validate_decimal_precision` for an array without nulls: ``` ldp x0, x1, [x23], #0x10 // the value add x8, sp, #0x10 // the Result goes on the stack mov x2, x20 // precision mov x3, x21 // scale bl <Decimal128Type as DecimalType>::validate_decimal_precision ldr x8, [sp, #0x10] cmn x8, #0x1 // Ok? b.eq <loop> ``` Every call sets up a 240-byte frame and saves eight registers. With nulls, each slot also takes six instructions to read its validity bit before the call. The generic scan compiles to 13 instructions per value with no call, and the shifted compare to 11. #### Callers Inside arrow-rs only tests and the `decimal_overflow` bench call `PrimitiveArray::validate_decimal_precision`. DataFusion calls it only from test code ([`clustered.rs` L266](https://github.com/apache/datafusion/blob/904afffc731637c4c927c8e095ed07fb195a6c79/datafusion/physical-plan/src/aggregates/group_values/multi_group_by/clustered.rs#L266)). arrow-cast calls the per-value `DecimalType::validate_decimal_precision`, which this proposal does not change. The arrow-rs disassembly and benchmarks were collected with Claude Code. -- 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]
