Efficiently copying a tree with shared children

General Usage Performance
, ,
22

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> 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> 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 LeafNodes 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> @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)))