ヒープに関する話題

概要

この記事では、Windows におけるヒープメモリの使い方と注意点について記載する。

• ヒープとは何か
• プロセスヒープとプライ ベートヒープ
• 断片化
• MP Heap

ヒープとは何か

Win32 のメモリ割り当て関数を大きく二種類に分類する。ひとつ目を VirtualAlloc 系、もうひとつを HeapAlloc 系とする。

VirtualAlloc 系ではページ単位でメモリを操作する。このため(アクセス権の設定の面で)柔軟であるが小さなメモリブロックの割り当てに向かない。一 方 HeapAlloc 系では、予めある程度 の仮想メモリ 領域を予約しておき、プログラムから要求がされ次第、その予約された領域からメモリを切り出してきてメモリブロックを確保する。小さなメモリブロックを多 数割り当てるにはこちらの方法のほうが効率が良い。Windows のヒープマネージャはこのような動作を実現できるように、プログラムと仮想メモリマネージャの間に入りメモリ割り当てを高速に行う。

ここで試しに、ヒープを使わずに仮想メモリから直接メモリを割り当てた場合と、ヒープを利用した場合で、割り当て速度にどの程度の速度 差が発生するのか比較してみる。使用したサンプルコードはこちら。

サンプルコード [perftest.zip, makefile プロジェクト]

ヒープを使う場合は HeapAlloc API を使い、ヒープを使わない場合は VirtualAlloc API を使いメモリを割り当てる (ヒープはプロセスヒープを使うことにする)。割 り当てバイト数を 16, 32, 64, ... , 8192 のように変え、それぞれのサイズのメモリブロックを 10000 個割り当てる。さらに、それぞれのブロックには x という文字を書き込む。この結果、次のようになった。水色の棒グラフが HeapAlloc、紫色の棒グラフが VirtualAlloc である。
※テスト機は Windows XP CPU: Mobile Intel(R) Pentiun(R) 4 CPU 2.8GHz HT, RAM: 1.37GB

このテストでは割り当てバイト数が 1～2kb 未満では特に HeapAlloc と VirtualAlloc の速度差が顕著であることがわかる。

尚、割り当て数が高々 10000 個であるため、HeapAlloc による割り当てでは 512 バイト以下では計測不能 (1ms 以下) であった。計測できるようにするため、割り当て数を増やそうと試みたが同じ条件では、VirtualAlloc による割り当てが失敗するため 10000 個のままとした。いずれにせよ、これで単に小 さなメモリブロックをたくさん割り当てるテストでは HeapAlloc は速い(VirtualAlloc より) ことは確認できる。

プロセス ヒープとプライベートヒープ

プロセスの起動時には、ヒープは既定でひとつ用意される。これはプロセスヒープ (あるいはデフォルトヒープ、プロセスデフォルトヒープなどとも言われるがどれも同じもの) と呼ばれる。GetProcessHeap API によってプロセスヒープのハンドルを取得することができる。

• GetProcessHeap

自分のプログラムからプロセスヒープを利用し続けることも可能で あるが、パフォーマンスの観点からヒープを独自に作成してそれを利用したほうが良い場合がある。自前で作ったヒープをプライベートヒープと呼ぶ。プライベートヒー プは HeapCreate API で作成できる。作成したヒープは HeapDestroy で破棄できる。

• HeapCreate
• HeapDestroy

プライベートヒープを作成する動機 ヒープは基本的にリスト構造をしている。そのリストの整合性を保つためにヒープはロックを持つ (ヒープロックという)。自分のプログラムからプロセスヒープを利用する場合、プロセスヒープは様々なライブラリから利用されているので、他のライブラリ の呼び出しによって自分のプログラムからの呼び出しが待たされる可能性がでてくる。これがプライベートヒープを作成する動機のひとつである。もうひとつ は、テストしてみればわかることだが、ヒープは (正確に言えば現在のWindowsの挙動・実装では) 一度予約したメモリ領域を解放しない。つまり、ある時点で ヒープ A にて大量のメモリ割り当てが発生すると、ヒープ A のサイズは可能なところまで伸張する。その後ヒープから割り当てたメモリを HeapFree などで解放しても、そのメモリブロックは 「解放済み」 と認識され、そのヒープ内では利用可能であるがヒープ全体は予約されたままとなる。したがって、そのヒープにおけるメモリブロックの割り当ては成功するだ ろうが、そのプロセスでの仮想メモリ空間は巨大な ヒープ A に占拠されたままとなるため、他のメモリ操作関数がメモリ不足で失敗する可能性が出てくる。これを避けるためにはヒープを HeapDestroy でヒープを破棄しなければならない。これがプライベートヒープを利用する動機の二つ目である。

ちょっと脱線かつ蛇足だが、何かの雑誌で 「一度割り当てたメモリは、実質的に二度と再利用されない」 というようなことを読んだが、そんなことはない。試してみればすぐに、それが誤りだとわかるだろう。

断片化

ヒープからのメモリ割り当てでは、あらかじめ用意したメモリ領域 からメモリブロックを切り出して使うと述べた。解放されたメモリは再利用される。しかし、断片化 (fragmentation) が進むと、メモリの秋領域があるにもかかわらずメモリ割り当てができない可能性が出てくる。

上図を見ていただきたい。今、ある特定サイズのヒープがあったと する (通常は必要に応じてヒープサイズは伸張するが、固定サイズにすることも可能)。黄緑色の領域は開き領域であり、赤色の部分は使用中のメモリ領域である。 この状況で、青色のサイズのメモリを割り当てたいと考える。明らかに緑色の総量は、青色のそれより多い。しかし、ヒープメモリの割り当てには連続した領域が必要 (同一セグメント内)であるから、青色のメモリ割り当ては失敗する。このように、メモリの割り当て状況が虫食い状態になってい くことを断片化 (fragmentation) という。

Windows XP 以降では、ヒープの断片化が起きにくいようにメモリ割り当てを行うように、ヒープマネージャに指示することができる。この機能を LFH (Low Fragmentation Heap) という。LFH は既定では設定されておらず、プログラムの中から HeapSetInformation API を呼び出すことで有効にする。

    ULONG ulEnableLFH = 2;
   
    HeapSetInformation (
        hHeap,
        HeapCompatibilityInformation,
        &ulEnableLFH,
        sizeof(ulEnableLFH));

尚、CRT に使われているヒープもプライベートヒープであり LFH は既定では有効ではない。しかし、_get_heap_handle を使ってヒープハンドルを取得し HeapSetInformation を使えば、CRT ヒープに対しても LFH を有効にできる。

特に、断片化はある程度長時間の運用によって表面化してくることがあり、一般的にテスト環境では再現は難しい。断片化を避けるために配 慮する事項としては、「生存期間があまりに異なるメモリブロックを同じヒープから割り当てない (専用のプライベートヒープを作る)」 「長時間割り当てる場合は、割り当てサイズをなるべく揃える」 こと等が挙げられる。

MP Heap

• MpHeapCreate
• MpHeapDestroy
• MpHeapAlloc
• MpHeapFree
• MpHeapValidate
• MpHeapCompact
• MpHeapReAlloc
• MpHeapGetStatistics

参考資料

Heap: Pleasures and Pains
http://msdn.microsoft.com/library/en-us/dngenlib/html/heap3.asp