askoa commented on PR #3622:
URL: https://github.com/apache/arrow-rs/pull/3622#issuecomment-1407681130
I added a different approach to find physical indices for give logical
indices. This approach sorts the input logical indices and then loops through
run_ends array instead of doing a binary search.
I ran benchmarks comparing the two approaches. When the length of physical
array and take indices are higher, the loop based approach is the clear winner
with over 30% improvement compared to binary search approach. However for
inputs of smaller size, the binary search approach seems to have better
performance. I have furnished the results below. In the below benchmark
results, the feature `take_run_loop` uses the loop based approach.
```
cargo bench --bench primitive_run_take -- --save-baseline="take_run"
cargo bench --features="take_run_loop" --bench primitive_run_take --
--baseline="take_run"
```
<details>
<summary>Benchmark result</summary>
```
primitive_run_take/(run_array_len:1024, physical_array_len:512, take_len:4)
time: [2.1093 µs 2.1189 µs 2.1308 µs]
change: [-0.7829% -0.2254% +0.3476%] (p = 0.43 >
0.05)
No change in performance detected.
Found 3 outliers among 100 measurements (3.00%)
3 (3.00%) high mild
primitive_run_take/(run_array_len:1024, physical_array_len:512, take_len:16)
time: [2.4320 µs 2.4392 µs 2.4484 µs]
change: [-3.0738% -2.1892% -1.3544%] (p = 0.00 <
0.05)
Performance has improved.
Found 11 outliers among 100 measurements (11.00%)
4 (4.00%) high mild
7 (7.00%) high severe
primitive_run_take/(run_array_len:1024, physical_array_len:512, take_len:64)
time: [3.8899 µs 3.8999 µs 3.9125 µs]
change: [+3.5299% +4.5620% +5.4698%] (p = 0.00 <
0.05)
Performance has regressed.
Found 11 outliers among 100 measurements (11.00%)
2 (2.00%) high mild
9 (9.00%) high severe
primitive_run_take/(run_array_len:512, physical_array_len:64, take_len:256)
time: [9.4130 µs 9.4375 µs 9.4719 µs]
change: [+14.863% +17.956% +20.601%] (p = 0.00 <
0.05)
Performance has regressed.
Found 12 outliers among 100 measurements (12.00%)
5 (5.00%) high mild
7 (7.00%) high severe
primitive_run_take/(run_array_len:512, physical_array_len:128, take_len:512)
time: [16.928 µs 16.995 µs 17.081 µs]
change: [+3.4116% +4.2677% +5.0618%] (p = 0.00 <
0.05)
Performance has regressed.
Found 18 outliers among 100 measurements (18.00%)
4 (4.00%) high mild
14 (14.00%) high severe
primitive_run_take/(run_array_len:1024, physical_array_len:256, take_len:128)
time: [5.7324 µs 5.7492 µs 5.7709 µs]
change: [+11.442% +11.876% +12.367%] (p = 0.00 <
0.05)
Performance has regressed.
Found 5 outliers among 100 measurements (5.00%)
3 (3.00%) high mild
2 (2.00%) high severe
primitive_run_take/(run_array_len:1024, physical_array_len:512,
take_len:1024)
time: [40.290 µs 40.403 µs 40.548 µs]
change: [-30.546% -30.184% -29.833%] (p = 0.00 <
0.05)
Performance has improved.
Found 15 outliers among 100 measurements (15.00%)
6 (6.00%) high mild
9 (9.00%) high severe
primitive_run_take/(run_array_len:2048, physical_array_len:1024,
take_len:1024)
time: [40.288 µs 40.376 µs 40.488 µs]
change: [-33.022% -32.420% -31.912%] (p = 0.00 <
0.05)
Performance has improved.
Found 10 outliers among 100 measurements (10.00%)
3 (3.00%) high mild
7 (7.00%) high severe
```
</details>
--
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]
