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]

Reply via email to