ヒープ : 喜びと苦悩

  • [アーティクル]

Murali R. Krishnan
Microsoft Corporation

February 1999

概要 : 一般的なヒープ機能の問題についての考察とその対処方法。

はじめに

動的に割り当てられる C/C++ オブジェクトに満足していますか? モジュール間の通信にオートメーションを十分に使用していますか? ヒープの割り当てが原因でプログラムの動きが遅くなっている可能性はありませんか? あなたは 1 人ぼっちではありません。多くのプロジェクトでは、遅かれ早かれヒープの問題が生じてきます。通常は "ヒープが原因で遅いのであって、自分のコードにはまったく問題がない" と言われることが多いようです。なるほど、それも一理あります。ヒープについて、その使用方法と何が起こるかについて詳細に理解しておく価値はあります。

ヒープとは何か?

(既にヒープについての知識がある方は、「一般的なヒープ機能の問題とは?」に進んでください。)

ヒープは、プログラムが使用するオブジェクトを動的に割り当てたり、解放したりしています。ヒープは次のような場合に呼び出されます。

  1. プログラムが必要とするオブジェクトの数や大きさが事前に分からない場合。

  2. オブジェクトが大きすぎて、スタック アロケータに収まらない場合。

ヒープは、実行時にコードやスタックに割り当てられたメモリ以外の部分を使用します。以下の図では、ヒープ アロケータの階層を示しています。

ms810466.heap3(ja-jp,MSDN.10).gif

GlobalAlloc/GlobalFree : Microsoft(R) Win32(R) ヒープ呼び出しでは、処理単位の既定ヒープと直接対話を行います。

LocalAlloc/LocalFree : Win32 ヒープ呼び出し (Microsoft Windows NT(R) での互換性のため) では、処理ごとの既定ヒープと直接対話を行います。

COM の IMalloc アロケータ (または CoTaskMemAlloc/CoTaskMemFree) : 関数はプロセス単位の既定ヒープを使用します。オートメーションでは COM (Component Object Model) のアロケータを使用し、処理単位の既定ヒープを要求します。

CRT (C/C++ Run-time) アロケータ : "new" および "delete" と同様に、"malloc()" および "free()" オペレータを提供します。Microsoft Visual Basic(R) および Java でも、新しいオペレータを提供してヒープの代わりにガーベージ コレクションを使用します。CRT は Win32(R) ヒープ上に独自のプライベート ヒープを作成します。

Windows NT において、Win32 ヒープは Windows NT ランタイム アロケータを取り巻く薄い層です。すべての API は NTDLL へ要求を転送します。

Windows NT ランタイム アロケータは、Windows NT 上にコア ヒープ アロケータを提供します。このアロケータは、8 ～ 1,024 バイトまでの 128 のフリー リストを持つフロントエンド アロケータで構成されています。バックエンド アロケータは仮想メモリを使用してページの予約や保存を行います。

図の下端は仮想メモリ アロケータを示しています。これは OS が使用するページの予約や保存を行います。すべてのアロケータは仮想メモリ機能を使用してデータにアクセスします。

ブロックの割り当てや解放を簡単にする必要はないのでしょうか? なぜ、これほど時間がかかるのでしょうか?

ヒープの実装における注意事項

以前より、オペレーティング システムとランタイム ライブラリにはヒープの実装が含まれていました。OS は最初に "プロセス ヒープ" と呼ばれる既定のヒープを作成します。他にヒープが使用されていない場合、プロセス ヒープがブロックを割り当てます。開発言語のランタイムにおいても、処理中に別のヒープを作成することができます (たとえば、C ランタイムは独自のヒープを作成します)。これらの専用ヒープに加えて、アプリケーション プログラムまたは多くの読み込まれた DLL (ダイナミック リンク ライブラリ) でも別のヒープを作成して使用することがあります。Win32 には、プライベート ヒープを作成して使用するための API が豊富にあります。

アプリケーションや DLL がプライベート ヒープを作成した場合、ヒープは処理スペースに存在し、処理内のいずれからでもアクセスすることができます。与えられたヒープで行われるデータの割り当ては、同じヒープに対して解放される必要があります (ヒープからの割り当てを別のヒープへ解放しても意味がありません)。

