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

  • [アーティクル]

実行が速いコードを書くには、アプリケーションのすべての側面およびシステムとのやり取りを理解する必要があります。 この記事では、コードのタイム クリティカルな部分が適切に動作することを保証するために役立つ、より明確なコーディング手法の一部に代わる方法を提案します。

要約すると、タイム クリティカルなコードを改善するには、次を行う必要があります。

  • プログラムのどの部分を高速にする必要があるかを知る。

  • コードのサイズと速度を知る。

  • 新しい機能のコストを知る。

  • ジョブを完了するために必要な最小限の作業を知る。

コードのパフォーマンスに関する情報を収集するには、パフォーマンス モニター (perfmon.exe) を使うことができます。

この記事のセクション

キャッシュ ミスとページ フォールト

ミスしたキャッシュ ヒット (内部および外部キャッシュの両方) およびページ フォールト (プログラムの命令とデータのために 2 次的なストレージに行く) は、プログラムのパフォーマンスを遅らせます。

CPU キャッシュ ヒットでは、プログラムで 10-20 クロック サイクルが必要になります。 外部キャッシュ ヒットでは、20-40 クロック サイクルが必要になります。 ページ フォールトには、100 万クロック サイクルのコストがかかる場合があります (5 億命令/秒を処理するプロセッサと、ページ フォールトに対して 2 ミリ秒の時間を処理するプロセッサを想定)。 そのため、キャッシュ ヒットのミスやページ フォールトの数を減らすコードを書くことが、プログラムの実行に大きく役立ちます。

プログラムが遅いことの一因に、必要以上にページ フォールトの回数やキャッシュ ミスの回数が多いことがあります。 この問題を回避するには、参照の局所性が良好なデータ構造を使用することが重要です。つまり、関連するものを一緒に保持します。 データ構造が優れているように見えても、参照場所が良くないため、実は劣った構造であったり、その逆もあります。 次に 2 つの例を挙げます。

  • 動的に割り当てられたリンク リストにより、プログラムのパフォーマンスが低下する可能性があります。 アイテムを検索するとき、またはリストを最後まで走査すると、スキップされた各リンクがキャッシュを見逃したり、ページ エラーが発生したりする可能性があります。 キャッシュが向上し、ページ フォールトが少なくなるため、単純な配列に基づくリストの実装が高速になる場合があります。 配列の拡張が困難になるという事実を許容したとしても、それはまだ速いかもしれません。

  • 動的に割り当てられたリンク リストを使うハッシュ テーブルはパフォーマンスを低下させる可能性があります。 その延長で、動的に割り当てられたリンク リストを使ってコンテンツを保存するハッシュ テーブルは、パフォーマンスがさらに劣る可能性があります。 最終的には、配列を使った単純な一方向の検索のほうが実際には速い場合があります (状況に応じて)。 配列ベースのハッシュ テーブル (いわゆる "閉じたハッシュ") の使用は、見過ごされがちな実装であり、パフォーマンスが優れていることがよくあります。

並べ替えと検索

並べ替えは、多くの一般的な操作と比べて本質的に時間がかかります。 不必要な遅延を避ける最善の方法は、重要な時間帯に並べ替えを避けることです。 次を行うことができます。

  • パフォーマンスに重要な影響が及ばない時間帯になるまで並べ替えを待つ。

  • 前もってパフォーマンスに重要な影響が及ばない時間帯にデータを並べ替える。

  • 並べ替えが本当に必要な部分だけデータを並べ替える。

並べ替えられた順番でリストをビルドできる場合があります。 ただし、並べ替えられた順番でデータを挿入する必要がある場合、より複雑なデータ構造が必要となって参照場所の配置が悪くなる可能性があり、キャッシュ ミスやページ フォールトにつながるため注意する必要があります。 すべてのケースで動作するアプローチはありません。 いくつかの方法を試してみて、違いを測定します。

並べ替えに関する一般的なヒントを次に示します。

  • ストックの並べ替えを使ってバグを最小限にします。

  • 並べ替えの複雑さを軽減するために事前に行える作業は、実行する価値があります。 データを 1 回だけ渡すと比較が簡略化され、O(n log n) から O(n) への並べ替えが減る場合は、ほぼ確実に先に進みます。

  • 並べ替えアルゴリズムの参照場所と実行対象のデータについて考えます。

