How to avoid allocations in recursive data structures

General Usage Performance
, ,
1

For my project I need a tree-like data structure. Since I didn’t find a way to forward declare types I am using the trick of an abstract type instead of a reference a concrete type. The problem is that when using this data structure, additional allocations are issued. See for example the following code:

using BenchmarkTools

abstract type AbstractP end

struct V
    n::Int64
    d::Vector{AbstractP}
    V(n::Int64) = new(n, [])
end

struct P <: AbstractP
    v::V
    t::Float64
end

Base.push!(v::V, w::V, t::Float64) = push!(v.d, P(w,t))

top = V(1)
push!(top, V(2), 2.)
push!(top, V(3), 3.)
push!(top, V(4), 4.)

function foo(v::V)
    sum::Float64 = 0.
    for d in v.d
       sum += d.t 
    end
    sum
end

@show top
@btime foo(top)

I obtain

top = V(1, AbstractP[P(V(2, AbstractP[]), 2.0), P(V(3, AbstractP[]), 3.0), P(V(4, AbstractP[]), 4.0)])
  462.500 ns (9 allocations: 144 bytes)

Is there a way to build these kind of data structures and not having the overhead of the allocations?

2

Make V parametric on the element type for d being a subtype of AbstractP.

1 Like
3

Thanks very much. This works, although is a bit ugly that the type is now called V{P}. Somehow I see it as a deficiency of Julia not be able to forward declare, instead you need to do a delayed declaration using parametric types.

1 Like
4

You can define a type alias to make it less ugly for users of V.