すべての仮想メモリ システムでは、ヒープはオペレーティング システムの仮想メモリ マネージャ上に存在します。同様に、開発言語ランタイム ヒープも仮想メモリ上に存在します。場合によってはこれらが OS ヒープの上層になりますが、開発言語ランタイム ヒープは大きなブロックを割り当てることで独自にメモリ管理を行います。OS ヒープを経由せずに仮想メモリ機能を使用することで、ヒープはより効率的に割り当てをしたり、ブロックを使用することができます。

典型的なヒープの実装は、フロントエンドおよびバックエンド アロケータで構成されています。フロントエンド アロケータは、固定サイズ ブロックのフリー リストを保持しています。割り当ての呼び出しにおいて、ヒープはフロントエンド リストで空きブロックを探します。空きブロックがない場合、要求を満たすために、ヒープは強制的にバック エンドから大きなブロックを割り当てられます (仮想メモリの予約や保存を行います)。一般的な実装では、ブロックごとの割り当てにオーバーヘッドがあり、実行サイクルに際して、コストがかかったり、使用可能な記憶域が少なくなります。

Knowledge Base の記事 Q10758、「Managing Memory with calloc() and malloc()」(記事 ID 番号で検索してください) に詳細なバックグラウンドが掲載されています。またヒープの実装および設計に関する詳細については、Paul R. Wilson、Mark S. Johnstone、Michael Neely、および David Boles の『Dynamic Storage Allocation: A Survey and Critical Review』を参照してください。1995 年 9 月、英国スコットランドのキンロスで行われた "International Workshop on Memory Management" において発表されました (http://www.cs.utexas.edu/users/oops/papers.html) (英語)。

Windows NT の実装 (Windows NT 4.0 以降) では、8 ～ 1,024 バイトの範囲で 8 バイトに調整されたブロックの 127 のフリー リストと種々雑多なリストを使用しています。種々雑多なリスト (フリー リスト[0]) には、1,024 バイトより大きいサイズのブロックが存在します。フリー リストには二重リンク リストで互いにリンクしているオブジェクトが含まれます。既定では、プロセス ヒープは併合操作を行います (併合とは、より大きなブロックを構築するために隣の空きブロックと結合することを示します)。併合には余分なサイクルが必要になりますが、ヒープ ブロックの内部の断片化を減少します。

単一のグローバル ロックでは、ヒープがマルチスレッドで使用されません (https://msdn.microsoft.com/en-us/library/ms951773.aspx#tencom_topic4 (英語) の MSDN Online Web Workshop にある、George Reilly の「Server Performance and Scalability Killers」に記載されている最初の "commandment" を参照してください)。このロックは、複数スレッドでのランダム アクセスからヒープ データ構造を保護するために不可欠です。このロックは、ヒープ操作が頻繁に行われる場合には性能の面で逆効果になります。

一般的なヒープ機能の問題とは?

ヒープを使用する場合に起こる最も一般的な障害を以下に示します。

  • 割り当て操作の結果として、スローダウンが起こる 割り当てには時間がかかります。最も可能性のある原因としては、フリー リストにブロックがなく、そのためにランタイム アロケータのコードによって、大きな空きブロックを検索するサイクル、またはバックエンド アロケータからの新しいブロックを割り当てるサイクルが行われることが挙げられます。

  • 解放操作の結果として、スローダウンが起こる 主に結合が有効になっている場合、解放操作にはより多くのサイクルが必要になります。結合が行われている間、各解放操作は隣のブロックを "検索" し、それらを抽出してより大きなブロックを作成し、そのブロックをフリー リストに再挿入します。検索の間、メモリはランダムに操作されるため、キャッシュの喪失やパフォーマンスのスローダウンが起こります。

  • ヒープの競合によりスローダウンが起こる 競合とは、2 つ以上のスレッドが同時にデータへアクセスしようとして、1 つのスレッドが作業を完了するまでほかのスレッドが作業を実行できないでいる状態を示します。競合は常に問題を引き起こします。マルチプロセッサ システムでは最も大きな問題となります。メモリ ブロックを大量に使用するアプリケーションや DLL は、マルチプロセッサ システムで複数のスレッドと共に実行した場合にスローダウンを起こします。単一ロックを使用する一般的なソリューションでは、ヒープの操作がシリアル化されています。シリアル化により、スレッドはロックを待つ間にコンテキストの切り替えを行います。点滅している赤信号での停止および発進によって生じるスローダウンを想像してください。

    競合は通常、スレッドおよびプロセスのコンテキスト切り替え要因になります。コンテキストの切り替えには非常にコストがかかりますが、プロセッサ キャッシュから失ったデータを、後にスレッドが回復した際に再構築する場合よりはかかりません。

  • ヒープの破損によりスローダウンが起こる アプリケーションがヒープ ブロックを適切に使用しなかった場合に破損が起こります。一般的なシナリオとしては、解放した後のブロックを再び解放したり使用すると、境界を越えて上書きを行ってしまうという明らかな問題があります (破損についてはこの記事では扱いません。詳細については、Visual C++ プログラマーズ ガイド プログラムのデバッグで、メモリの上書きおよびメモリ リークについて参照してください)。

  • 頻繁な alloc および realloc によりスローダウンが起こる これは、スクリプト言語を使用する場合に起こる非常に一般的な現象です。文字列が繰り返し割り当てられることによって文字列が大きくなり、解放されます。このようなコードは実行しないでください。可能であれば、大きな文字列を割り当てるようにして、バッファを使用してください。別の方法として、連結操作を最小限に抑えることもできます。

競合は、解放と同様に割り当てにおいてもスローダウンを引き起こします。ヒープを競合させず、迅速に割り当ておよび解放を行うことが理想的です。このような一般的な目的に使用されるヒープは、まだありませんが、将来的には開発されるかもしれません。

すべてのサーバー システム (IIS、MSProxy、DatabaseStacks、ネットワーク サーバー、Exchange など) において、ヒープのロックは非常に大きな障害になります。プロセッサ数が多くなるほど競合も増加します。

ヒープから自分を守る

さて、ヒープに関する問題について理解したところで、こうした問題を取り除いてくれる魔法の杖が欲しくありませんか? 1 本でもあれば助かるのですが、残念ながらヒープを速くする魔法はありません。製品発送前の週になって物事を迅速に行うことは期待できません。ヒープ対策を早めに計画しておくと非常に楽になります。ヒープの使用方法を変更してヒープの使用回数を減らすことは、パフォーマンスを向上させる実質的な対策になります。

どうすれば、ヒープ操作の使用回数を減らすことができるでしょうか? データ構造内部での局所性を利用することができます。以下の例を検討してください。


struct ObjectA {
   // オブジェクト A のデータ
}

struct ObjectB {
   // オブジェクト B のデータ
}

// オブジェクト A とオブジェクト B を組み合わせて使用します。

//
// ポインタを使用します。
//
struct ObjectB {
   struct ObjectA * pObjA;
   // オブジェクト B のデータ
}

//
// 埋め込みを使用します。
//
struct ObjectB {
   struct ObjectA pObjA;
   // オブジェクト B のデータ
}

//
// 集合体 ? オブジェクト A およびオブジェクト B を互いのオブジェクト内で使用します。
//

struct ObjectX {
   struct ObjectA  objA;
   struct ObjectB  objB;
}

  1. 2 つのデータ構造に関係するポインタを使用しない 2 つのデータ構造に関連するポインタを使用する場合、前述の例のオブジェクト A および B に対してそれぞれ個別に割り当ておよび解放が行われます。これには追加コストが必要になるので "回避するべき" です。

  2. ポイントされた子オブジェクトを親オブジェクトに埋め込む オブジェクトがポインタを持っているということは、動的なエレメント (80%) があり、新しい位置がデリファレンスされることを意味しています。埋め込みによって局所性が増すため、それ以上の割り当てまたは解放の必要性が低下します。これによりアプリケーションのパフォーマンスが向上します。

  3. 小さなオブジェクトを結合して、より大きなオブジェクトを形成する (集合体) 集合体は、割り当てられて解放されるブロックの数を減らします。複数の開発者が設計のさまざまな部分を担当している場合、最終的に多くの小さなオブジェクトを結合することになります。この統合で難しい点は、適切な集合体の境界を見つけることです。

  4. 要求の 80% を満たすバッファを並べる (80 対 20 の法則) 場合によっては、メモリ バッファに文字列またはバイナリ データを保存する必要があり、総バイト数が事前に分からないことがあります。測定基準を適用して要求を 80% 満たすサイズのバッファを計ります。残りの 20% には、新しいバッファを割り当ててそのバッファに対するポインタを設定します。この方法で、データの空間的な局所性と同様に割り当てや解放の呼び出し回数を減らすことができ、最終的にはコードのパフォーマンスを向上することになります。

  5. オブジェクトをひとまとまりで割り当てる (チャンク化) チャンク化とは、オブジェクトを 2 つ以上のグループで同時に割り当てることを指します。項目のリストを記録する必要がある場合、たとえば {名前、値} の組み合わせリストでは 2 つの選択肢があります。選択肢 1 では、名前と値の組み合わせごとにノードを 1 つ割り当てます。選択肢 2 では、5 つの名前と値の組み合わせを持つことのできる構造を割り当てます。そして、たとえば、4 組を保存しておくことが一般的なシナリオでは、ノードの数や追加のリンクリスト ポインタに必要であったスペースを減らすことができます。

    チャンク化によって局所性が向上するため、特に L1 キャッシュにとってはプロセッサ キャッシュフレンドリであると言えます。チャンク化された割り当てに対して、いくつかのデータ ブロックが同じ仮想ページに位置付けられることは言うまでもありません。

  6. _amblksiz を適切に使用する CRT (C ランタイム) には、ブロックをバック エンド (Win32 ヒープ) から _amblksiz サイズで割り当てるカスタム フロントエンド アロケータがあります。_amblksiz の設定値を高くすると、バック エンドに対して行われる呼び出し回数を減らすことができる可能性があります。これは、CRT を頻繁に使用するプログラムに対してのみ適用できます。

これらの技術を使用して節約できるものは、オブジェクトの種類、サイズ、およびワークロードによって異なります。ただし、パフォーマンスおよびスケーラビリティは常に向上することができます。マイナス面として、コードがビットで特定されることが挙げられますが、十分に考慮すれば管理は可能です。

パフォーマンスをより向上させる方法

スピードを向上させる技術には、さらに次のようなものがあります。

  1. Windows NT5 ヒープを使用する

    開発チームの尽力と懸命な努力のおかげで、1998 年初期に Microsoft Windows 2000 に次のようないくつかの重要な改善がなされました。

    • ヒープ コード内部のロックの向上 ヒープ コードは各ヒープごとにロックを 1 つ使用します。このグローバル ロックを使用することで、マルチスレッド環境で使用されるヒープ データ構造を保護します。残念ながら、高トラフィック シナリオでは、ヒープはいまだにこのグローバル ロックの泥沼にはまり込み、結果として激しい競合を引き起こしたり、パフォーマンスが低下する可能性があります。Windows 2000 では、内部ロック コードのクリティカル領域を減らして競合の起こる可能性を最小限に抑えることにより、スケーラビリティが向上されています。

    • 索引リストの使用 ヒープ データ構造は、8 ～ 1,024 バイト (8 バイト増加) ブロック サイズの空の項目すべてに対して高速キャッシュを使用します。高速キャッシュはもともとグローバル ロック内で保護されていましたが、検索リストを使用して高速キャッシュ フリー リストへのアクセスが可能です。これらのリストにはロックが必要ありません。その代わりに 64 ビットのインターロック操作を使用するので、パフォーマンスが向上します。

    • 内部データ構造のアルゴリズムも同様に改善されています。

    これらの改善により割り当てキャッシュの必要はなくなりましたが、その他の最適な設定を妨げないようにしてください。Windows NT 5 ヒープを使用したコード評価が 1,024 バイト (1 KB) より小さいブロックにとっては最適です。"GlobalAlloc()" および "LocalAlloc()" は同一のヒープをベースとし、共通の構造を使用して処理単位のヒープにアクセスを行います。Heap* API を使用して、処理単位のヒープにアクセスするか、高度にローカライズされたパフォーマンスが必要な場合は独自のヒープを作成し割り当て操作を行います。大きなブロックの操作が必要な場合は、"VirtualAlloc()" または "VirtualFree()" を使用することもできます。

    これらの改善点は、Windows 2000 beta 2 および Windows NT 4.0 SP4 において実現されています。改善後はヒープ ロックの競合が起こる割合が著しく減少しました。こうした利益はすべて Win32 ヒープのユーザーに直接もたらされています。CRT ヒープは Win32 ヒープの上に作成されますが、独自のヒープ内の小さなブロックのみを使用するので Windows NT の改善による恩恵は受けません (Visual C++ 6.0 にも改善されたヒープ アロケータがあります)。

  2. 割り当てキャッシュを使用する

    割り当てキャッシュを使用して、割り当てられたブロックを将来再利用するためにキャッシュに格納することができます。これにより、一度割り当てられたブロックを可能な限り再利用できるだけでなく、プロセス ヒープ (または グローバル ヒープ) を行う alloc/free 呼び出しの回数を減らすことができます。さらに、割り当てキャッシュを使用して、より高度なレベルでのオブジェクトの使用方法について深く理解するための統計を取ることもできます。

    一般的に、カスタム ヒープ アロケータはプロセス ヒープの上に実装されています。カスタム ヒープ アロケータはシステム ヒープと非常に似た動作をします。大きな違いは、割り当てられたオブジェクトに対してプロセス ヒープ上にキャッシュを提供している点です。キャッシュは固定サイズ (たとえば、32 バイト、64 バイト、128 バイトなど) に合わせて設計されています。これは計画としては優れていますが、この種類のカスタム ヒープ アロケータは、割り当てられて解放されるオブジェクトに関連する "形式情報" を失ってしまいます。

    カスタム ヒープ アロケータとは対照的に、クラスごとの割り当てキャッシュとして "Alloc-caches" が実装されています。これは、カスタム ヒープ アロケータの優れた機能を提供するだけでなく、多くの "形式情報" を保存することができます。各割り当てキャッシュのハンドラは、ターゲットとなるバイナリのオブジェクト 1 つと関連付けられています。これは、同時実行レベル、オブジェクトのサイズ、フリー リストに保持するエレメント数などを示すパラメータと共に初期化することができます。割り当てキャッシュ ハンドラのオブジェクトは、解放されたエンティティの独自のプライベート プール (指定されたしきい値を超えない) を管理していて、専用ロックを使用して保護を行います。割り当てキャッシュおよびプライベート ロックを併用することによって、メイン システム ヒープへのトラフィックが減少し、同時並行、再利用の最大回数が増え、より大きなスケーラビリティを提供することができます。

    スカベンジャ(scavenger)を使用して、すべての割り当てキャッシュ ハンドラの稼動状況を定期的に確認し、使用していないリソースを解放する必要があります。何も稼動していない場合は、割り当てオブジェクトの領域が解放されるので、パフォーマンスが向上します。

    各 alloc/free の活動状況を監査することができます。第 1 レベルの情報には、オブジェクト、割り当て、および解放呼び出しが行われた回数の総数が含まれます。統計を参照することにより、さまざまなオブジェクト間の形式リレーションを得ることができます。このリレーションを使用すると、ここで説明した多くのテクニックのいずれかを使って、メモリの割り当てを削減することができます。

    割り当てキャッシュをデバッグ エイドとして使用し、適切にクリーン アップされなかったオブジェクト数を確認することもできます。またクリーン アップされなかったオブジェクトに加えて、動的なスタック バック トレースや署名を見ることによって、呼び出しに失敗した正確な回数を確認することも可能です。

  3. MP ヒープ

    MP ヒープとは、マルチプロセッサに適応した分散割り当て用のパッケージで、Win32 SDK (Windows NT 4.0 以降) で使用することができます。元は JVert によって実装されており、ここでのヒープ抽象化は Win32 ヒープ パッケージ上で行われます。MP ヒープは複数の Win32 ヒープを作成し、あらゆる単一ロックにおける競合を減少することを目的として、割り当て呼び出しを異なるヒープへ分散しようとします。

    このパッケージは有効な手段であり、改善された MP フレンドリなカスタム ヒープ アロケータの 1 つです。ただし、形式情報は提供されず統計もありません。MP ヒープは、SDK ライブラリとして使用するのが一般的な方法です。この SDK ライブラリを使用して再利用可能なコンポーネントを作成することができれば大きな利益となります。ただし、あらゆる DLL に SDK ライブラリを構築するとワーキング セットを増やすことになります。

  4. アルゴリズムおよびデータ構造を再検討する

    マルチプロセッサ マシンで評価を行うためには、アルゴリズム、実装、データ構造、およびハードウェアが動的に評価を行う必要があります。最も頻繁に割り当ておよび解放が行われているデータを参照してください。そして、"別のデータ構造を使ってこの作業を実行できないか?" と考えてみてください。たとえば、アプリケーションの起動時に読み込まれる読み取り専用項目のリストがある場合、このリストはリニアなリンクを含むリストにする必要はありません。動的に割り当てられる配列にしてもいいでしょう。動的に割り当てられる配列は、メモリ内のヒープ ブロックや断片化を減らし、そのためパフォーマンスを増大させます。

    必要となる小さなオブジェクトの数を減らすことで、ヒープ アロケータの負担を軽くすることができます。たとえば、サーバーのクリティカル プロセス パスにおいて 5 つの異なるオブジェクトを使用する場合、各オブジェクトはそれぞれ個別に割り当てられ解放されます。オブジェクトをキャッシュと共に格納すると、5 回のヒープ呼び出しを 1 回にすることができ、特に 1 秒間に 1,000 より多い要求を処理している場合には、ヒープの負担を大幅に軽減することができます。

    オートメーション構造を頻繁に使用する場合、Automation BSTR を主要コードから除外するか、少なくとも BSTR 上で操作を繰り返さないようにしてください (BSTR 連結には結果として余分な realloc および alloc/free 操作が必要になります)。

要約

ヒープはすべてのプラットフォームに汎用的な状態で実装される傾向があり、そのため大量のオーバーヘッドがかかります。各コードには特定の条件がありますが、ヒープの対話を減らすために、ここで検討した原理を設計の時点で考慮することができます。

  1. コードでのヒープの利用について十分に評価する。

  2. クリティカル パスおよび固定データ構造を分析して、ヒープ呼び出しが少なくなるようにコードを簡素化し、効率を上げる。

  3. カスタム ラッパを導入する前に、ヒープ呼び出しのコストを測る測定基準を作成する。

  4. パフォーマンスについて不満がある場合は、ヒープを改善するよう OS グループに伝える。こうした要求が増えることにより、ヒープをよりよく改善しようとする関心が高まります。

  5. OS が提供するヒープ上でアロケータを薄いラッパにするよう C ランタイム グループに伝える。結果として、OS が改善されると C ランタイムのヒープ呼び出しのコストが削減されます。

  6. ヒープの改善はオペレーティング システム (Windows NT ファミリ) において引き続き行われています。今後の動向に注目し、同様に利用してください。

Murali Krishnan は、IIS (Internet Information Server) チームのソフトウェア設計技術主任です。バージョン 1.0 の開発から関わっており、バージョン 1.0 から 4.0 までを完成させました。Murali は IIS のパフォーマンス チームを組織した 1995 年から 1998 年までの 3 年間チームをリードし、初日から IIS のパフォーマンスに影響を与えてきました。彼はウィスコンシン州立マディソン大学で修士号を、インドのアンナ大学で学士号を取得しました。いずれもコンピュータ サイエンスの分野です。仕事以外の時間には読書、バレーボール、そして家で料理をして過ごしています。