Strange inference problems here

General Usage
1

I’m seeing some weird behavior with respect to type inference. Here’s the code:

function SimpleGraph{T}(nv::Integer, ne::Integer; rng::AbstractRNG=GLOBAL_RNG) where {T<:Integer}
    tnv = T(nv)
    maxe = div(Int(nv) * (nv - 1), 2)
    @assert(ne <= maxe, "Maximum number of edges for this graph is $maxe")
    ne > div((2 * maxe), 3)  && return complement(SimpleGraph(tnv, maxe - ne))
    g = SimpleGraph(tnv)
    while g.ne < ne
        source = rand(rng, one(T):tnv)
        dest = rand(rng, one(T):tnv)
        source != dest && add_edge!(g, source, dest)
    end
    return g
end
SimpleGraph(nv::T, ne::Integer; rng::AbstractRNG=GLOBAL_RNG) where {T<:Integer} =
    SimpleGraph{T}(nv, ne, rng=rng)

The problem comes in when I try to create a SimpleGraph(10, 20, rng=MersenneTwister(1)):

julia> @code_warntype SimpleGraphs.Graph(10,20, rng=MersenneTwister(1))
Variables                                                                                                                                             
  #unused#::Core.Compiler.Const(Core.var"#kw#Type"(), false)               
  @_2::NamedTuple{(:rng,),Tuple{MersenneTwister}}                          
  @_3::Type{SimpleGraph}                                                                                                                              
  nv::Int64                                                                                                                                           
  ne::Int64                                                                                                                                           
  rng::MersenneTwister                                                     
  @_7::MersenneTwister       
                                                                                                                                                      
Body::Any                                                                                                                                             
1 ─ %1  = Base.haskey(@_2, :rng)::Core.Compiler.Const(true, false)                                                                                    
│         %1                                                                                                                                          
│   %3  = Base.getindex(@_2, :rng)::MersenneTwister                                                                                                   
│   %4  = (%3 isa LightGraphs.SimpleGraphs.Generators.AbstractRNG)::Core.Compiler.Const(true, false)                                                  
│         %4
└──       goto #3
2 ─       Core.Compiler.Const(:(%new(Core.TypeError, Symbol("keyword argument"), :rng, LightGraphs.SimpleGraphs.Generators.AbstractRNG, %3)), false)
└──       Core.Compiler.Const(:(Core.throw(%7)), false)
3 ┄       (@_7 = %3)
─       goto #5
4 ─       Core.Compiler.Const(:(@_7 = LightGraphs.SimpleGraphs.Generators.GLOBAL_RNG), false)
5 ┄       (rng = @_7)
│   %13 = (:rng,)::Core.Compiler.Const((:rng,), false)
│   %14 = Core.apply_type(Core.NamedTuple, %13)::Core.Compiler.Const(NamedTuple{(:rng,),T} where T<:Tuple, false)
│   %15 = Base.structdiff(@_2, %14)::Core.Compiler.Const(NamedTuple(), false)
│   %16 = Base.pairs(%15)::Core.Compiler.Const(Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}(), false)
│   %17 = Base.isempty(%16)::Core.Compiler.Const(true, false)
│         %17
└──       goto #7
6 ─       Core.Compiler.Const(:(Base.kwerr(@_2, @_3, nv, ne)), false)
7 ┄ %21 = LightGraphs.SimpleGraphs.Generators.:(var"#SimpleGraph#2")(rng, @_3, nv, ne)::Any
└──       return %21

SimpleGraph(10, 20) infers correctly (no type warning). Also weird:

julia> @edit SimpleGraphs.Graph(10,20, rng=MersenneTwister(1))
ERROR: could not determine location of method definition
Stacktrace:
 [1] error(::String) at ./error.jl:33
 [2] functionloc(::Method) at ./methodshow.jl:131
 [3] functionloc at ./methodshow.jl:141 [inlined]
 [4] edit(::Function, ::Any) at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.3/InteractiveUtils/src/editless.jl:102
 [5] top-level scope at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.3/InteractiveUtils/src/macros.jl:15

Now, what’s even WEIRDER is that if I start my REPL session off with a SimpleGraph(10, 20), subsequent SimpleGraph(10, 20, rng=MersenneTwister(1))s infer correctly.

This issue is causing new type inference problems in the package. I hope I’m just overlooking something trivial. Any ideas?

2

Not sure about your case, but any time I see order-dependent inference issues, this comes to mind, which describes why some seemingly valid things in Julia won’t infer: https://juliacomputing.com/blog/2017/05/15/inference-converage2.html

It seems plausible its that since since you’ve got SimpleGraphs recursively calling itself, which is at least one of the conditions to get what’s described there.

If its really this, a possible workaround I think might be to add precompile statements that cause inference to go through things in the order that works, which you could do at least for some of the concrete types you care about.

3

A quick update: annotating the return type solves the problem. But this doesn’t happen for the almost identical SimpleDiGraph constructor.

4

There shouldn’t be any recursion here.

5

I think there is, it looks like there’s at least one branch in your code above where SimpleGraph{T}(...) calls SimpleGraph(...) which calls SimpleGraph{T}(...) with the argument types being (Int,Int) in the first and last calls, so that’d be the part I’d be suspicious could be related to what’s decsribed in that blog post (but I don’t really know enough about this to be sure though).

6

sorry, I’m lost. Where is this branch?

7

Inside your SimpleGraph{T} function, you have a call to SimpleGraph(...) with two arguments (specifically in complement(SimpleGraph(tnv, maxe - ne))), and that in turn calls SimpleGraph{T} again.

You could try changing it to complement(SimpleGraph{T}(tnv, maxe - ne)) (ie add a {T}, and maybe to the other call as well) so SimpleGraph{T} is only calling itself, which that post seems to suggest is better.

1 Like
8

That was it, precisely. Thank you so much!

1 Like