次の方法で共有

   タイム クリティカルなコードを高速化するためのヒント

  • [アーティクル]

タイム クリティカルなコード、つまりプログラム全体の実行速度を決定するコードを高速化するには、あらゆる面から注意深くコードを分析し、そのコードがシステムとどのようにやり取りしているかを調べる必要があります。ここでは、プログラムを高速化するための、コードを修正する方法について説明します。

タイム クリティカルなコードを高速化するには、次の点を確認します。

  • プログラムのどの部分を高速化すべきか。
  • コードのサイズと実行速度はどのくらいか。
  • 新しい機能にかかるコストはどのくらいか。
  • 処理を完了するのに最小限どのくらいの作業が必要か。

キャッシュのミスとページ違反

内部キャッシュおよび外部キャッシュがヒットしなかった場合も、プログラム命令やデータを 2 次記憶装置に検索に行くページ違反が発生した場合と同様に、プログラムのパフォーマンスが低下します。

CPU キャッシュがヒットしなかった場合は、10-20 クロック分のロスが発生すると計算されます。外部キャッシュがヒットしなかった場合は、20-40 クロック分のロス、ページ違反が発生した場合は 100 万命令分のロスが生じます。したがって、プログラムを高速化するには、キャッシュのミスヒットとページ違反を減らすことに最大限の注意を払う必要があります。

プログラムが遅い原因の 1 つとして、必要以上にページ違反やキャッシュのミス ヒットが発生していることが考えられます。これを避けるには、データ参照の局所性が高いデータ構造を使用すること、つまり関連のあるデータをまとめておくことが重要です。一見優れているように見えるデータ構造でも、データ参照の局所性が低いためにパフォーマンスが悪くなってしまうこともあれば、逆にあまり優れているように見えないデータ構造でも、データ参照の局所性が高いために高速になることもあります。次に、例を 2 つ挙げます。

  • 動的メモリ割り当てで作成されたリンク リストは、プログラムのパフォーマンスを低下させる原因になります。リスト中の要素を検索したり、リストを最後まで走査するような場合、リンクをたどるたびにキャッシュのミスヒットやページ違反が発生することがあるからです。実際、単純な配列でインプリメントしたリストの方が、キャッシュが有効に働いてページ違反の回数が減るので、はるかに高速です。配列のサイズを拡張する際に余分な処理が必要になることを考慮しても、やはりこの方法が高速です。
  • 動的メモリ割り当てで作成されたリンク リストを使用したハッシュ テーブルも、パフォーマンスを低下させる原因になります。このようなリンク リストにハッシュ テーブルの内容だけが格納されている場合でも、予想以上にパフォーマンスが低下する場合があります。実際、配列を使った単純な線形検索の方が最終的には高速だったという例もあります。配列を使ったハッシュ テーブル、いわゆるクローズド ハッシュ法は見落とされがちですが、パフォーマンス的には優れた方法です。

ソートとサーチ

ソート (並べ替え) はほかの典型的な処理と比較して本質的に時間がかかります。ソートが原因で遅くなっているコードを高速化する最良の方法は、ソートをまったく行わなくて済む方法を見つけることです。

  • ソートは、パフォーマンスに影響しないタイミングで行うことができる場合がある。
  • 本当にソートする必要があるのは、データのほんの一部にすぎない場合がある。
  • 後でより簡単にソートを行うための情報が、どこかで取得されていた場合がある。

ソートされた順序でリストを作ることもできますが、これは全体的な速度を低下させることになります。新しい要素を順にリストに挿入していくと、データ構造の局所性が低くなってしまうからです。簡単には最良の解決策が見つからないかもしれませんが、いろいろな方法を試して違いを測定してみてください。

ソートを行う必要がある場合は、次の点に注意します。

  • 既存のライブラリのソート関数を使うこと。
  • ソートを行う前に、ソート中に行う必要のある作業をできる限り単純化しておくこと。たとえば、最初のソート アルゴリズムの計算量が O(n log n) であったとしても、データ比較処理を単純化しておけば、計算量を O(n) にすることができる場合があります。
  • ソート対象のデータの形式と照らし、現在使用しているソート アルゴリズムがデータ参照の局所性を保っているかどうかを考慮すること。

