YUZHEthefool opened a new pull request, #10605: URL: https://github.com/apache/arrow-rs/pull/10605
# Which issue does this PR close? - Closes #10604. # Rationale for this change `byte_view_rank` currently materializes full byte slices and compares them throughout the sort. For view values longer than the 12-byte inline capacity, this can repeatedly dereference backing buffers in the O(n log n) comparison loop. #10600 adds the standard fixed- and variable-length `StringView` rank benchmarks. This PR follows up on that baseline with an optimization plus sparse-long and prefix-collision pressure cases. It is independent of #10600 at the code level so the benchmark-only PR remains focused on its original coverage task. # What changes are included in this PR? - Sort fully inline views using their precomputed `u128` inline keys. - Cache a big-endian 16-byte key once for long and mixed views, resolving full values only when keys collide. - Sample up to eight valid values across two local windows and fall back to the existing slice path when the sampled key-collision rate is high. - Return early from sampling when four equal keys already guarantee the fallback threshold. - Add sparse-long, 7-byte common-prefix, and 16-byte all-collision benchmarks, including nullable variants where relevant. - Add `StringView` and `BinaryView` correctness tests for key collisions, zero bytes, prefix-length relationships, duplicates, nulls, and all sort option combinations. # Are these changes tested? Yes. - `cargo test -p arrow-ord`: 272 unit tests and 6 doctests passed. - `cargo clippy -p arrow-ord --all-targets -- -D warnings` passed. - `cargo fmt --all -- --check` passed. - `cargo bench -p arrow --features test_utils --bench sort_kernel -- "rank string_view"` passed. Criterion results for 4,096 values on x86-64 Windows, comparing separate clean-`main` and proposed builds: | Case | `main` | Proposed | Change | | --- | ---: | ---: | ---: | | `string_view[10]` | 190.13 us | 38.96 us | -79.4% | | `string_view[10]` nulls | 80.46 us | 22.38 us | -72.3% | | `string_view[0-13]` sparse long | 244.57 us | 73.98 us | -69.9% | | `string_view[0-400]` | 235.66 us | 51.36 us | -78.2% | | `string_view[0-400]` nulls | 95.69 us | 27.31 us | -71.5% | | `string_view[13-100]` same 7-byte prefix | 480.16 us | 53.34 us | -89.1% | | `string_view[13-100]` same prefix, nulls | 206.60 us | 26.19 us | -87.0% | | `string_view[24]` same 16-byte prefix | 132.59 us | 132.79 us | no significant change (`p = 0.11`) | | `string_view[24]` same prefix, nulls | 62.76 us | 62.58 us | no significant change (`p = 0.06`) | An index-only comparator prototype regressed these workloads by 20-43%, and using the 16-byte key without fallback regressed the all-collision case by about 71%. The adaptive fallback is what preserves the existing worst-case behavior. # Are there any user-facing changes? No API or behavior changes. This only changes the internal rank implementation and adds benchmark coverage. -- 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]
