Sort extremely slow for `Vector` of large `UnitRange`s

[jakewilliami]

While doing a programming puzzle, I noticed that the performance of sorting Vector{UnitRange{T}} seems to depend heavily on the size of the elements that are being sorted.

I'm not sure if this has been raised before, and it's not a bug per se, but I thought it would be useful to discuss if there are ways this could be faster.

I think it will be using this method, which has to check many steps in the range (though someone like @LilithHafner will have a much better idea where the levels of dispatching stops for Vector{UnitRange{T}}).

julia> @time sort([1:3, 1:2, 5:3])
  0.000001 seconds (2 allocations: 112 bytes)
3-element Vector{UnitRange{Int64}}:
 5:4
 1:2
 1:3

julia> @time sort([1:30_000_000_000, 1:20_000_000_000, 50_000_000_000:3])
  9.416790 seconds (2 allocations: 112 bytes)
3-element Vector{UnitRange{Int64}}:
 50000000000:49999999999
 1:20000000000
 1:30000000000

[mlechu]

julia> @time @eval Base.cmp(1:30_000_000_000, 1:20_000_000_000)
  7.477206 seconds (92 allocations: 3.609 KiB)

I would imagine there are ways this could be faster :)

[jakewilliami]

@mlechu nice catch—I didn't realise that's part of the reason it's so slow!