ソースレベルでの最適化

早いコードを書こう！

　最適化はコンパイラがある程度はやってくれます。賢いコンパイラであればある程度適当にプログラミングしても早いコードを生成してくれます。ですが、コンパイラの最適化能力が弱かったり及ばなかったりするケースもありますし、長時間走らせるソフトなどで少しでも早くしたいと言う願望が出てくる場合もあります。もちろんその部分をアセンブリ言語で書くのが一番良いのですが、ポータビリティーが無くなりますし、何よりアセンブリ言語を知っている必要があります。しかしながら、そのようなことをしなくてもC言語のソースレベルでもプログラムを最適化することは出来ます。今回はそのあたりを突っ込んで見ましょう。

ループの最適化

　普通最適化したくなるのはループです。そしてもっとも最適化できるのもループだったりします。次の例で見てみましょう。

  for ( i = 0; i < GetDataLen(); i++ )
    Data[i] = a * b;

　最適化の宝庫ですね。
このようなプログラムは次ぎのように書けば多分早くなります。

  register int *p;
  register int *p_end;
  register int data;
  
  data  = a * b;
  p_end = &Data[GetDataLen()];
  for ( p = Data; p < p_end; p++ )
    *p = data;

　とまあ可読性は悪いですがやっていることは

ループ中の変数を使用頻度の高い順に register 宣言する。
ループ内で行う計算で毎回変化の無い部分はループの外で計算を済ませておく。

　の２点です。簡単なことですが、上記の GetDataLen 関数を呼んでいる部分などはコンパイラがどんなにがんばっても値が変わるかどうかのチェックは出来ませんので手動で最適化しないといけないです。配列を操作する場合も上記のようにポインタを使えば計算量が減ります。

インライン展開

　関数の呼び出しには、呼び出しとリターンでロスが生じます。関数を呼ばずに関数の中身をそのままそこに書いてしまえば高速化されます。C++であれば inline 指定子がありますので活用すればいいでしょう。Cの場合はちょっと難しいですが、小さいものであればマクロ定義などで切りぬけることが可能です。

キャッシュのヒット率を上げよう

　たとえば次ぎのような関数を多用するとしましょう。

int a[DATASIZE];
int b[DATASIZE];
int c[DATASIZE];

int GetMulData(int n)
{
  return a[n] * b[n] * c[n];
}

　このようなとき、データの並びを変えて

struct TData {
  int a;
  int b;
  int c;
  int dumy;  /* 構造体サイズを 2のべき乗にそろえる */
} data[DATASIZE];

int GetMulData(int n)
{
  register struct TData *p;
  p = &data[n];
  return p->a * p->b * p->c;
}

　とすれば多分早くなります。通常キャッシュミスヒットが起こった場合ページアクセスモードを使ってDRAMからキャッシュメモリにバースト転送が行われますので、アクセス時に周辺のメモリが同時にキャッシュに乗ります。つまり、上記の関数の例だと、構造体のメンバ a にアクセスに行った時点で b, c もキャッシュに乗りますから高速化されるわけです。ついでに配列のアドレス計算も一回になりますからこれも高速化に繋がりますし、まとめて使うデータを一箇所に集めることはメモリのスワップを減らす効果もあります。

おわりに

　まあ、思いつくまま適当に書いてみましたが、他にもいろいろあると思います。ただ、このような技法の多くは可読性やメンテナンス性を下げることになりかねませんのでコンパイラ自身の最適化能力と相談しながら本当に必要な部分にのみ行うことが大切でしょう。できることならアルゴリズムの工夫による最適化が一番ですし、最近の風潮を考えると速度よりも安全性を重視するべきでしょう。