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