プログラミング :: 高速なプログラムを書く為に

-- ≪ ≫ メモリプログラミング :: 高速なプログラムを書く為に :: 初めに

注意

この文章は自分で色々調べながら生半可の理解で書いた物であり、信用出来ない部分が沢山あります。

何やら、変な宗教を流行らせるなという注意を受けてしまいました → 本の虫: いまだに変な宗教が流行っている。 (しかし、内部向けに書いた物を、よく見てくれる人がいる物だ。御免なさい…詳しい人は見ないと思って、調子に乗って、適当な事を偉そうに書いちゃってますが…。)

とはいえど、勉強になるのでありがたいです。何か間違っている事があったら、直接連絡もして頂けると尚嬉しいです。 (或いは、コメント欄とかを用意した方が良いのかなあ。)

後、受けたコメントについて調べたりした内容も載せておく事にします → 初めに (コメントに対し)。

高速なプログラムを書く為に

GPGPU について書こうと思ったのですが、それよりも先に、高速なプログラムを書くに当たって注意するべき一般的な事を述べておいた方が良い様に思ったので、「高速なプログラムを書く為に」という題で簡単に纏めてみる事にしました。特にメモリに関しては、GPGPU でも重要になってきます。

内容としては以下の様な物を今の所考えています。最後まで書ききれるかどうかは分かりませんが。

初めに

当たり前ですが、プログラムは高速に動いた方が嬉しいです。其処で、ここではプログラムを高速にどうさせるにはどの様な事に注意したらよいのかという事を簡単に説明しようという訳です。

先ずは完成させてから

初めから高速になる様に高速になる様に、と考えて書かなくても良いです。慣れてくれば、何も意識せず或る程度効率の良い書き方をできる様になります。もし慣れていないのであれば、後で修正するつもりで書きましょう。

慣れていないのに、細かい事を考えてプログラムを書いていると、プログラムの全体像を見失って何時まで経っても完成しなかったり、不整合を生んで泥沼に嵌ったりします。幾ら遅いプログラムでも、完成しないプログラムと比べたらずっと上です。従って、プログラムを書く際には無理して高速に書こうと言う事は考えずに、先ずは、完成させる事を考えて書くと良いです。

プログラムがより高速に動く様に調整するのは、プログラムが完成してからです。もしかすると、高速化をするに当たって、プログラムの構造を大幅に変更する必要が出て来る事もあるかも知れません。でも、だからといって、初めに書いたプログラムが無意味だったという訳ではありません。初めに書いたプログラムはけがきか下書きの様な物です。初めに書いたプログラムが在ればこそ、もう少し複雑な構造を持ったプログラムを書くのが楽になる訳です。まあ、そんな風に思って気軽に書き始める事をお薦めします。

実行時間とコーディング時間のトレードオフ

プログラムの高速化に関して説明する前に、ちょっと釘を刺しておきます。目的を忘れてプログラムの最適化 (＝より高速に動く様に調整する事) に没頭しても意味はありません。

プログラムを出来るだけ速く動作する様に工夫すると一口に言っても、簡単に出来る物からとても面倒くさい物・時間の掛かる物まで色々あります。プログラムを極限まで高速に動作させようと思ったら、面倒くさい物・時間の掛かる物までありとあらゆる手管を考えてプログラムを書く事になるでしょう。そうして時間を掛ければ掛ける程、より高速なプログラムが出来る訳です。

でも、少々待って下さい…。本当に、そんなに沢山の時間をかけてプログラムを最適化する必要があるか良く考えなくてはなりません。プログラムを書くのは何でかというと、人間には面倒で出来ない計算・時間が掛かりすぎて出来ない計算を計算機に実行させて、「その結果を素早く得る」為です。要するに、結果が出来るだけ早く得られればよい訳です。プログラムを高速化させると嬉しいのは、結果が早く得られるからです。しかし、結果が欲しいと思ってから結果が得られる迄の時間は、プログラムの実行時間だけで占められている訳ではありません。人間がプログラムを記述している時間も含まれているのです。

なので、現実的には「プログラムを記述するのに掛かる時間＋プログラムを実行するのに掛かる時間」が一番最小になる様に考えるのが適当です。 (まあ、一々厳密に計測して時間の最小化をする人はいないとは思いますが…。後、勿論、「趣味でプログラムの最適化という名のパズルにチャレンジするのだ」というのであれば、幾ら時間を掛けて戴いても一向に構いません。) 例えば、一時間唸った挙げ句にプログラムの実行時間を一秒短縮させても、そのプログラムが一回しか実行されないのであれば、努力の意味がありません。三千六百回以上実行させる期待があるのであれば意味があるかも知れませんが。

