mbutrovich commented on code in PR #7658:
URL: https://github.com/apache/datafusion-comet/pull/7658#discussion_r4592405387


##########
native/spark-expr/benches/check_overflow.rs:
##########
@@ -85,6 +95,9 @@ fn criterion_benchmark(c: &mut Criterion) {
     c.bench_function("check_overflow: ansi no overflow", |b| {
         b.iter(|| black_box(ansi.evaluate(black_box(&no_overflow)).unwrap()))
     });
+    c.bench_function("check_overflow: ansi no overflow, with nulls", |b| {
+        b.iter(|| 
black_box(ansi.evaluate(black_box(&no_overflow_nulls)).unwrap()))
+    });

Review Comment:
   Could we add a shape for the scan's worst case? Both `sparse overflow` and 
`dense overflow` put an overflow at row 0, because `build` tests `i % 
overflow_every == 0`, so the scan stops in the first chunk. The costliest input 
for this design is one overflow near the end of the batch: the scan reads every 
chunk, and then `null_if_overflow_precision` reads the batch again. 
apache/arrow-rs#12058 and apache/arrow-rs#12062 use the same 
one-pass-then-fallback design without stopping early, so every overflow case 
they benchmark pays for the full pass plus the fallback, and they report that 
cost. Could you add this shape's numbers to the description? It needs `use 
arrow::compute::concat_batches;` at the top.
   
   ```suggestion
       c.bench_function("check_overflow: ansi no overflow, with nulls", |b| {
           b.iter(|| 
black_box(ansi.evaluate(black_box(&no_overflow_nulls)).unwrap()))
       });
   
       // One overflow in the last row, so the scan reads the whole batch 
before the slow path runs.
       // `sparse overflow` and `dense overflow` overflow at row 0 and stop in 
the first chunk.
       let head = build(size - 1, 0, 0);
       let last_row_overflow = concat_batches(&head.schema(), [&head, &build(1, 
0, 1)]).unwrap();
       c.bench_function("check_overflow: last row overflow", |b| {
           b.iter(|| 
black_box(legacy.evaluate(black_box(&last_row_overflow)).unwrap()))
       });
   ```



##########
native/spark-expr/src/math_funcs/internal/checkoverflow.rs:
##########
@@ -249,6 +248,38 @@ impl PhysicalExpr for CheckOverflow {
     }
 }
 
+/// Values per chunk in the no-null scan of [`fits_precision`].
+const FITS_PRECISION_CHUNK: usize = 64;
+
+/// Whether every non-null value of `array` fits `precision`, the check that
+/// `Decimal128Type::is_valid_decimal_precision` makes for one value.
+#[inline]
+fn fits_precision(array: &Decimal128Array, precision: u8) -> bool {
+    let bounds = (
+        MIN_DECIMAL128_FOR_EACH_PRECISION.get(precision as usize),
+        MAX_DECIMAL128_FOR_EACH_PRECISION.get(precision as usize),
+    );
+    match bounds {
+        (Some(&min), Some(&max)) if array.null_count() == 0 => {
+            // Without nulls every slot holds a value, so scan the values 
buffer directly instead
+            // of reading the null bitmap per slot. Shifting by `min` turns 
the two bounds checks
+            // into one unsigned comparison. The check is branchless within a 
chunk, which lets
+            // the compiler unroll it, and the scan still stops at the first 
chunk that holds an
+            // overflow.
+            let range = max.wrapping_sub(min) as u128;
+            array.values().chunks(FITS_PRECISION_CHUNK).all(|chunk| {
+                chunk.iter().fold(true, |fits, &v| {
+                    fits & (v.wrapping_sub(min) as u128 <= range)
+                })
+            })
+        }
+        _ => array
+            .iter()
+            .flatten()
+            .all(|v| Decimal128Type::is_valid_decimal_precision(v, precision)),
+    }

Review Comment:
   Could the values scan cover arrays with nulls too? A null slot can hold any 
value, so when some slot doesn't fit, we can fall back to the existing scan 
that skips nulls, and only then. apache/arrow-rs#12062 does the same for the 
checked decimal kernels in 
[`unless_valid_overflow`](https://github.com/apache/arrow-rs/blob/aee0225d3937ac7ee79b406c5b19eb76d9f94288/arrow-arith/src/numeric.rs#L468-L485):
 it runs over every slot and reads the validity bits only when something was 
flagged.
   
   Builders write 0 into null slots, and 0 fits every precision. So the `with 
nulls` and `dense nulls` shapes, which this PR leaves at 4.76 us and 3.88 us, 
would take the same scan as `no overflow`. A batch whose null slots hold values 
that don't fit pays for the values scan up to that chunk, then for today's 
scan. The last test in my comment on the tests covers that case. Could you 
rerun the null shapes with this change and add the numbers to the description?
   
   ```suggestion
   /// Values per chunk in the scan of [`fits_precision`].
   const FITS_PRECISION_CHUNK: usize = 64;
   
   /// Whether every non-null value of `array` fits `precision`, the check that
   /// `Decimal128Type::is_valid_decimal_precision` makes for one value.
   #[inline]
   fn fits_precision(array: &Decimal128Array, precision: u8) -> bool {
       let bounds = (
           MIN_DECIMAL128_FOR_EACH_PRECISION.get(precision as usize),
           MAX_DECIMAL128_FOR_EACH_PRECISION.get(precision as usize),
       );
       let valid_fit = || {
           array
               .iter()
               .flatten()
               .all(|v| Decimal128Type::is_valid_decimal_precision(v, 
precision))
       };
       match bounds {
           (Some(&min), Some(&max)) => {
               // Scan every slot of the values buffer, null or not, instead of 
reading the null
               // bitmap per slot. Shifting by `min` turns the two bounds 
checks into one unsigned
               // comparison, and the scan stops at the first chunk that holds 
a value that doesn't
               // fit.
               let range = max.wrapping_sub(min) as u128;
               let all_fit = 
array.values().chunks(FITS_PRECISION_CHUNK).all(|chunk| {
                   chunk.iter().fold(true, |fits, &v| {
                       fits & (v.wrapping_sub(min) as u128 <= range)
                   })
               });
               // A null slot can hold any value, so a value that doesn't fit 
only counts if the
               // scan that skips nulls finds one too.
               all_fit || (array.null_count() > 0 && valid_fit())
           }
           _ => valid_fit(),
       }
   ```



##########
native/spark-expr/src/math_funcs/internal/checkoverflow.rs:
##########
@@ -249,6 +248,38 @@ impl PhysicalExpr for CheckOverflow {
     }
 }
 
+/// Values per chunk in the no-null scan of [`fits_precision`].
+const FITS_PRECISION_CHUNK: usize = 64;
+
+/// Whether every non-null value of `array` fits `precision`, the check that
+/// `Decimal128Type::is_valid_decimal_precision` makes for one value.
+#[inline]
+fn fits_precision(array: &Decimal128Array, precision: u8) -> bool {

Review Comment:
   Should this scan also go into arrow-rs, in 
[`PrimitiveArray::validate_decimal_precision`](https://github.com/apache/arrow-rs/blob/4f1ed42f7a1fb76d090ec1351cfdb6e904f59f0b/arrow-array/src/array/primitive_array.rs#L1708-L1723)?
 It makes the same check with the same per-slot `is_valid` lookup and early 
return that this PR removes here. The vectorized arithmetic in 
apache/arrow-rs#12058 and apache/arrow-rs#12062 detects only `i128` overflow 
and doesn't check precision, so it won't replace this check when it lands.
   
   #5104 lists `CheckOverflow` as hand-rolled on purpose, because ANSI errors 
need the offending value. This PR splits the scan, which returns only a `bool`, 
from the error path that finds the value, so that reason no longer covers the 
scan.
   
   I'd land the scan here first and settle its design in this PR, including the 
null handling and loop form from my other comments. Then the arrow-rs change 
can port the same code instead of reopening those choices. Could you file the 
arrow-rs issue now and link it from a comment on `fits_precision`? Once Comet's 
arrow version includes the upstream change, `fits_precision` can become 
`validate_decimal_precision(precision).is_ok()`, and DataFusion and other 
arrow-rs callers get the faster check too.



##########
native/spark-expr/src/math_funcs/internal/checkoverflow.rs:
##########
@@ -249,6 +248,38 @@ impl PhysicalExpr for CheckOverflow {
     }
 }
 
+/// Values per chunk in the no-null scan of [`fits_precision`].
+const FITS_PRECISION_CHUNK: usize = 64;
+
+/// Whether every non-null value of `array` fits `precision`, the check that
+/// `Decimal128Type::is_valid_decimal_precision` makes for one value.
+#[inline]
+fn fits_precision(array: &Decimal128Array, precision: u8) -> bool {
+    let bounds = (
+        MIN_DECIMAL128_FOR_EACH_PRECISION.get(precision as usize),
+        MAX_DECIMAL128_FOR_EACH_PRECISION.get(precision as usize),
+    );
+    match bounds {
+        (Some(&min), Some(&max)) if array.null_count() == 0 => {
+            // Without nulls every slot holds a value, so scan the values 
buffer directly instead
+            // of reading the null bitmap per slot. Shifting by `min` turns 
the two bounds checks
+            // into one unsigned comparison. The check is branchless within a 
chunk, which lets
+            // the compiler unroll it, and the scan still stops at the first 
chunk that holds an
+            // overflow.
+            let range = max.wrapping_sub(min) as u128;
+            array.values().chunks(FITS_PRECISION_CHUNK).all(|chunk| {
+                chunk.iter().fold(true, |fits, &v| {
+                    fits & (v.wrapping_sub(min) as u128 <= range)
+                })
+            })

Review Comment:
   The comment says the branchless chunk lets the compiler unroll the loop. On 
aarch64 with Comet's [`release` 
profile](https://github.com/apache/datafusion-comet/blob/83514229e195880569cc5d9d07f51e1d096bf594/native/Cargo.toml#L93-L98)
 (thin LTO, `codegen-units = 1`), which `cargo bench` inherits, LLVM vectorizes 
the `&` reduction instead. In the linked `check_overflow` bench binary at this 
commit, the main loop takes 32 values per iteration in 396 instructions, and 88 
of those are stack loads and stores. Each compare stays scalar, and only its 
flag moves into a NEON register:
   
   ```asm
   ldr    x8, [x0, #0x80]    ; low half of a value
   subs   x8, x8, x9         ; minus the low half of min
   str    x8, [sp, #0x108]   ; spilled
   ...
   cmp    x10, x5            ; range against v - min, 128 bits
   sbcs   xzr, x11, x26
   cset   w8, hs             ; fits
   sbfx   x8, x8, #0, #1
   dup.2d v4, x8             ; flag into a vector lane for the `&`
   ```
   
   That's about 12 instructions per value plus the spills, against 9 in the 
same binary's one-value remainder loop. On x86-64 the fold unrolls two values 
per iteration at 11 instructions per value.
   
   Could you benchmark the fold against a plain `array.values().iter().all(|&v| 
v.wrapping_sub(min) as u128 <= range)` on both architectures? That compiles to 
a scalar loop with one branch that isn't taken until a value doesn't fit: 10 
instructions per value on aarch64 and 12 on x86-64, with no spills. In the 
no-overflow case that branch is always predicted correctly, so going branchless 
doesn't save anything there. If it's as fast, it drops `FITS_PRECISION_CHUNK` 
and the fold. Either way, the comment should describe what the compiler does.



##########
native/spark-expr/src/math_funcs/internal/checkoverflow.rs:
##########
@@ -509,4 +540,22 @@ mod tests {
         let out = eval_array(&array_check_overflow(3, 0, false), &batch);
         assert_eq!(out.iter().collect::<Vec<_>>(), vec![Some(999), None]);
     }
+
+    #[test]
+    fn test_array_no_nulls_overflow_past_first_chunk_and_sliced() {
+        // The no-null scan reads the values buffer in chunks, so an overflow 
in a later chunk
+        // must still be found, and a sliced array must only be checked within 
its slice.
+        let mut values = vec![Some(5); 200];
+        values[130] = Some(1000);
+        let batch = array_batch(values, 38, 0);
+        let out = eval_array(&array_check_overflow(3, 0, false), &batch);
+        assert_eq!(out.null_count(), 1);
+        assert!(out.is_null(130));
+
+        // Starts right after the overflowing value, so the slice has a 
non-zero offset.
+        let sliced = batch.slice(131, 69);
+        let out = eval_array(&array_check_overflow(3, 0, true), &sliced);
+        assert_eq!(out.len(), 69);
+        assert_eq!(out.null_count(), 0);
+    }
 }

Review Comment:
   Could we add tests that move the value that doesn't fit through every row, 
and that cover the edges of the shift? The compiled scan handles each part of 
the batch with different code: on aarch64 a 32-value vector loop, an 8-value 
loop, and a one-value loop, and on x86-64 a two-value unrolled loop and a 
remainder. The new test checks one position, row 130. apache/arrow-rs#12058 
sweeps the overflowing row through every lane for the same reason.
   
   The array tests also all use precision 3, so nothing checks precision 38, 
where `v - min` wraps for `i128::MAX` and `i128::MIN`. The last test covers a 
null slot that holds a value that doesn't fit, which the suggestion on 
`fits_precision` makes reachable.
   
   ```suggestion
       }
   
       #[test]
       fn test_array_no_nulls_overflow_at_every_position() {
           // The compiled scan handles the main loop, the chunk boundaries, 
and the remainder
           // differently, so move one value that doesn't fit through every 
row. 203 rows leave a
           // last chunk of 11 values.
           for overflow in [1000, -1000] {
               for i in 0..203 {
                   let mut values = vec![Some(5); 203];
                   values[i] = Some(overflow);
                   let batch = array_batch(values, 38, 0);
                   let out = eval_array(&array_check_overflow(3, 0, false), 
&batch);
                   assert_eq!(out.null_count(), 1, "{overflow} at {i}");
                   assert!(out.is_null(i), "{overflow} at {i}");
                   let ansi = array_check_overflow(3, 0, true).evaluate(&batch);
                   assert!(ansi.is_err(), "{overflow} at {i}");
               }
           }
       }
   
       #[test]
       fn test_array_no_nulls_precision_38_extremes() {
           // The scan shifts by the precision's minimum and compares unsigned, 
so check the values
           // where that shift wraps, at the widest precision.
           let max = MAX_DECIMAL128_FOR_EACH_PRECISION[38];
           let min = MIN_DECIMAL128_FOR_EACH_PRECISION[38];
           let fits = array_batch(vec![Some(max), Some(min), Some(0)], 38, 0);
           let out = eval_array(&array_check_overflow(38, 0, true), &fits);
           assert_eq!(out.null_count(), 0);
           for v in [max + 1, min - 1, i128::MAX, i128::MIN] {
               let batch = array_batch(vec![Some(0), Some(v)], 38, 0);
               let out = eval_array(&array_check_overflow(38, 0, false), 
&batch);
               assert!(out.is_null(1), "{v}");
               let ansi = array_check_overflow(38, 0, true).evaluate(&batch);
               assert!(ansi.is_err(), "{v}");
           }
       }
   
       #[test]
       fn test_array_null_slot_out_of_range_is_ignored() {
           // A null slot can hold any value. One that doesn't fit the 
precision must not null out
           // valid values or raise an ANSI error.
           use arrow::buffer::NullBuffer;
   
           let nulls = NullBuffer::from(vec![true, false, true]);
           let arr = Decimal128Array::new(vec![5, 1000, 7].into(), Some(nulls))
               .with_precision_and_scale(38, 0)
               .unwrap();
           let schema = Schema::new(vec![Field::new("d", 
arr.data_type().clone(), true)]);
           let batch = RecordBatch::try_new(Arc::new(schema), 
vec![Arc::new(arr)]).unwrap();
           for fail_on_error in [false, true] {
               let out = eval_array(&array_check_overflow(3, 0, fail_on_error), 
&batch);
               assert_eq!(out.iter().collect::<Vec<_>>(), vec![Some(5), None, 
Some(7)]);
           }
       }
   }
   ```



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

Reply via email to