Extremely slow comparison of large ranges

[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!

[LilithHafner]

Nothing to be done on the sort side, but this should definitely be sped up by adding a specialized Base.cmp method. @StefanKarpinski, would you like to offer advice on how to compare two floating point ranges? e.g. how many bugs does this naive implementation have?

function cmp(r1::AbstractRange, r2::AbstractRange)
    (isempty(r1) || isempty(r2)) && return cmp(isempty(r2), isempty(r1))
    first(r1) != first(r2) && return cmp(first(r1), first(r2))
    length(r1) > 1 && length(r2) > 1 && step(r1) != step(r2) && return cmp(step(r1), step(r2))
    cmp(length(r1), length(r2))
end