Why does my constructor does 15 allocations?

Jean_Michel · December 21, 2018, 4:57pm

You will have to load my package github/jmichel7/Gapjm.jl to run the code below, but my question is simple enough.

julia> W=WeylGroup(:A,2)
WeylGroup(:A,2)

julia> Pol(:q)
q

julia> H=hecke(W,(q,-q^-1),q)
Hecke(WeylGroup(:A,2),(q, -q^-1),q)

julia> d=[one(H.W)=>one(Pol{Int})]
1-element Array{Pair{Perm{UInt8},Pol{Int64}},1}:
 {UInt8}() => 1

julia> @btime HeckeTElt($d,$H)
  1.517 μs (15 allocations: 816 bytes)
T()

In the code above, I construct fairly complex objects d and H but then just call a constructor:

struct HeckeTElt{P,C}<:HeckeElt{P,C}
  d::SortedPairs{P,C}
  H::HeckeAlgebra{C,<:CoxeterGroup}
end

There is no other constructor function, and the arguments are of the right type:

julia> typeof(d)
Array{Pair{Perm{UInt8},Pol{Int64}},1}

julia> SortedPairs
Array{Pair{K,V},1} where V where K

julia> typeof(H)
HeckeAlgebra{Pol{Int64},WeylGroup}

So why on earth does my constructor allocates 15 objects? I thought from various discussions that having a big object H in my struct takes no more memory that a reference to it in another language. Actually sizeof() returns 16 on my object. So why is the constructor so costly?

Daniel_Berge · December 21, 2018, 6:59pm

Your type isn’t fully parameterized to, due to the <:CoxeterGroup.

struct HeckeTElt{P,C}<:HeckeElt{P,C}
  d::SortedPairs{P,C}
  H::HeckeAlgebra{C,<:CoxeterGroup}
end

You would want to do a

struct HeckeTElt{P,C,G<:CoxeterGroup}<:HeckeElt{P,C}
  d::SortedPairs{P,C}
  H::HeckeAlgebra{C,G}
end

You will still have a allocation per element as the WelyGroup has a String in the in the struct.
After the modification I get:

@btime HeckeTElt($d,$H) # 7.052 ns (1 allocation: 32 bytes)

Jean_Michel · December 21, 2018, 7:08pm

Thank you very much! Clearly I missed the need for “full parametrization”. Can you explain a bit more what happens here?

Daniel_Berge · December 21, 2018, 7:16pm

Essentially, the compiler can’t tell from your type signature what exactly the memory layout of the structure is. For instance, for a Complex{Int}, the compiler can know that the memory layout will be a real and imaginary portion, in a specific order, using Int64s. In your case of HeckeTElt{P,C}, the compiler knows that HeckeAlgebra will have a CoxeterGroup, but will not know what a CoxeterGroup actually is, while HeckeTElt{P,C,G} will give the compiler the info it needs.

Jean_Michel · December 21, 2018, 7:21pm

Actually, in any other language, I would put in the field H a pointer to an Hecke algebra. So there would be no need to understand the memory layout of a HeckeAlgebra to build a HeckeElt (the algebra, to which the element belongs, is just there to be able to consult some of its properties when, for example, multiplying the elements). But I was told you do not have pointers in Julia. Is there any other way to design my struct in view of that?

Daniel_Berge · December 21, 2018, 7:43pm

It may be better for someone more knowledgeable to chime in at this point, from to the best of my understanding it has to do with multiple dispatch, and a function will be specialized to to a type signature. If the signature is insufficient to describe the operations without requiring dynamic type inference.

For example in the case of Complex{Int}, the macro @code_warntype shows us that everything is known that is required.

a=2+3im
b=2+4im
@code_warntype a+b

Body::Complex{Int64}
266 1 ─ %1 = (Base.getfield)(z, :re)::Int64                                                                                                                                                                       │╻╷ real
    │   %2 = (Base.getfield)(w, :re)::Int64                                                                                                                                                                       ││╻  getproperty
    │   %3 = (Base.add_int)(%1, %2)::Int64                                                                                                                                                                        │╻  +
    │   %4 = (Base.getfield)(z, :im)::Int64                                                                                                                                                                       ││╻  getproperty
    │   %5 = (Base.getfield)(w, :im)::Int64                                                                                                                                                                       ││╻  getproperty
    │   %6 = (Base.add_int)(%4, %5)::Int64                                                                                                                                                                        │╻  +
    │   %7 = %new(Complex{Int64}, %3, %6)::Complex{Int64}                                                                                                                                                         ││╻  Type
    └──      return %7

Now lets make an alternative type with only a partial signature.

import Base: +
struct MyComplex{T<:Real}
    re::T
    im
end
+(a::T,b::T) where {T<:MyComplex} = MyComplex(a.re+b.re,a.im+b.im)

mya=MyComplex(2,3)
myb=MyComplex(2,4)
@code_warntype mya+myb

Body::MyComplex{Int64}
7 1 ─ %1 = (Base.getfield)(a, :re)::Int64                                                                                                                                                                          │╻  getproperty
  │   %2 = (Base.getfield)(b, :re)::Int64                                                                                                                                                                          ││
  │   %3 = (Base.add_int)(%1, %2)::Int64                                                                                                                                                                           │╻  +
  │   %4 = (Base.getfield)(a, :im)::Any                                                                                                                                                                            │╻  getproperty
  │   %5 = (Base.getfield)(b, :im)::Any                                                                                                                                                                            ││
  │   %6 = (%4 + %5)::Any                                                                                                                                                                                          │
  │   %7 = %new(MyComplex{Int64}, %3, %6)::MyComplex{Int64}                                                                                                                                                        ││╻  Type
  └──      return %7

The :im field is of type Any, so the runtime has to dynamically dispatch on those types to determine which method is necessary, and what the return will be.

From my understanding, to keep the memory layout of MyComplex{Int} consistent, the :im field will actually be a pointer since the value has to be “boxed”, and that is what allows dynamic dispatch to happen.

The allocations you were seeing were the creation of the objects that the Any type will point to.

lwhitefox · December 21, 2018, 8:04pm

Ah, this is helpful - thanks. I’m still struggling with understanding why allocations crop up in what is to me a mysterious manner. This concise example and the last statement help a lot. Cool.