Ominous type instability

Hi there!

I am working on some Code that is supposed to be a demonstration of how you can create fast and efficient code with just a few easy, readable lines in Julia. Sadly one of the functions turns out to be not typestable with some really weird behaviour, and I dont know why.

Some Background: f, the function in question, should iterate over a combination of indices of a Matrix and reduce them to a single value. Since I want to apply this later to the RGB-channels of an Image, I use multiple dispatch and define a method for f(x::Array{T,3}) that just sums f over all relevant slices.
To not bother you with irrelevant details I stripped away as much details as was possible while still recreating the instability. Here’s the Code:

function f(v::AbstractMatrix{T}) where T
    sum(1 for r in (1,2))
end
  
function f(ν::AbstractArray{T,3}) where {T}
    return @views sum( f(ν[:, :, i]) for i in 1:size(ν, 3))
end
  
@code_warntype f(zeros(2, 2, 2))
MethodInstance for f(::Array{Float64, 3})
  from f(ν::AbstractArray{T, 3}) where T in Main at In[79]:1
Static Parameters
  T = Float64
Arguments
  #self#::Core.Const(f)
  ν::Array{Float64, 3}
Locals
  #59::var"#59#60"{Array{Float64, 3}}
Body::Any
1 ─ %1 = Main.:(var"#59#60")::Core.Const(var"#59#60")
│   %2 = Core.typeof(ν)::Core.Const(Array{Float64, 3})
│   %3 = Core.apply_type(%1, %2)::Core.Const(var"#59#60"{Array{Float64, 3}})
│        (#59 = %new(%3, ν))
│   %5 = #59::var"#59#60"{Array{Float64, 3}}
│   %6 = Main.size(ν, 3)::Int64
│   %7 = (1:%6)::Core.PartialStruct(UnitRange{Int64}, Any[Core.Const(1), Int64])
│   %8 = Base.Generator(%5, %7)::Core.PartialStruct(Base.Generator{UnitRange{Int64}, var"#59#60"{Array{Float64, 3}}}, Any[var"#59#60"{Array{Float64, 3}}, Core.PartialStruct(UnitRange{Int64}, Any[Core.Const(1), Int64])])
│   %9 = Main.sum(%8)::Any
└──      return %9

Note the returntype of Any. Here are some parts that I find odd about this:

  • Even though f, given an appropriate matrix view is typestable, f(::Array{T,3}) is not.
  • Furthermore, if I check this fact with @code_warntype f(zeros(2,2)), the instability just ‘goes away’;
    if I run
    function f(v::AbstractMatrix{T}) where T
        sum(1 for r in (1,2))
    end
    
    function f(ν::AbstractArray{T,3}) where {T}
        return @views sum( f(ν[:, :, i]) for i in 1:size(ν, 3))
    end
    
    @code_warntype f(zeros(2, 2))
    @code_warntype f(zeros(2, 2, 2))
    
    then suddenly everything is typestable. This is confirmed by some Performance testing: when I call
    function testf()
        a=zeros(2,2,2)
        @time f(a)
    end
    testf()
    
    I get 5 allocations per call, but when I run @code_warntype f(zeros(2, 2)) beforehand the allocations disappear.
  • If I replace f in the generator with any other scalar valued function, e.g. maximum, the instability goes away.
  • If I just let the first method return 2, the instability goes away, even though this is of course equivalent (which the compiler knows, as of @code_llvm f(zeros(2,2)).

When trying to recreate the problem I recommend to regularly restart the kernel and only run the proper sections, due to the instable instability ( :wink:) .

I work in a Jupyter Notebook on Windows with a 1.7.2 kernel.

Any help of whats going on here is welcome.

1 Like

These observations can be reproduced in a fresh REPL, with julia 1.7.3.

It looks like the compiler gave up.
Until someone explains what’s going on,
an annotation for the output type (Int64) can stabilize the process:

julia> function f(v::AbstractMatrix{T})::Int64  where T
           sum(1 for r in (1,2))
       end

Thanks for the suggestion. While its true that this superficially solves the instability, the actual problem (unnessecary allocations during the function call) doesnt go away with a type annotation: the performance check

still returns 5 allocations per call. My guess is that internally the function still returns Any, and just checks retrospectively that it acually wrapped an integer.

That syntax is not a “return type hint” , it is a short hand for convert

function f(v::AbstractMatrix{T})::Int64  where T
    sum(1 for r in (1,2))
end

is exactly equivelent to:

function f(v::AbstractMatrix{T})  where T
    x = sum(1 for r in (1,2))
    convert(Int64, x)
end

Indeed, thanks (I did not know it was just syntactic sugar).
What I meant by “stabilize the process” is that
@code_warntype f(zeros(2, 2, 2))
no longer showed any Any, which meant that it helped the compiler
find out the return type of the other method.

@oxynabox discourse said you were answering to me, but after some rest, it seems clear that your comment was directed to @arik, and to the point.
By the way, I’d warmly recommend your juliacon 2022 talk, thanks !

@arik It might be worth trying again in a fresh session ?
In a fresh REPL, there are 0 allocations.

1 Like

Nope. Problem still remains. Here is how to reproduce it reliably:
From a fresh 1.7.3 REPL:

julia>include("testf.jl")
testf (generic function with 1 method)

julia>testf()
 0.061456 seconds (191.43 k allocations: 11.033 MiB, 9.09% gc time, 99.96% compilation time)
4

julia> testf()
  0.000004 seconds (6 allocations: 176 bytes)
4

or, alternatively, from a fresh REPL:

julia>include("testf.jl")
testf (generic function with 1 method)

julia> @code_warntype f(zeros(2,2,2))
<Some stuff here>

julia> testf()
  0.000001 seconds
4

With the content of testf.jl beiing:

function f(v::AbstractMatrix{T}) where T
    sum(1 for r in (1,2))
end
  
function f(ν::AbstractArray{T,3}) where {T}
    return @views sum( f(ν[:, :, i]) for i in 1:size(ν, 3))
end

  function testf()
    a=zeros(2,2,2)
    @time f(a)
end

Note that the allocations just ‘go away’ if you call @code_warntype f(zeros(2,2)) before testf() .
Adding a typetag to either the function (f(...)::Int) or the offending sum itself (return @views sum(...)::Int) changes nothing. Do you think this is a bug?

On a personal note, thanks from me too for your talk, @oxinabox. I’ve seen it, but didn’t immediatly associate it with you. Some very interesting points, I did not know you could manually add backedges to generated functions, but this is some useful information to have.

Indeed, one has to be very careful not to call @code_warntype f(zeros(2, 2)) before ftest,
and to call ftest in this manner.

Here is another take, still with Julia Version 1.7.3.

function f(v::AbstractMatrix{T})::Int64 where T
    sum(1 for r in (1,2))
end

function f(ν::AbstractArray{T,3}) where {T}
    return @views sum( f(ν[:, :, i]) for i in 1:size(ν, 3))
end

a=zeros(2,2,2)
using BenchmarkTools
@btime f(a)
  12.055 ns (0 allocations: 0 bytes)

So far so good.

Now in a fresh session, intercalating testf

function f(v::AbstractMatrix{T})::Int64 where T
       sum(1 for r in (1,2))
end

function f(ν::AbstractArray{T,3}) where {T}
    return @views sum( f(ν[:, :, i]) for i in 1:size(ν, 3))
end

function testf()
    a=zeros(2,2,2)
    @time f(a)
end

# this call is breaking (if commented out, there are no allocations)
testf()

b=zeros(2,2,2)
using BenchmarkTools
@btime f(b)
    62.790 ns (5 allocations: 144 bytes)

With the official release candidate 1.8.0-rc3, the results are similar; without ftest:

  11.132 ns (0 allocations: 0 bytes)

and with the ftest() call:

  63.632 ns (5 allocations: 144 bytes)

This is unexpected indeed, filing an issue might be useful,
unless experts already know about this ?

I’ll file an issue tomorrow, when I have some time. Thanks for your efforts so far.

If you pass a function as the first argument, this should become a mapreduce.

function f(v::AbstractMatrix{T})::Int64 where T
       sum(x->1,(1,2))
end

function f(ν::AbstractArray{T,3}) where {T}
   sum(i->f(@view(ν[:, :, i])), 1:size(ν, 3))
end

function testf()
    a=zeros(2,2,2)
    @time f(a)
end

julia> @code_warntype f(zeros(2,2,2))
MethodInstance for f(::Array{Float64, 3})
  from f(ν::AbstractArray{T, 3}) where T in Main at REPL[32]:1
Static Parameters
  T = Float64
Arguments
  #self#::Core.Const(f)
  ν::Array{Float64, 3}
Locals
  #13::var"#13#14"{Array{Float64, 3}}
Body::Int64
1 ─ %1 = Main.:(var"#13#14")::Core.Const(var"#13#14")
│   %2 = Core.typeof(ν)::Core.Const(Array{Float64, 3})
│   %3 = Core.apply_type(%1, %2)::Core.Const(var"#13#14"{Array{Float64, 3}})
│        (#13 = %new(%3, ν))
│   %5 = #13::var"#13#14"{Array{Float64, 3}}
│   %6 = Main.size(ν, 3)::Int64
│   %7 = (1:%6)::Core.PartialStruct(UnitRange{Int64}, Any[Core.Const(1), Int64])
│   %8 = Main.sum(%5, %7)::Int64
└──      return %8