Poor performance in sort::sort_to_indices with limit option in arrow2

[sundy-li]

Hello, I did a benchmark vs arrow1.

It shows that arrow2 has great performance improved in min, sum and max etc.

But the sort::sort_to_indices function with limit 100 has a performance drop.

Benchmark results:

arrow2-sort 2^13 f32    time:   [67.831 us 67.978 us 68.144 us]   

arrow1-sort 2^13 f32    time:   [34.306 us 34.405 us 34.521 us] 

Codes: https://github.com/sundy-li/learn/tree/master/arrow-vs-arrow2/benches

Scripts:
cargo bench -- "arrow1-sort 2\^13 f32"
cargo bench -- "arrow2-sort 2\^13 f32"

[sundy-li]

as_slice is the bottleneck.

I think we can use values: &[T] to replace get: G.

Improved in commit: datafuse-extras#1

Now:

arrow2-sort-limit 2^13 f32                                                                             
  time:   [46.601 us 46.665 us 46.728 us]
  change: [-24.847% -24.656% -24.483%] (p = 0.00 < 0.05)
  Performance has improved.

Another bottleneck is from_usize().unwrap() in the loop.

[jorgecarleitao]

Great finding; thanks for sharing!

Would you like me to backport it here?

[sundy-li]

Great finding; thanks for sharing!

Would you like me to backport it here?

Sure, after I finish the migration, I'll create pr to arrow2.