What is the status of type inference of recursive calls? Odd statefulness?

Internals & Design
,
1

Evidently, the situation has improved from v1.10.10 because the examples from the links below on v1.11.7 are inferred with concrete return types and pass JET.@report_opt. Note that type instabilities that don’t cause internal runtime dispatches pass @report_opt e.g. f(x) = x[1]; @report_opt f(Any[1]).

But it’s still possible to run into problems. Here’s a more complex MWE rooted in nested SVectors discovered a couple weeks ago. I attempted to make a similar but more simplified example. Note that a simpler sum or x->sum(x) for the first input to the outer sum call results in type-stability on both v1.10.10 and v1.11.7.

julia> using StaticArrays, BenchmarkTools, JET, Test

julia> inputs = (x->sum(identity, x), zero(SVector{4,SVector{2,Float64}}));

julia> @code_warntype sum(inputs...)
MethodInstance for sum(::var"#5#6", ::SVector{4, SVector{2, Float64}})
  from sum(f::Union{Function, Type}, a::StaticArray{<:Tuple, T}; dims, init) where T @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:295
Static Parameters
  T = SVector{2, Float64}
Arguments
  #self#::Core.Const(sum)
  f::Core.Const(var"#5#6"())
  a::SVector{4, SVector{2, Float64}}
