My favorite compiler example to show to folks.

One of my favorite compiler example to show to folks who do not interact with compilers that often is the sum(1..N). The idea is, hey you, sum the number 1 to N, i.e. 1+2+3+4+...+N. Pretty simple.

This is how it looks in C++. ignore the int instead of size_t.

int sum(int N) {
    int result = 0;
    for(int i = 1; i <= N; i++) {
        result += i;
    }
    return result;
}

We will use clang and btw feel free to use godbolt for this.

Clang generates something like this:

sum(int):
    ; load some variables
Label_1:
    ; if i > N
    jmp Label_2
    ; else accumulate result
    jmp Label_1
Label_2:
    ; populate eax
    ret

Looks simple enough, right. Till you turn on optimization flag. Even -O1.

Lets look at code with it.

sum(int):
    test    edi, edi
    jle     .LBB0_1
    lea     eax, [rdi - 1]
    lea     ecx, [rdi - 2]
    imul    rcx, rax
    shr     rcx
    lea     eax, [rcx + 2*rdi]
    dec     eax
    ret
.LBB0_1:
    xor     eax, eax
    ret

Wait a minute, there is no loop. There is a jump, but thats an exit jump, not a loop jump. So what happened here? Lets look it line by line.

First line: test edi, edi.

x86 linux calling convention is we pass first 6 arguments in 6 registers, not going through that, the first arg is in rdi. But thats 64 bit register. edi is lower 32 bits, which is what we want. We basically check for N <= 0. If its <= 0 we peace out of the function.

lea eax, [rdi - 1] means eax = N - 1.

lea ecx, [rdi - 2] means ecx = N - 2

imul rcx, rax is rcx = (N - 1) * (N - 2) which means rcx = N^2 - 3N + 2

We are way off from a loop with this, but our journey continues.

shr rcx is fancy way of dividing it by 2. So rcx = (N^2 - 3N + 2) / 2

lea eax, [rcx + 2*rdi] means eax = ((N^2 - 3N + 2) / 2) + (2 * N).

I hate markdown rendering equations and I'll learn and setup LaTeX someday, but that day isn't today.

So lets simplify this further so that its easier to read.

eax = (N^2 + N + 2) / 2.

dec eax is simply eax -= 1.

so eax is now ((N^2 + N + 2) / 2) - 1. (N^2 + N) / 2. So thats now N(N+1) / 2.

If you remember your high school, you might recall this formula, of summing 1 to N. Basically clang ends up using that formula instead of loop and you get the same result.

We wrote a O(N) function and compiler converted it into a O(1).

Beautiful right?