Not understanding linear growing allocations

peremato · November 18, 2021, 5:17pm

I’m trying to understand why returning a tuple of static vectors have the effect of constantly growing allocations. I have the following code to demonstrate

using BenchmarkTools
using StaticArrays

Vector2 = SVector{2}{Float64}

abstract type AbstractShape end

struct Box <: AbstractShape
    x::Float64
    y::Float64
end

function extent(b::Box)
    (Vector2(-b.x,-b.y), Vector2(b.x,b.y))
end

box = Box(1,1)

function area(box::Box)
    lower, upper =  extent(box)
    sum = 0.
    for i in 1:1000
        sum += (upper[1]-lower[1]) * (upper[2]-lower[2])
    end
    sum
end

@btime area($box)

It shows.

  139.743 μs (8011 allocations: 125.30 KiB)
4000.0

Changing the iterations it grows linearly, so the allocations happens on the getindex for lower and upper static vectors.

I see with @code_warntype that extent(box) returns Tuple{Any, Any}. I tried to qualify the definition of extent with function extent(b::Box)::Tuple{Vector2,Vector2} ... end but nothing changes for the allocations.

Is anything I am doing wrong?

goerch · November 18, 2021, 5:31pm

This

const Vector2 = SVector{2,Float64}

works for me.

DNF · November 18, 2021, 5:48pm

You will find the explanation in Performance Tips · The Julia Language This is required reading, IMO. The observed behavior pertains to performance tip number one.

goerch · November 18, 2021, 5:54pm

Would it be possible for the compiler to give a warning when a non const global variable is referenced in a function?

peremato · November 18, 2021, 5:55pm

Thanks very much. I read the performance tips, of course, but I was not expecting that a type alias Vector2 = SVector{2}{Float64} was not const implicitly. A simple const can make you waste hours

DNF · November 18, 2021, 5:58pm

Well, it’s not const unless you say so, it’s just a normal variable assignment. But yeah, it’s of course annoying when it happens.

I don’t think the compiler should warn against this, @goerch, but a linter should, perhaps.

carstenbauer · November 18, 2021, 10:06pm

FWIW GitHub - JunoLab/Traceur.jl would warn you.

julia> @trace area(box)
┌ Warning: uses global variable Main.Vector2
└ @ REPL[7]:2
┌ Warning: uses global variable Main.Vector2
└ @ REPL[7]:2
┌ Warning: dynamic dispatch to Main.Vector2(Base.neg_float(Base.getfield(_2, x)), Base.neg_float(Base.getfield(_2, y)))
└ @ REPL[7]:2
┌ Warning: dynamic dispatch to Main.Vector2(Base.getfield(_2, x), Base.getfield(_2, y))
└ @ REPL[7]:2
┌ Warning: sum is assigned as Float64
└ @ REPL[9]:3
┌ Warning: sum is assigned as Any
└ @ REPL[9]:5
┌ Warning:  is assigned as Tuple{Int64, Int64}
└ @ REPL[9]:4
┌ Warning:  is assigned as Union{Nothing, Tuple{Int64, Int64}}
└ @ REPL[9]:5
┌ Warning: dynamic dispatch to Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 2), 1)
└ @ REPL[9]:5
┌ Warning: dynamic dispatch to Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 1), 1)
└ @ REPL[9]:5
┌ Warning: dynamic dispatch to Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 2), 1) - Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 1), 1)
└ @ REPL[9]:5
┌ Warning: dynamic dispatch to Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 2), 2)
└ @ REPL[9]:5
┌ Warning: dynamic dispatch to Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 1), 2)
└ @ REPL[9]:5
┌ Warning: dynamic dispatch to Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 2), 2) - Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 1), 2)
└ @ REPL[9]:5
┌ Warning: dynamic dispatch to (Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 2), 1) - Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 1), 1)) * (Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 2), 2) - Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 1), 2))
└ @ REPL[9]:5
┌ Warning: dynamic dispatch to φ (%4 => 0.0, %25 => %14) + (Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 2), 1) - Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 1), 1)) * (Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 2), 2) - Base.getindex(Base.getfield($(Expr(:invoke, MethodInstance for extent(::Box), :(Main.extent), Core.Argument(2))), 1), 2))
└ @ REPL[9]:5
┌ Warning: area returns Any
└ @ REPL[9]:1
4000.0

goerch · November 18, 2021, 10:09pm

Tried that once, gives me too many false positives.

carstenbauer · November 18, 2021, 10:11pm

Well, in this case the good old @code_warntype is enough to detect this quickly (note that the red color highlighting is lost here on discourse):

julia> @code_warntype area(box)
MethodInstance for area(::Box)
  from area(box::Box) in Main at REPL[9]:1
Arguments
  #self#::Core.Const(area)
  box::Box
Locals
  @_3::Union{Nothing, Tuple{Int64, Int64}}
  @_4::Int64
  sum::Any
  upper::Any
  lower::Any
  i::Int64
