# How to avoid allocations in recursive data structures

**URL:** <https://discourse.julialang.org/t/how-to-avoid-allocations-in-recursive-data-structures/71268>\
**Category:** Performance\
**Tags:** memory-allocation, parametric-types, data\_structures\
**Created:** [November 10, 2021, 5:03pm UTC](https://discourse.julialang.org/t/how-to-avoid-allocations-in-recursive-data-structures/71268 "2021-11-10T17:03:12Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![peremato](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/peremato/32/29128_2.png) [@peremato](https://discourse.julialang.org/u/peremato)\
**Post date:** [November 10, 2021, 5:03pm UTC](https://discourse.julialang.org/t/how-to-avoid-allocations-in-recursive-data-structures/71268/1 "2021-11-10T17:03:12Z")

</div>

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:

```julia
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

```julia
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?

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [November 10, 2021, 5:08pm UTC](https://discourse.julialang.org/t/how-to-avoid-allocations-in-recursive-data-structures/71268/2 "2021-11-10T17:08:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![peremato](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/peremato/32/29128_2.png) [@peremato](https://discourse.julialang.org/u/peremato)\
**Post date:** [November 11, 2021, 7:11am UTC](https://discourse.julialang.org/t/how-to-avoid-allocations-in-recursive-data-structures/71268/3 "2021-11-11T07:11:43Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [November 11, 2021, 4:00pm UTC](https://discourse.julialang.org/t/how-to-avoid-allocations-in-recursive-data-structures/71268/4 "2021-11-11T16:00:26Z")

</div>

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