Determine possibility to sort via hasmethod(isless, (T,T) for AbstractVector{T}

I want to decide if an AbstractVector is sorted to adequately choose the code path for my algorithm. For this I first need to know if it is safe to call issorted(A). Are there faster/better/more robust ways than doing it like this:

issafelysorted(A::AbstractVector{T}) where T = isconcretetype(T) && 
    hasmethod(isless, (T,T)) &&
    (issorted(A) || issorted(A, rev = true))
# or
issafelysortedTry(x::AbstractVector{T}) where T = 
    try issorted(x) || issorted(x, rev = true) catch e false end

Both are quite expensive to call in case isless is not defined, as can be seen here:

julia> using BenchmarkTools

julia> struct Foo x end

julia> b = [Foo(4), Foo(6)]
2-element Array{Foo,1}:
 Foo(4)
 Foo(6)

julia> @btime issafelysorted($b)

  6.412 ÎĽs (4 allocations: 176 bytes)
false

julia> @btime issafelysortedTry($b)
  55.576 ÎĽs (5 allocations: 208 bytes)
false

julia> Base.isless(x::Foo,y::Foo) = x.x < y.x

julia> @btime issafelysorted($b)
  349.260 ns (1 allocation: 32 bytes)
true

julia> @btime issafelysortedTry($b)
  36.243 ns (0 allocations: 0 bytes)
true

I am confused: if you want to sort, wouldn’t you need isless anyway? So I would just assume that it exists and get a MethodError early if it doesn’t.

For this algorithm the AbstractVector doesn’t necessarily needs to be sortable, but if it is sortable and sorted I can follow a faster code path.

if sortable(A) && issorted(A)
# fast code path
else
# slow code path
end

If you don’t need the issafelysorted function to be dynamic, you could determine this at compile time with a generated function.

Maybe something like this?

@generated function issafelysorted(A::AbstractVector{T}) where T
    if isconcretetype(T) && hasmethod(isless, Tuple{T,T})
        return :(issorted(A) || issorted(A, rev=true))
    else
        return :false
    end
end
2 Likes

Thx, I might be misreading something but apparently this is now allowed (manual - metaprogramming):

Generated functions must not mutate or observe any non-constant global state (including, for example, IO, locks, non-local dictionaries, or using hasmethod ).

2 Likes

You’re correct. It’s not allowed, although it will sometimes work (the fact that it only sometimes works is exactly why it’s not allowed).

Julia makes no guarantees about when, or how often, the @generated function body will be called. By putting a hasmethod() call in there, you’re fixing the result based on whether that method happened to exist when the @generated function body was called. That can give inconsistent behavior if, for example, that generator happens to be run before the relevant isless method is defined.

4 Likes

I was asking exactly the same question a few weeks ago :slight_smile:

1 Like