Inference regression with inhomogeneous tuples

[pablosanjose]

Ref: https://discourse.julialang.org/t/puzzling-inference-with-a-splat/20498/4

f(term, sets...) = (sets..., term), term

g(sets, term, terms...) = g(_g(sets, term), terms...)
g(sets) = sets
function _g(sets, term)
    newsets, newset = f(term, sets...)
    return newsets
end

function main(terms)
    sets = g((), terms...)
    return sets
end

using StaticArrays
ss = zero.((SVector{2,Int}, SVector{1,Float64}, SVector{2,Int}))

In short: main doesn't infer in v0.7 and above. It did in v0.6.

julia> @code_warntype main(ss)
Body::Tuple
...
julia> @code_warntype g((), ss...)
Body::Tuple{SArray{Tuple{2},Int64,1,2},SArray{Tuple{1},Float64,1,1},SArray{Tuple{2},Int64,1,2}}
...

A most interesting observation was made by @KristofferC: if we run this in global REPL scope (though not in a module), the order in which we first call @call_warntype affects inference (and therefore the performance of main). Suggests a caching bug?

julia> @code_warntype g((), ss...)
Body::Tuple{SArray{Tuple{2},Int64,1,2},SArray{Tuple{1},Float64,1,1},SArray{Tuple{2},Int64,1,2}}
...
julia> @code_warntype main(ss)
Body::Tuple{SArray{Tuple{2},Int64,1,2},SArray{Tuple{1},Float64,1,1},SArray{Tuple{2},Int64,1,2}}
...

[pablosanjose]

It seems splatting has nothing to do with this issue. This splat-free example fails in a similar way (including the caching anomaly in REPL scope), though inference gets a little bit further

f(newset, sets) = (sets, newset), newset

g(sets, terms) = g(_g(sets, first(terms)), Base.tail(terms))
g(sets, ::Tuple{}) = sets
function _g(sets, term)
    newsets, newset = f(term, sets)
    return newsets
end

function main(terms)
    sets = g((), terms)
    return sets
end

using StaticArrays
ss = zero.((SVector{2,Int}, SVector{1,Float64}, SVector{2,Int}))

Note the Any below:

julia> @code_warntype main(ss)
Body::Tuple{Tuple{Any,SArray{Tuple{1},Float64,1,1}},SArray{Tuple{2},Int64,1,2}}
...

[pablosanjose]

One more clue: the problem seems to stem from the empty tuple seed in the first call to g inside main. A version of this without an empty () infers correctly, at least in the examples I tried (see update in https://discourse.julialang.org/t/puzzling-inference-with-a-splat/20498/4)

[martinholters]

IIUC, the first argument to g is growing during the recursion? Then it's expected that inference bails out.

[pablosanjose]

Yes, the empty tuple grows to include one element for each of the terms in the input. The final length of the tuple is thus a compile-time constant. Why should inference bail out? As mentioned above, a minor modification that does not start with an empty tuple doesn't fail:

f(newset, sets...) = (sets..., newset), newset
g(term, terms...) = _g(first(f(term)), terms...)
_g(sets, term, terms...) = _g(_g(sets, term), terms...)
_g(sets, term) = first(f(term, sets...))
_g(sets) = sets

function main(terms)
    sets = g(terms...)
    return sets
end

using StaticArrays
ss = zero.((SVector{2,Int}, SVector{1,Float64}, SVector{2,Int}))

With this:

julia> @code_warntype main(ss)
Body::Tuple{SArray{Tuple{1},Float64,1,1},SArray{Tuple{2},Int64,1,2},SArray{Tuple{2},Int64,1,2},SArray{Tuple{1},Float64,1,1},SArray{Tuple{2},Int64,1,2}}
...

Also note that v0.6 could handle both this and the original example in the OP. Note also the cache anomaly noted by @KristofferC. That is a definite signal that there is a bug here.

[martinholters]

This is a very nice reason for why we need something like #31000.

[pablosanjose]

This is no longer an issue (since 1.1). Not sure what the relevant PR was. Closing!