タイム クリティカルなコードを高速化するためのヒント
更新 : 2007 年 11 月
処理速度の速いコードを作成するには、あらゆる面からアプリケーションを分析し、そのコードがシステムとどのようにやり取りするかを調べる必要があります。ここでは、コードのタイム クリティカルな部分のパフォーマンスを向上させるための、いくつかのコーディング テクニックについて説明します。
タイム クリティカルなコードを高速化するには、以下の点を確認します。
プログラムのどの部分を高速化すべきか
コードのサイズと実行速度はどのくらいか
新しい機能にかかるコストはどのくらいか
処理を完了するのに最小限どのくらいの作業が必要か
コードのパフォーマンスに関する情報を収集するには、パフォーマンス モニタ (perfmon.exe) を使用します。
キャッシュのヒット カウントとページ フォールト
並べ替えと検索
MFC ライブラリとクラス ライブラリ
共有ライブラリ
ヒープ
スレッド
小さなワーキング セット
キャッシュ ミスとページ フォールト
内部キャッシュおよび外部キャッシュがヒットしなかった場合も、ページ フォールト (プログラム命令やデータを 2 次ストレージに検索に行くこと) が発生した場合と同様に、プログラムのパフォーマンスが低下します。
CPU キャッシュがヒットしないと、10 ～ 20 クロック分のロスが発生すると計算されます。外部キャッシュがヒットしないと、20 ～ 40 クロック分のロスが生じます。ページ フォールトが発生した場合は、プロセッサが毎秒 5 億の命令を処理し、1 回のページ フォールトで 2 ミリ秒かかると仮定すると、100 万クロック分のロスが生じます。したがって、プログラムを高速化するには、キャッシュのミス ヒットとページ フォールトを減らすことに細心の注意を払う必要があります。
プログラムが遅い原因の 1 つとして、必要以上にページ フォールトやキャッシュのミス ヒットが発生していることが考えられます。これを避けるには、データ参照の局所性が高いデータ構造体を使用すること、つまり関連のあるデータをまとめておくことが重要です。一見優れているように見えるデータ構造体でも、データ参照の局所性が低いためにパフォーマンスが悪くなってしまうこともあれば、逆にあまり優れているように見えないデータ構造体でも、データ参照の局所性が高いために高速になることもあります。2 つの例を次に示します。
動的メモリ割り当てで作成されたリンク リストは、プログラムのパフォーマンスを低下させる原因になります。リスト内のアイテムを検索したり、リストの最後まで移動したりする場合、リンクをたどるたびにキャッシュのミス ヒットやページ フォールトが発生することがあるためです。実際、単純な配列で実装したリストの方が、キャッシュが有効に働いてページ フォールトの回数が減るため、はるかに高速です。配列のサイズを拡張するときに余分な処理が必要になることを考慮しても、やはりこの方が高速です。
動的メモリ割り当てで作成されたリンク リストを使用したハッシュ テーブルも、パフォーマンスを低下させる原因になります。このようなリンク リストにハッシュ テーブルの内容だけが格納されている場合でも、予想以上にパフォーマンスが低下する場合があります。実際、配列を使用した単純なリニア サーチの方が最終的には高速だったという例もあります。配列ベースのハッシュ テーブル (いわゆる "クローズド ハッシュ法") は見落とされがちですが、パフォーマンス的には優れた方法です。
並べ替えと検索
並べ替えは、多くの一般的な処理と比較して本質的に時間がかかります。処理速度の低下を防ぐ最良の方法は、重要な部分で並べ替えを行わなくても済む方法を見つけることです。たとえば、次の方法があります。
並べ替えの開始を遅らせ、パフォーマンスに影響しない時間に実行する。
パフォーマンスに影響しない時間にあらかじめデータを並べ替えておく。
本当に並べ替えが必要なデータ部分だけを並べ替える。
並べ替えられた順序でリストを作成することもできます。並べ替えられた順にデータを挿入する必要がある場合は、データ参照の局所性が低い複雑なデータ構造体が必要になり、キャッシュのミス ヒットやページ フォールトが発生する可能性があるために注意が必要です。すべての状況に対して有効な方法はありません。いろいろな方法を試して違いを測定してください。
並べ替えに関する一般的なヒントを次に示します。
手持ちの並べ替え関数を使用してバグを最小限に抑えます。
並べ替えを行う前に、並べ替え中に行う必要のある作業をできる限り単純化しておきます。たとえば、最初の並べ替えの計算量が O(n log n) であったとしても、データ比較処理を単純化しておけば、計算量を O(n) にすることができる場合があります。
並べ替え対象のデータの形式と照らし、現在使用している並べ替えアルゴリズムがデータ参照の局所性を保っているかどうかを考慮します。
検索のパフォーマンスを向上させる方法は、並べ替えの場合ほど多くありません。通常、検索がタイム クリティカルな場合は、バイナリ サーチつまりハッシュ テーブルの照合を使用しますが、検索の場合と同様に、データ参照の局所性を保つように心がけてください。小さな配列を使用したリニア サーチの方が、多くのポインタを持つデータ構造体を使用したバイナリ サーチよりも高速である場合があります。後者はページ フォールトやキャッシュのミス ヒットを発生させることがあるためです。
MFC ライブラリとクラス ライブラリ
MFC (Microsoft Foundation Class) を使用すると、コードの記述が簡単になります。タイム クリティカルなコードを記述する場合、クラスよってはオーバーヘッドが生じる可能性があるので注意が必要です。タイム クリティカルな部分で使用する MFC コードを調べ、そのコードが要求されるパフォーマンスに見合うかどうかを判断します。MFC のクラスおよび関数についての注意点を以下に示します。
CString MFC は C ランタイム ライブラリを呼び出して、CString のメモリを動的に割り当てます。通常、CString は、動的に割り当てられたほかの文字列と同じ役割を果たします。CString では、動的に割り当てられたその他の文字列と同様に、動的割り当てと割り当ての解除のときにオーバーヘッドが生じます。多くの場合、スタック上で単純な char 型の配列をとると、同じ処理を高速化できます。CString は定数文字列の格納に使用しないでください。定数文字列には const char * を使用します。CString オブジェクトを使用して行う処理には、常にオーバーヘッドを伴います。ランタイム ライブラリの文字列関数を使用した方が高速化できる場合があります。
CArray CArray には、通常の配列にはない柔軟性がありますが、プログラムによってはこの柔軟性が必要でない場合もあります。配列の固有の制限がわかっている場合は、サイズ固定型のグローバル配列を使用できます。CArray を使用する場合は、CArray::SetSize を使用してサイズと再割り当て時の増加要素数を指定します。SetSize を使用しないと、要素を追加するたびに配列の再割り当てとコピーが行われるため、実行速度が低下してメモリが断片化します。また、配列にアイテムを挿入すると、CArray はメモリ内の後続のアイテムを移動するため、配列の拡張が必要になる場合があります。これらの処理はキャッシュのミス ヒットやページ フォールトの原因になります。MFC で使用するコードを調べて、パフォーマンスの向上に何が必要であるかを確認してください。たとえば、CArray はテンプレートなので、特定の型に対して CArray の特殊な形式を指定できます。
CList CList はダブルリンク リストなので、リストの先頭、末尾、および既知の位置 (POSITION) への要素の挿入が高速です。ただし、値やインデックスによって要素を検索するにはシーケンシャル サーチが必要です。これはリストが長くなると時間がかかります。コードにダブルリンク リストが必要でない場合は、CList を使用する必要があるかどうかを再検討してください。シングルリンク リストを使用すると、余分なポインタのためにメモリを消費することもなく、ポインタの更新によるオーバーヘッドを生じることもありません。余分なメモリの消費自体はそれほど大きな問題ではありませんが、キャッシュのミス ヒットやページ フォールトを増やす原因になります。
IsKindOf この関数は、多くの関数呼び出しを行うことによって、異なるデータ領域にあるさまざまなメモリにアクセスすることがあります。つまり、データ参照が局所的ではありません。この関数はデバッグ ビルドでは便利であり、ASSERT 呼び出しなどで使用されます。ただし、リリース ビルドでの使用は避けてください。
PreTranslateMessage PreTranslateMessage は、1 つのウィンドウ ツリーで異なるキーボード アクセラレータが必要なとき、またはメッセージ ポンプを挿入する必要があるときに使用します。PreTranslateMessage を使用すると、MFC のディスパッチ メッセージが変更されます。PreTranslateMessage のオーバーライドは、必要なレベルに対してだけ行うようにします。たとえば、あるビューの子ビューに送信するメッセージだけが必要な場合は、CMainFrame::PreTranslateMessage をオーバーライドする必要はありません。そのビュー クラスの PreTranslateMessage をオーバーライドするだけで済みます。
PreTranslateMessage を使用してすべてのウィンドウに送信されるメッセージを処理することによって、正常なディスパッチ パスを妨げることは避けてください。その必要がある場合は、ウィンドウ プロシージャと MFC メッセージ マップを使用します。
OnIdle アイドル イベントは、WM_KEYDOWN イベントと WM_KEYUP イベントの間など、予期しない時点で発生する場合があります。コードを実行するには、タイマを使用する方が効率的です。OnIdle を強制的に繰り返し呼び出すために、誤ったメッセージを生成したり、OnIdle をオーバーライドして常に TRUE を返したりしないでください。スレッドをスリープ状態にできなくなります。この場合も、タイマや独立したスレッドを使用する方が適切です。
共有ライブラリ
コードの再利用が望ましい場合があります。ただし、ほかのプログラマが作成したコードを使用する場合は、パフォーマンスに対するそのコードの影響について正確に把握しておく必要があります。ほかのプログラマのコードについて理解する最良の方法は、ソース コードをステップごとに実行したり、PView やパフォーマンス モニタなどのツールを使用してパフォーマンスを測定することです。
ヒープ
複数のヒープを使用する場合は、細心の注意が必要です。HeapCreate および HeapAlloc を使用して追加のヒープを作成したら、割り当てた領域を管理し、使い終わったら解放します。メモリを過剰にコミットしないでください。複数のヒープを使用する場合は、最初にコミットしたメモリ量に常に細心の注意を払ってください。
複数のヒープを使用する代わりに、ヘルパ関数をコードと既定のヒープ間のインターフェイスにすることができます。ヘルパ関数を使用して独自のメモリ割り当て方法を実現することによって、アプリケーションのパフォーマンスを向上させることができます。たとえば、小さなメモリ割り当てを頻繁に実行する場合は、割り当てを既定のヒープの一部から行います。最初に大きなメモリ ブロックを割り当て、次にヘルパ関数を使用してそのブロックから小さなブロックを割り当てることができます。このように既定のヒープからメモリ割り当てを行うと、未使用のメモリで追加のヒープ領域を作る必要がなくなります。
これに対し、既定のヒープを使用すると、予想以上にデータ参照の局所性が低下する場合があります。プロセス ビューア、Spy++、またはパフォーマンス モニタを使用して、ヒープ間でオブジェクトを移動した場合の影響を測定してください。
ヒープ上のすべての割り当てを明らかにするには、ヒープを測定します。C ランタイムのデバッグ ヒープ ルーチンを使用すると、チェックポイントを設定し、ヒープをダンプできます。出力を Microsoft Excel などのスプレッドシート プログラムに読み込み、ピボット テーブル形式で確認できます。また、割り当てたメモリの数とサイズの合計や、割り当て分布を知ることができます。これらの結果をワーキング セットのサイズと比較します。また、サイズからオブジェクトをクラスタリングします。
メモリの使用量は、パフォーマンス カウンタで調べることもできます。
スレッド
バックグラウンド タスクに対しては、スレッドを使用するよりも、イベントのアイドル処理を効率的に利用する方が高速になる場合があります。シングルスレッド プログラムでは、データ参照の局所性を簡単に管理できます。
おおよその方針としては、ブロックする必要があるオペレーティング システムからの通知がバックグラウンド処理の根幹となっている場合に限り、スレッドを使用します。このような場合にはスレッドを使うのが最良の方法であり、あるイベントのメイン スレッドをブロックするのは実際的ではありません。
スレッドを使用すると通信上の問題も発生します。スレッド間の通信リンクを管理するために、メッセージ リストを使用したり、共有メモリを割り当てたりする必要があります。また、競合状態やデッドロックの問題を回避するために同期が必要になります。このような処理は複雑であるため、バグやパフォーマンス低下の原因になります。
詳細については、「アイドリング ループ処理」および「マルチスレッド」を参照してください。
小さなワーキング セット
ワーキング セットが小さいほど、データ参照の局所性が高くなり、ページ フォールトが減り、キャッシュのヒット率が高くなります。オペレーティング システムが直接提供しているプロセス ワーキング セットは、データ参照の局所性の正否を判断するうえで最良の尺度です。
ワーキング セットの上限と下限を設定するには、SetProcessWorkingSetSize を使用します。
ワーキング セットの上限と下限の値を取得するには、GetProcessWorkingSetSize を使用します。
ワーキング セットのサイズを表示するには、Spy++ を使用します。