Ominous type instability

arik · August 2, 2022, 2:25pm

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 ( ) .

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

Any help of whats going on here is welcome.

ederag · August 2, 2022, 3:18pm

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

arik · August 2, 2022, 3:28pm

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.

oxinabox · August 2, 2022, 3:41pm

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

ederag · August 2, 2022, 3:51pm

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.

ederag · August 3, 2022, 3:21pm

@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.

arik · August 3, 2022, 4:56pm

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.

ederag · August 3, 2022, 6:56pm

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 ?

arik · August 3, 2022, 7:04pm

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

mkitti · August 3, 2022, 7:23pm

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

nsajko · August 20, 2022, 3:46am

This seems to be a known issue:

github.com/JuliaLang/julia

Typeinference depends on execution order but should not

opened 09:42AM - 20 May 22 UTC

schlichtanders

inference

Hi there, this issue was already discussed on [discourse](https://discourse.j…ulialang.org/t/need-help-with-incomprehensible-typeinference/81056). While we could gather some clarification, it couldn't be solved. Hence I raise it as an issue here. I am the author of [ExtensibleEffects.jl](https://github.com/JuliaFunctional/ExtensibleEffects.jl) and [TypeClasses.jl](https://github.com/JuliaFunctional/TypeClasses.jl) and experience crucial performance difficulties due to bad type inference. As I got multiple requests from the community whether ExtensibleEffects.jl could be made fast, I want to tackle these problems. ExtensibleEffects.jl is an advanced functional package, hence please bear with me if the following example looks not understandable why you ever would like to do something like this. It is a minified version of the actual ExtensibleEffects code, and I am very sorry that I was not able to simplify it anyway further so far. At least it is reproducible and fits into an issue. # My Motivation <details> <summary>if you want to understand the motivation for the example, this might help</summary> ```julia using ExtensibleEffects using TypeClasses using Test vector_of_eff_of_vector = map(x -> noeffect([x]), [1, 20]) e1 = vector_of_eff_of_vector[1] e2 = vector_of_eff_of_vector[2] # some functional monadic helpers to work WITHIN the effects mygoal(e1, e2) = @syntax_flatmap begin v1 = e1 v2 = e2 @pure [v1; v2] end ``` ```julia julia> mygoal(e1, e2) Eff(effectful=NoEffect{Vector{Int64}}([1, 20]), length(cont)=0) julia> @inferred mygoal(e1, e2) ERROR: return type ExtensibleEffects.Eff{NoEffect{Vector{Int64}}, Tuple{}} does not match inferred return type ExtensibleEffects.Eff julia> @code_warntype mygoal(e1, e2) # on the terminal this gives nice color output and will show that only the last step does not infer ``` The case boils down to something like the following ```julia function test_fails(e1, e2) combine(v1, v2) = [v1; v2] curried_combine(v1) = v2 -> combine(v1, v2) e1_f = map(curried_combine, e1) f_flatmap(f) = TypeClasses.map(v2 -> f(v2), e2) TypeClasses.flatmap(f_flatmap, e1_f) end @inferred test_fails(e1, e2) # same as before # ERROR: return type ExtensibleEffects.Eff{NoEffect{Vector{Int64}}, Tuple{}} does not match inferred return type ExtensibleEffects.Eff @code_warntype test_fails(e1, e2) # same as before ``` If this could be stabilized, much is gained for ExtensibleEffects.jl </details> # Same code, two execution orders, one fails, the other infers Here the one which works ```julia using ExtensibleEffects using TypeClasses using Test vector_of_eff_of_vector = map(x -> noeffect([x]), [1, 20]) e1 = vector_of_eff_of_vector[1] e2 = vector_of_eff_of_vector[2] function prepare_test(e1, e2) combine(v1, v2) = [v1; v2] curried_combine(v1) = v2 -> combine(v1, v2) e1_f = map(curried_combine, e1) f_flatmap(f) = TypeClasses.map(v2 -> f(v2), e2) f_flatmap, e1_f end f_flatmap, e1_f = prepare_test(e1, e2) @inferred TypeClasses.flatmap(f_flatmap, e1_f) # infers perfectly function test_infers(e1, e2) f_flatmap, e1_f = prepare_test(e1, e2) TypeClasses.flatmap(f_flatmap, e1_f) end @inferred test_infers(e1, e2) # infers perfectly ``` And here the one which fails ```julia using ExtensibleEffects using TypeClasses using Test vector_of_eff_of_vector = map(x -> noeffect([x]), [1, 20]) e1 = vector_of_eff_of_vector[1] e2 = vector_of_eff_of_vector[2] function prepare_test(e1, e2) combine(v1, v2) = [v1; v2] curried_combine(v1) = v2 -> combine(v1, v2) e1_f = map(curried_combine, e1) f_flatmap(f) = TypeClasses.map(v2 -> f(v2), e2) f_flatmap, e1_f end function test_infers(e1, e2) f_flatmap, e1_f = prepare_test(e1, e2) TypeClasses.flatmap(f_flatmap, e1_f) end @inferred test_infers(e1, e2) # ERROR: return type ExtensibleEffects.Eff{NoEffect{Vector{Int64}}, Tuple{}} does not match inferred return type ExtensibleEffects.Eff f_flatmap, e1_f = prepare_test(e1, e2) @inferred TypeClasses.flatmap(f_flatmap, e1_f) # ERROR: return type ExtensibleEffects.Eff{NoEffect{Vector{Int64}}, Tuple{}} does not match inferred return type ExtensibleEffects.Eff ``` It seems that a top-level call to `TypeClasses.flatmap` at the right place informs the compiler about things it usually does not have available (but should have available). ------------ This drives me crazy :smile: I feel like a little child: 10 years programming experience are not enough to solve this on my own, I am depending on you deep core Julia developers and hope someone recognizes what is going on here. <details> <summary>(tested on Julia 1.7.1 and Julia 1.8.0-beta3.4)</summary> ```julia julia> versioninfo() Julia Version 1.7.1 Commit ac5cc99908 (2021-12-22 19:35 UTC) Platform Info: OS: Linux (x86_64-pc-linux-gnu) CPU: Intel(R) Core(TM) i7-1065G7 CPU @ 1.30GHz WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-12.0.1 (ORCJIT, icelake-client) ``` ```julia julia> versioninfo() Julia Version 1.8.0-beta3.4 Commit a4e69c5088 (2022-05-20 09:32 UTC) Platform Info: OS: Linux (x86_64-unknown-linux-gnu) CPU: 8 × Intel(R) Core(TM) i7-1065G7 CPU @ 1.30GHz WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-13.0.1 (ORCJIT, icelake-client) Threads: 1 on 8 virtual cores Environment: LD_LIBRARY_PATH = /run/opengl-driver/lib:/run/opengl-driver-32/lib:/usr/lib:/usr/lib32:/nix/store/0fih0yvy9lwxkaaci06gw0x1f5a5aqld-sane-config/lib/sane ``` </details>

github.com/JuliaLang/julia

problem with the unreliable approximation of `Core.Compiler.return_type`

opened 08:44AM - 08 May 20 UTC

stev47

bug inference

Using Julia master (newer than 301db971daaeeb627ba768375538e6e7ff36d215), the fo…llowing does not infer the correct type (see also the discussion in #34048): ```julia 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.