Prof David May (End of Knuth) Examples

Prof David May pointed out in a seminar that given a 2-D array filled with the indentity function

int initialise(int dasize)
{
  for (j=0; j!=dasize; j++)
      for (i=0; i!=dasize; i++)
        adata[ i + (j*dasize)] = i;
}

The following three ways of iterating through it run at very different speeds:

Sumarray0:

int dm_sumarray0(int dasize)
  ...
  for (i=0; i!=dasize; i++)
    for (j=0; j!=dasize; j++)
      {
        sum += adata[ j + (i*dasize)]; 
      }

Sumarray1:

int dm_sumarray1(int dasize)
{
  ...
  for (i=0; i!=dasize; i++)
    for (j=0; j!=dasize; j++)
      {
        sum += adata[ i + (j*dasize)];
      }
  return sum;
}

Sumarray2:

int dm_sumarray2(int dasize)
  ...
  for (j=0; j!=dasize; j++)
    {
      i=0;
      while (i!=dasize)
        {
          int v = adata[ i + (j*dasize)]; 
          sum += v;
          i = v+1; // Data-dependent loop - cannot unroll.  
        }
    }
  return sum;
}

And hence the great works of D. Knuth that exploit the wonders of the array for imperative programming (and the associated idea for cost of an algorithm) all go out the window.

Try it on prazor (see david-may-examples folder) and a real computer and experience 3 different orders of magnitude in terms of run time!