検索の場合、並べ替えと比べて代替方法が少なくなります。 検索がタイム クリティカルな場合、バイナリ検索またはハッシュ テーブル ルックアップがほとんどいつも最善の方法となりますが、並べ替えの場合と同じく、場所も考慮する必要があります。 小さな配列を使用した線形検索は、ページ フォールトやキャッシュ ミスを引き起こす多くのポインターを持つデータ構造を使用したバイナリ検索よりも高速です。

MFC とクラス ライブラリ

Microsoft Foundation Classes (MFC) は、コードの作成を大幅に簡略化します。 タイム クリティカルなコードを作成する場合、一部のクラスに特有のオーバーヘッドについて理解する必要があります。 タイム クリティカルなコードが使用する MFC コードがパフォーマンス要件を満たしているかどうか確認します。 次は、知っておく必要のある MFC クラスと関数の一覧です。

  • CString MFC は C ランタイム ライブラリを呼び出して、メモリ CString を動的に割り当てます。 一般に、 CString 他の動的に割り当てられた文字列と同じくらい効率的です。 また他の動的に割り当てられた文字列と同様に、動的な割り当てとリリースのオーバーヘッドがあります。 多くの場合、スタック上のシンプルな char 配列を使用して、同じ処理をより高速に実行できます。 定数文字列を保存するのに CString は使用しません。 const char * を代わりに使用します。 CString オブジェクトで行う操作には何らかのオーバーヘッドがあります。 ランタイム ライブラリの文字列機能を使用するほうが速い可能性があります。

  • CArray A CArray は、通常の配列にはない柔軟性を提供しますが、プログラムでは必要ない場合があります。 配列に特定の制限があることを知っている場合、代わりにグローバル固定配列を使用できます。 CArray を使用する場合、CArray::SetSize を使ってそのサイズを設定し、要素の数を指定します。再割り当てが必要なときにはこれを利用して拡張します。 それ以外の場合、要素を追加すると配列に対して頻繁に再割り当てとコピーが行われるため、非効率的となり、メモリが断片化されます。 また、配列に項目を挿入する場合は、後続の項目をメモリ内に移動し、 CArray 配列を拡張する必要がある場合があります。 これらの操作によって、キャッシュ ミスやページ フォールトが生じることがあります。 MFC が使用するコードを見直すと、自分のシナリオに応じてより具体的に記述することで、パフォーマンスを向上できる可能性があります。 CArray はテンプレートであるため、たとえば特定の型に応じて CArray 特殊化することもできます。

  • CListCList は二重にリンクされたリストであるため、要素の挿入は頭、尾、およびリスト内の既知の位置 (POSITION) で高速です。 要素を値またはインデックスで検索する場合、順次検索が必要となり、リストが長い場合は遅くなります。 コードで二重にリンクされたリストが必要ない場合は、次を使用して CList再考することができます。 個別にリンクされたリストを使用すると、すべての操作に対して別のポインターを更新するオーバーヘッドと、そのポインターのメモリが節約されます。 余分なメモリは大きくありませんが、キャッシュ ミスやページ フォールトのもう 1 つの機会です。

  • IsKindOf この関数は多数の呼び出しを生成でき、異なるデータ領域のメモリにアクセスし、参照のローカリティが悪くなります。 デバッグ ビルド (AS Standard Edition RT 呼び出しなど) には便利ですが、リリース ビルドでは使用しないようにしてください。

  • PreTranslateMessage ウィンドウの特定のツリーが異なるキーボード アクセラレータを必要とする場合、またはメッセージ ポンプにメッセージ処理を挿入する必要がある場合に、PreTranslateMessage を使用します。 PreTranslateMessage は MFC ディスパッチ メッセージを変えます。 PreTranslateMessage をオーバーライドする場合、必要なレベルでのみ行います。 たとえば、特定のビューの子に送信されるメッセージにのみ関心がある場合は、オーバーライド CMainFrame::PreTranslateMessage する必要はありません。 代わりに、ビュー クラスの PreTranslateMessage をオーバーライドします。

    任意のウィンドウに送信されたメッセージを処理するために使用 PreTranslateMessage して、通常のディスパッチ パスを回避しないでください。 その目的用に、ウィンドウ プロシージャおよび MFC メッセージ マップを使用します。

  • OnIdle アイドル 状態のイベントは、間 WM_KEYDOWN や WM_KEYUP イベントなど、予期しない場合に発生する可能性があります。 コードをトリガーするには、タイマーのほうがより効果的な場合があります。 OnIdle誤ったメッセージを生成したり、常にオーバーライドOnIdleから戻TRUEったりして繰り返し呼び出されないようにしてください。これにより、スレッドがスリープ状態になることはありません。 ここでも、タイマーまたは個別のスレッドのほうが適切な場合があります。

