Loop unrolling

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Loop unrolling is a technique to speed up a program by enlarging what happens in each loop iteration. Instead of doing one item per pass, the loop does several items at once. This can reduce overhead from loop control, like pointer increments and end-of-loop tests, and can hide memory delays. It can be done by a programmer (static/manual unrolling) or automatically by an optimizing compiler. On modern processors, making the code bigger can sometimes slow things down because of worse cache usage, so unrolling is not always helpful.

Why use loop unrolling
- It reduces the amount of work spent on loop control (fewer tests and branches per item).
- It can minimize branch penalties and help prefetching.
- If each iteration’s work is independent, the added work can sometimes be done in parallel.
- It can be done at compile time or runtime (dynamic/unrolled sequences chosen by a JIT or optimiser).

What are the downsides
- Code size grows, which can hurt instruction caches and memory on small devices.
- Readability and maintainability suffer if you hand-unroll by hand.
- It can interfere with other optimizations, like inlining.
- More registers may be needed to hold intermediate values across unrolled iterations.
- More branches can increase misprediction risk on some patterns.

Static/manual loop unrolling
- A programmer rewrites the loop to perform several iterations per pass. For example, a loop that processes 100 items might handle 5 items per iteration.
- Pros: clear speedups when loop overhead is significant.
- Cons: code becomes longer and harder to maintain; handling leftovers when the total isn’t a multiple of the unroll factor can complicate things.

Early complexity and Duff’s device
- In simple cases, unrolling may just replicate code to avoid loop overhead. More complex patterns can become tricky; some techniques (like Duff’s device) mix unrolling with other tricks, but they can be hard to read and maintain.

Unrolling WHILE loops
- Similar idea: perform several loop bodies in one go, reducing the number of jumps back to the top. A well-structured unrolled version can cut the number of end-of-loop jumps significantly.

Dynamic unrolling
- If the amount of work isn’t known at compile time (for example, a run-time array size), a JIT or dynamic optimizer can choose a suitable unroll factor or generate a short, direct sequence for each element.
- Advantage: better adaptability to different input sizes and often smaller overall code growth, since the unrolled parts can be generated on the fly.

C and assembly-style examples (conceptual)
- Simple C example (dynamic/unrolled):
- Define a bunch size (e.g., 8).
- Process items in groups of eight inside a loop, then handle any remaining items with a switch or final steps.
- This reduces the number of loop iterations and can improve performance, especially when the processor and memory subsystem benefit from fewer loop tests.
- Assembly-oriented example (illustrative):
- In some cases, unrolling is done by explicitly loading multiple array elements, computing products, and accumulating results in a compact sequence.
- The idea is the same: do several elements per iteration to cut loop control overhead and memory latency, accepting larger code size.

C example of unrolling in practice
- A dynamic, runtime-style unrolling in C can use a fixed BUNCHSIZE and a loop that processes BUNCHSIZE items per iteration, then handles any leftover items with a small switch or final checks.
- The key concept: the compiler may replace pointer arithmetic with exact offsets to avoid extra calculations, but full unrolling works best when you can refer to elements by fixed indices.

C to MIPS example (high level)
- The same idea applies to translating loops to another architecture: you can unroll the inner loop by a factor (such as 4) so you load and multiply several pairs of elements in one pass, accumulate the result, then advance pointers by the total processed size.
- This reduces the number of iterations and can improve throughput if the target architecture benefits from fewer loop-control operations.

When to rely on unrolling
- Modern compilers often unroll loops automatically where it’s beneficial. Manual unrolling can still help in very hot code paths or on systems with specific memory or cache characteristics, but it’s not guaranteed to help.
- If the loop body is small and the iteration count is large, unrolling may help. If the loop has complex dependencies, nonlinear access patterns, or tight memory bandwidth limits, unrolling may hurt performance.

Bottom line
- Loop unrolling is a trade-off: you gain faster loops by reducing control overhead, but you pay with larger code size and potential cache or readability penalties.
- Use it when you have a clear, measurable performance benefit, and consider letting the compiler optimise automatically when possible. If you do manual unrolling, keep it well documented and handle leftovers cleanly to maintain correctness and readability.