Help understand allocation in small custom struct

General Usage Performance
1

I have the following small custom structs that one of which is recursive in nature

abstract type TTNNode{T} end

struct LeafNode{T,A<:AbstractMatrix{T}} <: TTNNode{T}
    U::A         # Basis matrix U_ℓ ∈ ℝ^{n_ℓ × r_ℓ}
    n::Int        # Dimension n_ℓ of the leaf
    r::Int         # Rank r_ℓ of the leaf
end

function LeafNode(U::AbstractMatrix{T}) where {T}
    s = size(U)
    @inbounds LeafNode{eltype(U),typeof(U)}(U, s[1], s[2])
end

struct TTN{T,A<:AbstractArray{T},M} <: TTNNode{T} where {M}
    C::A                  # Connection tensor C_τ ∈ ℝ^{r_τ × r_τ₁ × ... × r_τₘ}
    r::Int                  # Rank r_τ of the internal node
    leaves::NTuple{M,TTNNode{T}}  # Child nodes τ₁, ..., τₘ
end

@check_allocs function TTN(C::AbstractArray{T}, leaves::NTuple{M,TTNNode}) where {T,M}
    TTN{T,typeof(C),M}(C, size(C,1), leaves)
end

as you can see I am checking for allocations using the AllocCheck.jl package, but when I run the following snippet:

begin 
    l1 = LeafNode(rand(16,5))
    l2 = LeafNode(rand(16,5))
    C1 = rand(5,5,5); l = (l1,l2)
     try 
         TTN(C1, l)
     catch err
          err.errors
     end
end

I get:

1-element Vector{Any}:
 Allocation of Tuple{LeafNode{Float64, Matrix{Float64}}, LeafNode{Float64, Matrix{Float64}}} in TTN.jl:15
  | C::A                    # Connection tensor C_τ ∈ ℝ^{r_τ × r_τ₁ × ... × r_τₘ}

but the struct is immutable and I can’t understand why there is an allocation there. Can someone please help me?

2

TTNNode is an abstract type, and leaves::NTuple{M,TTNNode{T}} is thus a tuple of abstract types? The compiler cannot know how large this abstract type is so it cannot palce it on the stack, and must allocate on the heap to store it.

1 Like
3

Do I have to use concrete types on NTuple so as not to allocate then?

4

Yes. Whenever you have an abstractly typed field in a struct, or a tuple, the compiler just doesn’t know what you will put in there. There are ways around this using packages like

but if you can design without heterogeneous types it would likely simplify things for you.

1 Like
5

Thank you so much!

1 Like