Unrolled.jl

Unrolling loops at compile-time
Author cstjean
Category Algorithms
Github
Popularity
42 Stars
Updated Last
1 Year Ago
Started In
March 2017

Unrolled

Build Status

Coverage Status

codecov.io

Unrolled.jl provides functions to unroll loops on sequences whose length is known at compile-time (mostly Tuple and StaticArrays). This can significantly improve performance and type-stability.

The @unroll macro

julia> using Unrolled

julia> @unroll function my_sum(seq)
       	   # More on why we need @unroll twice later.
	   total = zero(eltype(seq))
           @unroll for x in seq
               total += x
           end
           return total
       end
my_sum_unrolled_expansion_ (generic function with 1 method)

julia> my_sum((1, 2, 3))
6

To see what code will be executed,

# Tuples are unrolled
julia> @code_unrolled my_sum((1,2,3))
quote  
    total = zero(eltype(seq))
    begin  
        let x = seq[1]
            total += x
        end
        let x = seq[2]
            total += x
        end
        let x = seq[3]
            total += x
        end
    end
    return total
end

# But not vectors, since their length is not part of Vector{Int}
julia> @code_unrolled my_sum([1,2,3])
quote
    total = zero(eltype(seq))
    for x = seq
        total += x
    end
    return total
end

All types for which length is implemented will be unrolled (this includes the fixed-size vectors from StaticArrays.jl and FixedSizeArrays.jl)

Usage

@unroll works by generating (at compile-time) a separate function for each type combination. This is why we need (at least) two @unroll:

  • One in front of the function definition
  • One in front of each for loop to be unrolled

@unroll can only unroll loops over the arguments of the function. For instance, this is an error:

# Sum every number in seq except the last one
@unroll function my_sum_but_last(seq)
    total = zero(eltype(seq))
    @unroll for x in seq[1:end-1]   # Bad!
        total += x
    end
    return total
end

An easy work-around is to use a helper function

@unroll function _do_sum(sub_seq) # helper for my_sum_but_last
    total = zero(eltype(sub_seq))
    @unroll for x in sub_seq
        total += x
    end
    return total
end

# Sum every number in seq except the last one
my_sum_but_last(seq) = _do_sum(seq[1:end-1])

my_sum_but_last((1,20,3))    # 21

As a special case, @unroll also supports iteration over 1:some_argument

@unroll function foo(tup)
    @unroll for x in 1:length(tup)
        println(x)
    end
end
foo((:a, :b, :c))
> 1
> 2
> 3

Unrolled functions

Unrolled.jl also provides the following unrolled functions, defined on Tuples only.

unrolled_map, unrolled_reduce, unrolled_in, unrolled_any, unrolled_all, unrolled_foreach

and

unrolled_filter, unrolled_intersect, unrolled_union, unrolled_setdiff

The functions in this second group will only perform well when the computations can be performed entirely at compile-time (using the types). For example, unrolled_filter(x->isa(x, Int), some_tuple).

In this other example, unrolled_filter is compiled to a constant:

using Unrolled, Base.Test

@generated positive{N}(::Val{N}) = N > 0
@inferred unrolled_filter(positive, (Val{1}(), Val{3}(), Val{-1}(), Val{5}()))

Note on Val

In my experience, Val objects are more type-stable than Val types. Favor Val{:x}() over Val{:x}.

Required Packages

Used By Packages