それから、数値計算のプログラムではなくて、通常のアプリケーションの場合にはまた少し違った状況になります。結論から言うと、通常のアプリケーションでは最適化の必要は殆どありません。(常識的な実装をしているのであれば。) 音声・画像・映像の処理を行う物は除いて、元々そんなに重くないからです。例えば、Word とか Excel とかを起動して使っていても CPU の使用率が 100% になったりする事は滅多にありません。もしその様なソフトが存在したら、不良ソフトだと思われてしまいます。これはどういう事かというと、普通のアプリケーションは「殆ど暇にしている」という事です。一般のソフトに於いては殆どの処理は文字通り一瞬で終わってしまうので、人間が一生懸命ソフトを操作して仕事していても、アプリケーションにとってはユーザーの指示を待機している時間の方が大半を占めているのです。その様な状況で、処理に掛かる時間が数倍変化しようとも、プログラムの動作に表面上の違いは出てこないでしょう。

※ 矛盾した事を言う様ですが、本当に最適なプログラムを書ける様になりたいというのであれば、長い時間を掛けて一つのプログラムを最適化する等という事をしないと身に付かないと思います。要するに、練習のプログラムでは時間をかけて最適化を学び、実用のプログラムではトレードオフを考えて最短で結果を得よ、という事です。 (最適化を本気で学ぶかどうかは個人の判断に任せます。)

コンパイラの最適化

上で最適化という言葉が出てきましたが、最適化は何もプログラマだけがする事ではありません。コンパイラも最適化を実行します。 (というか、単に「最適化 Optimization」と言った場合には、「コンパイラによる最適化」の事を指す事が多いと思います。) コンパイラも、完成するプログラムが高速に動作する様に、コードの組み替えや色々な調整を実行するのです。

例

例えば、以下の様なプログラムが存在するとします。

#include <stdio.h>
int main(){
  int a=60;
  ::printf("a*a == %d\n",a*a);
  return 0;
}

このプログラムを最適化しようと思って、以下の様に人の手で書き直しても意味はありません。

#include <stdio.h>
int main(){
  ::printf("a*a == %d\n",3600); // 60*60 を自分で計算して直接記入
  return 0;
}

何でかというと、コンパイラの最適化によって、一つ目のコードは、自動的に二つ目のコードと等価な物に変換されてしまうからです。

上の例から分かる様に、どうせコンパイラが最適化する様な事を、一々人の手で書き直しても全く意味がありません。時間の無駄ですし、往々にして見た目に分かりにくいコードになってしまいます。何一つ良い事はありませんので、そう言う書き換えは止めましょう。

例えば、上のプログラムの例で言うと、いきなり 3600 という数字がプログラムに書き込まれていたとすると、どう考えて 3600 という数字にしたのかが分かりにくくなってしまいます。更に、60*60 を計算する時に万一誤って、変な数値を書き込んだ時には、なかなかバグに気付かないという事も考えられます。

まとめ

0. コンパイル時の設定

これは、プログラムの書き方ではないのですが、見ているとプログラムを VS のデバッグモードで動作させている人が沢山いるみたいなので、色々書いて置きます。

コンパイラを選択する事

コンパイラによって最適化の性能が異なります。実行速度に本当に拘るのであれば、コンパイラを選択する事も重要になってくるんじゃないかと思います。とは言っても、これはそれ程には気にしなくても良いと思います。 (あ、でも、コンパイラは常に進化し続けているので vc6 とか bcc5.5 とか化石コンパイラを用いるのは宜しくありません。速度的にも、C++ 標準準拠度的にも。)

各コンパイラの性能についてですが、どうやら、世間的には

流石は CPU の設計元の Intel だけあって icc が一番評価が高いようです。 (icc は五月祭のスパコンで使用した人もいると思います。) gcc は色々なプロセッサに対応してバイナリを吐ける様になっているので、個別アーキテクチャに特化した最適化は苦手と言われています。然し一方で、本当に個々の CPU に合わせた最適化が可能なので、一般配布を必要としない数値計算のプログラムに於いては有利です。実際に、gcc 4 系列では CPU の拡張命令を用いた最適化が改善され、 VC に勝っていると僕は勝手に思っています。

※ 念の為。vc は Windows でなければ使えないし、 icc も IA32 や IA64 等 Intel のアーキテクチャを採用している CPU でなければ使えません。

処理を DLL に分離しない

DLL にすると、バージョンの変化に対する対応がし易い・メモリを有効に使える等の利点がありますが、数値計算に於いては積極的に使用するのは止めておいた方が良いです。その理由には以下の様な物があります。

