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]