sunchao opened a new pull request, #10849: URL: https://github.com/apache/arrow-rs/pull/10849
## Why are the changes needed? ### Which issue does this PR close? Closes https://github.com/apache/arrow-rs/issues/10846. Benchmark source is supplied separately in https://github.com/apache/arrow-rs/pull/10848, following the contributor guide's benchmark-first workflow. ### Rationale for this change Selecting two early logical indices currently scans the remaining physical runs even after both outputs are known. A short logical slice can likewise retain a large backing buffer and scan beyond the relevant range. ## What changes were proposed in this PR? ### What changes are included in this PR? Find the physical run containing the already-validated largest requested logical index once, then bound the existing iteration with a slice. The inner loop is unchanged. Enumerating before skipping retains the original physical indices; the existing bounds checks and error fallback remain in place. ### Are there any user-facing changes? Small selections that end early in a large backing buffer avoid scanning later runs. Results, ordering, duplicate handling, slicing, bounds errors, and the public API are unchanged. This is not a new sparse-lookup algorithm for arbitrary distant indices. ## How was this PR tested? ### Are these changes tested? - All 345 `arrow-buffer` library tests passed, including a new reordered/duplicate prefix test with sliced and invalid-index controls. - Formatting and affected-crate, all-target, all-feature Clippy with warnings denied passed. - Two repeated baseline/patch comparisons used independent build directories after compilation, with no concurrent task test/build workload. The benchmark-only commit was applied for these measurements. Representative first-run Criterion point estimates: | Case | Base | Patch | | --- | ---: | ---: | | Prefix, 1,024 runs | 352 ns | 44 ns | | Sliced prefix, 1,024 runs | 205 ns | 45 ns | | All indices, 1,024 runs | 1.63 us | 1.44 us | | Prefix, 1,048,576 runs | 264 us | 89 ns | | Sliced prefix, 1,048,576 runs | 133 us | 134 ns | | All indices, 1,048,576 runs | 1.66 ms | 1.44 ms | Both repeats improved prefix cases and showed no full-scan-control regression. These are local microbenchmarks, not an end-to-end query-speedup claim. Earlier shared-target comparisons were discarded because Cargo reused a binary across worktrees; an iterator-`take` variant also regressed full scans and is not included in this PR. AI assistance: Codex generated the implementation, regression test, benchmark, and PR text, and performed the stated local checks and source review. This does not claim a separate human review. -- 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]
