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

   # Which issue does this PR close?
   
   - Relates to #9731.
   
   # Rationale for this change
   
   `LevelEncoder::put_with_observer` costs 5-7 ns per level for random or 
nullable definition levels,
   more than encoding most values. There are two causes:
   - Every level goes through `RleEncoder::put`, whose run state lives in the 
encoder and is stored
     and reloaded per level.
   - Outside RLE runs the observer is called once per level, and the column 
writer's histogram update
     makes each level wait on the previous one.
   
   # What changes are included in this PR?
   
   - `RleEncoder`'s group-at-a-time `put_batch` path is generalized over the 
value width as
     `put_batch_observed<T: RleValue, O: RunObserver<T>>`, so `i16` levels use 
it without being
     widened. `put_batch` behaves as before.
   - The observer hears about each RLE run, single-value group and per-value 
fallback as one run.
   - Values in bit-packed groups are counted without calling the observer: per 
group for 1-bit levels,
     and in a small histogram for up to 4 bits. The counts are reported once 
per call.
   - Runs are extended 32 values at a time with vector compares.
   - `put_with_observer`'s documented contract changes from "called once per 
run" to "totals per
     level". Its callers only accumulate counts.
   
   Output is byte-identical.
   
   # Are these changes tested?
   
   - A new test checks the observer's totals per level for max levels between 0 
and 40, run-heavy and random
     inputs, and ragged batch sizes. It also compares the encoded bytes against 
per-value `put`.
   - Writer output was checked to be byte-identical to main's on files with 
nullable and nested list
     columns.
   
   `level_encoding` bench, Intel Xeon Platinum 8559C, default x86-64 target, 
median of 5 alternating
   rounds:
   
   | `level_encoding` bench | main | PR | Speedup |
   | :--- | ---: | ---: | ---: |
   | uniform/max1 | 17.91 µs | 2.31 µs | 7.76x |
   | long_runs/max3 | 18.54 µs | 2.82 µs | 6.57x |
   | random/max1 | 387.30 µs | 88.93 µs | 4.36x |
   | random/max3 | 277.27 µs | 73.84 µs | 3.76x |
   | random/max7 | 206.99 µs | 59.30 µs | 3.49x |
   | alternating/max1 | 130.11 µs | 42.19 µs | 3.08x |
   | nullable_25pct/max1 | 323.35 µs | 118.91 µs | 2.72x |
   | sparse_99pct_null/max1 | 49.20 µs | 28.09 µs | 1.75x |
   | list_0_4_25pct_null, def_max3 / rep_max1 | | | 3.26x / 4.10x |
   | list_0_9, def_max3 / rep_max1 | | | 1.57x / 3.13x |
   | list_list, def_max5 / rep_max2 | | | 3.71x / 3.77x |
   | mixed_runs/max3 | 81.08 µs | 80.59 µs | 1.01x |
   
   `arrow_writer`, 7 rounds: `primitive` 1.25x, `list_primitive` 1.27x, 
`list_nested` 1.27x,
   `primitive_sparse_99pct_null` 1.13x, `struct_sparse_99pct_null` 1.09x, 
`string` 1.06x. Non-null
   controls, which encode no levels, were 0.97-1.01x over 9 rounds.
   
   A first version counted levels in separate passes after encoding. It slowed 
run-heavy inputs to
   0.36-0.55x, because the encoder already reports runs for free. Taking the 
counts from the encoder's
   own runs and groups is what keeps those cases fast.
   
   None of the measured inputs got slower.
   
   # Are there any significant user-facing changes?
   
   The documented contract of `LevelEncoder::put_with_observer`, which is 
experimental and hidden from
   the docs.
   
   # AI usage disclosure
   
   An AI coding agent (Claude Code) generated the code, the tests 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