サーチのパフォーマンスを向上させる方法は、ソートの場合ほど多くありません。通常、サーチがタイム クリティカルな場合は、バイナリ検索つまりハッシュ法を使用します。ただし、繰り返しますが、データ参照の局所性を保つように心がけてください。小さな配列を用いた線形検索の方が、データ構造の特性上多くのポインタを持つバイナリ検索よりも高速である場合があります。後者はページ違反やキャッシュのミス ヒットを発生させることがあるからです。

MFC とそのほかのクラス ライブラリ

MFC (Microsoft Foundation Class) ライブラリは、コーディングを簡単にするためのフレームワークを提供します。タイム クリティカルなコードを記述する場合、クラスによってはオーバーヘッドが生じることを知っておく必要があります。タイム クリティカルな部分で使用する MFC のコードを調べ、それが要求されるパフォーマンスに見合うものかどうかを判断します。以下は、MFC において理解しておく必要のあるパフォーマンスについての注意点です。

  • CString   MFC は C ランタイム ライブラリを呼び出して CString のメモリを動的に割り付けます。文字列を動的に割り当てた場合と同様、メモリの割り当てや解放のためのオーバーヘッドを負うことになるため、同じ目的を果たすにはスタック上の単純な char 型の配列を使った方が通常は高速です。単に文字列定数を格納するためだけに CString を使用しないでください。文字列定数には const char * を使用します。CString オブジェクトを使用して行う処理にはどれも、パフォーマンスに大きな影響を与えるオーバーヘッドが伴うことを忘れないでください。ランタイム ライブラリの文字列処理関数を使用した方が高速化できるかもしれません。

  • CArray   CArray は、通常の配列にはない機能を提供します。配列の上限がわかっている場合は、CArray を使う必要はありません。グローバルな固定サイズの配列を使えば済みます。CArray を使う場合は、CArray::SetSize 関数を使用してそのサイズと再割り当て時の増加要素数を指定します。SetSize を使用しないと、要素を追加するたびにメモリの再割り当てとコピーが行われます。その結果、実行速度が低下してメモリが断片化してしまいます。また、配列に要素を挿入すると、その要素よりも後ろにある要素がメモリ上で移動するので注意してください。移動する前に、CArray のサイズを拡張する必要があるかもしれません。これらの処理はいずれもキャッシュのミス ヒットとページ違反の可能性を増やします。これは CArray クラスのメンバ関数を使用した場合に起こる問題の、ほんの一例です。MCF を使用したコードをステップごとに実行して、コードのパフォーマンスを向上させるために何が必要かを確認してください。たとえば、CArray はテンプレートなので、特定の型に対して特別な CArray を用意することも考えられます。

  • CList   CList は双方向のリンク リストなので、リストの先頭、末尾、および特定の既知の位置への要素の挿入が高速です。ただし、値や位置によって要素を検索するには、順次検索が必要になります。これはリストが長くなると時間がかかります。単方向のリンク リストで十分な場合は、CList を使う必要があるかどうか再検討してください。双方向のリンク リストは、余分なポインタのためにメモリを消費するうえ、ポインタを更新するためにオーバーヘッドがかかります。余分なメモリを消費すること自体は通常あまり問題になりませんが、キャッシュのミス ヒットやページ違反を増やす原因になります。

  • IsKindOf   この関数は多くの関数呼び出しを行って、異なるデータ領域にあるさまざまなメモリにアクセスすることがあります。つまり、データ参照が局所的ではありません。MCF のソース コードをステップごとに実行してみると、その様子がわかります。IsKindOf 関数はデバッグ ビルドに有用であり、たとえば ASSERT 呼び出しの中で使われています。ただし、リリース ビルドでの使用はお勧めしません。

  • PreTranslateMessage   PreTranslateMessage 関数は 1 つのウィンドウ ツリーで、異なるキーボード アクセラレータが必要な場合に使用します。また、PreTranslateMessage を使用して、メッセージ ポンプにメッセージ ハンドラを挿入することもできます。PreTranslateMessage は、MFC のメッセージ ディスパッチ方法を変更するための手段として認められています。PreTranslateMessage のオーバーライドは、最小限必要なレベルに対してだけ行うように注意してください。たとえば、あるビューの子ビューに送られるメッセージだけが必要な場合は、CMainFrame::PreTranslateMessage をオーバーライドする必要はありません。そのビューの PreTranslateMessage をオーバーライドするだけでかまいません。

    PreTranslateMessage を使用して、すべてのウィンドウに送られるあらゆるメッセージを処理し、正常なディスパッチ パスを妨げることを避けてください。その必要がある場合は、ウィンドウ プロシージャと MFC メッセージ マップを使用してください。

  • OnIdle   アイドル イベントは、WM_KEYDOWN イベントと WM_KEYUP イベント間など、予期しない時点で発生する場合があります。希望する動作を開始するには、タイマーを使う方が効率的です。また、OnIdle を強制的に繰り返し呼び出すために、誤ったメッセージを生成したり、OnIdle 関数をオーバーライドして常に TRUE を返すようにするのは避けてください。そのスレッドをスリープ状態にすることができなくなるからです。繰り返しますが、ほとんどの場合はタイマーや独立したスレッドを使う方が適切です。

