プログラムの処理速度の比較

[たかし]

学校で同じ実行内容のプログラムを3種類作りました。
１つめは配列を使ったもの、２つめはポインタを使ったもの、3つめはポインタをレジスタに置いたものです。
プログラムの内容は乱数を発生させるプログラムで乱数ファイルを作り、その乱数データを入力として、乱数を単純選択ソートで値の小さいもの順に並べ替えるものです。

以下がそれらのプログラムです。

配列

コード:

#include <stdio.h>
#define nmax 100000

void select_sort(int a[], int n)
{
  int i,j,min,t;
  for(i=0;i<n;i++)
    {
      min=i;
      for(j=i+1;j<n;j++)
	if(a[j]<a[min]) min=j;
      t=a[min]; a[min] = a[i]; a[i]=t;
    }
}

main(){

  int a[nmax+1],n,i;
  n=0;
  while(scanf("%d",&a[n]) !=EOF) n++;
  select_sort(a,n);
  /* printf("%d\n\n",n);*/
  for(i=0;i<n;i++){
    /* printf(" &d\n",a[i]);*/
  }
}

ポインタ

コード:

#include <stdio.h>
#define nmax 100000

void select_sort(int *a, int n)
{
  int *ptr1;
  int *ptr2;
  int *min;
  int t;

  for(ptr1=a;(ptr1-a)<n; ptr1++){

    min=ptr1;
    for(ptr2=ptr1+1;(ptr2-a)<n;ptr2++){

      if(*ptr2<*min){
	min=ptr2;
      }
    }
    t=*min;
    *min=*ptr1;
    *ptr1=t;
    
  }
  

}

main()
{
  int a[nmax+1], n,i;
  n=0;
  while(scanf("%d",&a[n])!=EOF) n++;
  select_sort(a,n);
  /* printf("%d\n\n",n);*/
  for(i=0;i<n;i++) {
    /*printf("%d\n",a[i]);*/
  }
}

レジスタ

コード:

#include <stdio.h>
#include <limits.h>
#define nmax 100000

void select_sort(int *a, int n)
{
  register int *ptr1;
  register int *ptr2;
  register int *min;
  int t;

  for(ptr1=a;(ptr1-a)<n; ptr1++){

    min=ptr1;
    for(ptr2=ptr1+1;(ptr2-a)<n;ptr2++){

      if(*ptr2<*min){
	min=ptr2;
      }
    }
    t=*min;
    *min=*ptr1;
    *ptr1=t;
    
  }
  
}

main()
{
  int a[nmax+1], n,i;
  n=0;
  while(scanf("%d",&a[n])!=EOF) n++;
  a[n+1]=INT_MAX;
  select_sort(a,n);
  /*printf("%d\n\n",n);*/
  for(i=0;i<n;i++) {
    /*printf("%d\n",a[i]);*/
  }
}

乱数

コード:

#include<stdio.h>

#define MAX_DIGIT 10000

main(int argc, char *argv[])
{
  int i,size,count;

  srand(time(&i));

  if(argc<2){
    size =1000;
  }else{
    size = atoi(argv[1]);
  }

  for(count = 0; count < size; count++){
    fprintf(stdout,"%6d ", rand() % MAX_DIGIT);
  }
}

そしてプログラムごとに、最適化オプション、-O1,-O2,-O3とオプションなし、で実行時間を測定しました。
また実行時間の影響を少なくするために、出力はコメントアウトしました。

以下が測定結果です。

配列
-O1 11.11
-O2 11.11
-O3 16.65
無し 34.21
ポインタ
-O1 13.94
-O2 13.88
-O3 13.88
無し 30.74
レジスタ
-O1 13.88
-O2 13.88
-O3 16.65
無し 38.01

ここで結果について質問です。
私の予想では、レジスタ＞ポインタ＞配列　の順で速いかと思ったのですが、オプションなしの結果は
ポインタ＞配列＞レジスタの順でした。
レジスタについて調べてみたら、レジスタをポインタに置けば、
変数のアクセスのためにメモリをアクセスする必要がなくなるので、変数へのアクセスが高速化される、
ということがわかったのでレジスタが最も早いと思ったのですが、結果は違いました。
この理由はなぜですか？

また、最適化オプションは
-O3＞-O2＞-O1の順でパフォーマンスの向上をしてくれるものだと思ってました。
しかし今回の結果で、オプション-O1と-O2ではどのプログラムでも実行時間にあまり違いがありませんでした。
なぜ-O2にしても速くならなかったのですか？
さらに、-O3のとき、ポインタでは-O1,-O2同様変化がなく、配列とレジスタでは速くなるどころか遅くなっています。
この理由もわかりません。

よろしくお願いします。

[softya（ソフト屋)]

