This is an automated email from the ASF dual-hosted git repository.
dheres 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 83b6908f92 Unroll interleave -25-30% (#9542)
83b6908f92 is described below
commit 83b6908f92de32c6695d95d7dc2b0a0116aa3185
Author: Daniël Heres <[email protected]>
AuthorDate: Sat Mar 14 18:50:38 2026 +0100
Unroll interleave -25-30% (#9542)
# Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and
enhancements and this helps us generate change logs for our releases.
You can link an issue to this PR using the GitHub syntax.
-->
- Closes #NNN.
# Rationale for this change
```
🤖: Benchmark completed
Details
group
main interleave
-----
---- -----------
interleave dict(20, 0.0) 100 [0..100, 100..230, 450..1000]
1.08 805.6±8.28ns ? ?/sec 1.00 748.5±14.05ns
? ?/sec
interleave dict(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000]
1.18 2.6±0.00µs ? ?/sec 1.00 2.2±0.01µs
? ?/sec
interleave dict(20, 0.0) 1024 [0..100, 100..230, 450..1000]
1.21 2.6±0.01µs ? ?/sec 1.00 2.2±0.02µs
? ?/sec
interleave dict(20, 0.0) 400 [0..100, 100..230, 450..1000]
1.16 1431.6±3.11ns ? ?/sec 1.00 1232.9±14.26ns
? ?/sec
interleave dict_distinct 100
1.03 2.9±0.12µs ? ?/sec 1.00 2.9±0.07µs
? ?/sec
interleave dict_distinct 1024
1.02 2.9±0.06µs ? ?/sec 1.00 2.8±0.03µs
? ?/sec
interleave dict_distinct 2048
1.03 2.9±0.02µs ? ?/sec 1.00 2.8±0.08µs
? ?/sec
interleave dict_sparse(20, 0.0) 100 [0..100, 100..230, 450..1000]
1.00 2.7±0.26µs ? ?/sec 1.02 2.8±0.21µs
? ?/sec
interleave dict_sparse(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000]
1.11 5.3±0.31µs ? ?/sec 1.00 4.8±0.40µs
? ?/sec
interleave dict_sparse(20, 0.0) 1024 [0..100, 100..230, 450..1000]
1.16 4.8±0.25µs ? ?/sec 1.00 4.1±0.23µs
? ?/sec
interleave dict_sparse(20, 0.0) 400 [0..100, 100..230, 450..1000]
1.05 3.5±0.31µs ? ?/sec 1.00 3.3±0.29µs
? ?/sec
interleave i32(0.0) 100 [0..100, 100..230, 450..1000]
1.21 313.8±1.03ns ? ?/sec 1.00 258.9±4.98ns
? ?/sec
interleave i32(0.0) 1024 [0..100, 100..230, 450..1000, 0..1000]
1.34 1856.5±17.40ns ? ?/sec 1.00 1385.9±32.73ns
? ?/sec
interleave i32(0.0) 1024 [0..100, 100..230, 450..1000]
1.34 1848.6±8.80ns ? ?/sec 1.00 1382.4±48.64ns
? ?/sec
interleave i32(0.0) 400 [0..100, 100..230, 450..1000]
1.37 843.3±7.37ns ? ?/sec 1.00 615.5±22.71ns
? ?/sec
interleave i32(0.5) 100 [0..100, 100..230, 450..1000]
1.09 604.2±5.60ns ? ?/sec 1.00 555.1±4.48ns
? ?/sec
interleave i32(0.5) 1024 [0..100, 100..230, 450..1000, 0..1000]
1.12 4.3±0.01µs ? ?/sec 1.00 3.8±0.04µs
? ?/sec
interleave i32(0.5) 1024 [0..100, 100..230, 450..1000]
1.13 4.4±0.06µs ? ?/sec 1.00 3.9±0.17µs
? ?/sec
interleave i32(0.5) 400 [0..100, 100..230, 450..1000]
1.12 1889.4±19.68ns ? ?/sec 1.00 1691.5±17.15ns
? ?/sec
interleave list<i64>(0.0,0.0,20) 100 [0..100, 100..230, 450..1000]
1.07 2.7±0.03µs ? ?/sec 1.00 2.5±0.03µs
? ?/sec
interleave list<i64>(0.0,0.0,20) 1024 [0..100, 100..230, 450..1000,
0..1000] 1.06 26.2±0.11µs ? ?/sec 1.00
24.6±0.31µs ? ?/sec
interleave list<i64>(0.0,0.0,20) 1024 [0..100, 100..230, 450..1000]
1.06 25.9±0.14µs ? ?/sec 1.00 24.5±0.29µs
? ?/sec
interleave list<i64>(0.0,0.0,20) 400 [0..100, 100..230, 450..1000]
1.07 10.5±0.21µs ? ?/sec 1.00 9.9±0.06µs
? ?/sec
interleave list<i64>(0.1,0.1,20) 100 [0..100, 100..230, 450..1000]
1.05 5.8±0.25µs ? ?/sec 1.00 5.5±0.06µs
? ?/sec
interleave list<i64>(0.1,0.1,20) 1024 [0..100, 100..230, 450..1000,
0..1000] 1.05 47.4±2.23µs ? ?/sec 1.00
45.2±0.14µs ? ?/sec
interleave list<i64>(0.1,0.1,20) 1024 [0..100, 100..230, 450..1000]
1.06 48.0±2.35µs ? ?/sec 1.00 45.5±0.64µs
? ?/sec
interleave list<i64>(0.1,0.1,20) 400 [0..100, 100..230, 450..1000]
1.05 19.2±0.90µs ? ?/sec 1.00 18.2±0.03µs
? ?/sec
interleave str(20, 0.0) 100 [0..100, 100..230, 450..1000]
1.01 786.8±1.50ns ? ?/sec 1.00 779.4±4.35ns
? ?/sec
interleave str(20, 0.0) 1024 [0..100, 100..230, 450..1000, 0..1000]
1.04 6.3±0.12µs ? ?/sec 1.00 6.0±0.02µs
? ?/sec
interleave str(20, 0.0) 1024 [0..100, 100..230, 450..1000]
1.04 6.2±0.08µs ? ?/sec 1.00 6.0±0.01µs
? ?/sec
interleave str(20, 0.0) 400 [0..100, 100..230, 450..1000]
1.09 2.7±0.01µs ? ?/sec 1.00 2.4±0.01µs
? ?/sec
interleave str(20, 0.5) 100 [0..100, 100..230, 450..1000]
1.04 1064.4±19.37ns ? ?/sec 1.00 1023.8±3.56ns
? ?/sec
interleave str(20, 0.5) 1024 [0..100, 100..230, 450..1000, 0..1000]
1.03 10.3±0.06µs ? ?/sec 1.00 10.1±0.13µs
? ?/sec
interleave str(20, 0.5) 1024 [0..100, 100..230, 450..1000]
1.02 10.3±0.05µs ? ?/sec 1.00 10.1±0.54µs
? ?/sec
interleave str(20, 0.5) 400 [0..100, 100..230, 450..1000]
1.04 3.7±0.03µs ? ?/sec 1.00 3.6±0.17µs
? ?/sec
interleave str_view(0.0) 100 [0..100, 100..230, 450..1000]
1.01 856.9±2.90ns ? ?/sec 1.00 849.1±7.00ns
? ?/sec
interleave str_view(0.0) 1024 [0..100, 100..230, 450..1000, 0..1000]
1.00 5.0±0.15µs ? ?/sec 1.02 5.1±0.02µs
? ?/sec
interleave str_view(0.0) 1024 [0..100, 100..230, 450..1000]
1.00 4.9±0.05µs ? ?/sec 1.04 5.1±0.02µs
? ?/sec
interleave str_view(0.0) 400 [0..100, 100..230, 450..1000]
1.00 2.2±0.05µs ? ?/sec 1.03 2.2±0.01µs
? ?/sec
interleave struct(i32(0.0), i32(0.0) 100 [0..100, 100..230, 450..1000]
1.20 874.3±4.12ns ? ?/sec 1.00 729.1±12.04ns
? ?/sec
interleave struct(i32(0.0), i32(0.0) 1024 [0..100, 100..230, 450..1000,
0..1000] 1.34 4.0±0.01µs ? ?/sec 1.00
3.0±0.02µs ? ?/sec
interleave struct(i32(0.0), i32(0.0) 1024 [0..100, 100..230, 450..1000]
1.31 4.0±0.04µs ? ?/sec 1.00 3.0±0.01µs
? ?/sec
interleave struct(i32(0.0), i32(0.0) 400 [0..100, 100..230, 450..1000]
1.24 1905.1±19.48ns ? ?/sec 1.00 1532.8±33.13ns
? ?/sec
interleave struct(i32(0.0), str(20, 0.0) 100 [0..100, 100..230, 450..1000]
1.00 1340.9±6.76ns ? ?/sec 1.01 1347.8±12.50ns
? ?/sec
interleave struct(i32(0.0), str(20, 0.0) 1024 [0..100, 100..230, 450..1000,
0..1000] 1.08 8.3±0.16µs ? ?/sec 1.00 7.7±0.02µs
? ?/sec
interleave struct(i32(0.0), str(20, 0.0) 1024 [0..100, 100..230, 450..1000]
1.08 8.3±0.06µs ? ?/sec 1.00 7.7±0.06µs
? ?/sec
interleave struct(i32(0.0), str(20, 0.0) 400 [0..100, 100..230, 450..1000]
1.09 3.7±0.13µs ? ?/sec 1.00 3.4±0.02µs
? ?/sec
interleave struct(str(20, 0.0), str(20, 0.0)) 100 [0..100, 100..230,
450..1000] 1.05 1927.3±9.31ns ? ?/sec 1.00
1842.2±18.19ns ? ?/sec
interleave struct(str(20, 0.0), str(20, 0.0)) 1024 [0..100, 100..230,
450..1000, 0..1000] 1.04 12.6±0.06µs ? ?/sec 1.00
12.1±0.08µs ? ?/sec
interleave struct(str(20, 0.0), str(20, 0.0)) 1024 [0..100, 100..230,
450..1000] 1.04 12.6±0.03µs ? ?/sec 1.00
12.1±0.14µs ? ?/sec
interleave struct(str(20, 0.0), str(20, 0.0)) 400 [0..100, 100..230,
450..1000] 1.04 5.4±0.07µs ? ?/sec 1.00
5.2±0.04µs ? ?/sec
```
# What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it
is sometimes worth providing a summary of the individual changes in this
PR.
-->
# Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example,
are they covered by existing tests)?
-->
# Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be
updated before approving the PR.
If there are any breaking changes to public APIs, please call them out.
-->
---------
Co-authored-by: Claude Opus 4.6 (1M context) <[email protected]>
---
arrow-select/src/interleave.rs | 51 +++++++++++++++++++++++++++++++++++++-----
1 file changed, 46 insertions(+), 5 deletions(-)
diff --git a/arrow-select/src/interleave.rs b/arrow-select/src/interleave.rs
index be4e98ffcc..711e816f70 100644
--- a/arrow-select/src/interleave.rs
+++ b/arrow-select/src/interleave.rs
@@ -154,13 +154,54 @@ fn interleave_primitive<T: ArrowPrimitiveType>(
data_type: &DataType,
) -> Result<ArrayRef, ArrowError> {
let interleaved = Interleave::<'_, PrimitiveArray<T>>::new(values,
indices);
+ let arrays = &interleaved.arrays;
+ let len = indices.len();
+
+ let mut output = Vec::with_capacity(len);
+ let dst: *mut T::Native = output.as_mut_ptr();
+ let mut base = 0;
+
+ // Process 8 elements at a time to issue multiple independent loads
+ // and increase memory-level parallelism for random access patterns.
+ let chunks = indices.chunks_exact(8);
+ let remainder = chunks.remainder();
+ for chunk in chunks {
+ let v0 = arrays[chunk[0].0].value(chunk[0].1);
+ let v1 = arrays[chunk[1].0].value(chunk[1].1);
+ let v2 = arrays[chunk[2].0].value(chunk[2].1);
+ let v3 = arrays[chunk[3].0].value(chunk[3].1);
+ let v4 = arrays[chunk[4].0].value(chunk[4].1);
+ let v5 = arrays[chunk[5].0].value(chunk[5].1);
+ let v6 = arrays[chunk[6].0].value(chunk[6].1);
+ let v7 = arrays[chunk[7].0].value(chunk[7].1);
+
+ // SAFETY: base+7 < len == output capacity
+ debug_assert!(base + 7 < len);
+ unsafe {
+ dst.add(base).write(v0);
+ dst.add(base + 1).write(v1);
+ dst.add(base + 2).write(v2);
+ dst.add(base + 3).write(v3);
+ dst.add(base + 4).write(v4);
+ dst.add(base + 5).write(v5);
+ dst.add(base + 6).write(v6);
+ dst.add(base + 7).write(v7);
+ }
+ base += 8;
+ }
- let values = indices
- .iter()
- .map(|(a, b)| interleaved.arrays[*a].value(*b))
- .collect::<Vec<_>>();
+ for idx in remainder {
+ // SAFETY: base < len == output capacity
+ debug_assert!(base < len);
+ unsafe { dst.add(base).write(arrays[idx.0].value(idx.1)) };
+ base += 1;
+ }
+
+ // SAFETY: all `len` elements have been initialized
+ debug_assert!(base == len);
+ unsafe { output.set_len(len) };
- let array = PrimitiveArray::<T>::try_new(values.into(),
interleaved.nulls)?;
+ let array = PrimitiveArray::<T>::try_new(output.into(),
interleaved.nulls)?;
Ok(Arc::new(array.with_data_type(data_type.clone())))
}
