Course contentsShow
← Computer Science
Lesson 2068 of 2,87246. Compilation and InterpretationFree lesson

Loop Unrolling

Replicating loop bodies to reduce loop overhead and enable further optimizations.

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.