dtenedor opened a new pull request, #12281:
URL: https://github.com/apache/arrow-rs/pull/12281

   # Which issue does this PR close?
   
   - Relates to #9731.
   
   Builds on #12276, whose commit is included. Only the last commit is new.
   
   # Rationale for this change
   
   With #12276, encoding definition levels is still the largest single cost of 
writing nullable
   primitive columns: `RleEncoder::put_batch_observed` is 16% of 
`arrow_writer`'s `primitive/default`.
   Three parts of `RleEncoder` cause most of it:
   - It keeps every value of an open bit-packed run in a `Vec<u64>` and packs 
them only when the run
     closes. Each `i16` level is widened to 8 bytes, with SSE2-emulated sign 
extension, written, and
     read back.
   - When an RLE run ends, the next 8 values go through the per-value `put`, 
because the group path
     needs the encoder at a group boundary. With 25% nulls that is about 10% of 
all levels.
   - Whether a group repeats one value is tested with a short-circuiting `all`. 
Where it exits is
     data-dependent for levels, which take few distinct values, so it 
mispredicts.
   
   # What changes are included in this PR?
   
   - When an RLE run ends inside `put_batch_observed`, it is written out right 
there, as `put` would
     on that value. The values after it then take the group path.
   - Groups of values up to 8 bits wide, which covers levels and small 
dictionaries, are packed into
     `bit_width` bytes as soon as they are complete. Only the trailing partial 
group is kept unpacked,
     in a `[u64; 8]`.
   - Wider values, such as the indices of a large dictionary, are still 
collected and packed with one
     `put_batch` call when the run closes. A version that packed them per group 
too made
     1%-cardinality dictionary writes 0.94x.
   - A group of `i16` levels is compared without exiting early. Other values, 
which are dictionary
     indices, keep `all`: with many distinct values its early exit is 
predictable.
   - `len()` gives the same estimates as before, because page sizing depends on 
it.
   
   Output is byte-identical.
   
   # Are these changes tested?
   
   Covered by the existing encoder and writer tests, including the per-value 
comparison from #12276.
   `RleEncoder` output, and `len()` at checkpoints, were also checked to be 
byte-identical to main's
   for:
   - bit widths from 0 to 64
   - lengths from 0 to 10,007
   - random, run-heavy, sparse, alternating and constant values
   - per-value `put`, whole-batch `put_batch`, and ragged mixes of both
   
   Benchmarks against #12276, Intel Xeon Platinum 8559C, default x86-64 target, 
median of 5
   alternating rounds:
   
   | `level_encoding` bench | #12276 | PR | Speedup |
   | :--- | ---: | ---: | ---: |
   | nullable_25pct/max1 | 116.56 µs | 54.69 µs | 2.13x |
   | random/max1 | 88.40 µs | 42.58 µs | 2.08x |
   | list_0_4_25pct_null/rep_max1 | 84.63 µs | 42.07 µs | 2.01x |
   | list_0_9/rep_max1 | 87.12 µs | 49.68 µs | 1.75x |
   | sparse_99pct_null/max1 | 27.11 µs | 16.95 µs | 1.60x |
   | mixed_runs/max3 | 78.87 µs | 50.14 µs | 1.57x |
   | list_0_9/def_max3 | 146.88 µs | 96.51 µs | 1.52x |
   | list_0_4_25pct_null/def_max3 | 107.56 µs | 73.82 µs | 1.46x |
   | list_list/def_max5 / rep_max2 | | | 1.40x / 1.35x |
   | random/max3 | 74.57 µs | 58.61 µs | 1.27x |
   | alternating/max1 | 43.03 µs | 38.26 µs | 1.12x |
   | long_runs/max3 / random/max7 | | | 1.04x / 1.01x |
   | **uniform/max1** | 2.27 µs | 2.35 µs | **0.97x** |
   
   Flushing ended runs alone gives mixed_runs 1.60x, sparse_99pct_null 1.54x 
and nullable_25pct
   1.20x. Packing groups as they complete, together with the full comparison, 
gives the rest.
   
   | `arrow_writer` bench | Speedup |
   | :--- | ---: |
   | `bool/default` | 1.21x |
   | `primitive_sparse_99pct_null/default` / `struct_sparse_99pct_null/default` 
| 1.14x / 1.11x |
   | `int64_dictionary/default` | 1.12x |
   | `primitive/default` / `primitive/parquet_2` | 1.11x / 1.09x |
   | `list_primitive/default` / `list_nested/default` / `list_nested/parquet_2` 
| 1.08x / 1.07x / 1.05x |
   | `string/default`, `primitive_non_null/default` | 0.99-1.01x |
   | `short_string_non_null/default`, 
`string_dictionary_low_cardinality_20/default` | 0.93-0.94x |
   | `int64_dictionary_1pct_cardinality/default`, 
`primitive_dictionary_1pct_cardinality/default` | 0.98x |
   
   Slower inputs:
   - `uniform/max1`, a single run, is about 1 ns slower per call of 1,024 
levels. That is fixed
     overhead, not per-level cost.
   - The `arrow_writer` cases at 0.93-0.98x don't run the changed code much. 
`short_string_non_null`'s
     profile has no `RleEncoder` frames at all. But changing `rle.rs` changes 
how rustc splits the
     crate into codegen units, and with it the register allocation of the 40 KB
     `ByteArrayEncoder::write_gather`. Building both sides with 
`codegen-units=1` and every function
     aligned to 64 bytes (`-C llvm-args=-align-all-functions=6`) puts those 
cases at 1.00-1.02x, while
     `primitive` stays at 1.14x, `bool` 1.26x and `list_nested` 1.07x.
   
   Not measured on aarch64.
   
   # Are there any significant user-facing changes?
   
   No.
   
   # AI usage disclosure
   
   An AI coding agent (Claude Code) generated the code 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