# Optimizing Immutable and Purity

December 20, 2008

In earlier installments, I talked about immutable data and pure functions offering opportunities for better compiler optimization. I've been working on taking advantage of these in the D programming language compiler, and so can show what these are.

To recap, immutable data is data that, once set, cannot be modified. It cannot be modified by the current thread, any other thread, or any other reference to that same data. As far as the program logic is concerned, it is engraved in stone. Immutability of data is also transitive, meaning that anything reachable through that immutable data by following pointers, arrays, or other references, is also immutable. Imagine the data in a program as a large graph with values at nodes and directed edges drawn by following pointers; then, immutable data forms subgraphs of that graph that have an interesting property. You can start from a mutable data node and get to immutable data; but once you're in immutable-land, there's no way to get back to a mutable node.

A pure function is one that has no side effects, and depends only upon its input parameters. That means it cannot read any mutable state that is not local to the pure function, it cannot write to any global state, and it cannot transitively modify any of its parameters (transitive meaning anything reachable through its parameters). A pure function's only effect is its return value.

For these examples, I'll use the D programming language compiler that is currently under development. I encourage you to try the equivalent code out in your favorite language and compiler, and compare. (One of the reasons I'm a compiler nerd is I think it's fun to examine the assembler output of a compiler, like a motorhead likes to tear an engine apart.)

int bar(int);

int foo(int i)
{
return bar(i) + bar(i);
}

