# Should \`literal\_pow\` optimize for bigger exponents?

**URL:** <https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167>\
**Category:** Internals & Design\
**Created:** [February 10, 2022, 2:02pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167 "2022-02-10T14:02:32Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [February 10, 2022, 2:02pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/1 "2022-02-10T14:02:32Z")

</div>

`Base.literal_pow` allows `x^2` and `x^3` to be turned into `x*x` and `x*x*x`, turning it into very efficient machine code. I was wondering if it could be extended to higher exponents. The function I used for this is this one:

```julia
Base.literal_pow(::typeof(^),x::Number,n::Val{N}) where N = prod(ntuple(Returns(x),Val(N)))

```

I found that for exponents up to `x^32`, the compiled versions are faster, but the compile time gets longer and longer:

 ![image](https://global.discourse-cdn.com/julialang/original/3X/4/8/48d5e9110b1887981206b99095c3ab58638d8fa3.png)  
 ![belapsed](https://global.discourse-cdn.com/julialang/original/3X/a/8/a82b245c37eb10762f49a35a36b0415f7863ce6d.png)

> **Code used to generate the data**
>
> ```julia
> using BenchmarkTools, ProgressMeter
> 
> #Base.literal_pow(::typeof(^),x::Number,n::Val{N}) where N = prod(ntuple(Returns(x),Val(N)))
> 
> t1 = Float64[]
> t2 = Float64[]
> 
> @showprogress for n in 0:50
> @eval f(x) = x^$n
> a = 2
> push!(t1, @elapsed f(2))
> push!(t2, @belapsed f($(Ref(a))[]))
> end
> 
> ```

> **My versioninfo()**
>
> ```julia-repl
> julia> versioninfo()
> Julia Version 1.7.2
> Commit bf53498635 (2022-02-06 15:21 UTC)
> Platform Info:
> OS: Windows (x86_64-w64-mingw32)
> CPU: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
> WORD_SIZE: 64
> LIBM: libopenlibm
> LLVM: libLLVM-12.0.1 (ORCJIT, skylake)
> 
> ```

up to `x^26`, the compiled code is very efficient:

```julia-repl
julia> @code_llvm (x->x^26)(2)
; @ REPL[9]:1 within `#23`
; Function Attrs: uwtable
define i64 @"julia_#23_1634"(i64 signext %0) #0 {
top:
; ┌ @ C:\Users\mittel\juliastuff\literal_pow.jl:3 within `literal_pow`
; │┌ @ tuple.jl:499 within `prod`
; ││┌ @ operators.jl:655 within `*`
; │││┌ @ operators.jl:634 within `afoldl`
; ││││┌ @ int.jl:88 within `*`
       %1 = mul i64 %0, %0
       %2 = mul i64 %1, %0
       %3 = mul i64 %2, %2
       %4 = mul i64 %3, %3
       %5 = mul i64 %4, %0
       %6 = mul i64 %5, %5
; └└└└└
  ret i64 %6
}

```

between `x^27` and `x^32` the compiled code is more complicated but apparently it is still ok, but after `x^33` it’s catastrophical.

Would it make sense to extend this? (up to 5? 10? 26?)

Also I don’t know how it behaves on other architectures or with other types (Float64, Float32, Int32…)

_ **edit:** _ corrected benchmark

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [February 10, 2022, 2:06pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/2 "2022-02-10T14:06:23Z")

</div>

This doesn’t work because it is too inaccurate. However, in 1.8, `pow` with integer exponents got a bunch faster (it uses compensated power by squaring).

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [February 10, 2022, 2:13pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/3 "2022-02-10T14:13:09Z")

</div>

do you mean for floats? it shouldn’t be a problem for integers?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [February 10, 2022, 2:19pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/4 "2022-02-10T14:19:02Z")

</div>

Oh, sorry. I missed that you were timing integers. This still seems really weird. Are you sure your benchmark isn’t just constant folding the whole benchmark away?

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [February 10, 2022, 2:26pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/5 "2022-02-10T14:26:42Z")

</div>

maybe…

the `@code_llvm` looks optimized and beautiful:

```julia
julia> @code_llvm (x->x^23)(2)
; @ REPL[23]:1 within `#45`
; Function Attrs: uwtable
define i64 @"julia_#45_1838"(i64 signext %0) #0 {
top:
; ┌ @ C:\Users\mittel\juliastuff\literal_pow.jl:3 within `literal_pow`
; │┌ @ tuple.jl:499 within `prod`
; ││┌ @ operators.jl:655 within `*`
; │││┌ @ operators.jl:631 within `afoldl`
; ││││┌ @ int.jl:88 within `*`
       %1 = mul i64 %0, %0 # x^2
       %2 = mul i64 %1, %1 # x^4
       %3 = mul i64 %2, %0 # x^5
       %4 = mul i64 %3, %3 # x^10
       %5 = mul i64 %4, %0 # x^11
       %6 = mul i64 %5, %0 # x^12
       %7 = mul i64 %6, %5 # x^23
; └└└└└
  ret i64 %7
}

```

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [February 10, 2022, 2:37pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/6 "2022-02-10T14:37:59Z")

</div>

It’s definitely constant folded. There’s no such thing as pikosecond operations on today’s computers. There’s some discussion about this and how to avoid it in the [BenchmarkTools README](https://github.com/JuliaCI/BenchmarkTools.jl).

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [February 10, 2022, 2:56pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/7 "2022-02-10T14:56:01Z")

</div>

indeed

> **with this corrected code**
>
> ```julia
> using BenchmarkTools, ProgressMeter
> 
> #Base.literal_pow(::typeof(^),x::Number,n::Val{N}) where N = prod(ntuple(Returns(x),Val(N)))
> 
> t1 = Float64[]
> t2 = Float64[]
> 
> @showprogress for n in 0:50
> @eval f(x) = x^$n
> a = 2
> push!(t1, @elapsed f(2))
> push!(t2, @belapsed f($(Ref(a))[]))
> end
> 
> ```

![belapsed](https://global.discourse-cdn.com/julialang/original/3X/a/8/a82b245c37eb10762f49a35a36b0415f7863ce6d.png)  
 ![belapsedlog](https://global.discourse-cdn.com/julialang/original/3X/2/6/269add2f544dee67f530b781123f5189a01c52f7.png)

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [February 10, 2022, 2:58pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/8 "2022-02-10T14:58:17Z")

</div>

I think we might be able to get the same result (without the performance cliff) by doing more aggressive constant propagation here.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 10, 2022, 2:58pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/9 "2022-02-10T14:58:59Z")

</div>

> [@MarcMush](#):
>
> I found that for exponents up to `x^32` , the compiled versions are faster, but the compile time gets longer and longer:

`prod(ntuple(...))` is a very suboptimal way to compute large powers — you want to use repeated squaring, or more generally an optimal addition chain. This is implemented in:

> **[GitHub - JuliaMath/FastPow.jl: optimal addition-chain exponentiation for Julia](https://github.com/JuliaMath/FastPow.jl)**
>
> optimal addition-chain exponentiation for Julia. Contribute to JuliaMath/FastPow.jl development by creating an account on GitHub.

but it isn’t the default for `literal_pow` because it is slightly less accurate (for floating-point types).

> [@MarcMush](#):
>
> the `@code_llvm` looks optimized and beautiful:
> 
> ```julia
> julia> @code_llvm (x->x^23)(2)
> 
> ```

LLVM only does this by default for integer types; for floating-point types you have to use `@fastmath` because it changes (worsens) the roundoff errors. The FastPow package extends this to other types beyond the small set of built-in types supported by LLVM.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [February 10, 2022, 3:00pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/10 "2022-02-10T15:00:43Z")

</div>

If you look at the generated code, it looks like LLVM is smart enough to figure this out by itself.

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [February 10, 2022, 3:02pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/11 "2022-02-10T15:02:03Z")

</div>

only up to 26

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 10, 2022, 3:06pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/12 "2022-02-10T15:06:21Z")

</div>

Benchmarking powers for integer types is pretty misleading.

In practice, you are almost always going to use floating-point types in calculations involving large exponents, to avoid overflow (unless you are doing number theory, in which case you will be using `BigInt`). And LLVM optimizes products of floating point numbers _very_ differently because floating-point multiplication is not associative.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 10, 2022, 3:22pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/13 "2022-02-10T15:22:09Z")

</div>

In particular, here is the result (on my 2016 Intel laptop) with `@fastpow`, benchmarking for floating-point exponentiation:

> **benchmark code**
>
> ```julia
> using BenchmarkTools, ProgressMeter, FastPow
> 
> t_old = Float64[]
> t_new = Float64[]
> 
> @showprogress for n in 0:50
> @eval f(x) = x^$n
> @eval @fastpow g(x) = x^$n
> a = 2.0
> push!(t_old, @belapsed f($(Ref(a))[]))
> push!(t_new, @belapsed g($(Ref(a))[]))
> end
> 
> ```

 ![image](https://global.discourse-cdn.com/julialang/original/3X/f/d/fd1919f81404944c84dd5718eef56eba75b43095.jpeg)

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [February 10, 2022, 3:28pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/14 "2022-02-10T15:28:42Z")

</div>

See also [https://github.com/JuliaLang/julia/pull/44106](https://github.com/JuliaLang/julia/pull/44106) which should allow better constant prop through `^`

---

<div class="post-metadata">

**Author:** ![MarcMush](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marcmush/32/18006_2.png) [@MarcMush](https://discourse.julialang.org/u/MarcMush)\
**Post date:** [February 10, 2022, 3:51pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/15 "2022-02-10T15:51:22Z")

</div>

I found an improvement for `BigInt` up to 5, for `Complex{Int64}` up to 6, and nothing for `Float64` compared to `@fastmath`

![bigint](https://global.discourse-cdn.com/julialang/original/3X/5/4/547602ca26b287d78818e118d82352ff9f6677e9.png)  
 ![complex](https://global.discourse-cdn.com/julialang/original/3X/6/6/661688dbba0fa9ab257ea73e4603ee4ed5ebd86e.png)  
 ![float64](https://global.discourse-cdn.com/julialang/original/3X/0/7/071860efad5b47cad99c2edcf67396ca34e70c8e.png)

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 10, 2022, 4:44pm UTC](https://discourse.julialang.org/t/should-literal-pow-optimize-for-bigger-exponents/76167/16 "2022-02-10T16:44:54Z")

</div>

> [@MarcMush](#):
>
> I found an improvement for `BigInt` up to 5, for `Complex{Int64}` up to 6, and nothing for `Float64` compared to `@fastmath`

As I said above, LLVM knows how to optimize small-integer exponents for a handful of built-in types, including floating-point types if you use `@fastmath`, but won’t do anything for more general types (including complex numbers).

For `BigInt`, in general I wouldn’t expect any improvement from unrolling, since the arithmetic is so expensive there that the underlying GMP library can already afford to do something pretty good, and the optimal algorithm is more complicated. (I can’t reproduce your improvement for small powers on my machine, but in any case even that should go away if you make your starting integer larger.)

For `Complex` numbers, LLVM can’t do anything, even with `@fastmath`, but with `@fastpow` it should faster for _all_ powers (not just “up to 6”, which is an artifact of your unrolling the power in the most inefficient way and hoping that the compiler will rearrange to compensate, which it can’t for more general number types):

 ![image](https://global.discourse-cdn.com/julialang/original/3X/4/b/4b1e2fc200fa74bdfee5840468a51499ef0fe21d.jpeg)