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.

Topic		Replies	Views
Strange memory allocations General Usage performance	7	611	February 27, 2023
Julia allocates when passing variable to function instead of constant New to Julia question	15	1066	June 2, 2024
Static array or tuple allocate at construction Performance memory-allocation , staticarrays , ntuple	2	370	March 11, 2024
Why is Julia allocating when accessing these structs? Performance	18	1441	June 10, 2024
Local arrays in for loops New to Julia	55	2613	March 3, 2021

Not understanding linear growing allocations

Related topics