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]

Reply via email to