dtenedor opened a new pull request, #12272:
URL: https://github.com/apache/arrow-rs/pull/12272
# Which issue does this PR close?
None.
# Rationale for this change
On the default x86-64 target, `DeltaBitPackEncoder` spends most of its time
in reductions that the
CPU can only emulate:
- INT32 deltas are kept as `i64`, so the per-block `min` and per-miniblock
`max` run on 64-bit
lanes. SSE2 has no 64-bit compare, so each reduction costs about 10
instructions per 2 values.
- `put` checks for a full block after every value, so the delta loop can't
vectorize.
Profile of INT32 encoding on main: `flush_block_values` 57%, `put` 26%.
# What changes are included in this PR?
- `put` fills each block a slice at a time. It is `#[inline]`, so callers
that put one value at a
time, like the Arrow writer's DELTA_BYTE_ARRAY lengths, keep it in their
loop.
- Deltas are stored, reduced and packed in the column's width (`i32`/`u32`
for INT32).
- A miniblock's bit width comes from the OR of its adjusted deltas. They are
all non-negative, so
this equals the bit width of their maximum. The OR is fused into the loop
that subtracts the
minimum, which removes the max pass.
- The zero padding at the end of the last miniblock is packed with the rest
of it, instead of one
`put_value` per padding slot.
Output is byte-identical.
The first commit adds the benchmark cases, so it can serve as the benchmark
baseline.
# Are these changes tested?
Covered by the existing encoder round-trip tests. Output was also checked to
be byte-identical to
main's on more than 2,600 inputs: every block layout, several `put`
chunkings, page splits, and
sorted, random, constant, arithmetic, extreme and bursty data.
The first commit adds DELTA_BINARY_PACKED cases to the `encoding` bench: 16K
values, well predicted
(sorted, small gaps) and poorly predicted (uniformly random). The encoder is
reused across
iterations, as the column writer reuses it across pages. Measured on an
Intel Xeon Platinum 8559C,
default x86-64 target, median of 3-5 alternating rounds:
| `encoding` bench | main | PR | Speedup |
| :--- | ---: | ---: | ---: |
| encode i32 sorted | 57.86 µs | 15.34 µs | 3.77x |
| encode i32 random | 57.83 µs | 14.15 µs | 4.09x |
| encode i64 timestamps | 54.58 µs | 24.34 µs | 2.24x |
| encode i64 random | 55.61 µs | 25.89 µs | 2.15x |
| decode, all four | | | 0.98-1.00x |
Filling blocks a slice at a time gives 1.23-1.29x on its own. The rest comes
from the native width
and the fused OR.
In `arrow_writer`, `primitive_non_null/parquet_2` is 1.21x faster. String
columns with `parquet_2`,
which put one length at a time, are 1.00-1.02x. The default-property cases
don't use this encoder
and stayed within ±3%.
None of the measured inputs got slower. For INT64 the block minimum over
`i64` is still emulated on
SSE2; `x86-64-v2` builds vectorize it. Not measured on aarch64, which has
64-bit vector compares,
so the gain there may be smaller.
# Are there any significant user-facing changes?
No.
# AI usage disclosure
An AI coding agent (Claude Code) generated the code, the benchmark cases and
this description, and
ran the benchmarks and the output checks. 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]