The Cost of Going Around Again

A loop is not just its body. Every iteration also pays for the loop's machinery: incrementing the counter, comparing it against the limit, and jumping back to the top. For a loop with a fat body that overhead is lost in the noise. For a loop with a tiny body, the bookkeeping can rival the actual work.

Loop unrolling attacks this by doing more than one iteration's worth of work per pass. If the optimizer handles two iterations each time around, it only pays the counter-and-compare-and-jump cost half as often. This lesson shows what that looks like in a real listing.

A Simple Accumulating Loop

Here is a function that sums the integers from 0 up to n - 1:

int sumTo(int n)
{
    int total{0};
    for (int i{0}; i < n; ++i)
    {
        total += i;
    }
    return total;
}

The body is one addition. The machinery, ++i, i < n, and the conditional jump, is comparable in size to the body itself. That is exactly the situation where unrolling pays off.

The Unoptimized Loop

At -O0 the loop is translated literally, one iteration per trip:

sumTo(int):
	push	rbp
	mov	rbp, rsp
	mov	DWORD PTR -20[rbp], edi
	mov	DWORD PTR -4[rbp], 0
	mov	DWORD PTR -8[rbp], 0
	jmp	.L2
.L3:
	mov	eax, DWORD PTR -8[rbp]
	add	DWORD PTR -4[rbp], eax
	add	DWORD PTR -8[rbp], 1
.L2:
	mov	eax, DWORD PTR -8[rbp]
	cmp	eax, DWORD PTR -20[rbp]
	jl	.L3
	mov	eax, DWORD PTR -4[rbp]
	pop	rbp
	ret

This is the classic loop shape from Chapter 3. .L3 is the body (total += i, then ++i), and .L2 is the test (i < n, jump back if so). Every single iteration runs that whole test-and-branch. The counter i lives at -8[rbp] and total at -4[rbp], reloaded and rewritten every time.

The Unrolled Loop

Now -O2:

sumTo(int):
	test	edi, edi
	jle	.L4
	xor	eax, eax
	xor	edx, edx
	test	dil, 1
	je	.L3
	mov	eax, 1
	cmp	edi, 1
	je	.L1
.L3:
	lea	edx, 1[rdx+rax*2]
	add	eax, 2
	cmp	edi, eax
	jne	.L3
.L1:
	mov	eax, edx
	ret
.L4:
	xor	edx, edx
	mov	eax, edx
	ret

This is denser, so let us read it in pieces. First, everything is in registers now: the running total is in edx, the counter in eax. No stack at all.

The heart of it is the loop at .L3:

.L3:
	lea	edx, 1[rdx+rax*2]
	add	eax, 2
	cmp	edi, eax
	jne	.L3

Look at add eax, 2: the counter advances by two each pass, not one. The single lea edx, 1[rdx+rax*2] adds both of the next two values to the running total in one instruction (rax*2 + 1 is the sum of the current counter value and the next one). So each trip through .L3 accounts for two iterations of your original loop, but pays the cmp/jne machinery only once. That is the unroll: the per-iteration overhead has been cut roughly in half.

The Remainder Problem

If the loop does two iterations at a time, what happens when n is odd? You cannot do "half a pair". This is why unrolled loops grow extra code around the main loop, and it explains the instructions before .L3:

	test	dil, 1
	je	.L3
	mov	eax, 1
	cmp	edi, 1
	je	.L1

test dil, 1 checks whether n is odd (the low bit of n). If it is, the code handles a single leftover iteration first (setting the counter to 1 and adding the value 0), so that the remaining count is even and the two-at-a-time loop can run cleanly. This bit of setup is called the loop peeling or remainder handling, and seeing it is a reliable sign that a loop has been unrolled: a tidy main loop, plus a little extra code to deal with counts that do not divide evenly.

The test edi, edi / jle .L4 at the very top is a separate guard: if n <= 0 the loop runs zero times and the function returns 0 immediately via .L4.

Why the Optimizer Bothers

Unrolling trades a little code size for speed. More instructions in the binary, but fewer branches executed and more independent operations the CPU can work on at once. On modern processors, back-to-back independent additions can overlap in the pipeline, so cutting the branch overhead and exposing parallel work both help.

Unrolling is also a stepping stone to the next lesson. Once the optimizer is processing several iterations together, it is a short hop to processing them with a single instruction that operates on multiple values at once. That is vectorisation, and it builds directly on the idea you have just seen.

Reading the Clue

When you see a -O2 loop whose counter advances by 2, 4, or 8 instead of 1, or a loop preceded by a chunk of setup that handles "leftover" iterations, you are looking at an unrolled loop. Do not let the extra code fool you into thinking the function is more complicated than your source: the main loop is doing several of your iterations per pass, and the surrounding code is just cleaning up the remainder.

Key Takeaways

  • Every loop iteration pays for machinery: incrementing, comparing, and jumping. For tiny bodies this overhead is significant.
  • Loop unrolling does several iterations' work per pass, paying the machinery cost less often.
  • In sumTo at -O2, the counter advances by 2 (add eax, 2) and one lea folds two values into the running total per pass.
  • Unrolling requires remainder handling (loop peeling) for counts that do not divide evenly, which shows up as extra setup code around the main loop.
  • A counter that steps by more than 1, or a loop preceded by leftover-handling code, is a reliable sign of unrolling.
  • Unrolling trades code size for speed and sets the stage for vectorisation.