Developer Guide · UnrolledUtilities.jl

How to Unroll

There are two general ways to implement loop unrolling in Julia—recursively splatting iterator contents and manually constructing unrolled expressions. For example, a recursively unrolled version of the foreach function is

unrolled_foreach(f, itr) = _unrolled_foreach(f, itr...)
_unrolled_foreach(f) = nothing
_unrolled_foreach(f, item, items...) = (f(item); _unrolled_foreach(f, items...))

In contrast, a manually unrolled implementation of this function looks like

unrolled_foreach(f, itr) = _unrolled_foreach(Val(length(itr)), f, itr)
@generated _unrolled_foreach(::Val{N}, f, itr) where {N} =
    Expr(:block, (:(f(generic_getindex(itr, $n))) for n in 1:N)..., nothing)

Julia's compiler can only pass up to 32 values through function arguments without allocating heap memory, so recursive unrolling is not type-stable for iterators with lengths greater than 32. Generated functions have no such limit, but they take more time and memory to compile than hard-coded functions, and for short iterators this cost exceeds that of recursive inlining. Hard-coded methods for the shortest iterators keep the latency of the manually unrolled implementation low:

_unrolled_foreach(::Val{0}, f, itr) = nothing
_unrolled_foreach(::Val{1}, f, itr) = (f(generic_getindex(itr, 1)); nothing)
_unrolled_foreach(::Val{2}, f, itr) =
    (f(generic_getindex(itr, 1)); f(generic_getindex(itr, 2)); nothing)
_unrolled_foreach(::Val{3}, f, itr) =
    (f(generic_getindex(itr, 1)); f(generic_getindex(itr, 2)); f(generic_getindex(itr, 3)); nothing)

With this modification, manual unrolling does not exceed the compilation requirements of recursive unrolling across a wide range of use cases. Since it also avoids type instabilities for arbitrarily large iterators, a combination of hard-coded and generated functions with manual unrolling serves as the basis of all unrolled functions defined in this package. Similarly, the ntuple(f, ::Val{N}) function in Base uses this strategy to implement loop unrolling.

For benchmarks that compare these two implementations, see Manual vs. Recursive Unrolling.

Interface API

The functions exported by this package can be used with any statically sized iterators, as long as those iterators make appropriate use of the following interface:

UnrolledUtilities.generic_getindex — Function

generic_getindex(itr, n)

Return the n-th item of itr. Equivalent to getindex(itr, n), with added methods for the lazy iterators Base.Generator, Iterators.Reverse, Iterators.Enumerate, and Iterators.Zip. Statically sized iterators that do not support getindex can add methods to this function instead.

source

UnrolledUtilities.output_type_for_promotion — Function

output_type_for_promotion(itr)

Return the type of container that unrolled functions construct for the input itr: a Type, a ConditionalOutputType when the container type depends on the item type, or NoOutputType() when itr has no container type of its own. Defaults to Tuple, and lazy iterators from Base forward to the iterators they wrap.

source

UnrolledUtilities.AmbiguousOutputType — Type

AmbiguousOutputType

Abstract supertype for the results of output_type_for_promotion that are not Types: NoOutputType and ConditionalOutputType.

source

UnrolledUtilities.NoOutputType — Type

NoOutputType()

The AmbiguousOutputType of iterators with no container type of their own, such as StaticOneTo. It is promoted to any other output type, and it becomes Tuple on its own.

source

UnrolledUtilities.ConditionalOutputType — Type

ConditionalOutputType(allowed_item_type, output_type, [fallback_type])

An AmbiguousOutputType that resolves to output_type when the item type of the output is a subtype of allowed_item_type, and to fallback_type (Tuple by default) otherwise. StaticBitVector uses it to fall back to Tuple for items that are not Bools.

source

UnrolledUtilities.output_promote_rule — Function

output_promote_rule(output_type1, output_type2)

Return the output type for iterators whose output_type_for_promotions are output_type1 and output_type2, or Union{} when the pair has no rule. Only one direction needs a method; when both directions return Union{}, the output type is Tuple.

By default, every type takes precedence over NoOutputType(), and the conditional part of a ConditionalOutputType is kept while its fallback type is promoted.

source

UnrolledUtilities.constructor_from_tuple — Function

constructor_from_tuple(output_type)

Return a function that constructs a container of type output_type from a Tuple of items. Defaults to identity, which suits Tuples and containers that wrap them, such as SVectors. For NamedTuple types, the function throws an ArgumentError when the number of items differs from the number of field names.

Container types that cannot be constructed from a Tuple efficiently can add methods to the *_into functions listed in the Developer Guide instead.

How to Use the Interface

To unroll over a statically sized iterator of some user-defined type T, follow these steps:

Add a method for getindex(::T, n), or for generic_getindex(::T, n) if getindex should not be defined for iterators of type T
If every unrolled function that needs to construct an iterator when given an iterator of type T can return a Tuple instead, stop here
Otherwise, to return a non-Tuple iterator whenever it is efficient to do so, follow these steps:
- Add a method for output_type_for_promotion(::T) = O, where O can be T, a supertype of T, some other Type, or an AmbiguousOutputType
- If an iterator whose output type is O can be used together with an iterator whose output type is O′, add a method for output_promote_rule(O, O′)
- If O is a NoOutputType, stop here
- Otherwise, to handle the unambiguous output type U that underlies O (where U is equivalent to O unless O is a ConditionalOutputType), follow these steps:
  - If an iterator of type U can be efficiently constructed from a Tuple, add a method for constructor_from_tuple(U)
  - Otherwise, for each of the following functions, add a method if it can be implemented to construct an iterator of type U without first storing the iterator's contents in a Tuple:
    - empty_output(U)
    - unrolled_push_into(U, itr, item)
    - unrolled_append_into(U, itr1, itr2)
    - unrolled_take_into(U, itr, val_N)
    - unrolled_drop_into(U, itr, val_N)
    - unrolled_setindex_into(U, itr, item, val_N)
    - unrolled_insert_into(U, itr, item, val_N)
    - unrolled_map_into(U, f, itr)
    - unrolled_accumulate_into(U, op, itr, init)

Note

When a relevant method for the interface is not defined, unrolled functions will typically fall back to using Tuples instead of other iterator types.