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

General Usage
1

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
2

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.

3

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
4

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
5

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
6

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
7

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

1 Like