重い処理を丸ごと DLL に封じ込めるなどという事ならば問題在りませんが、ループの中で DLL の関数を呼び出すなどといった事をするのはとんでもないです。試してみれば、可成り遅くなると言う事を実感出来ると思います。

最適化のオプション

数値計算のプログラムを最適化の設定などを一切せずに実行する事は、足枷を嵌めて徒競走に出る様な物です。何も最適化の設定をしないとデバグし易いコード (＝殆ど最適化してない) になってしまうのです。

※ 時々、C++ は C よりも遅いと断言している人がいますが、そう言う様な人は「自分は無知だから、足枷を嵌めて C++ を走らせているのだ」という事を周りに喧伝している様な物です。 (まあ、実際の所、C++ は例外機構とか仮想関数とか色々最適化を妨げる物が入っているので、 C より遅くなると言うのは事実なのですが…そういった物は書き方によって改善する事が可能です。)

VC の場合 (コマンドラインから)

コマンドラインからコンパイルする場合、本番用バイナリの生成ではコンパイラオプションを適切に設定しましょう。

vc で使える最適化に関するオプションには以下の様な物があります。

説明はともかくとして、大体の環境では↓の用にして置けば、大方問題ないと思います。

※ 上のオプションを指定しなければならないのは、本番の実行前の時だけです。最適化などのオプションを指定すると、当然の事ながら最適化の為にコンパイル時間が長くなります。書いている途中の場合は、コンパイルに時間が掛からない様に、何もオプションを指定しないでおいて構いません。

GCC の場合

gcc で使える最適化に関するオプションには以下の様な物があります。

例えば、上の CPU の例では以下の様にして、本番用のバイナリをコンパイルします。

Visual Studio を使っている場合

本番は Release モードで

先にも述べた様に、デバッグモードで実行している人が多すぎです。

Visual Studio のデバッグモードというのは、デバッグの為にコンパイラによる最適化を実行しないで、バイナリ (機械語) に変換するモードです。コンパイラの最適化は、プログラムの構造自体を劇的に変化させる可能性がありソースコードとの対応が意味を為さなくなる事があります。従って、ソースコードを見ながらデバッグする際には、コンパイラの最適化は無効にしておく必要があるのです。

デバッグモードと対照を為すのがリリースモードです。リリースモードでは、デバッグの為に控えていたコンパイラの最適化がちゃんと動作します。実際に数値計算を実行する際には必ずリリースモードにして実行する様にしましょう。 C++ でクラスを多用してプログラムを組んでいる場合、五倍ぐらい速度が変化するという事はよくある事です。

※ 普通の Windows アプリケーションなんかの場合には、上でも書いた様に殆ど暇な時間を過ごしているので、デバッグモードでコンパイルして其れを使っていても速度上の問題は生じません (配布という観点での問題は生じますが…)。なので、普通のアプリケーションに書き慣れている人には実感はないかも知れませんが、数値計算を行うプログラムに於いては、デバッグモードとリリースモードの違いは如実に顕れてきます。

やり方

デバッグモードとリリースモードの切替は簡単です。 Visual Studio の window の上の方に、[実行] の意味の右三角矢印がありますが、そのすぐ右の欄がモードの選択を行う欄になっています。其処を Release にすれば Release モードになります。

プロジェクトを新しく作成すると自動的に Debug モードになっていますが、基本的に Release モードで開発して、バグが発生したら Debug モードに戻すというのがお薦めです。

コンパイラオプション

コンパイル時の最適化に関するオプションも弄っておくと良いです。

やり方

プロファイル

更に、VS の自動プロファイル/最適化の機能を使用する事もお薦めします。こちらは 2 倍ぐらい速度が変化する可能性があります。(何か余り効果がない場合もありますが。)

プロファイルというのは、簡単に言ってしまうと、実際に実行してプログラムの動作を統計し、それを最適化に役立てる事です。例えば、良く実行される関数はメモリ上で出来るだけ近くに配置するとか、プログラムの分岐点で頻度の多い分岐先を近くに配置するとか、そう言う事です。

実行に何時間もかかる様な数値計算の場合には、初めに何分かプロファイルを取って最適化をしてから、本番の計算に臨むと良いでしょう。

やり方

1. 最適化の対象

プログラムの最適化を図る時には、何処を重点的に最適化するのかというのも重要です。普通、プログラムの中で沢山実行される部分・実行に時間が掛かっている部分を最適化します。例えば、プログラムの中で、起動時に一回しか実行されない様な部分を最適化しても殆ど意味がありません。逆に言えば、ループの中の場合些細な違いが大きな結果を齎す事もあります。

