# Compile time exponentiation

**URL:** <https://discourse.julialang.org/t/compile-time-exponentiation/24390>\
**Category:** General Usage\
**Tags:** question\
**Created:** [May 20, 2019, 3:09am UTC](https://discourse.julialang.org/t/compile-time-exponentiation/24390 "2019-05-20T03:09:42Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [May 20, 2019, 3:09am UTC](https://discourse.julialang.org/t/compile-time-exponentiation/24390/1 "2019-05-20T03:09:42Z")

</div>

I want to evaluate `x^y` at compile time.  
The reason is to facilitate efficient construction of `NTuple` using `ntuple(f, Val(N)) method`.

Compare `bar1` and `bar2` functions below:

```julia
struct Foo end

getX(::Foo) = 5

function bar1(foo::Foo)
    X = getX(foo)
    Y = 2^X
    return (ntuple(i->1, Val(X)), ntuple(i->2, Val(Y)))
end

function bar2(foo::Foo)
    X = getX(foo)
    Y = prod(ntuple(i->2, Val(X)))
    return (ntuple(i->1, Val(X)), ntuple(i->2, Val(Y)))
end

```

Benchmarking and `@code_warntype` suggest that exponentiation is evaluated at run time for `bar1` and compile time for `bar2`.

1. Is this the correct interpretation?
2. If so why isn’t `x^y` evaulated at compile time? (I believe +, -, +, / operators are?)
3. On a practical note, is there any reason not to use `bar2`?

```julia
Julia-1.1.0> using BenchmarkTools

Julia-1.1.0> @btime bar1(foo)
  2.965 μs (1 allocation: 304 bytes)
((1, 1, 1, 1, 1), (2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2))

Julia-1.1.0> @btime bar2(foo)
  7.184 ns (0 allocations: 0 bytes)
((1, 1, 1, 1, 1), (2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2))

```

```julia
Julia-1.1.0> @code_warntype bar1(foo)
Body::Tuple{NTuple{5,Int64},Any}
1 ─ nothing
2 ┄ %2 = φ (#1 => 2, #6 => %16)::Int64
│ %3 = φ (#1 => 2, #6 => %23)::Int64
│ %4 = φ (#1 => 2, #6 => %15)::Int64
│ %5 = (Base.slt_int)(0, %4)::Bool
└── goto #7 if not %5
3 ─ %7 = (Base.cttz_int)(%4)::Int64
│ %8 = (Base.add_int)(%7, 1)::Int64
│ %9 = (Base.sle_int)(0, %8)::Bool
│ %10 = (Base.bitcast)(UInt64, %8)::UInt64
│ %11 = (Base.ashr_int)(%4, %10)::Int64
│ %12 = (Base.neg_int)(%8)::Int64
│ %13 = (Base.bitcast)(UInt64, %12)::UInt64
│ %14 = (Base.shl_int)(%4, %13)::Int64
└── %15 = (Base.ifelse)(%9, %11, %14)::Int64
4 ┄ %16 = φ (#3 => %2, #5 => %21)::Int64
│ %17 = φ (#3 => %8, #5 => %18)::Int64
│ %18 = (Base.sub_int)(%17, 1)::Int64
│ %19 = (Base.sle_int)(0, %18)::Bool
└── goto #6 if not %19
5 ─ %21 = (Base.mul_int)(%16, %16)::Int64
└── goto #4
6 ─ %23 = (Base.mul_int)(%3, %16)::Int64
└── goto #2
7 ─ goto #8
8 ─ goto #9
9 ─ %27 = %new(Main.:(##6#8))::Core.Compiler.Const(getfield(Main, Symbol("##6#8"))(), false)
│ %28 = invoke Main.Val(%3::Int64)::Val{_1} where _1
│ %29 = (Main.ntuple)(%27, %28)::Any
│ %30 = (Core.tuple)((1, 1, 1, 1, 1), %29)::Core.Compiler.PartialTuple(Tuple{NTuple{5,Int64},Any}, Any[Const((1, 1, 1, 1, 1), false), Any])
└── return %30

Julia-1.1.0> @code_warntype bar2(foo)
Body::Tuple{NTuple{5,Int64},NTuple{32,Int64}}
1 ─ %1 = (Core.tuple)((1, 1, 1, 1, 1), (2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2))::Core.Compiler.Const(((1, 1, 1, 1, 1), (2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2)), false)
└── return %1

```

---

<div class="post-metadata">

**Author:** ![c42f](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/c42f/32/52842_2.png) [@c42f](https://discourse.julialang.org/u/c42f)\
**Post date:** [May 20, 2019, 3:33am UTC](https://discourse.julialang.org/t/compile-time-exponentiation/24390/2 "2019-05-20T03:33:14Z")

</div>

It looks like the compiler doesn’t propagate known constants through `Base.power_by_squaring`. For example look at the `@code_warntype` of `pbs25() = Base.power_by_squaring(2,5)`.

You can work around this by introducing a shim function marked with `@pure`:

```julia
Base.@pure _power(m,n) = m^n

function bar3(foo::Foo)
    X = getX(foo)
    Y = _power(2,X)
    return (ntuple(i->1, Val(X)), ntuple(i->2, Val(Y)))
end

```

`@pure` comes with some caveats, but should be safe if you’re only putting integers into `_power`.

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [May 20, 2019, 3:57am UTC](https://discourse.julialang.org/t/compile-time-exponentiation/24390/3 "2019-05-20T03:57:15Z")

</div>

Thanks!  
(I must admit I don’t really understand `@pure`, but it seems to work here, so I’m happy)

---

<div class="post-metadata">

**Author:** ![c42f](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/c42f/32/52842_2.png) [@c42f](https://discourse.julialang.org/u/c42f)\
**Post date:** [May 20, 2019, 4:27am UTC](https://discourse.julialang.org/t/compile-time-exponentiation/24390/4 "2019-05-20T04:27:05Z")

</div>

Currently I think of `@pure` as a tool for convincing the compiler that it should constant propagate through a function with abandon. I believe the name comes from the [standard definition of pure function](https://en.wikipedia.org/wiki/Pure_function). For functions which are pure in that mathematical sense, it’s always valid to evaluate them with compile-time constant inputs.

The compiler team have avoided committing to the mathematical definition so far or making it a public API. I think mostly because it’s considered a compiler implementation detail, but also because it’s easy to abuse.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [May 20, 2019, 8:22am UTC](https://discourse.julialang.org/t/compile-time-exponentiation/24390/5 "2019-05-20T08:22:35Z")

</div>

A big problem with `@pure` is that it does not conform to the naive mathematical standard definition: @pure functions don’t properly propagate backedges. This means that their reverse dependencies, i.e. call-sites, don’t get recompiled if something in (or downstream of) your pure function changes, and this creates lots of load-order dependent behavior and potential debug nightmares.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [May 20, 2019, 8:40am UTC](https://discourse.julialang.org/t/compile-time-exponentiation/24390/6 "2019-05-20T08:40:25Z")

</div>

> [@c42f](#):
>
> also because it’s easy to abuse.

I think that the consensus is that _not_ misusing `Base.@pure` requires a level of understanding about Julia’s internals that very few people have, and even then it is easy to make mistakes.

I don’t think it is [good practice](https://discourse.julialang.org/t/suggestion-keeping-responses-appropriate-for-the-implicit-category/21345) to advocate its use on this forum, especially in the Usage category.

---

<div class="post-metadata">

**Author:** ![c42f](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/c42f/32/52842_2.png) [@c42f](https://discourse.julialang.org/u/c42f)\
**Post date:** [May 20, 2019, 10:09am UTC](https://discourse.julialang.org/t/compile-time-exponentiation/24390/7 "2019-05-20T10:09:28Z")

</div>

Well of course it’s good to avoid messy hacks, but I think this use of pure is pretty harmless. (The annotation may go away of course.)

Feel free to offer an alternative. I didn’t find a neat one yet.