共有ライブラリ

望ましいのはコードを再利用することです。 ただし、他のユーザーのコードを使用する場合は、パフォーマンスが重要な場合に何が行われるかを正確に把握しておく必要があります。 これを理解する最善の方法は、ソース コードをステップ実行するか、PView や パフォーマンス モニター などのツールを使用して測定することです。

ヒープ

複数のヒープを思慮深く使用します。 HeapCreate および HeapAlloc で作成した追加のヒープにより、関連する割り当てのセットを管理し、破棄することができます。 過多のメモリをコミットしないようにします。 複数のヒープを使用する場合、最初にコミットするメモリの量に特に注意します。

複数のヒープを使用する代わりに、ヘルパー機能を使ってコードと既定のヒープを相互作用させることができます。 ヘルパー機能はカスタム割り当て戦略を促進して、アプリケーションのパフォーマンスを改善することができます。 たとえば、小さな割り当てを頻繁に行う場合、これらの割り当てを既定のヒープの一部にローカライズすることができます。 メモリの大きなブロックを割り当てた後、ヘルパー機能を使ってそのブロックからサブ割り当てすることができます。 その後、割り当てが既定のヒープから出てくるため、未使用のメモリを持つ複数のヒープはありません。

ただし、場合によっては既定のヒープを使うことで参照場所を減らせる場合があります。 Process Viewer、Spy++、またはパフォーマンス モニターを使って、オブジェクトをヒープからヒープへ移動させる影響を測定します。

ヒープを測定して、ヒープ上のすべての割り当てを把握します。 C ランタイムのデバッグ ヒープ ルーチンを使用して、ヒープのチェックポイントとダンプを行います。 出力を Microsoft Excel などのスプレッドシート プログラムに読み込ませ、ピボット テーブルを使って結果を表示できます。 割り当ての合計数、サイズ、および分布を確認します。 これらの結果をワーキング セットのサイズと比較します。 また、関連サイズのオブジェクトのクラスタリングも確認します。

さらに、パフォーマンス カウンターでメモリの使用量を監視できます。

スレッド

バックグラウンド タスクの場合、スレッドを使用するよりも、イベントの効果的なアイドル処理のほうが速い可能性があります。 シングル スレッド プログラムのほうが参照場所を理解しやすくなります。

経験則として、ブロックするオペレーティング システムの通知がバックグラウンド作業のルートにある場合にのみ、スレッドを使用します。 スレッドは、イベントでメインスレッドをブロックすることは実用的ではないので、このような場合に最適なソリューションです。

また、スレッドは通信問題を引き起こす場合があります。 メッセージのリストまたは共有メモリの割り当てと使用によって、スレッド間の通信リンクを管理する必要があります。 通信リンクの管理には、競合状態やデッドロック問題を回避するために、通常は同期が必要です。 この複雑さのせいで、バグやパフォーマンスの問題が簡単に生じ得ます。

詳細については、「アイドリング ループ処理」とマルチスレッドに関する記事を参照してください。

小さな作業セット

作業セットが小さいと、参照場所が向上し、ページ フォールトが少なくなり、キャッシュ ヒットが増えます。 プロセス作業セットは、オペレーティング システムが参照場所を測定するために直接提供する最も近いメトリックです。

  • 作業セットの上限と下限を設定するには、SetProcessWorkingSetSize を使用します。

  • 作業セットの上限と下限を取得するには、GetProcessWorkingSetSize を使用します。

  • 作業セットのサイズを表示するには、Spy++ を使用します。

関連項目

コードの最適化