Julia: sporadic type instability with mapreduce / norm

[stev47]

Using Julia master (newer than 301db971daaeeb627ba768375538e6e7ff36d215), the following does not infer the correct type (see also the discussion in #34048):

using Test, LinearAlgebra
# @inferred mapreduce(norm, +, [rand(1)]);
@inferred mapreduce(norm, +, [rand(1)]; init = 0.);

Note that the third line works if you comment out the second line (start from a fresh Julia session), which makes testing this issue difficult.

[mbauman]

Possibly related to #35813?

[JeffBezanson]

Reduced:

julia> using LinearAlgebra

julia> X = [randn(n,n) for n = 1:5];

julia> @code_typed Base.mapfoldl(norm, +, X, init=0.)
CodeInfo(
1 ─ %1 = invoke Base.foldl_impl($(QuoteNode(Base.MappingRF{typeof(norm),Base.BottomRF{typeof(+)}}(LinearAlgebra.norm, Base.BottomRF{typeof(+)}(+))))::Base.MappingRF{typeof(norm),Base.BottomRF{typeof(+)}}, _2::NamedTuple{(:init,),Tuple{Float64}}, _6::Array{Array{Float64,2},1})::Any
└──      return %1
) => Any

julia> code_typed(Base.foldl_impl, (Base.MappingRF{typeof(norm),Base.BottomRF{typeof(+)}}, NamedTuple{(:init,),Tuple{Float64}}, Array{Array{Float64,2},1}))
1-element Array{Any,1}:
 CodeInfo(
1 ─ %1 = Base.getfield(nt, :init)::Float64
│   %2 = invoke Base._foldl_impl(_2::Base.MappingRF{typeof(norm),Base.BottomRF{typeof(+)}}, %1::Float64, _4::Array{Array{Float64,2},1})::Float64
└──      goto #3 if not false
2 ─      nothing::Nothing
3 ┄      return %2
) => Float64

So mapfold is Any, but when we look at the method it calls that gets inferred as Float64.

[JeffBezanson]

Possibly related to #35813?

I don't know what's going on yet, but I would guess not, since specialization is supposed to be orthogonal to inference; it only affects what we generate code for, not what we know about types.

[tkf]

I think a bigger problem is the context dependency of @inferred result. Maybe some kind of cache problem? I thought it was considered a bug if the type inference is not deterministic.

(I'm just mentioning it since, IIUC, Cthulhu.jl had a similar "bug" and at some point it was fixed.)

[JeffBezanson]

Yes, everybody agrees this is a bug.

[tkf]

Thanks. I was commenting because your comment https://github.com/JuliaLang/julia/issues/35800#issuecomment-626018140 seems to be focusing on a single call of @code_typed rather than @inferred mapreduce(norm, +, [rand(1)]); and _then_ @inferred mapreduce(norm, +, [rand(1)]; init = 0.);.

[tkf]

Another "context dependent" behavior in #35537

[baggepinnen]

Another very strange inference problem has popped up in https://github.com/chriselrod/LoopVectorization.jl/issues/114
only appears on some architectures and for Float32 but not Float64.

[chriselrod]

In case it helps, that inference failure was solved by replacing this:

@generated function vzero(::Type{Vec{W,T}}) where {W,T}
    typ = llvmtype(T)
    vtyp = "<$W x $typ>"
    instrs = """
    ret $vtyp zeroinitializer
    """
    quote
        $(Expr(:meta,:inline))
        Base.llvmcall($instrs, Vec{$W,$T}, Tuple{}, )
    end
end
@inline vzero(::Val{W}, ::Type{T}) where {W,T} = SVec(vzero(Vec{W,T}))

with

@generated function vzero(::Val{W}, ::Type{T}) where {W,T}
    typ = llvmtype(T)
    vtyp = "<$W x $typ>"
    instrs = """
    ret $vtyp zeroinitializer
    """
    quote
        $(Expr(:meta,:inline))
        SVec(Base.llvmcall($instrs, Vec{$W,$T}, Tuple{}, ))
    end
end

EDIT:
What would be easier on inference: generated functions like the above, or a bunch of different methods on concrete types (e.g., created in a loop with @eval)?
Would it help to have generated functions as fall backs, and make concrete versions for the most common use cases?
It seems like that may be better at avoiding heuristics that make inference give up.

[JeffBezanson]

A bit more information:

First this is called:

  foldl_impl(Base.MappingRF{typeof(LinearAlgebra.norm),
                            Base.BottomRF{typeof(Base.:(+))}}, Float64, Array{Array{Float64, 2}, 1})

which eventually calls norm, which calls

  foldl_impl(Base.MappingRF{getfield(Base, Symbol("#208#209")){getfield(Base, Symbol("#62#63")){typeof(Base.iszero)}},
                            Base.BottomRF{typeof(Base.add_sum)}}, Int64, Array{Float64, 2})

which appears to be recursion, so it's widened to

  foldl_impl(Base.MappingRF{F, T} where T where F, Int64, Array{Float64, 2})

which infers to Any. However, the un-widened signature does not lead to recursion (since the recursion is via norm and not just foldl_impl), so if you infer that on its own it's fine.

[JeffBezanson]

The order dependence happens because if we have already inferred e.g. norm, then we just use the cached result instead of looking through and seeing the recursion.

[JeffBezanson]

This is a fairly deep issue, and there is no way to promise fixing it within the 1.6 timeframe.

[maleadt]

Another possibly related case, reduced from https://discourse.julialang.org/t/code-warntype-understanding/48627/23:

function b(c)
    function (d, e)
        sum(sum(d) for i in c)
    end
end
f(d, g) = sum(d)
c = 0.3

using Test
CONDITIONAL || f(1.0, [])
h = b(c)
@inferred h(2.2, 1.0)

The execution of f as controlled by CONDITIONAL determines whether h will infer or not. This reproduces on latest nightly.

[maleadt]

Further reduced:

# Broadcast
struct a
    c
    args
end
e(n) = a(==, collect(n))

# Generator
struct f{h,i}
    c::h
    iter::i
end
Base.iterate(g) = g.c(iterate(g.iter))
collect(itr) = iterate(itr)

# from user code
b(d) = l(f(m->l(d), 0))
l(itr) = j(f(identity, itr))
j(itr) = e(itr).c

using Test
isempty(ARGS) || l(0)
@inferred b(0)

+ julia main.jl doit
+ julia main.jl
ERROR: LoadError: return type typeof(==) does not match inferred return type Any