# Loop unrolling, type param to macro, generated functions

**URL:** <https://discourse.julialang.org/t/loop-unrolling-type-param-to-macro-generated-functions/1911>\
**Category:** General Usage\
**Tags:** question, unrolling\
**Created:** [February 5, 2017, 12:02am UTC](https://discourse.julialang.org/t/loop-unrolling-type-param-to-macro-generated-functions/1911 "2017-02-05T00:02:38Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![pint](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pint/32/125_2.png) [@pint](https://discourse.julialang.org/u/pint)\
**Post date:** [February 5, 2017, 12:02am UTC](https://discourse.julialang.org/t/loop-unrolling-type-param-to-macro-generated-functions/1911/1 "2017-02-05T00:02:38Z")

</div>

yeah, i don’t seem to know what my question is. below you find 3.

i have a type `Mod{B, A}` which just encapsulates an UInt64 array.

and a naive function on it:

```julia
@inline limbs(b) = cld(b, 31)

mul!{B, A}(r::Mod{B, A}, a::Mod{B, A}, b::Mod{B, A}) = begin
  @inbounds begin
    for i in 1:limbs(B)
      r.n[i] = zero(UInt64)
    end
    for i in 1:limbs(B), j in 1:limbs(B)      
      r.n[i] += a.n[mod(i-j, limbs(B)) + 1] * b.n[j] * (j > i ? UInt64(A) : UInt64(1))
    end
  end
  r
end

```

the idea here is that every loop bound is known at compile time, the loops would get unrolled, and so the mod and the conditional does not even get into the native code. however, it seems that i exceeded some unroll threshold, and i get only the inner loop unrolled. the `mod` hurts especially badly, i tried using an optimized mod, which is good, but unrolling would be even better. so **question #1: is there a way to force unrolling?**

i tried to use @unroll as in [Unroll.jl](https://github.com/StephenVavasis/Unroll.jl), or more precisely a customized variant of it. however, it appears that macros are expanded before B is known, so not the value but just a symbol is passed. dead end? **question #2: do i give up on macros for this?**

i wound up doing a generated function. it makes super optimized code, and the speed significantly improved. however, i seem to recall that generated functions have some problems, maybe with precompiling, but some cursory googling did not help. so **question #3: are there any drawbacks to generated functions?**

below my creation. a little bit write only, but blazing fast.

```julia
@generated mul!{B, A}(r::Mod{B, A}, a::Mod{B, A}, b::Mod{B, A}) = begin
  li = limbs(B)
  r = esc(r); a = esc(a); b = esc(b)
  quote
    @inbounds begin
      $([quote
          t = UInt64(0)
          $([:( t += a.n[$(mod(i-j, li)+1)] * b.n[$j] ) for j = i+1:li]...)
          t *= $(UInt64(A))
          $([:( t += a.n[$(mod(i-j, li)+1)] * b.n[$j] ) for j = 1:i]...)
          r.n[$i] = t
        end for i = 1:li ]...)
    end
    r
  end
end

```

---

<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 5, 2017, 3:16am UTC](https://discourse.julialang.org/t/loop-unrolling-type-param-to-macro-generated-functions/1911/2 "2017-02-05T03:16:13Z")

</div>

> [@pint](#):
>
> the idea here is that every loop bound is known at compile time, the loops would get unrolled, and so the mod and the conditional does not even get into the native code. however, it seems that i exceeded some unroll threshold, and i get only the inner loop unrolled. the mod hurts especially badly, i tried using an optimized mod, which is good, but unrolling would be even better. so question #1: is there a way to force unrolling?

`ntuple` with a `Val` argument will be completely unrolled at compile time. See Jeff’s trick with the `circularshift!` function at: [https://github.com/stevengj/18S096-iap17/blob/master/lecture3/Types%20and%20Dispatch.ipynb](https://github.com/stevengj/18S096-iap17/blob/master/lecture3/Types%20and%20Dispatch.ipynb)

---

<div class="post-metadata">

**Author:** ![pint](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pint/32/125_2.png) [@pint](https://discourse.julialang.org/u/pint)\
**Post date:** [February 5, 2017, 9:06am UTC](https://discourse.julialang.org/t/loop-unrolling-type-param-to-macro-generated-functions/1911/3 "2017-02-05T09:06:09Z")

</div>

> [@stevengj](#):
>
> ntuple with a Val argument will be completely unrolled at compile time

it appears to me that the same threshold applies to this case. see

`@code_native circularshiftN!(ones(100), Val{50}())`

the loop is not unrolled anymore. i think it gets more eagerly unrolled because the loop body is very simple. there must be some limitation on the “total number of things after unrolling”, possibly similar to the inlining logic. however, this limit is maybe applied before the massive optimization of llvm can take place?

---

<div class="post-metadata">

**Author:** ![Orbots](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/orbots/32/3392_2.png) [@Orbots](https://discourse.julialang.org/u/Orbots)\
**Post date:** [April 19, 2017, 11:52pm UTC](https://discourse.julialang.org/t/loop-unrolling-type-param-to-macro-generated-functions/1911/4 "2017-04-19T23:52:34Z")

</div>

A trick I recently used for loop unrolling with macros is to use nested macros.

```julia
macro unrollit( n, body )
...
end

macro dowithunroll(n)
  quote
    ...   
    @unrollit( n, <stuff to unroll> ) 
    ....
  end
end

function nknown()
   withunroll(31)
end

```

The top level function calls a macro with a constant known at parse-time. Then that macro can call a more generic unrolling macro with that constant. In my case `dowithunroll` was a function that I converted to a macro and block quoted.

Would be cleaner if I could keep `dowithunroll` as a function, since I’m only converting to a macro so I can pass this parse-time constant down to the generic unrolling macro.

---

<div class="post-metadata">

**Author:** ![cstjean](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cstjean/32/1444_2.png) [@cstjean](https://discourse.julialang.org/u/cstjean)\
**Post date:** [April 20, 2017, 2:05am UTC](https://discourse.julialang.org/t/loop-unrolling-type-param-to-macro-generated-functions/1911/5 "2017-04-20T02:05:17Z")

</div>

I wrote a macro that expands into the generated function: [Unrolled.jl](https://github.com/cstjean/Unrolled.jl) (not registered). Your example doesn’t loop over sequences, but over `1:N`, so either look at the source and adapt it, or you could implement a `CompileTimeUnitRange{A, B}()` type and use a helper function. Something like:

```julia
mul!{B, A}(r::Mod{B, A}, a::Mod{B, A}, b::Mod{B, A}) = mul!_helper(r, a, b, CompileTimeUnitRange{1, limbs(B)}(), A)
@unroll function mul!_helper(r, a, b, limbs, A)
  @inbounds begin
      @unroll for i in limbs
        r.n[i] = zero(UInt64)
      end
      @unroll for i in limbs
        @unroll for j in limbs    
          r.n[i] += a.n[mod(i-j, length(limbs)) + 1] * b.n[j] * (j > i ? UInt64(A) : UInt64(1))
        end
      end
    end
  r
end

```