YUZHEthefool opened a new issue, #10604: URL: https://github.com/apache/arrow-rs/issues/10604
### Is your feature request related to a problem or challenge? `arrow_ord::rank` currently handles `Utf8View` and `BinaryView` by materializing `Vec<(&[u8], u32)>` and sorting the full slices. This is robust when many values share a prefix, but comparisons repeatedly operate on slice descriptors and can dereference backing buffers for values longer than the 12-byte inline capacity. #10600 adds the missing fixed- and variable-length `StringView` rank benchmarks. Those baselines, together with additional long-value and prefix-collision cases, show that there is substantial room to reduce comparison cost while preserving the existing behavior for adversarial collisions. ### Describe the solution you'd like Cache a sortable key once per value before sorting: - For fully inline arrays, convert each raw view to the same `u128` key used by the byte-view sort path. - For arrays with backing buffers, cache the first 16 bytes as a big-endian `u128` and resolve the full value only when two keys collide. - Sample valid values from small local windows in both halves of the array. If roughly one third of sampled keys collide, fall back to the existing slice-based implementation. - Return early from collision sampling when four equal keys already guarantee the fallback threshold. The fallback is important: always using the cached-key comparator made a workload where every value shares its first 16 bytes about 71% slower. With adaptive fallback, that workload remains statistically unchanged from the existing implementation. Criterion results for 4,096 values on x86-64 Windows, comparing a clean `main` build with the proposed implementation: | 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`) | ### Describe alternatives you've considered I prototyped sorting a `Vec<u32>` of indices and comparing the inline prefix before looking up the backing buffer. It regressed all tested workloads by 20-43% because the sort performs O(n log n) comparisons, and each comparison added branches, view lookups, and slice construction. Materializing a key once per value moves that work out of the comparison loop. Always using the 16-byte key without sampling performs well for normal and moderately colliding values, but regresses when all keys collide. Keeping the current slice path as an adaptive fallback avoids that tradeoff. ### Additional context - Related baseline benchmark PR: #10600 - Related byte-view prefix-collision work: #7350 - The implementation should cover both `StringViewArray` and `BinaryViewArray`, including zero bytes, prefix-length relationships, duplicate values, nulls, and values that differ only after byte 16. -- 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]
