adriangb opened a new pull request, #11459: URL: https://github.com/apache/arrow-rs/pull/11459
# Which issue does this PR close? - Closes https://github.com/apache/arrow-rs/issues/11458. This PR is stacked on https://github.com/apache/arrow-rs/pull/11235. Only the last commit is new: https://github.com/apache/arrow-rs/pull/11235 must merge first, and then I will rebase this PR. The new commit is https://github.com/apache/arrow-rs/commit/4eb95e77ad14408b2102bf24d87d8e0486b6a17b. # Rationale for this change `PushBuffers::release_ranges` visits all buffered ranges on each call. A caller that buffers many ranges pays `O(buffers)` for each call, also when the call releases nothing. # What changes are included in this PR? `release_ranges` now finds the buffers that can overlap a released range with a binary search, as `PushBuffers::find` does. It uses the sort order and `max_len` for this. The trim and split logic does not change. The steps after the trim also do less work. The removal of released buffers looks only at the buffers between the first and the last trimmed buffer. The sort runs only after a split. The `max_len` update runs only if a buffer of length `max_len` was trimmed. With 100,000 buffers, a call that releases nothing goes from 37 µs to 61 ns. A call that removes buffers at the front still moves the later buffers down in the `Vec`, so it is only 2 times faster. <details> <summary>Benchmark numbers and edge cases</summary> Time for each `release_ranges` call, from a temporary timing test (release build, Apple silicon). The test is not part of this PR. | Buffers | Call | Before | After | |--|--|--|--| | 1,000 | releases nothing | 495 ns | 55 ns | | 10,000 | releases nothing | 3.5 µs | 67 ns | | 100,000 | releases nothing | 37 µs | 61 ns | | 1,000 | trims one buffer | 1.5 µs | 82 ns | | 10,000 | trims one buffer | 8.5 µs | 91 ns | | 100,000 | trims one buffer | 86 µs | 81 ns | | 10,000 | removes 10 buffers at the front | 9.2 µs | 4.4 µs | | 100,000 | removes 10 buffers at the front | 92 µs | 44 µs | | 10,000 | removes 10 buffers at the end | 9.6 µs | 1.1 µs | | 100,000 | removes 10 buffers at the end | 94 µs | 8.6 µs | The "removes" rows start with the given number of buffers and release 10 buffers for each call until no buffer remains. Thus, the average call sees half of the buffers. - Removal at the front: `Vec::drain` moves all later buffers down. This is one `memmove` for each `Vec`, and it is the remaining `O(buffers)` cost. A different data structure is necessary to remove it. - `max_len`: if a trimmed buffer had length `max_len`, `release_ranges` computes `max_len` again from all buffers. This keeps `max_len` exact, so that lookups stay fast. The "removes at the end" rows show this cost. - Empty buffers: `push_range` accepts empty and inverted ranges, and `release_ranges` removes all of them when it releases bytes. To keep this behavior without a visit of all buffers, `PushBuffers` now counts the empty buffers. `release_ranges` looks at all buffers only if the count is not zero. - Sort order: a trim moves the start of a buffer only past released bytes, so the trimmed buffers stay in order. Only split parts can be out of order, and the sort now runs only after a split. </details> # Are these changes tested? Yes. The existing tests cover this, in particular `fuzz_release_ranges_matches_rebuild`, which compares `release_ranges` with a full rebuild and checks the sort order, `max_len` and `buffered_bytes`. `assert_invariants` now also checks the count of empty buffers. # Are there any user-facing changes? No. 🤖 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]
