Computing at Compile Time in Julia – A First Blog Post

This is a short post on the Val data type in Julia and using it for computing at compile-time. Some familiarity with the Julia programming language is assumed. This is going to be a fairly short post intended to take this blog on a spin.

The Val Type

Val is a very interesting type. From the docs on Val(c):

Return Val{c}(), which contains no run-time data. Types like this can be used to pass the information between functions through the value c, which must be an isbits value or a Symbol. The intent of this construct is to be able to dispatch on constants directly (at compile time) without having to test the value of the constant at run time.

So, Val is a paramteric type with one type parameter, and there can only be one possible value of each concrete Val{T}.

using Test

@testset "Val types" begin
	@test typeof(Val(7)) <: Val
	@test typeof(Val(0xc0ffee)) == Val{0xc0ffee}
end

Test Summary: | Pass  Total  Time
Val types     |    2      2  0.1s

A function that takes an argument of type ::Val{N}, where N is some isbits value, can only be passed the value Val(N). But, when I came across Val for the first time, the example in the docs did not quite aid my understanding.

using Test

f(::Val{true}) = "Good"
f(::Val{false}) = "Bad"

@testset "Passing values through Val" begin
	@test f(Val(true)) == "Good"
	@test f(Val(false)) == "Bad"
end

Test Summary:              | Pass  Total  Time
Passing values through Val |    2      2  0.0s

So, I tried to check my understanding of the "no-runtime data" aspect of this type by implementing my own example – factorial. Keep in mind that factorial is just a toy example, but the principles demonstrated here should carry over to developing more sophisticated examples.

using Test

import Base: factorial

factorial(::Val{0}) = 1
factorial(::Val{N}) where {N} = N * factorial(Val(N-1))

@testset "Comptime factorial" begin
    ns = 1:13
    for n in ns
        @test factorial(Val(n)) == factorial(n)
    end
end

Test Summary:      | Pass  Total  Time
Comptime factorial |   13     13  0.0s

All right that's great and all, but how does one check whether the Val variant is doing the entire calculation at compile-time?

Verification: Inspect Lowered Code

The various macros that allow inspection of lowered forms of your source code tell the story.

using InteractiveUtils  # loaded by default in the REPL

@show @code_typed factorial(Val(10))

#= none:2 =# @code_typed(factorial(Val(10))) = CodeInfo(
1 ─     return 3628800
) => Int64

That's right, it compiles down to return 3628800. In case you are still skeptical, you can also inspect the assembly.

@code_native factorial(Val(10))

	.text
	.file	"factorial"
	.globl	julia_factorial_1171            # -- Begin function julia_factorial_1171
	.p2align	4, 0x90
	.type	julia_factorial_1171,@function
julia_factorial_1171:                   # @julia_factorial_1171
; ┌ @ none:1 within `factorial`
	.cfi_startproc
# %bb.0:                                # %top
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register %rbp
	movl	$3628800, %eax                  # imm = 0x375F00
	popq	%rbp
	.cfi_def_cfa %rsp, 8
	retq
.Lfunc_end0:
	.size	julia_factorial_1171, .Lfunc_end0-julia_factorial_1171
	.cfi_endproc
; └
                                        # -- End function
	.section	".note.GNU-stack","",@progbits

Ignore the sections and directives (the symbols starting with . like .text, .p2align etc). The assembly corresponds to movl $3628800$, %eax followed by retq, which is basically return 3628800.

Verification: Benchmarking

using BenchmarkTools

@btime factorial($(Val(13)))
@btime factorial($(13))

  1.600 ns (0 allocations: 0 bytes)
  4.800 ns (0 allocations: 0 bytes)

NB: factorial from Julia base uses a lookup table and is quite fast. A naive, non-tail recursive implementation would be much slower than both of these.

function factorial_naive(n)
	n == 0 && return 1
	return n * factorial_naive(n-1)
end

@btime factorial_naive($(13))

  28.442 ns (0 allocations: 0 bytes)

Bounds Checking

There is still a problem with this – it does not check for negative values unlike the default factorial in Julia base. We can work around that as well.

function factorial(::Val{N}) where N
	N < 0 && throw(DomainError(N, "`factorial` expects non-zero integers."))
	N * factorial(Val(N-1))
end

@show @test_throws DomainError factorial(Val(-1))

#= none:2 =# @test_throws(DomainError, factorial(Val(-1))) = Test Passed
      Thrown: DomainError

Is it still comptime?

println(">>> TYPED CODE <<<")
@show @code_typed factorial(Val(13))
println()
println(">>> BENCHMARK <<<")
@btime factorial($(Val(13)))

>>> TYPED CODE <<<
#= none:1 =# @code_typed(factorial(Val(13))) = CodeInfo(
1 ─     nothing::Nothing
└──     return 6227020800
) => Int64

>>> BENCHMARK <<<
  1.500 ns (0 allocations: 0 bytes)

Looks like it is.

What is the use of all this?

We are effectively creating a compile-time lookup table in the julia runtime. This particular example would be very useful if you are working with something like Taylor series of many different functions, and you are calling them repeatedly. By using this, every call to factorial using Vals would reduce to a single register allocation (assuming first compilation is done of course).

As a next step, one could create a macro that would take code like factorial(13) and convert it to factorial(Val(13)) for ergonomics; think the @view macro that converts array slices (which would incur overhead of allocation and copying) into views. And since we have an analogy with @view, the next step would be a macro like @views that would recurse into an expression and replace all constants with their Val variants, and a macro that can generate Val variants of structs and functions, similar to @adapt_structure from Adapt.jl