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

General Usage
,
1

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
2

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

1 Like
3

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
4

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
5

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

6

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

7

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
8

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
9

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
10

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