Feel the cache size: a definitive experiment

Long gone the wonderful era of 640 kilobytes of memory and 8 to 12 MHz of clock speed, which "ought to be enough for anybody". Though Mr.Gates never said that, I still think that's a fair amount of memory and good speed for a lot of things. I wouldn't have said that if I hadn't worked in a fully-blown windowed desktop publishing system called Quark XPress on a Macintosh LC, which had, I think, some 2 MB of RAM and ran at 16MHz, back in 1991. Time has passed, the download size of the latest Quark XPress is about half a gig now (as opposed to the prehistoric version that fit a few diskettes at the time), we have gigabytes of memory and we run at staggering gigahertz speeds, and yet the same program with basically same functionality (oh, okay, plus-minus) is slower on a system that's a thousand times more powerful! Or take Acrobat Reader that has grown 15 times in size, has become damning slow and resource-hungry across versions 3.0 through 9.0 while doing same old thing - rendering PostScript programs.

Shouldn't 2 gigabytes/2 gigahertz really be enough for almost anything we can think of today, except maybe some heavy real-world 3D simulations, including games? If you are not going to calculate the state of all atoms in the Solar system in real time, 2/2 ought to be enough for you. Um, if you write your code carefully and thoughtfully. I don't think binaries I produced ever reached even a few megabytes in size, although there were some fairly complicated projects I worked on with hundreds of thousands of LOC. Hundreds of thousands of lines, mind you, usually means a gigantic project on the brink of unmaintainability.

Unfortunately the reason bloatware exists is not only because of the fallacy "don't optimize your code, because Mr.Moore is going to do that for you soon". One other reason that becomes apparent if you look at bloatware closely, is that large part of it is commercial software. Commercial vendors want you to feel comfortable about the money you pay. Because otherwise, just picture for a moment that you paid $500 of your hard-earned money for something 500 KB in size that downloads faster than you can blink. Doesn't this picture feel somewhat wrong?

I can't think of some bosses, of course, sitting there at Adobe, Microsoft and Sun, forcing employees to deliver bigger binaries. The mechanism is a bit more subtle: it is, I think, a whole culture of languages and platforms that unobtrusively force developers to produce monster code. Yes, that's Java and C# with their verbosity coupled with everything-is-an-object philosophy, as well as the C++ world, where nothing practically stops you from reckless use of templates - possibly the bloater number one in the neighbourhood.

I'm just wondering when (and if) natural selection can finally come into play in the software industry and wipe out the dinosaur herd in favour of smaller, quicker and smarter species. There are some barely noticable signs this is happening now (startups), but clearly, it's too early to trumpet Nature's victory.

***

But enough of emotions. I'm going to carry out an experiment to prove that we still live in the world of kilo and mega rather than giga, at least memory-wise. Why? The CPU cache.

It shouldn't come as a surprise to you that there's CPU cache in your machine: usually a very fast memory chip from kilobytes to megabytes in size, designed to make memory operations faster. Unfortunately it comes at a price: the CPU cache is organized in small chunks called cache lines, typically 64 bytes in size, that are read from and written to the main memory at once, as a whole. Because every cache miss triggers a memory read of a whole 64-byte chunk, while all the processor requested was, say, 4 bytes, it means in certain circumstances caching makes things worse than if there was no cache at all.

So what I'm going to do is, build a program that can do something - actually same thing at every run, using code segments of varying sizes. We will change the code block from a few bytes to tens of megabytes and measure the difference in running time. Would it be fair? I think so, yes. We are not going to interpret the results though, as in how and why, but rather how much, that is, this is going to be a purely quantitative experiment.

The idea is this: I generate a C program with exactly one million functions, each returning some number:

int f0() { return 1; }
int f1() { return 2; }
int f2() { return 3; }
int f3() { return 4; }
int f4() { return 5; }
...

and so on, to one million. Each function translates to 11 bytes of code:

_f0:
    pushq %rbp
    movq %rsp, %rbp
    movl %edi, -4(%rbp)
    movl -4(%rbp), %eax
    addl $1, %eax
    leave
    ret

I also generate a table of pointers to these functions so that we can pick them randomly in a tight loop.

Poor, poor GCC, it took almost 20 minutes to compile the file, even though I turned off optimizations. Anyway. The main module looks like this:

#include <stdlib.h>
#include <time.h>
#include <stdio.h>

#include "tab.h"

#define PRIME 99971
#define LOOP 1000000000


void run(int max)
{
   time_t begin = time(NULL);
   srand(PRIME);

   int i;
   for (i = 0; i < LOOP; i++)
       func_table[rand() % max]();

   int diff = (int)(time(NULL) - begin);
   printf("code size: %ld  time: %d secs\n",
       func_table[max] - func_table[0], diff);
}


int main()
{
   printf("Running...\n");
   run(1);
   run(10);
   run(100);
   run(1000);
   run(10000);
   run(100000);
   run(1000000);
   return 0;
}

As you can see, at every run we do equivalent job (same number of iterations, identical functions called), except bigger and bigger chunks of the code segment are involved. The results? Voila:

code size: 11  time: 12 secs
code size: 110  time: 22 secs
code size: 1100  time: 29 secs
code size: 110000  time: 36 secs
code size: 1100000  time: 45 secs
code size: 11000000  time: 174 secs

Notice the spike on the last line? That's a transition from 1MB to 10MB, whcih crosses the actual size of my L2 cache I have on my machine, and it's 2MB.

Anyway. The conclusion is, performing the same job using different binary sizes can be up to 15 times slower. That's it, and I'll leave you there deciding whether you should write simple, succinct, beautiful and fast code, or you should impress the rest of the world with "methodologies" you use and the monstrosity of your project. Sometimes size translates to money, true, but the opposite is your satisfaction with the job done. Haven't you decided yet?

Update: A lot of people pointed out that the code used in the experiment does not represent typical real-world situations. This is true, but let's say the impact in your case is 20% rather than 15 times. If it's a virtual machine for your language, for example, then optimization would be something you'd struggle for, as 20% for a runtime environment is a huge gain.