How to sort NTuple


#1

I have several integers input from a function like this

function foo(a::Int...)
end

How do I sort a? I have to collect it first and sort it as a vector at the moment. Will it possible to sort it directly?


#2

You can use https://github.com/JeffreySarnoff/SortingNetworks.jl:

julia> using SortingNetworks

julia> function foo(a::Int...)
           return swapsort(a)
       end
foo (generic function with 1 method)

julia> foo(5, 2, 4, 3, 1)
(1, 2, 3, 4, 5)

#4

Also, see TupleTools.jl


#5

Also, if your NTuple happens to live on the heap, consider Base.sort! with a pointer.

Re SortingNetworks.jl: This is really cool! But somehow 0.6 refuses to emit the good (CMOV instead of branch) code for small integers :frowning: (this gives an ~8x slowdown for Int32, Int16, Int8 compared to Int64, UInt64; for some reasons, floats are slow anyway)

Interpreting a pointer as a small array:

struct ptrArray{N,T}<:AbstractVector{T}
    ptr::Ptr{T}
end
ptrArray(ptr::Ptr{NTuple{N,T}}) where {N,T} = ptrArray{N,T}(convert(Ptr{T}, ptr))
Base.length(x::ptrArray{N,T}) where {N,T} =N 
Base.size(x::ptrArray{N,T}) where {N,T} =(N,) 
Base.getindex(x::ptrArray,i) = unsafe_load(x.ptr,i)
Base.setindex!(x::ptrArray,v,i) = unsafe_store!(x.ptr,v,i)
Base.IndexStyle(::ptrArray) = Base.IndexLinear()

Postscript: 0.7 fixes this on small integers (CMOV instead of branch), but still fails to generate branch-free code for floats (missing @fastmath leading to very complicated NaN-aware minmax?). I wonder whether someone cooked up sorting networks for vector instructions.


#6

Thanks for kind thoughts and hoorah for v0.7!