This is an automated email from the ASF dual-hosted git repository.
Jefffrey 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 6f51fb1b33 perf(arrow-cast): gate Dictionary -> View fast path on
cardinality (#10436)
6f51fb1b33 is described below
commit 6f51fb1b333a55469a4ffb9c5d9bc740cb9c1d9e
Author: Abhishek <[email protected]>
AuthorDate: Tue Aug 18 10:32:57 2026 +0530
perf(arrow-cast): gate Dictionary -> View fast path on cardinality (#10436)
# Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and
enhancements and this helps us generate change logs for our releases.
You can link an issue to this PR using the GitHub syntax.
-->
- Closes #8985
Supersedes #9768, which I closed it implemented these fast paths
ungated, and benchmarking showed that made things significantly slower.
Details below.
# Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly
in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand
your changes and offer better suggestions for fixes.
-->
`dictionary_cast` can build a view array from a dictionary two ways:
- (a) `unpack_dictionary` builds one view per dictionary *value*, then
gathers with `take`
- (b) `view_from_dict_values` builds one view per *row* directly against
the values buffer
The comment above (b) says (a) "incurs unnecessary data copy of the
value buffer". That
isn't the case. `impl From<&GenericByteArray> for GenericByteViewArray`
reuses the buffer
(it only falls back to copying when the values exceed the `u32` offset a
view can hold),
and `take_byte_view` passes `data_buffers().to_vec()` through untouched.
Neither step
copies value data, so there was no copy to remove.
What the two actually trade is a bandwidth-bound `u128` gather in `take`
against a
per-row `make_view` that reads each row's payload out of the values
buffer. The gather
wins once rows reach roughly 0.6x the dictionary size so (b) is a large
pessimisation in
the common case, and only pays off when the dictionary is substantially
larger than the
array is long, where (a) spends most of its time building views no row
references.
This means the existing `Utf8 -> Utf8View` and `Binary -> BinaryView`
fast paths on main
are currently **5-8x slower** than `unpack_dictionary` at typical batch
shapes.
# What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it
is sometimes worth providing a summary of the individual changes in this
PR.
-->
- Gate the direct path on `keys.len() < values.len() / 2`; everything
else falls through
to `unpack_dictionary`. The measured crossover is near `rows ≈ 0.6 *
values`; the gate
switches short of it, at `rows = values / 2`, where the direct path is
still ahead by
15-30%. That margin covers the crossover moving with cache size or
microarchitecture.
Being wrong in that direction only forgoes a win; being wrong the other
way is a
regression on the common case.
- Extend the direct path to the remaining combinations #8985 asks for:
`LargeUtf8`/`LargeBinary` -> `Utf8View`/`BinaryView`, and the `Utf8` <->
`Binary` cross
casts with the offset-fit check and UTF-8 validation the issue calls
out.
- Fix `view_from_dict_values` dropping null dictionary *values*: they
became empty strings
rather than nulls, where `unpack_dictionary` and `impl
From<&GenericByteArray>` both
produce nulls.
- Bounds-check the dictionary key before indexing the offsets, turning
an out-of-range key
from undefined behaviour into an error. The gate confines this loop to
short row counts,
so it is within noise when the dictionary holds no nulls. When the
dictionary does hold
nulls, the null check costs 25-40% on the direct path an unavoidable
random bitmap
lookup per row, and the price of emitting nulls rather than the empty
strings the
previous code produced.
## Benchmarks
Existing fast paths on main:
| cast | rows | dict values | main | this PR | change |
|---|---|---|---|---|---|
| `Utf8->Utf8View` | 8,192 | 100 | 26.3 µs | 3.4 µs | **-87.2%** |
| `Utf8->Utf8View` | 1,000,000 | 1,000 | 3188.9 µs | 554.6 µs |
**-82.6%** |
| `Binary->BinaryView` | 8,192 | 100 | 24.9 µs | 3.3 µs | **-86.6%** |
| `Binary->BinaryView` | 1,000,000 | 1,000 | 3296.0 µs | 593.6 µs |
**-82.0%** |
New arms, sparse shapes (dictionary larger than the array):
| cast | rows | dict values | main | this PR | change |
|---|---|---|---|---|---|
| `LargeUtf8->Utf8View` | 1,000 | 100,000 | 271.2 µs | 3.9 µs |
**-98.6%** |
| `LargeUtf8->BinaryView` | 10,000 | 1,000,000 | 15752.5 µs | 78.6 µs |
**-99.5%** |
| `LargeBinary->BinaryView` | 1,000 | 100,000 | 276.1 µs | 3.9 µs |
**-98.6%** |
| `Utf8->BinaryView` | 10,000 | 1,000,000 | 3005.8 µs | 73.1 µs |
**-97.6%** |
| `Binary->Utf8View` | 1,000 | 100,000 | 351.5 µs | 88.6 µs | **-74.8%**
|
| `LargeBinary->Utf8View` | 10,000 | 1,000,000 | 4570.7 µs | 1713.9 µs |
**-62.5%** |
(`Binary`/`LargeBinary -> Utf8View` gain less because UTF-8 validation
of the dictionary
values dominates.)
Dense shapes on the new arms are unchanged, -2.9% to +1.2% the gate
routes them to
`unpack_dictionary`. Worst cell across the whole matrix is +5.0%, on a
shape where both
versions take the direct path and the delta is the null and bounds
checks above.
<details>
<summary>Method</summary>
Both implementations were compiled into a single binary and timed in
alternating rounds so
thermal drift cancels out of the ratio. Cells whose code is identical in
both versions come
out at -2.9% to +1.2%, which bounds the method's noise; a two-run
criterion comparison of
those same cells reported up to +47% drift, which is why it wasn't used.
Outputs are
asserted equal per cell before timing. Measured on an i7-11700F; a
second independent run
reproduced every headline result within 3.2 points and produced the
identical set of cells
above 50%; the largest shift on any cell was 8.3 points, on a cell that
is flat in both runs.
</details>
# Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example,
are they covered by existing tests)?
If this PR claims a performance improvement, please include evidence
such as benchmark results.
-->
Yes. Every arm is exercised through **both** implementations (row counts
either side of the
gate), with results asserted equal to the `unpack_dictionary` reference
in each case. Null
dictionary values, null keys, and invalid UTF-8 under both `safe` and
strict `CastOptions`
are covered by dedicated tests.
# Are there any user-facing changes?
Casting `Dictionary<_, Utf8> -> Utf8View` and `Dictionary<_, Binary> ->
BinaryView` becomes
substantially faster at typical batch shapes 5-8x on the shapes
benchmarked above.
`Dictionary<_, LargeUtf8/LargeBinary> -> Utf8View/BinaryView` and the
`Utf8` <-> `Binary`
cross casts gain a fast path when the dictionary holds more than twice
as many values as the
array has rows. Outside that they behave as before, going through
`unpack_dictionary`.
Two behaviour changes, called out explicitly:
1. A null dictionary *value* now casts to null rather than an empty
string:
```rust
// values ["aa", NULL, "cc"], keys [0, 1, 2]
cast(&dict, &DataType::Utf8View) // before: ["aa", "", "cc"]
// after: ["aa", null, "cc"]
```
2. An out-of-range dictionary key now returns an `InvalidArgumentError`
instead of being
undefined behaviour. Only reachable for a dictionary built without
validation.
Happy to split either into its own PR if you'd prefer this one stay
purely about the fast path.
---------
Co-authored-by: Jeffrey Vo <[email protected]>
---
arrow-cast/src/cast/dictionary.rs | 288 ++++++++++++++++++++++++++++++++++++--
1 file changed, 278 insertions(+), 10 deletions(-)
diff --git a/arrow-cast/src/cast/dictionary.rs
b/arrow-cast/src/cast/dictionary.rs
index 367084cbdc..0acf12922a 100644
--- a/arrow-cast/src/cast/dictionary.rs
+++ b/arrow-cast/src/cast/dictionary.rs
@@ -28,25 +28,98 @@ pub(crate) fn dictionary_cast<K: ArrowDictionaryKeyType>(
) -> Result<ArrayRef, ArrowError> {
use DataType::*;
+ /// Whether the dictionary is sparse; gates short of the measured 0.6x
crossover for margin.
+ #[inline]
+ fn is_sparse<K: ArrowDictionaryKeyType>(array: &DictionaryArray<K>) ->
bool {
+ array.keys().len() < array.values().len() / 2
+ }
+
+ #[inline]
+ fn values_buffer_fits_in_view<T: ByteArrayType>(values:
&GenericByteArray<T>) -> bool {
+ values.values().len() < i32::MAX as usize
+ }
+
let array = array.as_dictionary::<K>();
let from_child_type = array.values().data_type();
match (from_child_type, to_type) {
(_, Dictionary(to_index_type, to_value_type)) => {
dictionary_to_dictionary_cast(array, to_index_type, to_value_type,
cast_options)
}
- // `unpack_dictionary` can handle Utf8View/BinaryView types, but
incurs unnecessary data
- // copy of the value buffer. Fast path which avoids copying underlying
values buffer.
- // TODO: handle LargeUtf8/LargeBinary -> View (need to check offsets
can fit)
- // TODO: handle cross types (String -> BinaryView, Binary ->
StringView)
- // (need to validate utf8?)
- (Utf8, Utf8View) => view_from_dict_values::<K, Utf8Type,
StringViewType>(
- array.keys(),
- array.values().as_string::<i32>(),
- ),
- (Binary, BinaryView) => view_from_dict_values::<K, BinaryType,
BinaryViewType>(
+ // `unpack_dictionary` operates per dictionary value before using take
kernel to form
+ // final view. `view_from_dict_values` builds output view directly per
row (key index).
+ // Based on benchmarking, `view_from_dict_values` is more efficient
for sparse dictionaries
+ // (more dictionary values than there are rows/keys), whilst
`unpack_dictionary` is
+ // more efficient for dense dictionaries, where a sparse dictionary is
when rows reach
+ // roughly 0.6x the dictionary size.
+ //
+ // Therefore delegate to the faster method based on the density of the
input dictionary.
+ (Utf8, Utf8View) if is_sparse(array) => {
+ view_from_dict_values::<K, Utf8Type, StringViewType>(
+ array.keys(),
+ array.values().as_string::<i32>(),
+ )
+ }
+ (Binary, BinaryView) if is_sparse(array) => {
+ view_from_dict_values::<K, BinaryType, BinaryViewType>(
+ array.keys(),
+ array.values().as_binary::<i32>(),
+ )
+ }
+ // `view_from_dict_values` directly appends the values buffer as a
block using
+ // `GenericByteViewBuilder::append_block` which asserts length of the
buffer; we must
+ // ensure this assertion holds to use it for large variants which may
exceed the max allowable length.
+ // If we exceed the length we can simply fallback to
`unpack_dictionary` which still builds it
+ // correctly.
+ (LargeUtf8, Utf8View)
+ if is_sparse(array)
+ &&
values_buffer_fits_in_view(array.values().as_string::<i64>()) =>
+ {
+ view_from_dict_values::<K, LargeUtf8Type, StringViewType>(
+ array.keys(),
+ array.values().as_string::<i64>(),
+ )
+ }
+ (LargeBinary, BinaryView)
+ if is_sparse(array)
+ &&
values_buffer_fits_in_view(array.values().as_binary::<i64>()) =>
+ {
+ view_from_dict_values::<K, LargeBinaryType, BinaryViewType>(
+ array.keys(),
+ array.values().as_binary::<i64>(),
+ )
+ }
+ // Cross casts to a binary view need no validation: valid UTF-8 is
valid binary.
+ (Utf8, BinaryView) if is_sparse(array) => {
+ view_from_dict_values::<K, Utf8Type, BinaryViewType>(
+ array.keys(),
+ array.values().as_string::<i32>(),
+ )
+ }
+ (LargeUtf8, BinaryView)
+ if is_sparse(array)
+ &&
values_buffer_fits_in_view(array.values().as_string::<i64>()) =>
+ {
+ view_from_dict_values::<K, LargeUtf8Type, BinaryViewType>(
+ array.keys(),
+ array.values().as_string::<i64>(),
+ )
+ }
+ // Cross casts to a string view require UTF-8 validation of the
dictionary values.
+ (Binary, Utf8View) if is_sparse(array) =>
binary_dict_to_string_view::<K, i32>(
array.keys(),
array.values().as_binary::<i32>(),
+ cast_options,
),
+ (LargeBinary, Utf8View)
+ if is_sparse(array)
+ &&
values_buffer_fits_in_view(array.values().as_binary::<i64>()) =>
+ {
+ binary_dict_to_string_view::<K, i64>(
+ array.keys(),
+ array.values().as_binary::<i64>(),
+ cast_options,
+ )
+ }
_ => unpack_dictionary(array, to_type, cast_options),
}
}
@@ -126,6 +199,73 @@ fn dictionary_to_dictionary_cast<K:
ArrowDictionaryKeyType>(
Ok(new_array)
}
+/// Cast `Dict<K, Binary>` or `Dict<K, LargeBinary>` to `Utf8View`, validating
UTF-8 for each
+/// dictionary value.
+///
+/// Fast path when all values are valid UTF-8: reuses the values buffer
without copying.
+/// When some values are invalid and `cast_options.safe` is true, rows
pointing to those
+/// values become null. When `cast_options.safe` is false, returns an error
immediately.
+fn binary_dict_to_string_view<K: ArrowDictionaryKeyType, O: OffsetSizeTrait>(
+ keys: &PrimitiveArray<K>,
+ values: &GenericByteArray<GenericBinaryType<O>>,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ match GenericStringArray::<O>::try_from_binary(values.clone()) {
+ Ok(_) => {
+ // All dictionary values are valid UTF-8: reuse the buffer
zero-copy.
+ view_from_dict_values::<K, GenericBinaryType<O>,
StringViewType>(keys, values)
+ }
+ Err(e) => {
+ if !cast_options.safe {
+ return Err(e);
+ }
+ // safe=true: validate each dictionary value individually so we
can nullify
+ // only the rows whose key points to a null or invalid UTF-8 value.
+ let valid: Vec<bool> = (0..values.len())
+ .map(|i| !values.is_null(i) &&
std::str::from_utf8(values.value(i)).is_ok())
+ .collect();
+
+ let value_buffer = values.values();
+ let value_offsets = values.value_offsets();
+ let mut builder = StringViewBuilder::with_capacity(keys.len());
+ builder.append_block(value_buffer.clone());
+
+ for key in keys {
+ match key {
+ Some(v) => {
+ let idx = v.to_usize().ok_or_else(|| {
+ ArrowError::ComputeError("Invalid dictionary
index".to_string())
+ })?;
+ let is_valid = *valid.get(idx).ok_or_else(|| {
+ ArrowError::InvalidArgumentError(format!(
+ "Dictionary key {idx} out of bounds for
dictionary values of length {}",
+ valid.len()
+ ))
+ })?;
+ if is_valid {
+ // Safety:
+ // (1) `idx` and `idx + 1` are in bounds, checked
above
+ // (2) offsets are monotonically increasing, so
end >= offset
+ // (3) the slice [offset..end] is within the buffer
+ // (4) the bytes are valid UTF-8, checked above
+ unsafe {
+ let offset =
value_offsets.get_unchecked(idx).as_usize();
+ let end = value_offsets.get_unchecked(idx +
1).as_usize();
+ let length = end - offset;
+ builder.append_view_unchecked(0, offset as
u32, length as u32);
+ }
+ } else {
+ builder.append_null();
+ }
+ }
+ None => builder.append_null(),
+ }
+ }
+ Ok(Arc::new(builder.finish()))
+ }
+ }
+}
+
fn view_from_dict_values<K: ArrowDictionaryKeyType, V: ByteArrayType, T:
ByteViewType>(
keys: &PrimitiveArray<K>,
values: &GenericByteArray<V>,
@@ -561,3 +701,131 @@ where
}
Ok(Arc::new(b.finish()))
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use DataType::*;
+
+ // Too few keys for the dictionary, so `is_sparse` holds and views are
built per row.
+ // Covers an inlined value, a buffer backed one, a null key and a null
dictionary value.
+ fn sparse_keys(values: &ArrayRef) -> Int32Array {
+ let keys = Int32Array::from(vec![Some(0), Some(2), None, Some(3)]);
+ assert!(
+ keys.len() < values.len() / 2,
+ "keys must reach the direct path"
+ );
+ keys
+ }
+
+ // One key per value, so `is_sparse` fails and `unpack_dictionary` runs.
+ fn dense_keys(values: &ArrayRef) -> Int32Array {
+ let keys = Int32Array::from(vec![
+ Some(0),
+ Some(2),
+ None,
+ Some(3),
+ Some(1),
+ Some(0),
+ Some(4),
+ Some(2),
+ Some(3),
+ Some(5),
+ ]);
+ assert!(
+ keys.len() >= values.len() / 2,
+ "keys must reach unpack_dictionary"
+ );
+ keys
+ }
+
+ fn make_dict(keys: &Int32Array, values: &ArrayRef) ->
DictionaryArray<Int32Type> {
+ DictionaryArray::try_new(keys.clone(), values.clone()).unwrap()
+ }
+
+ #[test]
+ fn test_dict_to_view_matches_take_then_cast() {
+ let long = "a value over twelve bytes";
+ let utf8: ArrayRef = Arc::new(StringArray::from(vec![
+ Some("aa"),
+ Some("bb"),
+ Some(long),
+ None,
+ Some("ee"),
+ Some("ff"),
+ Some("gg"),
+ Some("hh"),
+ Some("ii"),
+ Some("jj"),
+ ]));
+
+ for from in [Utf8, LargeUtf8, Binary, LargeBinary] {
+ let values = cast(&utf8, &from).unwrap();
+ for to in [Utf8View, BinaryView] {
+ for keys in [sparse_keys(&values), dense_keys(&values)] {
+ let expected = cast(&take(&values, &keys, None).unwrap(),
&to).unwrap();
+ let casted = cast(&make_dict(&keys, &values),
&to).unwrap();
+ assert_eq!(casted.as_ref(), expected.as_ref(), "{from:?}
-> {to:?}");
+ }
+ }
+ }
+ }
+
+ #[test]
+ fn test_dict_binary_to_utf8view_invalid_utf8() {
+ let bytes: Vec<&[u8]> = vec![
+ b"aa",
+ b"bb",
+ &[0xFF, 0xFE],
+ b"dd",
+ b"ee",
+ b"ff",
+ b"gg",
+ b"hh",
+ b"ii",
+ b"jj",
+ ];
+ let strict = CastOptions {
+ safe: false,
+ ..Default::default()
+ };
+ let safe = CastOptions {
+ safe: true,
+ ..Default::default()
+ };
+
+ for values in [
+ Arc::new(BinaryArray::from_vec(bytes.clone())) as ArrayRef,
+ Arc::new(LargeBinaryArray::from_vec(bytes.clone())) as ArrayRef,
+ ] {
+ // index 2 holds the invalid value, so keys pointing at it are
nullified when safe
+ for (keys, expected) in [
+ (
+ sparse_keys(&values),
+ vec![Some("aa"), None, None, Some("dd")],
+ ),
+ (
+ dense_keys(&values),
+ vec![
+ Some("aa"),
+ None,
+ None,
+ Some("dd"),
+ Some("bb"),
+ Some("aa"),
+ Some("ee"),
+ None,
+ Some("dd"),
+ Some("ff"),
+ ],
+ ),
+ ] {
+ let dict = make_dict(&keys, &values);
+ assert!(cast_with_options(&dict, &Utf8View, &strict).is_err());
+
+ let casted = cast_with_options(&dict, &Utf8View,
&safe).unwrap();
+ assert_eq!(casted.as_string_view(),
&StringViewArray::from(expected));
+ }
+ }
+ }
+}
