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

**URL:** <https://discourse.julialang.org/t/how-to-properly-store-a-compile-time-integer-constant-with-a-struct/34293>\
**Category:** General Usage\
**Tags:** performance, parametric-types\
**Created:** [February 7, 2020, 10:46am UTC](https://discourse.julialang.org/t/how-to-properly-store-a-compile-time-integer-constant-with-a-struct/34293 "2020-02-07T10:46:12Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![sloede](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sloede/32/44787_2.png) [@sloede](https://discourse.julialang.org/u/sloede)\
**Post date:** [February 7, 2020, 10:46am UTC](https://discourse.julialang.org/t/how-to-properly-store-a-compile-time-integer-constant-with-a-struct/34293/1 "2020-02-07T10:46:12Z")

</div>

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

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

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

```

---

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [February 7, 2020, 10:51am UTC](https://discourse.julialang.org/t/how-to-properly-store-a-compile-time-integer-constant-with-a-struct/34293/2 "2020-02-07T10:51:29Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [February 7, 2020, 11:18am UTC](https://discourse.julialang.org/t/how-to-properly-store-a-compile-time-integer-constant-with-a-struct/34293/3 "2020-02-07T11:18:50Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [February 7, 2020, 11:56am UTC](https://discourse.julialang.org/t/how-to-properly-store-a-compile-time-integer-constant-with-a-struct/34293/4 "2020-02-07T11:56:09Z")

</div>

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:

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

```

---

<div class="post-metadata">

**Author:** ![sloede](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sloede/32/44787_2.png) [@sloede](https://discourse.julialang.org/u/sloede)\
**Post date:** [February 7, 2020, 11:59am UTC](https://discourse.julialang.org/t/how-to-properly-store-a-compile-time-integer-constant-with-a-struct/34293/5 "2020-02-07T11:59:39Z")

</div>

@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.

---

<div class="post-metadata">

**Author:** ![sloede](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sloede/32/44787_2.png) [@sloede](https://discourse.julialang.org/u/sloede)\
**Post date:** [February 7, 2020, 12:02pm UTC](https://discourse.julialang.org/t/how-to-properly-store-a-compile-time-integer-constant-with-a-struct/34293/6 "2020-02-07T12:02:03Z")

</div>

> 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 [https://github.com/JuliaLang/julia/blob/2d5741174ce3e6a394010d2e470e4269ca54607f/base/array.jl#L45-L49](https://github.com/JuliaLang/julia/blob/2d5741174ce3e6a394010d2e470e4269ca54607f/base/array.jl#L45-L49), which just includes the lines

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

```

but no implementation details on the composite type.

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [February 7, 2020, 12:10pm UTC](https://discourse.julialang.org/t/how-to-properly-store-a-compile-time-integer-constant-with-a-struct/34293/7 "2020-02-07T12:10:04Z")

</div>

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:

> <https://github.com/JuliaArrays/StaticArrays.jl/blob/master/src/SArray.jl>

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.

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [February 7, 2020, 12:32pm UTC](https://discourse.julialang.org/t/how-to-properly-store-a-compile-time-integer-constant-with-a-struct/34293/8 "2020-02-07T12:32:55Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [February 7, 2020, 4:18pm UTC](https://discourse.julialang.org/t/how-to-properly-store-a-compile-time-integer-constant-with-a-struct/34293/9 "2020-02-07T16:18:38Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![tkluck](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkluck/32/15769_2.png) [@tkluck](https://discourse.julialang.org/u/tkluck)\
**Post date:** [February 7, 2020, 6:19pm UTC](https://discourse.julialang.org/t/how-to-properly-store-a-compile-time-integer-constant-with-a-struct/34293/10 "2020-02-07T18:19:30Z")

</div>

> [@sloede](#):
>
> 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.

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

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