adriangb opened a new pull request, #11237: URL: https://github.com/apache/arrow-rs/pull/11237
# Which issue does this PR close? - Part of https://github.com/apache/arrow-rs/issues/11234. # Rationale for this change `PushBuffers` scans all buffers to find the bytes of a range, and `clear_ranges` compares each buffer with each range to clear. If a caller pushes one buffer per requested range, the decoder does `O(buffers)` work for each lookup, so the work for one row group increases with the square of the number of column chunks. The existing `push_decoder` benchmark shows this: | Benchmark (`benches/push_decoder.rs`) | `main`, run 1 | `main`, run 2 | This PR | |---|---:|---:|---:| | `Nbuf/1000ranges` | 885 µs | 517 µs | 302 µs | | `Nbuf/10000ranges` | 19.3 ms | 12.9 ms | 3.0 ms | | `Nbuf/100000ranges` | 574 ms | 602 ms | 35 ms | | `1buf/*` | | | no reliable change (−40% to +6% between runs) | Local laptop, `cargo bench -p parquet --features arrow --bench push_decoder`, 3 s measurement. I ran `main` two times, before and after this PR, because the machine is noisy. The `Nbuf` improvement is clear in both runs. The `1buf` cases push one buffer, so this change does not affect them, and their differences are noise. The batch granularity in https://github.com/apache/arrow-rs/issues/11234 pushes one buffer per page, which makes the number of buffers much larger. # What changes are included in this PR? `PushBuffers` keeps its buffers sorted by the start of their range. | Operation | Before | After | |---|---|---| | `push_range` | append | binary search, then insert (append for ranges pushed in file order) | | `has_range`, `get_bytes`, `Read` | scan all buffers | binary search, then a short backward scan (overlapping ranges are still allowed, see the diagram on `find`) | | `clear_ranges` | compare each buffer with each range | sort the ranges once, then binary search | # Are these changes tested? Yes. New unit tests in `util/push_buffers.rs`: out-of-order pushes, overlapping pushes (a small buffer inside a larger one), `clear_ranges` with exact matches only, and a randomized test that compares lookups and clears with a linear scan over 200 seeds. # Are there any user-facing changes? No. https://github.com/apache/arrow-rs/pull/11235 and https://github.com/apache/arrow-rs/pull/11236 add `release_ranges` and `retain_ranges` to the same file. The PR that merges last must keep the buffers sorted in those methods. 🤖 Generated with [Claude Code](https://claude.com/claude-code) -- 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]
