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]

Reply via email to