Julia: searchsortedfirst fails with non-Int indices

[abhinavmehndiratta]

julia> arr = rand(1:100,10)
10-element Array{Int64,1}:
 78
  5
 23
 35
 67
 15
 52
 24
 78
 22

julia> searchsortedfirst(arr, 70, Int32(5), Int32(10), Base.Order.Forward)
ERROR: MethodError: no method matching searchsortedfirst(::Array{Int64,1}, ::Int64, ::Int32, ::Int32, ::Base.Order.ForwardOrdering)
Closest candidates are:
  searchsortedfirst(::AbstractArray{T,1} where T, ::Any, ::Int64, ::Int64, ::Base.Order.Ordering) at sort.jl:175
  searchsortedfirst(::AbstractArray{T,1} where T, ::Any; lt, by, rev, order) at sort.jl:294
  searchsortedfirst(::AbstractArray{T,1} where T, ::Any, ::Base.Order.Ordering) at sort.jl:292
  ...
Stacktrace:
 [1] top-level scope at none:0

julia> searchsortedfirst(arr, 70, 5, 10, Base.Order.Forward)
9

https://github.com/JuliaLang/julia/blob/80516ca20297a67b996caa08c38786332379b6a5/base/sort.jl#L173
I think changing to searchsortedfirst(v::AbstractVector, x, lo::Integer, hi::Integer, o::Ordering) should fix this

[kmsquire]

TL; DR: unless you plan to add start and stop indices and an Ordering to all searchsorted* calls, there's probably not much benefit in changing this. And if it's generally useful to add all of those arguments, then it would be better to come up with a nicer interface (e.g., optionally specifying the return type as the first parameter).

Just for curiosity, what is your use case for using this version of the call (which restricts the search to a subset of indices) vs. the version which searches all of v (i.e., searchsorted(v, k))?

It seems you want this for something in LightGraphs.jl, but I don't see any calls in that repo which would be affected by this change currently--they all call searchsorted(v, k), without providing start and stop indices, so the return type would always be Int64 (on a 64-bit system).

