prtkgaur opened a new pull request, #51295:
URL: https://github.com/apache/arrow/pull/51295
DESCRIPTION:
> Builds on #51250 and contains its commit, since the gain here depends on
it. Only the
> last two commits belong to this PR, and the benchmark below is measured
against its
> parent as well as against main.
### Rationale for this change
Once equal-width miniblocks are unpacked in one call, what is left per value
is the prefix
sum: a chain of dependent additions, one value at a time, with the running
total carried
from each to the next. That chain is now the cost of decoding a narrow
DELTA_BINARY_PACKED
page.
The sum can be computed several values at a time instead. A log-step
inclusive scan turns
a register of deltas into a register of running totals in log2(lanes)
shifted additions,
and the frame is added *before* the scan, which makes its running multiple
fall out of the
scan itself rather than needing a separate multiply per lane.
### What changes are included in this PR?
The value-at-a-time loop becomes a helper that scans whole registers and
finishes the
remainder one value at a time, carrying the running total across registers.
Every term
stays in the unsigned type, so the wrapping the format specifies is
unchanged and decoded
values are identical.
Two details are worth a reviewer's attention:
- **How the running total crosses registers.** The obvious way -- read the
last lane into a
general-purpose register, re-broadcast it -- puts a vector-to-scalar round
trip on the
critical dependency chain and is *slower than the scalar loop it
replaces*: measured in
isolation, 0.480 ns per value scalar, 1.528 ns that way, 0.361 ns keeping
the carry in a
vector register and broadcasting the last lane with a shuffle. The helper
does the last
of those.
- **The threshold is a lane count, not a type.** A scan pays off only once a
register holds
enough values to beat the additions it replaces; at two lanes it loses,
because one
doubling step plus the carry costs more than the two additions saved. So
the vector loop
is compiled only where a register holds four or more values, and otherwise
the remainder
loop does all the work. At Arrow's default 128-bit baseline that means
32-bit values are
scanned and 64-bit values fall through to the same loop as today; with a
wider baseline
both are scanned. The 64-bit vector loop therefore is not built by a
default
configuration and is not exercised by CI as it stands.
This overlaps #51249: the helper takes the frame and the running total by
value and returns
the new total, which is what that PR does by hand, so whichever lands second
needs a
trivial rebase. It is also why the 64-bit arms improve here without being
vectorized.
### Are these changes tested?
A new typed test walks every residual bit width for both integer widths, and
at each width
enough lengths to leave every remainder a register-sized group can leave, so
each width is
decoded through the vector loop, through the remainder, and across the
hand-off between
them. Deltas alternate between the frame and the widest value the width can
hold, which
pins the stored width, keeps a non-zero frame in play -- its running
multiple grows with
the index, so folding it in per register has to get that multiple right --
and wraps the
running total repeatedly, which is where a grouped total and a
value-at-a-time one part
company if any term is signed. Three mutations each turn it red: dropping
the frame's
running multiple and losing the carry between registers fail the 32-bit
instantiation,
which is the one that builds a vector loop here, and stopping the remainder
loop one value
early fails both.
Outside the tree, the helper was also checked element-wise against the loop
it replaces
over 2760 cases per width, across value counts 0 to 1024, forty seeds, and
full-range
wrapping / small / near-maximum value ranges.
### Benchmark
Same setup as #51250: AWS Graviton4, GCC 11.5, `Release`, one core, 9
repetitions, medians,
65,536 values. Every point built twice with the builds interleaved, so no
ratio crosses two
builds; both ratios are given. `NarrowSorted` is the arm added by the first
of the two
commits and holds non-decreasing values, the shape DELTA_BINARY_PACKED is
usually chosen
for. The `Fixed` arms are the zero bit width path, which has no prefix sum
to scan.
| benchmark | #51250 | this PR | | vs. main |
|---|--:|--:|--:|--:|
| `Decode_Int32_NarrowSorted` | 73.7 us | 45.7 us | **1.61x** / 1.61x |
**2.18x** |
| `Decode_Int32_Narrow` | 74.8 us | 46.4 us | **1.61x** / 1.61x | **2.15x** |
| `Decode_Int32_Wide` | 83.7 us | 53.6 us | **1.56x** / 1.56x | **1.90x** |
| `Decode_Int64_NarrowSorted` | 71.4 us | 55.0 us | **1.30x** / 1.30x |
**1.47x** |
| `Decode_Int64_Narrow` | 70.9 us | 55.2 us | **1.28x** / 1.29x | **1.49x** |
| `Decode_Int64_Wide` | 318.6 us | 301.3 us | 1.06x / 1.06x | 1.07x |
| `Decode_Int32_Fixed` | 20.4 us | 20.5 us | 1.00x / 1.00x | 0.97x |
| `Decode_Int64_Fixed` | 31.3 us | 31.3 us | 1.00x / 1.00x | 0.98x |
The gain needs #51250 underneath it. On top of #51249 alone, without
coalescing, the same
kernel measures 0.98x to 1.03x across the 32-bit arms -- a wash.
Per-register setup only
amortizes over the longer runs coalescing produces; at one unpack call per
32 values there
is not enough work between calls for it to pay.
### Are there any user-facing changes?
No. No API change, no format change, and decoded values are identical.
--
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]
