dtenedor opened a new pull request, #12275:
URL: https://github.com/apache/arrow-rs/pull/12275
# Which issue does this PR close?
None.
# Rationale for this change
Reading a nullable column decodes the non-null values densely, then
`ValuesBuffer::pad_nulls` moves
each one to its slot. With half the values null, that step is 41-60% of
reading an Int32 column,
whether PLAIN, DELTA or dictionary encoded. `OffsetBuffer::pad_nulls` is 45%
of reading strings.
The `Vec` implementation pairs a reversed range with a set-bit iterator
built from nested
`flat_map`/`from_fn` closures and bounds-checks both sides. It costs about
3.6 cycles per value.
# What changes are included in this PR?
Values are spread down from the last level, one 64-bit mask word at a time.
Each word picks a
strategy:
| Word contents | Strategy |
| :--- | :--- |
| every level valid | one `copy_within` |
| no level valid | nothing for `Vec`; one fill for offsets |
| at most half valid | one move per valid level. The loop walks the reversed
word, so each step only waits on clearing the lowest set bit. Offsets get one
fill per run of nulls. |
| mostly valid | a branchless write of every level that consumes a value
only at valid levels |
The branchless form works because null slots may hold any value (`Vec`) or
the running end offset
(`OffsetBuffer`).
`OffsetBuffer::pad_nulls` now counts the mask's valid levels up front. It
returns its existing
"corrupt level data" error whenever that count differs from `values_read`,
not only in some of
those cases.
The first commit adds `plain encoded, optional, 10% NULLs` and `90% NULLs`
cases to the primitive
`arrow_reader` benchmarks. Decoding PLAIN is a copy, so these isolate the
padding at both ends of
the density range.
# Are these changes tested?
- New randomized tests compare against the per-position definition. They
cover densities of 0%,
2%, 50%, 98% and 100%, non-zero read offsets, and lengths that aren't
multiples of 64. They also
check that inconsistent input doesn't panic.
- A new `OffsetBuffer` test checks that null levels are empty, not just
masked.
- The existing reader unit and integration tests pass.
`arrow_reader` bench, Intel Xeon Platinum 8559C, default x86-64 target,
median of 5 alternating
rounds:
| `arrow_array_reader` bench | main | PR | Speedup |
| :--- | ---: | ---: | ---: |
| Int32Array, plain, optional, 10% NULLs | 197.53 µs | 122.58 µs | 1.61x |
| Int32Array, plain, optional, half NULLs | 89.16 µs | 56.76 µs | 1.57x |
| Int32Array, plain, optional, 90% NULLs | 95.61 µs | 81.46 µs | 1.17x |
| Int32Array, dictionary, optional, half NULLs | 110.31 µs | 81.60 µs |
1.35x |
| Int64Array, plain, optional, 10% NULLs | 180.33 µs | 138.96 µs | 1.30x |
| Int64Array, plain, optional, half NULLs | 78.05 µs | 66.11 µs | 1.18x |
| Int64Array, plain, optional, 90% NULLs | 100.61 µs | 89.41 µs | 1.13x |
| Int64Array, dictionary, optional, half NULLs | 97.46 µs | 88.96 µs | 1.10x
|
| StringArray, plain, optional, half NULLs | 520.37 µs | 393.94 µs | 1.32x |
| StringArray, dictionary, optional, half NULLs | 482.09 µs | 360.66 µs |
1.34x |
| StringViewArray, plain / dictionary, optional, half NULLs | | | 1.03x /
1.07x |
| cases without NULLs | | | 1.00x |
On the 50% case, an all-branchless first version only reached 1.13x on the
padding step, and it
would have been slower than main on sparse columns. Picking a strategy per
word is what makes both
ends faster. For Int64 at 50% NULLs, walking the set bits from the top with
`leading_zeros` made no
difference. Reversing the word and clearing its lowest set bit took it from
1.04x to 1.18x.
None of the measured inputs got slower.
# Are there any significant user-facing changes?
No. On corrupt pages, string reads now return an error in more of the cases
where the level and
value counts disagree.
# AI usage disclosure
An AI coding agent (Claude Code) generated the code, the tests, the
benchmark cases and this
description, and ran the benchmarks. This PR is a draft until the submitter
has reviewed it.
This pull request and its description were written by Isaac.
--
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]