# How to properly store a compile-time integer constant with a struct?

I am developing a tree-like data structure for a numerical simulation package, based on a composite type named `Tree`. To keep things general, I keep the implementation dimension-agnostic, so it should work with 1D, 2D, and 3D trees (i.e., binary tree, quadtree, octree). However, I would also like to keep the code as fast as possible, i.e., have the dimensionality as a compile-time constant. How would I implement this properly in Julia?

My first attempt is to write the struct as follows

``````mutable struct Tree{D}
# implementation...
end
``````

and then write functions as `foo(t::Tree)` or `bar(t::Tree{D}) where D` depending on whether I need to access the dimension in the respective function body. However, I am wondering:

1. Is this in fact the right way to do it or is there a better way?
2. Does the compiler even “know” `D` wherever it is needed, or will it actually be a runtime value?

Note: As you might have guessed, I am coming from a C++ background, where the canonical way to implement such a behavior (i.e., having an integer as a compile-time constant) would be to use a non-type template parameter:

``````template <int D> struct Tree {
// implementation...
};
``````
2 Likes

It seems related to `Array{T,N}` so I would look at Julia’s code in `Base`.

1 Like

You seem to have the right understanding. The compiler knows what is stored in the type, i.e., it will know the values of `D` at compile time, provided that the code is written so that type inference can do it’s job.

1 Like

To elaborate a bit on the previous two answers, a common pattern in Julia is to then store a `Tuple` with `D` elements inside the struct, that way the compiler can generate very efficient specialized code without extra allocations. You don’t even have to make it mutable. For your tree example, this could then be implemented like this:

``````struct Tree{T,D,C<:NTuple{D}}
data::T
children::C
function Tree(data::T, children::Vararg{Union{Tree{T,D},Nothing},D}) where {T,D}
return new{T,D,typeof(children)}(data, children)
end
end
``````

And you could then create trees like this:

``````julia> Tree(1, Tree(2, nothing, nothing), Tree(3, nothing, nothing))
Tree{Int64,2,Tuple{Tree{Int64,2,Tuple{Nothing,Nothing}},Tree{Int64,2,Tuple{Nothing,Nothing}}}}(1, (Tree{Int64,2,Tuple{Nothing,Nothing}}(2, (nothing, nothing)), Tree{Int64,2,Tuple{Nothing,Nothing}}(3, (nothing, nothing))))
``````
1 Like

@baggepinnen How can I ensure to write code such that the compiler knows the value of `D` at compile time? Would it be sufficient to create an instance of the composite type with a value for `D` that is known at compile time, e.g., `tree = Tree{2} ` or `t = Tree{ndim}` where `const ndim = 2` is a global constant? Or would I also have to stick to certain rules when passing `t` from function to function, to ensure that the compiler never “loses” that piece of information?

As a side note, is it also possible to check, e.g., in a function whether the non-type parameter `D` is known at compile-time (maybe with a macro)? That way, I could verify manually that I didn’t do anything weird/stupid.

It seems related to `Array{T,N}` so I would look at Julia’s code in `Base` .

@rveltz Where exactly would I have to look? If I just follow the `source` link in the docs, I get redirected to julia/array.jl at 2d5741174ce3e6a394010d2e470e4269ca54607f · JuliaLang/julia · GitHub, which just includes the lines

``````"""
Array{T,N} <: AbstractArray{T,N}
`N`-dimensional dense array with elements of type `T`.
"""
Array
``````

but no implementation details on the composite type.

That is, because `Array` is implemented in C, so it’s maybe not the best example. A good example of this being implemented in pure Julia would be `StaticArrays.jl`. The struct `SArray` is declared here:

Just note, that the whole package is really highly specialized and very generically written in an effort to squeeze every possible bit of performance out of the compiler, so don’t be intimidated, if there’s a lot of low-level compiler hackery going on.

1 Like

My goto-tool is `@code_warntype`. If that does not give me the information I want, I may use the package `Cthulhu.jl` or `Traceur.jl`.

1 Like

I think you’re going in the right direction. `@code_warntype` is the best tool for determining whether all of the type parameters (including the dimension D) have been inferred by the compiler.

Another thing you might find helpful is that you can write a dimension accessor function with essentially no run-time cost. For example:

``````julia> struct Tree{D}
size::NTuple{D, Int}
end

julia> t = Tree((1, 2, 3))
Tree{3}((1, 2, 3))

julia> dimension(t::Tree{D}) where {D} = D
dimension (generic function with 1 method)

julia> dimension(t)
3
``````

The cool thing is that the compiler can trivially see that `dimension(t)` relies only on the type of `T` to return its value. So you can efficiently use `dimension(t)` to get the dimension even if you didn’t happen to write your function with an explicit `D` parameter.

This is easier to see with an example:

``````julia> function foo(t::Tree)
return dimension(t) + 1
end
foo (generic function with 1 method)
``````

Note that `foo` doesn’t explicitly list `D` as a type parameter. But it doesn’t matter: the compiler is smart enough to evaluate the value of `dimension(t)` just from the input type. In fact, the whole function just compiles down to essentially “return 4”:

``````julia> @code_warntype foo(t)
Variables
#self#::Core.Compiler.Const(foo, false)
t::Tree{3}

Body::Int64
1 ─ %1 = Main.dimension(t)::Core.Compiler.Const(3, false)
│   %2 = (%1 + 1)::Core.Compiler.Const(4, false)
└──      return %2
``````

Note the `Core.Compiler.Const(4)` showing that the entire function has been evaluated at compile-time into just the constant 4.

Of course, that doesn’t stop you from explicitly using `D` as a function parameter, but you don’t need to, and it can often be convenient to access type traits with functions in this way.

5 Likes

Its common to make an accessor method on the type, e.g.

``````Base.ndims(::Type{Tree{D}}) where D = D
Base.ndims(t::Tree) = ndims(typeof(t))
``````

and then just use `ndims(t)` in the function body. The compiler is smart enough to inline it and treat it as a compile-time constant.

Edit: @rdeits already wrote the same thing.

1 Like