Sorting could be much faster

[jw3126]

using SortingNetworks: swapsort
using StaticArrays

for N in 5:10
    @show N
    @btime sort($v) setup=(v = SVector{$N}(rand($N)))
    println("swapsort")
    @btime swapsort($v) setup=(v = SVector{$N}(rand($N)))
end

N = 5
sort
  7.938 ns (0 allocations: 0 bytes)
swapsort
  2.000 ns (0 allocations: 0 bytes)
N = 6
sort
  12.933 ns (0 allocations: 0 bytes)
swapsort
  2.190 ns (0 allocations: 0 bytes)
N = 7
sort
  20.211 ns (0 allocations: 0 bytes)
swapsort
  2.920 ns (0 allocations: 0 bytes)
N = 8
sort
  23.454 ns (0 allocations: 0 bytes)
swapsort
  3.460 ns (0 allocations: 0 bytes)
N = 9
sort
  28.281 ns (0 allocations: 0 bytes)
swapsort
  4.570 ns (0 allocations: 0 bytes)
N = 10
sort
  33.484 ns (0 allocations: 0 bytes)
swapsort
  5.280 ns (0 allocations: 0 bytes)

[stev47]

since swapsort uses < to sort, you should make the comparison fair:

julia> for N in 5:10
           @show N
           @btime sort(v; lt = <) setup=(v = SVector{$N}(rand($N)))
           println("swapsort")
           @btime swapsort(v) setup=(v = SVector{$N}(rand($N)))
       end

N = 5
  2.375 ns (0 allocations: 0 bytes)
swapsort
  2.305 ns (0 allocations: 0 bytes)
N = 6
  2.794 ns (0 allocations: 0 bytes)
swapsort
  2.793 ns (0 allocations: 0 bytes)
N = 7
  4.260 ns (0 allocations: 0 bytes)
swapsort
  3.771 ns (0 allocations: 0 bytes)
N = 8
  7.621 ns (0 allocations: 0 bytes)
swapsort
  3.911 ns (0 allocations: 0 bytes)
N = 9
  6.635 ns (0 allocations: 0 bytes)
swapsort
  5.797 ns (0 allocations: 0 bytes)
N = 10
  7.552 ns (0 allocations: 0 bytes)
swapsort
  6.775 ns (0 allocations: 0 bytes)

so, yes there is a small difference but the the Bitonic sorting network implementation in StaticArrays is general as opposed to the hard-coded minimal ones in SortingNetworks and allow for potential SIMD use in the future, see #952

[jw3126]

Thanks a lot for pointing this out. For my understanding, the slowdown we see in my benchmark is the price we pay for being able to sort arrays that can contain NaN. Is that correct or is there another difference in semantics?