You are viewing a plain text version of this content. The canonical link for it is here.

Posted to github@arrow.apache.org by "prtkgaur (via GitHub)" <gi...@apache.org> on 2026/09/10 19:53:36 UTC

[PR] GH-51268: [C++][Parquet] Scan DELTA_BINARY_PACKED deltas a vector at a time [arrow]

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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [WIP][POC] GH-51268: [C++][Parquet] Scan DELTA_BINARY_PACKED deltas a vector at a time [arrow]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.

github-actions[bot] commented on PR #51295:
URL: https://github.com/apache/arrow/pull/51295#issuecomment-5982210571

   <!--
     Licensed to the Apache Software Foundation (ASF) under one
     or more contributor license agreements.  See the NOTICE file
     distributed with this work for additional information
     regarding copyright ownership.  The ASF licenses this file
     to you under the Apache License, Version 2.0 (the
     "License"); you may not use this file except in compliance
     with the License.  You may obtain a copy of the License at
   
       http://www.apache.org/licenses/LICENSE-2.0
   
     Unless required by applicable law or agreed to in writing,
     software distributed under the License is distributed on an
     "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
     KIND, either express or implied.  See the License for the
     specific language governing permissions and limitations
     under the License.
   -->
   
   Thanks for opening a pull request!
   
   **This pull request has been automatically converted to a draft because its title doesn't match Arrow's required format.**
   
   If this is not a [minor PR](https://github.com/apache/arrow/blob/main/CONTRIBUTING.md#Minor-Fixes), could you open an issue for this pull request on GitHub? https://github.com/apache/arrow/issues/new/choose
   
   Opening GitHub issues ahead of time contributes to the [Openness](http://theapacheway.com/open/#:~:text=Openness%20allows%20new%20users%20the,must%20happen%20in%20the%20open.) of the Apache Arrow project.
   
   Then could you also rename the pull request title in the following format?
   
       GH-${GITHUB_ISSUE_ID}: [${COMPONENT}] ${SUMMARY}
   
   or
   
       MINOR: [${COMPONENT}] ${SUMMARY}
   
   **After updating the title, you can mark the pull request as ready for review.**
   
   See also:
   
     * [Other pull requests](https://github.com/apache/arrow/pulls/)
     * [Contribution Guidelines - Contributing Overview](https://arrow.apache.org/docs/developers/overview.html)
   


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org