(On the face of it, this looks like simply bad code that could and should be easily changed by hand into the sensible 2 * bar(i). Let's not forget, however, that such code is often yielded by other optimization passes that progressively inline and fold various other functions and code blocks, exposing redundancy to later steps.)

Compile it and look at the assembler output with:

dmd -c -O test.d
obj2asm test.obj >log

and the assembler output for the function looks like (I editted it a bit for readability, and added comments):

push    EAX  ; save argument i on stack
call    bar    ; call bar(i)
push    EAX  ; save return value of bar(i) on stack
sub     ESP,4   ; not really needed
mov     EAX,8[ESP]   ; reload argument i to pass to bar()
call    bar    ; call bar(i)
add     ESP,4   ; undo previous unneeded op
mov     ECX,EAX   ; put in ECX result of second bar(i)
pop     EAX    ; put in EAX the result of the first bar(i) call
pop     ECX    ; clean off stack

Why is bar(i) called twice? Because there's no way for the compiler to know what bar(i) is doing - it may be incrementing a global counter or printing stuff to a log file. So it must assume the worst and call it twice. But what if bar is pure?

pure int bar(int);

int foo(int i)
{
return bar(i) + bar(i);
}

Now the assembler output is:

push    EAX    ; save argument i on stack
call    bar    ; call bar(i)
pop     ECX    ; clean stack

bar(i) is called only once, and since it is a pure function, and i didn't change, it therefore must return the same value should it be called again, and so the second call is unnecessary. Notice that the compiler did not have access to bar's body. The pure declaration was all the compiler needed to optimize the second call away. At the definition of bar, the compiler will make sure that bar doth chastely fulfill the purity promise.

(And yes, if the optimizer was as good as my 1337 hand coding assembler skillz, I'd write it as:

call    bar  ; call bar(i)

but it's hard to get every trick I know wired into the compiler. I've never yet met a compiler I couldn't beat with carefully hand-crafted assembler.)

Now for immutability:

int foo(int* a, int* b)
{   int i = *a * *b;
int j = *a * *b;
return i + j;
}

and:

push    EAX
mov     ECX,8[ESP]
mov     EAX,[ECX]   ; EAX = *a
mov     EDX,[ESP]
imul    EAX,[EDX]   ; EAX *= *b
pop     ECX
ret     4

Wait a minute. Although (*a * *b) appears twice, the compiler only computed it once and double the result. This is called common subexpression elimination. So far, so good. Let's now rewrite our example as:

int bar();

int foo(int* a, int* b)
{   int i = *a * *b;
bar();
int j = *a * *b;
return i + j;
}

sub     ESP,0Ch
mov     ECX,010h[ESP]
push    EBX
mov     8[ESP],EAX
mov     EDX,[ECX]
imul    EDX,[EAX]
mov     0Ch[ESP],EDX
call    bar
mov     EAX,014h[ESP]
mov     EAX,[EAX]
mov     EBX,8[ESP]
imul    EAX,[EBX]
pop     EBX
ret     4

That sure threw a monkey wrench into the results. (*a * *b) is no longer a common subexpression, and gets recomputed. This is because the optimizer has no idea what bar() does - it could modify whatever it is that a and b point to, so it must play it safe and recompute them. But if a and b pointed to immutable data, we'd know that bar() could not affect them:

int bar();

int foo(immutable int* a, immutable int* b)
{   int i = *a * *b;
bar();
int j = *a * *b;
return i + j;
}

sub     ESP,0Ch
mov     ECX,010h[ESP]
mov     EDX,[ECX]
push    EBX
imul    EDX,[EAX]
mov     0Ch[ESP],EDX
mov     8[ESP],EDX
call    bar
mov     EAX,8[ESP]
mov     EBX,0Ch[ESP]
lea     EAX,[EBX][EAX]
pop     EBX
ret     4

and so the second multiply instruction has been elided, because no matter what bar did, it cannot alter immutable data. But wait, what if a and b were not immutable, but bar was pure?

pure int bar();

int foo(int* a, int* b)
{   int i = *a * *b;
bar();
int j = *a * *b;
return i + j;
}

push    EAX
mov     ECX,8[ESP]
mov     EAX,[ECX]
mov     EDX,[ESP]
imul    EAX,[EDX]
pop     ECX
ret     4

In this case the optimizer outdid itself by completely vanishing the call to bar(), AND then nicely squished the two multiplications down to one. This behavior is correct because since bar() has no side effects and the result is discarded, the compiler can discard the entire call. By the very definition of purity, you won't be able to to ever notice the absent call unless you are willing to place a precise thermal probe on the processor and notice a drop in the heat produced.

Now, on to yet another optimization allowed by the immutable/pure duo: code motion across pure calls. Let's not discard the result of bar():

pure int bar();

int foo(int* a, int* b)
{   int i = *a * *b;
int k = bar();
int j = k + *a * *b;
return i + j;
}

sub     ESP,0Ch
mov     ECX,010h[ESP]
mov     EDX,[ECX]
push    EBX
imul    EDX,[EAX]
mov     0Ch[ESP],EDX
mov     8[ESP],EDX
call    bar
mov     EBX,8[ESP]
lea     EAX,[EAX][EBX]
pop     EBX
ret     4

We're back to only one multiply. This example shows how pure functions affect the optimizations of the code that surrounds calls to them.

Despite all the gains in CPU technology, one rule that is fairly consistent is that fewer instructions execute faster. Purity and immutability have resulted in fewer instructions, so let's do a little benchmark.

int bar(int) { return 1; }

pure int purebar(int) { return 1; }

int foo1(int i)
{
return bar(i) + bar(i);
}

int foo2(int i)
{
return purebar(i) + purebar(i);
}

int foo3(int* a, int* b)
{   int i = *a * *b;
int j = *a * *b;
return i + j;
}

int foo4(int* a, int* b)
{   int i = *a * *b;
bar(1);
int j = *a * *b;
return i + j;
}

int foo5(immutable int* a, immutable int* b)
{   int i = *a * *b;
bar(1);
int j = *a * *b;
return i + j;
}

int foo6(int* a, int* b)
{   int i = *a * *b;
purebar(1);
int j = *a * *b;
return i + j;
}

int foo7(int* a, int* b)
{   int i = *a * *b;
int k = bar(1);
int j = k + *a * *b;
return i + j;
}

int foo8(int* a, int* b)
{   int i = *a * *b;
int k = purebar(1);
int j = k + *a * *b;
return i + j;
}

void main()
{   int a,b;
immutable int c = 7;
immutable int d = 8;

foreach(i; 0 .. 500_000_000)
{
// foo1(1);
// foo2(1);
// foo3(&a, &b);
// foo4(&a, &b);
// foo5(&c, &d);
// foo6(&a, &b);
// foo7(&a, &b);
// foo8(&a, &b);
}
}

We compile with full optimization, except inlining is turned off so the optimizer will not take advantage of the trivial content of bar. Each call to foo in turn is uncommented, and the time measured for that program to run:

foo1  8.39
foo2  5.73
foo3  4.47
foo4  8.35
foo5  9.12 !!
foo6  4.46
foo7  8.33
foo8  7.68

Things turned out as expected, except foo5 is slower than foo4, despite doing one less multiply. Turns out that a multiply is less expensive than caching a value on the stack for the particular computer I used. (This just goes to show what a tricky business optimization can be.) If it was more than just a multiply saved, it should be faster.

On a real program, how much faster is my code going to get, if I maximize use of pure functions and immutable data? I don't know. I don't have any experience with it on a large program. I doubt it will prove to be any barn-burner optimization, but compiler optimizers these days have gotten so good that there isn't much gain left to be gotten, and every bit helps.

One nice thing about automated optimizations vs. hand-written ones is that the compiler, just like the terminator on a mission, will never, ever, overlook applying them. That's in contrast to you and me, who in first approximation are less pedantic and do have a life. So once you've given the compiler the immutable and pure hints, it will always and everywhere try to take advantage of them.

I also wouldn't say these optimizations are the primary motivation for using immutability and purity, but they are a nice dividend.

Thanks to Andrei Alexandrescu, David Held, Bartosz Milewski, and Jason House for many helpful suggestions on this. Any remaining mistakes are solely my fault.

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>