Body::Any
1 ─      nothing
│   %2 = StaticArrays.:(var"#sum#204")::Core.Const(StaticArrays.var"#sum#204")
│   %3 = StaticArrays.:(:)::Core.Const(Colon())
│   %4 = StaticArrays._InitialValue()::Core.Const(StaticArrays._InitialValue())
│   %5 = (%2)(%3, %4, #self#, f, a)::Any
└──      return %5

julia> Test.@inferred sum(inputs...)
ERROR: return type Float64 does not match inferred return type Any
Stacktrace:
 [1] error(s::String)
   @ Base .\error.jl:35
 [2] top-level scope
   @ REPL[16]:1

julia> @btime sum($(inputs[1]), $(inputs[2]))
  227.033 ns (5 allocations: 336 bytes)
0.0

And a different stateful twist: if we instantiate equivalent inputs but try Test.@inferred or a plain call first, then the compiler succeeds at recursive type inference. However, @report_opt does not.

julia> using StaticArrays, BenchmarkTools, JET, Test # can stay in session or reload

julia> inputs = (x -> sum(identity, x), zero(SVector{4,SVector{2,Float64}}));

julia> Test.@inferred sum(inputs...) # or just execute sun(inputs...)
0.0

julia> @code_warntype sum(inputs...)
MethodInstance for sum(::var"#9#10", ::SVector{4, SVector{2, Float64}})
  from sum(f::Union{Function, Type}, a::StaticArray{<:Tuple, T}; dims, init) where T @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:295
Static Parameters
  T = SVector{2, Float64}
Arguments
  #self#::Core.Const(sum)
  f::Core.Const(var"#9#10"())
  a::SVector{4, SVector{2, Float64}}
Body::Float64
1 ─      nothing
│   %2 = StaticArrays.:(var"#sum#204")::Core.Const(StaticArrays.var"#sum#204")
│   %3 = StaticArrays.:(:)::Core.Const(Colon())
│   %4 = StaticArrays._InitialValue()::Core.Const(StaticArrays._InitialValue())
│   %5 = (%2)(%3, %4, #self#, f, a)::Float64
└──      return %5

julia> @btime sum($(inputs[1]), $(inputs[2]))
  2.300 ns (0 allocations: 0 bytes)
0.0

julia> @report_opt sum(inputs...)
═════ 6 possible errors found ═════
┌ sum(f::var"#9#10", a::SVector{4, SVector{2, Float64}}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:295
│┌ sum(f::var"#9#10", a::SVector{4, SVector{2, Float64}}; dims::Colon, init::StaticArrays._InitialValue) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:295
││┌ _mapreduce(::var"#9#10", ::typeof(+), ::Colon, ::StaticArrays._InitialValue, ::Size{(4,)}, ::SVector{4, SVector{…}}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:153
│││┌ _mapfoldl(f::var"#9#10", op::typeof(+), dims::Colon, init::StaticArrays._InitialValue, ::Size{…}, a::SVector{…}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:180
││││┌ (::var"#9#10")(x::SVector{2, Float64}) @ Main ./REPL[21]:1
│││││┌ sum(f::typeof(identity), a::SVector{2, Float64}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:295
││││││┌ sum(f::typeof(identity), a::SVector{2, Float64}; dims::Colon, init::StaticArrays._InitialValue) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:295
│││││││┌ _mapreduce(::typeof(identity), ::typeof(+), ::Colon, ::StaticArrays._InitialValue, ::Size, ::SVector{2, Float64}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:153
││││││││ runtime dispatch detected: StaticArrays._mapfoldl(identity, +, Colon(), [quote]::StaticArrays._InitialValue, %1::Size, %2::SVector{2, Float64})::Any
│││││││└────────────────────
││││││┌ sum(f::typeof(identity), a::SVector{2, Float64}; dims::Colon, init::StaticArrays._InitialValue) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:295
│││││││ failed to optimize due to recursion: StaticArrays.var"#sum#204"(::Colon, ::StaticArrays._InitialValue, ::typeof(sum), ::typeof(identity), ::SVector{…})
││││││└────────────────────
│││││┌ sum(f::typeof(identity), a::SVector{2, Float64}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:295
││││││ failed to optimize due to recursion: sum(::typeof(identity), ::SVector{2, Float64})
│││││└────────────────────
││││┌ (::var"#9#10")(x::SVector{2, Float64}) @ Main ./REPL[21]:1
│││││ failed to optimize due to recursion: (::var"#9#10")(::SVector{2, Float64})
││││└────────────────────
│││┌ _mapfoldl(f::var"#9#10", op::typeof(+), dims::Colon, init::StaticArrays._InitialValue, ::Size{…}, a::SVector{…}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:155
││││ failed to optimize due to recursion: StaticArrays._mapfoldl(::var"#9#10", ::typeof(+), ::Colon, ::StaticArrays._InitialValue, ::Size{…}, ::SVector{…})
│││└────────────────────
││┌ _mapreduce(::var"#9#10", ::typeof(+), ::Colon, ::StaticArrays._InitialValue, ::Size{(4,)}, ::SVector{4, SVector{…}}) @ StaticArrays C:\Users\Benny\.julia\packages\StaticArrays\DsPgf\src\mapreduce.jl:153
│││ failed to optimize due to recursion: StaticArrays._mapreduce(::var"#9#10", ::typeof(+), ::Colon, ::StaticArrays._InitialValue, ::Size{…}, ::SVector{…})
││└────────────────────

What’s going on here and what could be done about it?

2

The analogous code for Values from StaticVectors.jl (which I believe is a fork if StaticArrays.jl) seems to work fine. Maybe this can help to understand what’s going on.

julia> using StaticVectors: Values as SVector

julia> inputs = (x->sum(identity, x), zero(SVector{4,SVector{2,Float64}})); # NOTE: sum or x->sum(x) is stable

julia> @code_warntype sum(inputs...)
MethodInstance for sum(::var"#7#8", ::StaticVectors.Values{4, StaticVectors.Values{2, Float64}})
  from sum(f::Union{Function, Type}, a::StaticVectors.TupleVector{N, T}; dims) where {N, T} @ StaticVectors /usr/local/julia-depot/packages/StaticVectors/fpkZ5/src/mapreduce.jl:244
Static Parameters
  N = 4
  T = StaticVectors.Values{2, Float64}
Arguments
  #self#::Core.Const(sum)
  f::Core.Const(var"#7#8"())
  a::StaticVectors.Values{4, StaticVectors.Values{2, Float64}}
Body::Float64
1 ─      nothing
│   %2 = StaticVectors.:(var"#sum#108")::Core.Const(StaticVectors.var"#sum#108")
│   %3 = StaticVectors.:(:)::Core.Const(Colon())
│   %4 = (%2)(%3, #self#, f, a)::Float64
└──      return %4
1 Like
3

I tried comparing the printouts of @descend, and I really can’t spot a critical difference in method call chains or the source code. When type inference fails, the method signatures will lack type annotations and print “Warning: Inference terminated in an incomplete state due to argument-type changes during recursion”, but the signatures in the Values version do in fact change down the mild recursive chain. There’s just something in the recursion type inference heuristic I don’t know about. I’m not even sure if it’s related to the issue that changed between 1.10 and 1.11, which doesn’t mention the statefulness here.

4

In case you don’t know, the remarks=true option to @descend may give more info here. So: @descend remarks=true ...

1 Like
5

In this case, not significantly more info and I haven’t seen anything stand out.

1 Like