Loop Unrolling
What you'll learn: How compilers replicate loop bodies to reduce overhead and unlock additional optimizations.
The Core Idea
Loop unrolling is an optimization technique where the compiler duplicates the body of a loop multiple times, reducing the number of iterations needed. Instead of executing a loop 100 times with one operation per iteration, you might execute it 25 times with four operations per iteration.
Think of it like packing boxes: instead of making 100 trips carrying one item each time, you carry four items per trip and only make 25 trips. You've reduced the "overhead" of walking back and forth.
Why Unroll Loops?
Every loop iteration has overhead:
- Testing the loop condition
- Incrementing the counter
- Branching back to the loop start
By unrolling, you execute fewer iterations, meaning less overhead. Additionally, unrolling exposes more instructions to the optimizer, enabling techniques like constant folding, dead code elimination, and better instruction selection.
Example Transformation
Original loop:
for i = 0 to 3:
a[i] = a[i] + 1
Unrolled by factor of 2:
for i = 0 to 1:
a[2*i] = a[2*i] + 1
a[2*i+1] = a[2*i+1] + 1
Or fully unrolled:
a[0] = a[0] + 1
a[1] = a[1] + 1
a[2] = a[2] + 1
a[3] = a[3] + 1
The Tradeoff
Unrolling increases code size. More instructions mean more memory for the program and potential cache pressure. Compilers must balance the performance gain against the size increase, often unrolling only performance-critical loops.
Key Takeaway: Loop unrolling replicates loop bodies to reduce branching overhead and iteration count, enabling further optimizations at the cost of increased code size.