タイムクリティカルなコードを高速化するためのヒント
実行が速いコードを書くには、アプリケーションのすべての側面およびシステムとのやり取りを理解する必要があります。 この記事では、コードのタイム クリティカルな部分が適切に実行されることを保証するのに役立つ、よく知れ渡っているコーディング テクニックとは違う選択肢を提案します。
要約すると、タイム クリティカルなコードを改善するには、次を行う必要があります。
プログラムのどの部分を高速にする必要があるかを知る。
コードのサイズと速度を知る。
新しい機能のコストを知る。
ジョブを完了するために必要な最小限の作業を知る。
コードのパフォーマンスに関する情報を収集するには、パフォーマンス モニター (perfmon.exe) を使うことができます。
この記事のセクション
キャッシュ ミスとページ フォールト
ミスしたキャッシュ ヒット (内部および外部キャッシュの両方) およびページ フォールト (プログラムの命令とデータのために 2 次的なストレージに行く) は、プログラムのパフォーマンスを遅らせます。
CPU キャッシュ ヒットでは、プログラムで 10-20 クロック サイクルが必要になります。 外部キャッシュ ヒットでは、20-40 クロック サイクルが必要になります。 ページ フォールトでは、100 万クロック サイクルが必要になる場合があります (プロセッサが毎秒 5 億の命令を処理し、ページ フォールトで 2 ミリ秒かかると仮定)。 そのため、キャッシュ ヒットのミスやページ フォールトの数を減らすコードを書くことが、プログラムの実行に大きく役立ちます。
プログラムが遅いことの一因に、必要以上にページ フォールトの回数やキャッシュ ミスの回数が多いことがあります。 この問題を回避するには、参照の局所性が良好なデータ構造を使用することが重要です。つまり、関連するものをまとめて保持します。 データ構造が優れているように見えても、参照場所が良くないため、実は劣った構造であったり、その逆もあります。 次に 2 つの例を挙げます。
動的に割り当てられたリンク リストにより、プログラムのパフォーマンスが低下することがあります。 項目を検索する際、またはリストを最後まで走査する際に、スキップされた各リンクがキャッシュを見逃す、またはページ フォールトが発生することがあります。 単純な配列に基づくリストの実装は、キャッシュが向上し、ページ フォールトが少なくなるため、より高速になる可能性があります。 配列の拡張が困難になるという事実を考慮しても、それでもより高速になる可能性があります。
動的に割り当てられたリンク リストを使うハッシュ テーブルはパフォーマンスを低下させる可能性があります。 その延長で、動的に割り当てられたリンク リストを使ってコンテンツを保存するハッシュ テーブルは、パフォーマンスがさらに劣る可能性があります。 最終的には、配列を使った単純な一方向の検索のほうが実際には速い場合があります (状況に応じて)。 配列ベースのハッシュ テーブル (いわゆる「クローズド ハッシュ」) の使用は、見過ごされがちな実装ですが、多くの場合でより優れたパフォーマンスを発揮します。
並べ替えと検索
並べ替えは、多くの一般的な操作と比べて本質的に時間がかかります。 不必要な遅延を避ける最善の方法は、重要な時間帯に並べ替えを避けることです。 次を行うことができます。
パフォーマンスに重要な影響が及ばない時間帯になるまで並べ替えを待つ。
前もってパフォーマンスに重要な影響が及ばない時間帯にデータを並べ替える。
並べ替えが本当に必要な部分だけデータを並べ替える。
並べ替えられた順番でリストをビルドできる場合があります。 ただし、並べ替えられた順番でデータを挿入する必要がある場合、より複雑なデータ構造が必要となって参照場所の配置が悪くなる可能性があり、キャッシュ ミスやページ フォールトにつながるため注意する必要があります。 すべてのケースにおいて効果的なアプローチはありません。 いくつかの方法を試してみて、違いを測定します。
並べ替えに関する一般的なヒントを次に示します。
ストックの並べ替えを使ってバグを最小限にします。
並べ替えの複雑さを軽減するために事前に行える作業は、実行する価値があります。 データを一度だけ渡すことにより比較が単純化され、並べ替えが O(n log n) から O(n) に減る場合は、ほぼ確実に効果が出ます。
並べ替えアルゴリズムの参照場所と実行対象のデータについて考えます。
検索の場合、並べ替えと比べて代替方法が少なくなります。 検索がタイム クリティカルな場合、バイナリ検索またはハッシュ テーブル ルックアップがほとんどいつも最善の方法となりますが、並べ替えの場合と同じく、場所も考慮する必要があります。 ページ フォールトまたはキャッシュ ミスを引き起こす多くのポインターを含むデータ構造を使用したバイナリ検索よりも、小さな配列を線型検索するほうが、より高速になる可能性があります。
MFC とクラス ライブラリ
Microsoft Foundation Classes (MFC) は、コードの作成を大幅に簡略化します。 タイム クリティカルなコードを作成する場合、一部のクラスに特有のオーバーヘッドについて理解する必要があります。 タイム クリティカルなコードが使用する MFC コードがパフォーマンス要件を満たしているかどうか確認します。 次は、知っておく必要のある MFC クラスと関数の一覧です。
CStringMFC は C ランタイム ライブラリを呼び出して、CStringにメモリを動的に割り当てます。 一般にCStringは、他の動的に割り当てられる文字列と同じくらい効率的です。 また他の動的に割り当てられた文字列と同様に、動的な割り当てとリリースのオーバーヘッドがあります。 多くの場合、スタック上のシンプルなchar配列を使用して、同じ処理をより高速に実行できます。 定数文字列を保存するのにCStringは使用しません。 代わりにconst char *を使用してくださいCStringオブジェクトで行う操作には何らかのオーバーヘッドがあります。 ランタイム ライブラリの文字列機能を使用するほうが速い可能性があります。CArrayCArrayでは通常の配列にはない柔軟性が提供されますが、プログラムには必要ない場合があります。 配列に特定の制限があることを知っている場合、代わりにグローバル固定配列を使用できます。CArrayを使用する場合、CArray::SetSizeを使ってそのサイズを設定し、要素の数を指定します。再割り当てが必要なときにはこれを利用して拡張します。 それ以外の場合、要素を追加すると配列に対して頻繁に再割り当てとコピーが行われるため、非効率的となり、メモリが断片化されます。 また、配列に項目を挿入すると、CArrayは後続の項目をメモリ内に移動し、配列を増やす必要が生じる場合があります。 これらの操作によって、キャッシュ ミスやページ フォールトが生じることがあります。 MFC が使用するコードを見直すと、自分のシナリオに応じてより具体的に記述することで、パフォーマンスを向上できる可能性があります。CArrayはテンプレートであるため、たとえば特定の型に応じてCArray特殊化することもできます。CListCListは二重リンク リストであるため、要素の挿入はリスト内の先頭、末尾、既知の位置 (POSITION) では高速です。 要素を値またはインデックスで検索する場合、順次検索が必要となり、リストが長い場合は遅くなります。 コードで二重リンク リストが必要ない場合は、CListの使用を再検討することをお勧めします。 単一リンク リストを使用すると、すべての操作に対して別のポインターを更新するオーバーヘッドと、そのポインターのメモリが節約されます。 その余分なメモリは大きくはありませんが、キャッシュ ミスやページ フォールトが発生する可能性があります。IsKindOfこの関数は、多数の呼び出しを生成し、異なるデータ領域内でメモリにアクセスする可能性があるため、参照の局所性が悪くなる場合があります。 これはデバッグ ビルド (ASSERT 呼び出し内など) では有用ですが、リリース ビルド内では使用しないようにしてください。PreTranslateMessageウィンドウの特定のツリーが異なるキーボード アクセラレータを必要とする場合、またはメッセージ ポンプにメッセージ処理を挿入する必要がある場合に、PreTranslateMessageを使用します。PreTranslateMessageは MFC ディスパッチ メッセージを変えます。PreTranslateMessageをオーバーライドする場合、必要なレベルでのみ行います。 たとえば、特定のビューの子に届くメッセージのみに関心がある場合は、CMainFrame::PreTranslateMessageをオーバーライドする必要はありません。 代わりに、ビュー クラスのPreTranslateMessageをオーバーライドします。PreTranslateMessageを使用して、任意のウィンドウに送信された任意のメッセージを処理するために、通常のディスパッチ パスを迂回しないでください。 その目的用に、ウィンドウ プロシージャおよび MFC メッセージ マップを使用します。OnIdleアイドル イベントは、WM_KEYDOWNとWM_KEYUPイベントの間など、予期しないタイミングで生じる場合があります。 コードをトリガーするには、タイマーのほうがより効果的な場合があります。 誤ったメッセージを生成する、またはOnIdleのオーバーライドから常にTRUEを返すことで、繰り返しOnIdleを強制的に呼び出さないでください (さもなければ、スレッドがスリープできなくなります)。 ここでも、タイマーまたは個別のスレッドのほうが適切な場合があります。
共有ライブラリ
望ましいのはコードを再利用することです。 ただし、他のユーザーのコードを使用する場合は、パフォーマンスが重要なケースで何が行われるかを正確に把握する必要があります。 これを把握する最善の方法は、ソース コードをステップ実行するか、PView またはパフォーマンス モニターなどのツールを使用して測定することです。
ヒープ
複数のヒープを思慮深く使用します。 HeapCreate および HeapAlloc で作成した追加のヒープにより、関連する割り当てのセットを管理し、破棄することができます。 過多のメモリをコミットしないようにします。 複数のヒープを使用する場合、最初にコミットするメモリの量に特に注意します。
複数のヒープを使用する代わりに、ヘルパー機能を使ってコードと既定のヒープを相互作用させることができます。 ヘルパー機能はカスタム割り当て戦略を促進して、アプリケーションのパフォーマンスを改善することができます。 たとえば、小さな割り当てを頻繁に行う場合、これらの割り当てを既定のヒープの一部にローカライズすることができます。 メモリの大きなブロックを割り当てた後、ヘルパー機能を使ってそのブロックからサブ割り当てすることができます。 すると、既定のヒープから割り当てられるため、複数のヒープが未使用のメモリを持つことがなくなります。
ただし、場合によっては既定のヒープを使うことで参照場所を減らせる場合があります。 Process Viewer、Spy++、またはパフォーマンス モニターを使って、オブジェクトをヒープからヒープへ移動させる影響を測定します。
ヒープを測定して、ヒープ上のすべての割り当てを把握します。 C ランタイムのデバッグ ヒープ ルーチンを使用して、ヒープのチェックポイントとダンプを行います。 出力を Microsoft Excel などのスプレッドシート プログラムに読み込ませ、ピボット テーブルを使って結果を表示できます。 割り当ての合計数、サイズ、および分布を確認します。 これらの結果を、ワーキング セットのサイズと比較します。 また、関連サイズのオブジェクトのクラスタリングも確認します。
さらに、パフォーマンス カウンターでメモリの使用量を監視できます。
スレッド数
バックグラウンド タスクの場合、スレッドを使用するよりも、イベントの効果的なアイドル処理のほうが速い可能性があります。 シングル スレッド プログラムのほうが参照場所を理解しやすくなります。
経験則として、ブロックするオペレーティング システムの通知がバックグラウンド作業のルートにある場合にのみ、スレッドを使用します。 イベント上のメイン スレッドをブロックするのは実用的ではないため、このような場合にはスレッドが最適なソリューションです。
また、スレッドは通信問題を引き起こす場合があります。 メッセージのリストまたは共有メモリの割り当てと使用によって、スレッド間の通信リンクを管理する必要があります。 通信リンクの管理には、競合状態やデッドロック問題を回避するために、通常は同期が必要です。 この複雑さのせいで、バグやパフォーマンスの問題が簡単に生じ得ます。
詳細については、「アイドリング ループ処理」とマルチスレッドに関する記事を参照してください。
小さな作業セット
作業セットが小さいと、参照場所が向上し、ページ フォールトが少なくなり、キャッシュ ヒットが増えます。 プロセス作業セットは、オペレーティング システムが参照場所を測定するために直接提供する最も近いメトリックです。
作業セットの上限と下限を設定するには、
SetProcessWorkingSetSizeを使用します。作業セットの上限と下限を取得するには、
GetProcessWorkingSetSizeを使用します。作業セットのサイズを表示するには、Spy++ を使用します。