etseidl commented on PR #11997:
URL: https://github.com/apache/arrow-rs/pull/11997#issuecomment-6834300982
@adriangb I had my agent do some benchmarks to verify a fix to the #11996
regression. It's report follows (if you haven't seen "Colossus: The Forbin
Project" I highly recommend...I watched it many times as a kid and it's
frighteningly still relevant 🤣).
Thanks for this work. I ran a focused comparison and found useful gains, but
also two repeatable regression cases worth addressing.
Compared corrected base `b231cf15efa5dbbbe4ae8503849aa6ab3cfc4e0c` against
head `a9ef13a92e9272d378ee3fcd173da33635588f4b` on an Intel i7-12700K, Linux,
Rust 1.99.1. These are mean milliseconds for writer construction + write +
close of 1,048,576 rows, one nullable column, 99% nulls, write batch 1,024. Two
counterbalanced sweeps and longer repeats agreed on the directions:
| Input | Base | Head | Time change |
|---|---:|---:|---:|
| Random-null Utf8, 8-byte values, PLAIN | 1.2466 | 1.3091 | **+5.0%** |
| Same input, dictionary enabled | 1.3092 | 1.3766 | **+5.1%** |
| Random-null Utf8View, 8-byte inline values, PLAIN | 1.2706 | 1.1077 |
**−12.8%** |
| Random-null Utf8View, 32-byte values in one shared backing buffer, PLAIN |
1.2553 | 1.6390 | **+30.6%** |
| Clustered/trailing-null Utf8, 8-byte values, PLAIN | 0.6212 | 0.4345 |
**−30.1%** |
Base/head output files matched byte-for-byte for these cases. These are
bounded one-host results, not universal workload claims; the inline-View and
clustered gains are real.
### Repair target: repeated work over overlapping lookahead
Please inspect
[`ByteBudgetChunker::byte_budget_sub_batch`](https://github.com/apache/arrow-rs/blob/a9ef13a92e9272d378ee3fcd173da33635588f4b/parquet/src/column/writer/byte_budget_chunker.rs#L226-L261)
together with `count_within_budget_offsets`, `count_within_budget_views`, and
`max_view_value_len` in `parquet/src/arrow/arrow_writer/byte_array.rs`.
The gather window contains the next `chunk_size` **values**, rather than the
values belonging to the current `chunk_size` **levels**. At 99% random nulls,
successive windows overlap heavily. Separate untimed instrumentation found:
- Budget `value_count` calls fall from 1,024 to zero, eliminating a scan of
1,048,576 definition levels.
- Gather-sizing visits rise from about **10.5k to 998,924**; the offset fast
path checks **997,900** adjacent index pairs.
- Inline View passes its cheap bound. For the 32-byte View fixture, the
shared backing buffer is **337,152 bytes**, making `max_view_value_len` very
loose. Stage 2 repeatedly scans nearly a million view lengths instead of about
10.5k.
Thus avoiding the definition-level scan can replace it with substantially
more overlapping estimator work. The offset ordering change and expanded window
have coupled costs; this does not isolate all the slowdown to ordering
validation.
**Could you try avoiding expanded lookahead when estimating it requires a
linear scan?** A candidate is to retain speculative lookahead when a genuinely
cheap conservative bound proves it fits, otherwise count the current chunk and
size only its actual gather prefix. This is a direction to test, not a verified
fix; please prefer the smallest measured change rather than a broad encoder
redesign or unnecessary public API addition. Simply shrinking the speculative
window cannot establish that the whole chunk fits.
### Preserve correctness and retest
- Keep strict-order validation before using the offset-span bound. ListView
can repeat indices or jump backwards, including across chunk boundaries; do not
assume every gather is monotonic.
- Preserve #11996's `max_values`/`window_end_for_values` cap and
boundary-value semantics. The earlier common-fitting scan dates to #9972;
reverting the later cap is not the remedy.
- Keep the contiguous path count-first: padded placeholder `ByteArray`s
beyond the referenced values must not be sized.
For reproduction, use identical fixed-seed logical values/nulls for Utf8 and
Utf8View: 1,048,576 rows, about 1% present (ours has 10,536), a 128-value ASCII
alphabet, lengths 8 and 32. Explicit properties: uncompressed, writer version
1.0, page statistics, 1 MiB data/dictionary limits, 20,000-row page limit,
write batch 1,024, one row group. Ensure the out-of-line View uses **one shared
backing buffer**, not one small buffer per value. Generate input outside timing
and write to a discard sink.
Retest the table cases against the corrected base, plus random sparsity with
write batch 64. Validate roundtrip and actual page/dictionary bodies
separately, retaining the existing soft-limit/boundary allowances. Keep the
chunker/placeholder tests, page/dictionary-cap tests (including clustered
nulls), and both `test_arrow_writer_list_view_backward_gather*` regressions
passing. Please report per-representation results and explain any remaining
tradeoff. I can share the standalone harness and detailed results if useful.
--
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]
