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]