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]