C言語の問題

README.md

問題

以下の2つのソースコード test1.c と test2.c はどちらのほうが速いか、コードを見て予想せよ。

ただし、条件は以下のようにする:

gcc -O2 test1.c -o test1
gcc -O2 test2.c -o test2
time ./test1
time ./test2

補足

この問題はコンパイラの最適化に関する問題であるため、バージョンによっては作題意図通りの結果にならないかもしれない。作者は以下のバージョンで確認した。

$ gcc --version
gcc (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

test1.c

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

void foo(int a[], int b[]) {
  int i, j;
  for(i = 1; i < 1000; ++i) {
    for(j = 0; j < 1000; ++j) {
      b[i-1] = a[i-1] * 2;
      b[i] = a[i] * 2;
    }
  }
}

int main() {
  int i, repcnt;
  int *a = malloc(sizeof(int[1000]));
  int *b = malloc(sizeof(int[1000]));
  int sum = 0;
  for(repcnt = 0; repcnt < 1000; ++repcnt) {
    for(i = 0; i < 1000; ++i) {
      b[i] = a[i] = i - repcnt;
    }
    foo(a, b);
    sum += b[500];
  }
  printf("%d\n", sum);
  return 0;
}

test2.c

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

struct Bar { int x; };
struct Baz { int x; };

void foo(struct Bar a[], struct Baz b[]) {
  int i, j;
  for(i = 1; i < 1000; ++i) {
    for(j = 0; j < 1000; ++j) {
      b[i-1].x = a[i-1].x * 2;
      b[i].x = a[i].x * 2;
    }
  }
}

int main() {
  int i, repcnt;
  struct Bar *a = malloc(sizeof(struct Bar[1000]));
  struct Baz *b = malloc(sizeof(struct Baz[1000]));
  int sum = 0;
  for(repcnt = 0; repcnt < 1000; ++repcnt) {
    for(i = 0; i < 1000; ++i) {
      b[i].x = a[i].x = i - repcnt;
    }
    foo(a, b);
    sum += b[500].x;
  }
  printf("%d\n", sum);
  return 0;
}