C言語: 配列のサイズによって、最適なアルゴリズムが変化する例

というのを試してみた。パラメータは、環境によって異なると思われる。
-DT1をつけてコンパイルすると配列サイズが100x100になり、つけなければ400x400になる。（比較しやすいように適当にスケールを調整している）

$ gcc -DT1 -O3 test.c

$ ./a.exe 
1: 5507
2: 3865

$ gcc -O3 test.c

$ ./a.exe 
1: 2072
2: 4726

以下、ソースコード。

#ifdef T1
#define N 100
#define C 300

#else
#define N 400
#define C 1

#endif

#include <stdio.h>
#include <stdlib.h>
#include <sys/times.h>

typedef void (*myfunc)(double[N][N], double[N][N], double[N][N]);

double x[N][N], y[N][N], z[N][N];
struct tms t;

void test (int n, myfunc f)
{
  int i,j,k;
  time_t t0, t1;
  for (i=0; i<N; ++i)
    for (j=0; j<N; ++j){
      x[i][j] = 0.0;
	  y[i][j] = i;
	  z[i][j] = j;
    }

  t0 = times(&t);
  for (k=0; k<C; ++k)
    f(x,y,z);
  t1 = times(&t);
  printf("%d: %ld\n", n, t1 - t0);
}

void f1 (double x[N][N], double y[N][N], double z[N][N])
{
  int i,j,k;
  for (i=0; i<N; ++i)
    for (j=0; j<N; ++j)
      for (k=0; k<N; ++k)
        x[i][j] = x[i][j] + y[i][k] * z[k][j];
}

void f2 (double x[N][N], double y[N][N], double z[N][N])
{
  int i,j,k;
  for (k=0; k<N; ++k)
    for (j=0; j<N; ++j)
      for (i=0; i<N; ++i)
        x[i][j] = x[i][j] + y[i][k] * z[k][j];
}

int main (int argc, char **argv)
{
  test(1, f1);
  test(2, f2);
}