プログラム実行時間の99%以上がループ内で消費される。プログラムの速度が問題になる場合、ループを最適化するのは非常に重要である。
序
最近のコンパイラは非常に優秀で、高度な最適をしてくれる。そのため、アセンブラなど知る必要がないと高をくくる人は少なくない。しかし本当に知る必要がないのだろうか？アセンブラを知らずにどうやってコンパイルされたあとのコードの検証できるのであろうか？また逆に、Cレベルでも工夫すれば十分な最適化ができるにもかかわらず、「コンパイラの出力するコードはだめだ」と無闇にアセンブラに走る人間もいる。そして当人は高速化したつもりだが、実際には上手く最適化されたCコードよりも遅いコードを書いた上に、プログラムの保守性を著しく下げただけの場合も数多く見てきた。ここでは、そういったことに陥らないための最適化手法について解説する。
例題
まず、最適化のされていない、いいかげんなプログラムを以下に示す。このサンプルを見て３ヶ所の問題点を指摘でき、どの程度高速化できるか見積もれる方はここを読む必要はない。私が教えられることはたぶんないだろう。しかし、そうでないのであれば、是非とも一緒に考えてもらいたいものである。
| #include <windows.h> #include <stdio.h> #include <mmsystem.h> #pragma comment(lib, "winmm.lib") // 最適化が必要なサンプルのクラス class CTest{ private: int m_nCounter; int m_nSize; int* m_pBuffer; public: void Init(void); void Free(void); void SetValue(int n); }; void CTest::Init(void) { m_nCounter = 0; m_nSize = 10000; m_pBuffer = new int[m_nSize]; } void CTest::Free(void) { if(m_pBuffer != NULL) delete[] m_pBuffer; m_pBuffer = NULL; } void CTest::SetValue(int n) { for(m_nCounter = 0; m_nCounter < m_nSize; m_nCounter++){ m_pBuffer[m_nCounter] = n; } } // テスト用プログラム int main(void) { CTest test; test.Init(); DWORD time0 = timeGetTime(); for(int i = 0; i < 100000; i++) test.SetValue(i); DWORD time1 = timeGetTime(); test.Free(); printf("処理時間 %.3f秒\n", (double)(time1 - time0) / 1000); return EXIT_SUCCESS; } |
サンプルのクラスは、確保したメモリを指定した値で埋める単純なものである。そして最適化が必要で、問題点が３つある部分を赤色で示した。クラスの設計とか、テストプログラムの是非についてはここでは本質ではない。
最適化その１
まず、多くの方がすぐに気が付くのが、forループのカウンタである。こんなところにメンバ変数を使ってはならない。以下のように最適化する。
| void CTest::SetValue(int n) { for(int i = 0; i < m_nSize; i++){ m_pBuffer[i] = n; } } |
最適化その２
次も同じようなものであるが、ループの継続条件式の中である。カウンタに気が回っても、ここを見落としているプログラムは少なくない。
| void CTest::SetValue(int n) { int nSize = m_nSize; for(int i = 0; i < nSize; i++){ m_pBuffer[i] = n; } } |
最適化その３
ここまでの流れから、容易に想像はつくと思う。しかし、実際のプログラムでは、無視されている場合が多い。特に動的に配列を確保して、グローバルなポインタ変数を使っている場合も同じ問題に陥る。この場合、静的な配列より効率を落としている。ポインタを覚えて使ってみるのはいいが、改悪する者は少なくない。
| void CTest::SetValue(int n) { int nSize = m_nSize; int *pBuffer = m_pBuffer; for(int i = 0; i < nSize; i++){ pBuffer[i] = n; } } |
最適化の効果
以上３点の問題個所を最適化した場合にどの程度効果があったか調べてみる。以下にテストした結果を示す。
テスト環境(CPU Pentium!!! 700MHz, OS Windows98)
| 処理時間(sec) | |
| 最適化前 | 14.5 |
| 最適化その１ | 7.2 |
| 最適化その２ | 5.8 |
| 最適化その３ | 2.2 |
コンパイラによる最適化がかからない理由
なぜ、この程度の最適化がかからないのか不思議に思うかもしれない。しかし、その理由は実は単純なものである。「ループ内で書き込んでいるバッファ中に、参照しているメンバ変数が存在しているかもしれない」、つまり、「ループ内の書き込みにより、メンバ変数の値が書き換えられ、ループの条件が変わるかもしれない」ことをコンパイラは考慮しているのであり、コンパイラが賢いがゆえに最適化がかからないのである。今回メンバ変数を使って示したが、構造体のポインタ渡しでアクセスしている場合、グローバル変数を使っている場合でも起こる問題である。
一応その例を、以下に示しておく。
| #include <windows.h> #include <stdio.h> #include <mmsystem.h> #pragma comment(lib, "winmm.lib") const int nSize = 10000; int Buffer[nSize]; int *pBuffer; int main(void) { pBuffer = &Buffer[0]; DWORD time0 = timeGetTime(); for(int i = 0; i < 100000; i++){ for(int j = 0; j < nSize; j++) Buffer[j] = i; } DWORD time1 = timeGetTime(); printf("処理時間 %.3f秒\n", (double)(time1 - time0) / 1000); return EXIT_SUCCESS; } |
そして、赤で示した部分を、改悪した例。これは最適化その３で指摘した、ポインタを覚えて改悪し、静的な配列より効率を落としている例でもある。
| for(int j = 0; j < nSize; j++) pBuffer[j] = i; |
テスト結果。
テスト環境(CPU Pentium!!! 700MHz, OS Windows98)
| 処理時間(sec) | |
| 改悪前 | 2.2 |
| 改悪後 | 5.8 |
考察
最適化をする場合、ループ内で使用する変数は自動変数を使うようにすれば、確かに上記のような問題は解決し、高速化できる。しかし、私がここで学んでほしいことは、上記のような方法を使うようにすることだけではなく、上記のような方法を自分で見つけることである。最適化が必要な個所をアセンブリ言語で確認し、問題がある場合はどうしてそのようなコードを生成するのかコンパイラの気持ちになって考え、コンパイラに必要な情報を与え、最適化しやすくしてあげることである。そして、それでも更なる最適化が必要な場合だけにアセンブラを使用するようにすることである。
以下は最適化その１における、コンパイラの生成コードである。注目すべき個所をコメントで示した。
|
以下は最適化その３のコード。無駄がなくなっていることがわかると思う。
|