# Efficiently copying a tree with shared children

**URL:** <https://discourse.julialang.org/t/efficiently-copying-a-tree-with-shared-children/87787>\
**Category:** Performance\
**Tags:** question, package, performance\
**Created:** [September 25, 2022, 7:20pm UTC](https://discourse.julialang.org/t/efficiently-copying-a-tree-with-shared-children/87787 "2022-09-25T19:20:54Z")\
**Posts on this page:** 1\
**Page:** 2

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [September 27, 2022, 4:07pm UTC](https://discourse.julialang.org/t/efficiently-copying-a-tree-with-shared-children/87787/22 "2022-09-27T16:07:35Z")

</div>

Let’s start with a fully immutable `LeafNode`. Note that constructing these does not involve any memory allocation. If I ever needed to “change” one of these, I would just construct a new one rather than trying to mutate an existing one.

```julia
julia> struct LeafNode
           key::UInt
           degree::Int # 0 for constant/variable, 1 for cos/sin, 2 for +/* etc.
           val::Float32 # If is a leaf, this stores the value
           op::Int # enum over operators
           LeafNode(val::Float32) = new(get_node_key(), 0, val)
       end

julia> @allocated LeafNode(1.f0)
0

julia> @allocated LeafNode(1.f2)
0

julia> sizeof(LeafNode(1.f2))
32

```

I’ll also note here that the size of this leaf node is 32 bytes. You might think it should be 28 bytes because you tried to save 4 bytes with the `Float32`, but memory alignment means that you still end up needing 8 bytes for that field.

If you actually wanted to conserve memory, you need to make another field 4-bytes.

```julia
julia> struct LeafNode5
           key::UInt
           degree::Int
           val::Float32
           op::Int32
       end

julia> sizeof(LeafNode5)
24

```

The bigger point is that constructing these immutable `LeafNode` structs does not involve any dynamic allocation. It may be cheaper to reconstruct these `LeafNode`s than to keep them mutable.

As for my `Node` design above, I’m not entirely sure if I achieved my goals there. While I made the four fields immutable, you can still modify the `l` and `r` reference.

```julia
julia> @allocated n1 = Node(1.f0)
64

julia> @allocated n2 = Node(2.f0)
64

julia> @allocated n3 = Node(3, n1, n2)
96

julia> n3.l[] = Node(4.f0)
Node(0x000000000000000f, 0, 4.0f0, 7953757363372450154, #undef, #undef)

julia> n3.r[] = Node(5.f0)
Node(0x0000000000000010, 0, 5.0f0, 9223372036854775807, #undef, #undef)

julia> n3
Node(0x000000000000000e, 2, 0.0f0, 3, Base.RefValue{Node}(Node(0x000000000000000f, 0, 4.0f0, 7953757363372450154, #undef, #undef)), Base.RefValue{Node}(Node(0x0000000000000010, 0, 5.0f0, 9223372036854775807, #undef, #undef)))

```

[Previous page](https://discourse.julialang.org/t/efficiently-copying-a-tree-with-shared-children/87787.md?page=1)