This is an automated email from the ASF dual-hosted git repository.
Jefffrey pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
The following commit(s) were added to refs/heads/main by this push:
new cbbb56bba1 bench: byte view rank collisions (#10772)
cbbb56bba1 is described below
commit cbbb56bba13c85f36505453b08f22f8ab71b5794
Author: Thefool <[email protected]>
AuthorDate: Sat Aug 29 22:45:42 2026 +0800
bench: byte view rank collisions (#10772)
# Which issue does this PR close?
None. This benchmark coverage is split out of #10605 so the optimization
can be measured against the same benchmark cases on `main`.
# Rationale for this change
The existing `StringView` rank benchmarks cover fixed-length inline
values and mixed values. These cases add coverage for long values with a
sparse external-buffer path, common prefixes, and full 16-byte prefix
collisions.
# What changes are included in this PR?
- Add a sparse-long `string_view[0-13]` case.
- Add long values with a shared 7-byte prefix, including a nullable
case.
- Add long values with a shared 16-byte prefix, including a nullable
case.
This PR contains benchmark coverage only. The implementation change is
in #10605.
# Are these changes tested?
The benchmark target was run locally with:
```text
cargo bench -p arrow --features test_utils --bench sort_kernel -- "rank
string_view"
```
# Are there any user-facing changes?
No.
---
arrow/benches/sort_kernel.rs | 43 +++++++++++++++++++++++++++++++++++++++++++
1 file changed, 43 insertions(+)
diff --git a/arrow/benches/sort_kernel.rs b/arrow/benches/sort_kernel.rs
index 7e5584f090..ec9b6fd736 100644
--- a/arrow/benches/sort_kernel.rs
+++ b/arrow/benches/sort_kernel.rs
@@ -329,6 +329,13 @@ fn add_benchmark(c: &mut Criterion) {
b.iter(|| hint::black_box(rank(&arr, None).unwrap()))
});
+ // Mostly-inline values with enough 13-byte values to retain a backing
+ // buffer and therefore exercise the mixed view path.
+ let arr = create_string_view_array_with_len_range_and_seed(2usize.pow(12),
0.0, 0..14, 42);
+ c.bench_function("rank string_view[0-13] sparse long 2^12", |b| {
+ b.iter(|| hint::black_box(rank(&arr, None).unwrap()))
+ });
+
let arr = create_string_view_array(2usize.pow(12), 0.0);
c.bench_function("rank string_view[0-400] 2^12", |b| {
b.iter(|| hint::black_box(rank(&arr, None).unwrap()))
@@ -338,6 +345,42 @@ fn add_benchmark(c: &mut Criterion) {
c.bench_function("rank string_view[0-400] nulls 2^12", |b| {
b.iter(|| hint::black_box(rank(&arr, None).unwrap()))
});
+
+ // All values are longer than the inline capacity and share a 7-byte
+ // prefix, exercising collisions beyond the 4 bytes stored in the view.
+ let arr = create_longer_string_view_array_with_same_prefix(2usize.pow(12),
0.0);
+ c.bench_function("rank string_view[13-100] same prefix 2^12", |b| {
+ b.iter(|| hint::black_box(rank(&arr, None).unwrap()))
+ });
+
+ let arr = create_longer_string_view_array_with_same_prefix(2usize.pow(12),
0.5);
+ c.bench_function("rank string_view[13-100] same prefix nulls 2^12", |b| {
+ b.iter(|| hint::black_box(rank(&arr, None).unwrap()))
+ });
+
+ // All values share the same first 16 bytes, providing a worst-case
+ // collision input for prefix-key rank implementations.
+ let arr: StringViewArray = (0..2_u32.pow(12))
+ .map(|i| {
+ let suffix = i.wrapping_mul(2_654_435_761);
+ Some(format!("abcdefghijklmnop{suffix:08x}"))
+ })
+ .collect();
+ c.bench_function("rank string_view[24] same 16-byte prefix 2^12", |b| {
+ b.iter(|| hint::black_box(rank(&arr, None).unwrap()))
+ });
+
+ let arr: StringViewArray = (0..2_u32.pow(12))
+ .map(|i| {
+ (i % 2 == 0).then(|| {
+ let suffix = i.wrapping_mul(2_654_435_761);
+ format!("abcdefghijklmnop{suffix:08x}")
+ })
+ })
+ .collect();
+ c.bench_function("rank string_view[24] same 16-byte prefix nulls 2^12",
|b| {
+ b.iter(|| hint::black_box(rank(&arr, None).unwrap()))
+ });
}
criterion_group!(benches, add_benchmark);
