Count memory accesses, not operations

Jon Bentley argues in Programming Pearls—a great book—that programmers should have a cost model of the machines they are working on. Recently I had two experiences that really made me feel that "memory is time," as Michal put it. First, I implemented LCS using a n by n matrix. It turned out that this computation took considerable time in the whole program even if it was called for strings of length 10 to 20 on average. Then Michal changed it to use two arrays of length n, and this reduced the running time of the LCS by 40%! The reason is probably that everything now fit in a fast cache. The second story is about strings. I wanted a data structure that allows fast concatenation and subrange extraction. So I tried to do it with persistent balanced trees, which should offer these two operations in logarithmic time. For strings of a few tens of millions of characters it was slower than just using arrays. And the most likely reason is that the space overhead was huge: One needs about 15 times more memory. A few hundred megabytes of memory compared to ten megabytes is a big deal with today's computers.

So I felt like doing a little experiment that I want to share. Copy and paste the following program.

#include <stdio.h>
#define M 100000000
int a[M];

int main() {
  int i; // a counter
  int c; // a number undertaking strange transformations

  i=M, c=71263;
  while (i--) {
    if (i&1) c=3*c+2; else --c;
    a[(c<0?-c:c)%M]=c;   // (*)
  }
  printf("%d\n", a[0]);
  printf("%d\n", c);
}

Compile with optimizations (e.g., gcc -O3 file.c) and time the run (e.g., time ./a.out). Now comment the line (*) and repeat. Now divide the first by the second time and remember the result, which says how slow memory accesses are compared to arithmetic operations.

Oh, I almost forgot! Here is an example of a cost model used in practice.