Body::Any
1 ─ %1  = Main.extent(box)::Tuple{Any, Any}
│   %2  = Base.indexed_iterate(%1, 1)::Core.PartialStruct(Tuple{Any, Int64}, Any[Any, Core.Const(2)])
│         (lower = Core.getfield(%2, 1))
│         (@_4 = Core.getfield(%2, 2))
│   %5  = Base.indexed_iterate(%1, 2, @_4::Core.Const(2))::Core.PartialStruct(Tuple{Any, Int64}, Any[Any, Core.Const(3)])
│         (upper = Core.getfield(%5, 1))
│         (sum = 0.0)
│   %8  = (1:1000)::Core.Const(1:1000)
│         (@_3 = Base.iterate(%8))
│   %10 = (@_3::Core.Const((1, 1)) === nothing)::Core.Const(false)
│   %11 = Base.not_int(%10)::Core.Const(true)
└──       goto #4 if not %11
2 ┄ %13 = @_3::Tuple{Int64, Int64}
│         (i = Core.getfield(%13, 1))
│   %15 = Core.getfield(%13, 2)::Int64
│   %16 = sum::Any
│   %17 = Base.getindex(upper, 1)::Any
│   %18 = Base.getindex(lower, 1)::Any
│   %19 = (%17 - %18)::Any
│   %20 = Base.getindex(upper, 2)::Any
│   %21 = Base.getindex(lower, 2)::Any
│   %22 = (%20 - %21)::Any
│   %23 = (%19 * %22)::Any
│         (sum = %16 + %23)
│         (@_3 = Base.iterate(%8, %15))
│   %26 = (@_3 === nothing)::Bool
│   %27 = Base.not_int(%26)::Bool
└──       goto #4 if not %27
3 ─       goto #2
4 ┄       return sum

The above tells us that extent(box) is type unstable. Checking that function we get

julia> @code_warntype extent(box)
MethodInstance for extent(::Box)
  from extent(b::Box) in Main at REPL[7]:1
Arguments
  #self#::Core.Const(extent)
  b::Box
Body::Tuple{Any, Any}
1 ─ %1 = Base.getproperty(b, :x)::Float64
│   %2 = -%1::Float64
│   %3 = Base.getproperty(b, :y)::Float64
│   %4 = -%3::Float64
│   %5 = Main.Vector2(%2, %4)::Any
│   %6 = Base.getproperty(b, :x)::Float64
│   %7 = Base.getproperty(b, :y)::Float64
│   %8 = Main.Vector2(%6, %7)::Any
│   %9 = Core.tuple(%5, %8)::Tuple{Any, Any}
└──      return %9

So Main.Vector2(%2, %4)::Any is the culprit, i.e. the global variable (note the Main).

goerch · November 18, 2021, 10:24pm

Yeah, but this is not very accessible to beginners. Therefore my question of asking for a compiler warning.

DNF · November 18, 2021, 10:43pm

What would a compiler warning do? Is there such a thing? I’ve seen errors, but I can’t remember warnings.

goerch · November 18, 2021, 10:48pm

Similar to

x = 0
for i in 1:10
    x = 1
end

which results in

┌ Warning: Assignment to `x` in soft scope is ambiguous because a global variable by the same name exists: `x` will be treated as a new local. Disambiguate by using `local x` to suppress this warning or `global x` to assign to the existing global variable.
└

carstenbauer · November 18, 2021, 10:56pm

It doesn’t?

Are you using Jupyter notebooks or something similar by any chance?

UPDATE: Hm, no, in Jupyter I also don’t get this warning.

goerch · November 18, 2021, 11:07pm

I’m still on 1.6.3. Are we happy with this change? (I could live with the warning before)

DNF · November 18, 2021, 11:12pm

So that’s a compiler warning, is it?

Anyway, I think it should either be allowed, or not. Issuing a performance warning seems to me like the job of a linter.

That discussion was done to death many times over. It came after enormous popular demand.

carstenbauer · November 18, 2021, 11:13pm

No warning for me on 1.6.3 either.

Not sure what you’re / I’m doing differently.

goerch · November 18, 2021, 11:17pm

Here working with Juno

Sukera · November 18, 2021, 11:18pm

The warning is shown when running from a file. It isn’t shown in the REPL since it’s more likely that a user intended the access to a global variable and writing functions purely in the REPL is kind of hard to do.

carstenbauer · November 18, 2021, 11:21pm

Thanks, that makes sense. In any case, I agree with @DNF that a performance related warning is qualitatively different from a scoping warning. But I’m open to a --performance-warnings mode that shows all kinds of performance related warnings or similar.

goerch · November 18, 2021, 11:24pm

Sorry, but making differences when running a script from include or interactive shell simply sounds stupid to me.