# 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

1 Like