This is an automated email from the ASF dual-hosted git repository.
alamb pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
The following commit(s) were added to refs/heads/main by this push:
new 5a2db27df7 perf(arrow-cmp): Speed up eq/neq of a byte-view array
against a short scalar (#10689)
5a2db27df7 is described below
commit 5a2db27df70abf6d9ce09403b6b33248503a0092
Author: Giladi <[email protected]>
AuthorDate: Tue Aug 18 22:25:01 2026 +0300
perf(arrow-cmp): Speed up eq/neq of a byte-view array against a short
scalar (#10689)
# Which issue does this PR close?
- Closes #10688
# Rationale for this change
col = 'x' / col <> '' over a Utf8View or BinaryView column is one of the
hottest kernels in an analytical scan, and today the compare walks the
full 128-bit view through a sequence of branches even when the scalar is
small.
For a short constant almost none of that is needed. A constant of four
bytes or fewer is described entirely by a view's low 64 bits, which hold
the length and the first four bytes, so masking those and comparing them
against the constant resolved once up front settles a row with a single
narrow integer compare over the flat &[u128] view slice. That loop is
branch-free and vectorizes.
# What changes are included in this PR?
- arrow-ord: an eq_inline_scalar helper, and a guard in compare_op that
routes to it for Op::Equal / Op::NotEqual when one side is a scalar.
Everything else falls through to the existing generic path untouched:
dictionary and REE inputs, a null scalar (which the fast path's null
handling cannot express), non-view types, and constants longer than four
bytes.
- arrow: a stringview_scalar_eq benchmark group in comparison_kernels.rs
sweeping three sizes, so the cache-resident and bandwidth-bound ends of
the range are both visible.
Constants wider than four bytes are deliberately left alone. They need
the whole 128-bit view, and comparing that measured slower than the
generic path's early exit on a length mismatch (a six-byte constant
regressed 11.8%), so the cap is a measured limit rather than an
arbitrary one.
# Are these changes tested?
Yes. Three tests are added alongside the existing byte-view comparison
tests:
- test_byte_view_eq_null_scalar — a null constant makes every row null,
covering the shape the fast path declines.
- test_byte_view_eq_null_row — null rows in the values array stay null.
- test_byte_view_eq_scalar_either_side — the scalar on the left gives
the same answer as on the right.
The existing arrow-ord suite (272 tests) passes unchanged.
Benchmark evidence, cargo bench --bench comparison_kernels --
stringview_scalar_eq on an Intel Xeon @ 2.80GHz (66 MiB L3):
┌───────────┬─────────┬─────────┬─────────┬────────┐
│ rows │ views │ before │ after │ change │
├───────────┼─────────┼─────────┼─────────┼────────┤
│ 65,536 │ 1 MiB │ 111.4us │ 47.7us │ -57.2% │
├───────────┼─────────┼─────────┼─────────┼────────┤
│ 1,048,576 │ 16 MiB │ 2.04ms │ 983.2us │ -51.7% │
├───────────┼─────────┼─────────┼─────────┼────────┤
│ 8,388,608 │ 128 MiB │ 19.71ms │ 14.85ms │ -24.7% │
└───────────┴─────────┴─────────┴─────────┴────────┘
The win narrows at the largest size, where the views no longer fit in
cache and the kernel becomes bound by memory bandwidth rather than by
the comparison.
# Are there any user-facing changes?
Nope :)
---------
Co-authored-by: Andrew Lamb <[email protected]>
---
arrow-ord/src/cmp.rs | 99 ++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 99 insertions(+)
diff --git a/arrow-ord/src/cmp.rs b/arrow-ord/src/cmp.rs
index ad99b09e0e..6c9d6115c6 100644
--- a/arrow-ord/src/cmp.rs
+++ b/arrow-ord/src/cmp.rs
@@ -274,6 +274,30 @@ fn compare_op(op: Op, lhs: &dyn Datum, rhs: &dyn Datum) ->
Result<BooleanArray,
ree: r_ree_info.as_ref().map(|(_, info)| info),
};
+ // Special case: equality against a short scalar that fits the inlined
prefix
+ // of a view array, which reduces the comparison to a scan of fixed-width
+ // integers
+ if matches!(op, Op::Equal | Op::NotEqual)
+ && l_side.dict.is_none()
+ && r_side.dict.is_none()
+ && l_side.ree.is_none()
+ && r_side.ree.is_none()
+ {
+ let sides = match (l_s, r_s) {
+ (false, true) => Some((l, r, &l_nulls, &r_nulls)),
+ (true, false) => Some((r, l, &r_nulls, &l_nulls)),
+ _ => None,
+ };
+ // A null constant makes every row null, which this path cannot express
+ if let Some((values, scalar, values_nulls, scalar_nulls)) = sides
+ && scalar_nulls.as_ref().is_none_or(|n| n.null_count() == 0)
+ && let Some(mask) = eq_inline_scalar(values, scalar, l_t,
matches!(op, Op::NotEqual))
+ {
+ let nulls = values_nulls.clone().filter(|n| n.null_count() > 0);
+ return Ok(BooleanArray::new(mask, nulls));
+ }
+ }
+
// Defer computation as may not be necessary
let values = || -> BooleanBuffer {
let d = downcast_primitive_array! {
@@ -370,6 +394,46 @@ impl SideInfo<'_> {
}
}
+/// Longest constant whose length and bytes both fit a view's low 64 bits
+const MAX_LOW_HALF_LEN: u32 = 4;
+
+/// Attempts a special case: comparing every value of a byte-view array
against a
+/// short constant that fits entirely within a view's inlined prefix
+///
+/// Returns `None` for any other shape, which the caller then handles on the
+/// generic path.
+fn eq_inline_scalar(
+ l: &dyn Array,
+ r: &dyn Array,
+ data_type: &DataType,
+ negate: bool,
+) -> Option<BooleanBuffer> {
+ let (values, needle) = match data_type {
+ DataType::Utf8View => (
+ l.as_string_view().views(),
+ *r.as_string_view().views().first()?,
+ ),
+ DataType::BinaryView => (
+ l.as_binary_view().views(),
+ *r.as_binary_view().views().first()?,
+ ),
+ _ => return None,
+ };
+ // Only a constant whose length and bytes fit the view's low half. Wider
+ // constants need the whole 128-bit view, and comparing that is slower than
+ // the generic path's early exit on a length mismatch.
+ let needle_len = needle as u32;
+ if needle_len > MAX_LOW_HALF_LEN {
+ return None;
+ }
+ let significant = u64::MAX >> (32 - needle_len * 8);
+ let needle = needle as u64 & significant;
+ Some(collect_bool(values.len(), negate, |idx| {
+ let view = unsafe { *values.get_unchecked(idx) };
+ view as u64 & significant == needle
+ }))
+}
+
/// Perform a potentially vectored `op` on the provided `ArrayOrd`
fn apply<T: ArrayOrd>(
op: Op,
@@ -1137,6 +1201,41 @@ mod tests {
);
}
+ /// A null constant makes every row null, whatever the values are
+ #[test]
+ fn test_byte_view_eq_null_scalar() {
+ let a = arrow_array::StringViewArray::from(vec![Some(""), Some("x"),
None]);
+ let scalar = arrow_array::StringViewArray::new_null(1);
+
+ let r = neq(&a, &Scalar::new(&scalar)).unwrap();
+
+ assert_eq!(r.null_count(), 3);
+ }
+
+ /// A null row's view is arbitrary, so validity decides, not bytes
+ #[test]
+ fn test_byte_view_eq_null_row() {
+ let a = arrow_array::StringViewArray::from(vec![Some(""), Some("x"),
None]);
+ let scalar = arrow_array::StringViewArray::from(vec![""]);
+
+ let r = neq(&a, &Scalar::new(&scalar)).unwrap();
+
+ assert!(!r.value(0));
+ assert!(r.value(1));
+ assert!(r.is_null(2));
+ }
+
+ /// The constant may sit on either side; equality is symmetric
+ #[test]
+ fn test_byte_view_eq_scalar_either_side() {
+ let a =
+ arrow_array::StringViewArray::from(vec![Some(""), Some("xxxx"),
Some("xxxxxxxxxxxxx")]);
+ let scalar =
Scalar::new(arrow_array::StringViewArray::from(vec!["xxxx"]));
+
+ assert_eq!(eq(&a, &scalar).unwrap(), eq(&scalar, &a).unwrap());
+ assert_eq!(eq(&a, &scalar).unwrap().true_count(), 1);
+ }
+
#[test]
fn test_string_view_eq() {
let a = arrow_array::StringViewArray::from(vec