ヒープ

複数のヒープを使う場合は、細心の注意が必要です。HeapCreate 関数と HeapAlloc 関数を使って追加のヒープを作成したら、それらの領域を自分で管理し、使い終わったら解放する必要があります。メモリを必要以上に確保するのは望ましいことではありません。複数のヒープを使用する場合は、最初に割り当てたメモリ量に常に細心の注意を払ってください。

複数のヒープを使用する代わりに、既定のヒープを補助関数 (ヘルパー関数) で隠ぺいする方法もあります。その場合は、コードと既定のヒープ間のインターフェイスを取る補助関数を記述します。補助関数を使用して独自のメモリ割り当て方法を実現することによって、アプリケーションのパフォーマンスを向上させることができます。たとえば、小さなメモリ割り当てを頻繁に行う場合は、これらの割り当てを既定のヒープの一部から取得します。最初に大きなメモリ ブロックを確保しておいて、次に補助関数を使用してそこから小さなメモリ ブロックを割り当てます。

これに対し、既定のヒープを使用すると、予想以上にデータ参照の局所性が低下する場合があります。 Windows CE Remote Process Viewer、Windows CE Remote Spy、Windows CE Remote Heap Walkedd などのツールを使用して、ヒープからヒープへ移動した場合の影響を実際に測定してください。

ヒープ上のすべての割り当てを明らかにするには、ヒープを測定します。C ランタイム ライブラリのヒープ デバッグ用ルーチンを使用して、チェックポイントごとにヒープの内容をダンプできます。その出力結果は、Excel に取り込むことができ、ピボット テーブル形式で確認できます。また、割り当てたメモリの数とサイズの合計や、割り当て分布を知ることができます。これらの結果をワーキング セットのサイズと比較したり、サイズからオブジェクトをクラスタリングしてみても有益かもしれません。

メモリの使用量は、Windows NT パフォーマンス モニタで調べることもできます。

スレッド

バックグラウンド処理が必要な場合、スレッドが最良の方法とは限りません。イベントのアイドル ハンドラを効果的に利用する方がよい場合もあります。複数のスレッドを持つプログラムよりも 1 つのスレッドしか持たないプログラムの方がデータ参照の局所性の管理が容易です。

おおよその方針としては、ブロックする必要があるオペレーティング システムからの通知が、バックグラウンド処理の根幹となっている場合に限り、スレッドを使うようにします。このような場合にはスレッドを使うのが最良の方法であり、あるイベントのメイン スレッドをブロックするのは現実的ではありません。

スレッドを使用すると通信上の問題も発生します。スレッド間の通信リンクを管理するために、メッセージ リストを使用したり、共有メモリを割り当てることになります。また、競合やデッドロックを避けるために同期化する必要もあります。このような処理は複雑なので、バグやパフォーマンス低下の原因になります。

小さなワーキング セット

ワーキング セットが小さければ小さいほど、ページ違反が減り、キャッシュのヒット率が増します。オペレーティング システムが直接提供しているプロセス ワーキング セットは、データ参照の局所性の善し悪しを測定する上で最良の尺度です。

  • ワーキング セットの上限と下限を設定するには、SetProcessWorkingSetSize を使用します。
  • ワーキング セットの上限と下限を取得するには、GetProcessWorkingSetSize を使用します。
  • ワーキング セットのサイズを表示するには、Windows CE Remote Spy または Windows CE Remote Process Viewer を使用します。