Note that the given change will allow the call above with Int32 index values to work, but without more changes, the return value is still going to be an Int64 on a 64-bit system, because all of the constants (1's) in the function are of type Int64, and the sum of an Int64 and an Int32 will be an Int64 (even if the constant being added is 1).

So to also get the return value to be Int32 in this case, one would need to capture the type of lo and hi, and convert all constants to that type:

function searchsortedfirst(v::AbstractVector, x, lo::N, hi::N, o::Ordering) where N<:Union{Int32,Int64}
    lo = lo-one(N)
    hi = hi+one(N)
    @inbounds while lo < hi-one(N)
        m = (lo+hi)>>>1
        if lt(o, v[m], x)
            lo = m
        else
            hi = m
        end
    end
    return hi
end

Cc: @sbromberger

[kmsquire]

30763 describes a related issue with searchsorted, where the fix I give above should fix the problem.

(I'm still not sure it will provide any benefit here, though.)

[abhinavmehndiratta]

Thank you for your suggestions @kmsquire . LightGraphs uses ldiv! function here -
https://github.com/JuliaGraphs/LightGraphs.jl/blob/d08ab6bb29ac41e0abbda7646f0332fa9c9aa6c3/src/centrality/katz.jl#L36
which in turn uses this -
https://github.com/JuliaLang/julia/blob/b4e1d0eef9c8f2fe3a6e43847bb96cceeac4f4fc/stdlib/SparseArrays/src/linalg.jl#L516
i1 & i2 are of types colptr of the adjacency matrix. Now,I am using UInt64 for the colptr of adjacency matrix, hence the error.
This problem is not on Julia v1.0 though, the ldiv! function for triangular matrices was modified in #28507.

[kmsquire]

Ok, got it. Is there a benefit to using UInt64 over Int64 (or justInt)? Despite the fact that most indexing is strictly positive, it's more standard in Julia to use Int/Int32/Int64 for indexing.

[abhinavmehndiratta]

Ok, got it. Is there a benefit to using UInt64 over Int64 (or justInt)? Despite the fact that most indexing is strictly positive, it's more standard in Julia to use Int/Int32/Int64 for indexing.

The maximum number of edges for a graph can be nv*(nv-1)/2 . We cannot use Int64 for indexing in case the number of edges is more than typemax(Int64). Though, even I don't see the benefit of using UInt64 over Int64 in case of SimpleGraphs since the number of edges is restricted to Int
https://github.com/JuliaGraphs/LightGraphs.jl/blob/9a57a56d5643c7c66b4dcfa965a1ec4349e55eb4/src/SimpleGraphs/simplegraph.jl#L9
CC: @sbromberger

[sbromberger]

The issue is not necessarily with (or limited to) UInt64, but applies to other types (like UInt16 or Int32). In LG we try to minimize memory usage wherever possible, so we have places where indices aren't Int but are <:Integer.

[sbromberger]

See also #31617.

[kmsquire]

The issue is not necessarily with (or limited to) UInt64, but applies to other types (like UInt16 or Int32). In LG we try to minimize memory usage wherever possible, so we have places where indices aren't Int but are <:Integer.

Just for curiosity, what is the underlying array type indexed into with these indices?

30763 loosens the type on the index to be either Int32 or Int64, so will have to be updated.

Can you provide some code which errors on searchsorted*? That would make it easier to write tests.

[sbromberger]

Just for curiosity, what is the underlying array type indexed into with these indices?

It depends. It's always <: Integer but it's the type of the vertex index, which can be as little as UInt8 for very small graphs. On the upper bound, I don't know that UInt128 is well-defined but it might be.

Can you provide some code which errors on searchsorted*? That would make it easier to write tests.

See the first comment:

arr = rand(1:100,10);
searchsortedfirst(arr, 70, Int32(5), Int32(10), Base.Order.Forward)

will do it – if you replace Int32 with something else (say, UIn16), it should also fail.

[kmsquire]

Just for curiosity, what is the underlying array type indexed into with these indices?

It depends. It's always <: Integer but it's the type of the vertex index, which can be as little as UInt8 for very small graphs. On the upper bound, I don't know that UInt128 is well-defined but it might be.

Okay, my question wasn't very clear. I was really just wondering if you were indexing into Arrays, SparseArrays, StaticArrays, etc. All of the above? Any of the above?

See the first comment:

arr = rand(1:100,10);
searchsortedfirst(arr, 70, Int32(5), Int32(10), Base.Order.Forward)

will do it – if you replace Int32 with something else (say, UInt16), it should also fail.

Okay, I guess that answers my direct question (how to write a test), but I was more curious about the real world code that triggers this problem. Searching through LightGraphs, I don't see any calls to searchsortedfirst(arr, value, start, end, order). That's generally meant to be an internal method, although it is obviously exported.

Are you currently calling that function directly, or do you plan to in the near future? If so, maybe the interface should be simpified (e.g., by setting a default value for the order, at the very least).

Or are you triggering an error through some other code path? Because just calling the more standard searchsortedfirst(arr, 70) should never trigger an error on an Array (hence, my question above).

[abhinavmehndiratta]

Okay, my question wasn't very clear. I was really just wondering if you were indexing into Arrays, SparseArrays, StaticArrays, etc. All of the above? Any of the above?

Currently indexing into SparseArrays.

Are you currently calling that function directly, or do you plan to in the near future?

As of now, there are no direct calls to the function but as I pointed out earlier it is part of the ldiv! function that LightGraphs uses.

[kmsquire]

Currently indexing into SparseArrays.

Cool, thanks!

As of now, there are no direct calls to the function but as I pointed out earlier it is part of the ldiv! function that LightGraphs uses.

Thanks, sorry I missed that.

I'll update #30763.

It would still be nice to see an actual example of some code that fails--can you provide a code example that calls katz_centrality that can be copy and pasted into the terminal, and which errors on one of the searchsorted* functions?

[abhinavmehndiratta]

It would still be nice to see an actual example of some code that fails--can you provide a code example that calls katz_centrality that can be copy and pasted into the terminal, and which errors on one of the searchsorted* functions?

Sure, here (on Julia v1.1.0) -

julia> using LightGraphs

julia> g5 = SimpleDiGraph{Int64}(4)
{4, 0} directed simple Int64 graph

julia> add_edge!(g5, 1, 2); add_edge!(g5, 2, 3); add_edge!(g5, 1, 3); add_edge!(g5, 3, 4)
true

julia> katz_centrality(g5)
4-element Array{Float64,1}:
 0.3576644741698725
 0.4649638164208343
 0.6044529613470845
 0.5390003625739979

julia> g5 = DiGraph{UInt64}(g5) 
{4, 4} directed simple UInt64 graph

julia> katz_centrality(g5)
ERROR: MethodError: no method matching searchsortedfirst(::Array{UInt64,1}, ::Int64, ::UInt64, ::UInt64, ::Base.Order.ForwardOrdering)

[abhinavmehndiratta]

Closing issue as #31633 fixes this.