Abhisheklearn12 opened a new pull request, #10436:
URL: https://github.com/apache/arrow-rs/pull/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 +0.0% 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), covering null dictionary values, null keys, invalid UTF-8 under both
`safe` and
strict `CastOptions`. Results are asserted equal to the
`unpack_dictionary` reference in each case.
# 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.
--
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]