(コンパイラではなく自分で最適化をする場合、) 最適化の対象は基本的にはループの中にしましょう。それ以外の所を一生懸命考えて書き換えても、徒労に終わってしまうでしょう。

※ とは言っても、ループの外は適当に書けばいいと言う訳でもないと思います。殊更に高速化を図って書き換える必要はなくても、初めから効率を少し意識して書く様にすると良いです。訓練だと思って、ループの外でも効率を考えて書くのです。

プロファイル

また、前の項で少し出てきましたが、プロファイルという考え方も存在します。プロファイルというのは、実際にプログラムを実行してみて、

プログラムが複雑でどの関数が一番沢山呼ばれているか・どの関数で処理に時間が掛かっているか、が設計の段階で分からない様な場合にはプロファイリングの結果によってその事を調べます。プログラムの最適化は、実行に時間の掛かっている関数や、頻繁に呼び出される関数に対して行います。

2. アルゴリズム

FFT とか Runge-Kutta とか、複雑で劇的な効率を持つ物を自分で考案せよとは言いません。然し、どんな処理であっても、無駄のある様な処理手順を採用するのは、速度的にも、コードの見やすさ的にも良くありません。 ~~でもまあ、物理学科の皆さんなら、普通に書けば大体大丈夫でしょう~~…という訳でもないみたいです…。

唯、数値計算の様な物の場合は処理手順は余り問題にならないと思うので、やっぱりそんなに気にしなくて大丈夫です。というのも、大体の数値計算は、FFT や Runge-Kutta 等、確立された手法以外の部分に関しては、単純だからです。他に書きようがない様な計算が多いので、別段処理手順などについて意識する事はないでしょう。

普通に書けば大丈夫……とか思っていたのですが…。やはり、これは、可成り慣れと経験に依存する物みたいです…。

先ず、「この場合はこうするのが普通で効率的」というのの経験による蓄積が必要になるんじゃないかと思います。
また、「ちょっと複雑な処理になるとしてもちゃんと書く事が出来る」という自信も必要なのかも知れません。
後、プログラムの動作に関する直感もあった方が、効率の良い処理手順が思い付きやすいと思います。

歯切れが悪いのは…今迄余り意識した事がなかったからです。確かに、自分が昔書いていた物とかを見ると変な事してるなー、というのは沢山ある訳ですが、それは自分が馬鹿だったからだと思ってました。でも、他の人の書いている物を見て、ここはこうする方が普通だとかここはこうした方がいいんじゃないかとか色々考えて、初めてアルゴリズムに関しても経験が物を言うのだという事に想到した訳です…。

結局、沢山プログラムを書いたり読んだりして、どう言うパターンがあるかと言う事を学んだり、処理の仕方を考え出す練習をしたり、…という事しかないと思います。

以下思う事を箇条書きにして書いてみます。全然まとまってないですが

学ぶ
他の人の書いたコードを読むというのは大事です。

特に、同じ問題について他の人と一緒にコードを書いて、コードを交換して評価し合うというのはかなり勉強になると思います。
考える
「処理の仕方」というのは完全にパターンだけで記述出来る物ではなくて、毎回問題に応じて考え出す物です。パターンを暗記すればいいとかそういう物じゃないです。

普段からより効率の良い処理の仕方について考えながら書くと言う事は大切です。
パターン
「パターンだけで記述出来る物ではない」とは言っても、部分部分で見ると、色々他の物を参考に出来る部分は沢山あります。細かい部分に関してはパターンが有効になってくる場合がある訳です。
複雑な処理の仕方でも挑戦する
効率が良くても少し処理が複雑になる様な場合があります。そう言った時は、バグを混入させる事を恐れて、効率は悪いが実装しやすい物を選択してしまう事があります。でも、そう言う風に避けてばかり居ては何時まで経っても複雑な処理を書ける様になりません。

後、数値計算について言える事なのですが、出来るだけ式変形をして計算しやすい形に直してからプログラムにして下さい。いきなり、基礎の方程式を直接プログラムにして処理をしようと考える人がいるかも知れませんが、ちゃんと式変形しましょう。アルゴリズムと関係ないと考える人もいるかも知れないですが、効率良いアルゴリズムを考えるって言うのはいわば処理手順を「式変形」する事に他なりません。 (「式」という変形規則が定義された物よりも、変形が難しい、という違いはありますが。)

数値計算ライブラリ

後、線形代数の計算や、FFT の計算などに関しては、自分で記述しない方が良いです。自分の練習の為に書くのは良いかも知れませんが、速度を優先させたいプログラムの場合には既存のライブラリを使用するべきです。何故なら、既存のライブラリでは専門家の人が極限まで最適化を図って設計しているからです。