どうやって処理速度を計測したのかも問題になりそうな計測結果です。
あとgccだと思いますがバージョンにもよると思います。
それと入出力を含めて計測してないか心配です。

[h2so5]

測定したデータが正しいと仮定した場合の話をします。

今回の場合は配列とポインタでは違いはありませんが（シンタックスシュガーを使うかどうか）、
一般的には配列よりポインタの方がコンパイラの最適化が効きにくいためパフォーマンスは落ちやすいと思います。

また、最適化オプションは
-O3＞-O2＞-O1の順でパフォーマンスの向上をしてくれるものだと思ってました。
しかし今回の結果で、オプション-O1と-O2ではどのプログラムでも実行時間にあまり違いがありませんでした。
なぜ-O2にしても速くならなかったのですか？

プログラムの規模が小さいのでそれ以上最適化する余地がないということだと思います。

さらに、-O3のとき、ポインタでは-O1,-O2同様変化がなく、配列とレジスタでは速くなるどころか遅くなっています。
この理由もわかりません。

僕も詳しくは分かりませんが、インライン展開によってキャッシュヒット率が悪くなっている可能性があるようです。
似たような質問: http://www.linuxmisc.com/18-writing-Lin ... 13d05d.htm

最適化オプションはすべてのプログラムに有効なわけではなく、コードによっては逆効果になる場合もあります。
もちろん、OSやCPUによっても速度は変わります。

[softya（ソフト屋)]

そうですね。
短いコードの場合は、最適化の効果の評価は非常に難しいのである程度の規模のコードでしか効果の評価は意味を成さないかもしれません。

[たかし]

みなさん、返信ありがとうございます。
説明していただいた理由で納得できました。
それならこの結果でも問題ないように思えます。
ちなみに学校ではgccでコンパイルしてtimeコマンドを使って計測しました。
入力は以下のようにしてやりました。

gcc -O1 select-sort.o.c
/usr/bin/time -p a.out < rand100000

でも、計測結果が正しいのか心配になったので自宅のパソコンでCygwinを使って計測しなおしてみました。
以下がその結果です。
（select-sort.o.cが配列、selectsort.cがポインタ、select-sort2.cがレジスタとなっております。）

$ gcc select-sort.o.c

$ time -p ./a.exe < rand100000
real 17.98
user 17.67
sys 0.03

$ gcc -O1 select-sort.o.c

$ time -p ./a.exe < rand100000
real 11.54
user 11.27
sys 0.01

$ gcc -O2 select-sort.o.c

$ time -p ./a.exe < rand100000
real 5.55
user 5.24
sys 0.03

$ gcc -O3 select-sort.o.c

$ time -p ./a.exe < rand100000
real 0.49
user 0.04
sys 0.03

$ gcc select-sort.c

$ time -p ./a.exe < rand100000
real 15.53
user 15.28
sys 0.00

$ gcc -O1 select-sort.c

$ time -p ./a.exe < rand100000
real 11.45
user 11.20
sys 0.01

$ gcc -O2 select-sort.c

$ time -p ./a.exe < rand100000
real 5.35
user 5.10
sys 0.01

$ gcc -O3 select-sort.c

$ time -p ./a.exe < rand100000
real 4.21
user 3.94
sys 0.00

$ gcc select-sort2.c

$ time -p ./a.exe < rand100000
real 7.25
user 6.95
sys 0.03

$ gcc -O1 select-sort2.c

$ time -p ./a.exe < rand100000
real 11.41
user 11.16
sys 0.03

$ gcc -O2 select-sort2.c

$ time -p ./a.exe < rand100000
real 5.30
user 5.07
sys 0.03

$ gcc -O3 select-sort2.c

$ time -p ./a.exe < rand100000
real 4.16
user 3.93
sys 0.01

自宅でやった結果をみると私の思い描いていた結果に近いものになりました。
これはもしかして学校でやった時のが計測ミスだったということはあるんでしょうか？
それともＯＳやＣＰＵが学校と違うからこのような結果が出たということですか？

よろしくお願いします。

[softya（ソフト屋)]

timeコマンドでの計測だと入出力を含んでしまうので時間計測の評価は難しいです。
純粋にsort処理だけ計測した方が良いでしょう。

>それともＯＳやＣＰＵが学校と違うからこのような結果が出たということですか？

それを出来るだけ排除したほうが良いので、sort処理だけの方が良いです。
あと書きましたがgccのバージョンは重要です。

[きゃりーわんわん]

回答ではなく申し訳ないですが・・・

register intですが
registerを付けているからといって、
その変数が実際にレジスタに割り当てられることは保証されなかったような・・・

自分も人から聞いた知識なので出典は出せませんが
ググるとこんなのが出てきました。
http://dixq.net/forum/viewtopic.php?f=3&t=535

[みけCAT]

完全にレジスタを使いたかったら、インラインアセンブラで書いてみてはいかがですか？