Windows のヒープ管理 - Firefox3 のメモリ使用量 (2)
シアトル行く前に『jemalloc on Windows - Firefox3 のメモリ使用量 - NyaRuRuの日記』 の続きを片付けておきますか．
といいつつ，当初予定の内容はとりあえず破棄．書いているうちに気になることが色々出てきて，その度に実験するものだからあんまり進んでいなくて，このままだと永遠に終わらなそうなので方針を変えました．というわけで外部資料多めでお送りします．
最初に読むもの
UNIX 系の mmap を使ったメモリアロケーションならだいたい分かるよ，という人が，Windows のメモリ管理について興味を持ったとして，おすすめなのが 「（新）APIから知るWindowsの仕組み」シリーズの『第4回 メモリー管理のキー技術「仮想メモリー」を知る』という記事です．
というわけでここでまず上のページに飛んで，一通り読んでみて下さい．以下はその後で．
仮想アドレス領域の予約について
ポイントとなる仮想アドレス領域の予約を可能にする動機については，先ほどの記事の以下の部分で説明されています．
しかし，なぜこんな面倒なことをするのだろうか。それは，物理メモリーと同じくらい，仮想メモリーのアドレス領域も貴重だからである。物理メモリーが不足すれば，ページング・ファイルにデータを退避することで使い回しが利くが，仮想メモリーには4Gバイトという制限がある。しかも，4Gバイトのプロセス・メモリー空間をすべてプログラムが使ってよいわけではない。Windowsシステムのコードも同じメモリー空間に置かれるため，最大で2Gバイト（後述するように，これを3Gバイトに拡張することが可能なバージョンのWindowsもある）までしか，プログラムでは使用できないのだ。
もう一つ重要なポイントは，仮想メモリーのフラグメンテーション（断片化）である。いくつものメモリー領域を割り当てたり，解放したりを繰り返していると，メモリーの使用状況が図5のようになってしまうことがある。このように，メモリーの未使用領域が不連続になってしまうことを，フラグメンテーションと呼ぶ。
図5●メモリのフラグメンテーション
メモリー・ブロックを割り当てるには，必要なサイズ以上の連続領域が必要だ。しかし，フラグメンテーションが起こっていると，未使用領域のサイズの合計が十分であっても，必要なメモリー・ブロックを割り当てられない可能性が出て来る。フラグメンテーションができるだけ起こらないようにプログラムを記述する工夫が必要な一方で，連続するメモリー領域を予約しておくことが重要なのである。
一般的な説明はこれで十分だと思うので，以下私見モード．
実際のところ，仮想アドレス領域の予約を有効に使うのは案外と難しいんじゃないかと思います．
仮想アドレス領域が予約できても，そもそも必要な連続領域の上限値が分からないという根本的な問題は解決しません．例えば必要なメモリが高々 300 MB と分かっていれば，最初から VirtualAlloc で 300 MB コミットというのもひとつの手なのです．他のモダンな OS と同じく，Windows も実際にメモリアクセスが起きるまでは物理メモリを割り当てません．なので，300 MB のコミット領域の先頭 10 MB にのみアクセスして終了するプロセスは，結局 10 MB しか物理メモリに負荷をかけません．確かに仮想アドレス領域を 300 MB 予約して，部分コミットしていった方がベターではありますが，それは単に解ける問題をより効率的に解いているだけなのですよ．
現実的なシナリオとして，必要な連続領域のサイズが予想不能だとして，さばを読んでアドレス領域をかなり大量に予約するとどうなるでしょうか．例えば 1 GB とか．
ユーザランドのメモリアロケータがひとつしかなくて，予約を行うのがその唯一のメモリアロケータであればまあ問題はないでしょう．ただし DLL のロード等で行われる暗黙のファイルマッピングや，スレッドスタックが消費するアドレス領域を残しておくことを忘れずに，と．
でも現実はそう単純じゃないですよね．Windows は省メモリプログラミングが必須であった時代の名残か，共有ライブラリ (DLL) によるインプロセスコンポーネント技術が好まれます．各 DLL は様々な言語によってプログラミングされていて，それぞれは独自のメモリアロケータを持つでしょう．あるモジュールが大量にアドレス空間を予約すれば，別のモジュールからみた「利用可能領域」が確実に減少します．DLL X のメモリアロケータが 1 GB の連続領域を予約して，DLL Y のメモリアロケータが「本当に」 1 GB 必要としたらそれでアドレス領域を使い切ってしまいます．コンポーネントの可搬性を高めようとすればするほど，他のモジュールに迷惑をかけるようなアドレス領域の予約は難しくなるのです．
実際のところ Windows アプリケーションのメモリアロケータがどうなってるのか調べてみた
まずは，時代を現代に設定し，メモリ管理には特に思い入れのないプログラマが，Visual C++ 2008 で Win32 アプリケーションを作成した場合を考えましょう．この場合は MSVCRT のデフォルトメモリアロケータが使われているはずです．MSVCRT は静的リンク版と動的リンク版があって，静的リンクを選んで作ったモジュール (EXE または DLL) は，そのモジュール内に独立したメモリアロケータを持つことになります．動的リンクを選んだモジュールの場合，メモリ周りの処理は MSVCRT DLL に丸投げされますので，同一バージョンの CRT を利用するモジュール間ではメモリアロケータを共有することになります．
と，簡単に済ませられるほど単純ではないようなんですよね．
Visual C++ には CRT ソースコードが付属しているのですが，それを読むと，Visual C++ 7.0 (Visual C++.NET 2002) 以降の MSVCRT は，3 種類のメモリアロケータから環境や設定に応じてひとつを選んでいることが分かります．*1．
ソースを読むと，どうやら Visual C++ 5.0/6.0 は small heap block と呼ばれる仕組みで小さなサイズのメモリ割り当てを独自管理していたようです．一方，システムヒープアロケータは，Windows 2000 以降の kernel32.dll に存在するヒープ管理 API で，Visual C++ 7.0 は小さなメモリ割り当ても全てこのヒープ API に丸投げなようですよと．
絡繰りが見えてきた感じですね．
同一バージョンのコンパイラ/リンカが使われているのであれば，仮にモジュールが分かれていても CRT のメモリアロケータを無理矢理統合することは不可能ではなさそうですし，実際 Visual C++ 5.0/6.0 はそういうことをやっていたようです．
さらに Windows 2000 と Visual C++ 7.0 では，これを言語非依存に拡張した，と．つまり 各プロセスにヒープ管理の単一ファサードを OS レベルで提供し，全ての言語のランタイムライブラリがそれを利用すれば皆ハッピー計画．JVM や CLR では当たり前の「メモリアロケータの統合」ですが，Win32 な C/C++ その他の世界でも 2002 年頃になんとかこぎつけていたんですなぁ．
そしてメモリアロケータが統一できるのであれば，そう，仮想アドレス領域の予約が意味を持ってくるはずです．
そして解答編
結局のところ正解は当事者にしか分かりませんので，以下の資料には目を通すことをお勧めします．先ほどの考察を念頭に置けば，だいぶ読みやすくなっているはずです．
例えば歴史に関しては次の資料によくまとまっています．
OS が提供するヒープマネージャの概論については次の資料がおすすめです．
- インサイド Microsoft Windows 第4版〈上〉 7.2.9 ヒープマネージャ
Windows XP 以降の低断片化ヒープに関する実装詳細については以下の資料がおすすめです．
- コンピュータ科学特別講義III (戦略ソフトウェア特論II)
- Ask the Performance Team : MSDN blog
感想
Windows の特殊事情ってのを理解しているかどうかで，資料の読みやすさがだいぶ違うのは確かにあると思います．見落としがちな視点として，次の 2 つに注意すると良いかもしれません．
- Windows では「ソースから再コンパイルすればいいじゃん」は成り立たない．膨大なアプリケーションやバイナリコンポーネント資産がそういうエコシステムと深く結びついている．バイナリ互換と性能向上を両立させるという動機は，複雑で大規模な仕組みを OS に導入するのに十分な理由である．
- Microsoft にとっての持ち駒は主に次の 2 つ．この駒で「メモリアロケータの統合と改良」を行うにはどうするか？ ただし過去に出荷したバイナリコンポーネントは原則的に変更できないことに注意．
振り返って，『Firefox 3 のメモリ使用量』を読み直すと「これはアプリケーション開発者の視点だなぁ」とつくづく思います．Win32 の設計と進化を考えれば，実のところ足りないのは「Win32 front-end heap を独自アルゴリズムに置き換える仕組み」かもしれません．Windows は何年もかけて front-end heap への一本化を進めていたので，それを jemalloc の同等物に置き換える仕組みさえあれば，ソースを弄ることもなく，Firefox 3 のプロセス全体でヒープ管理を改善できていたはずだよなぁと．
ビルド時に標準 CRT の malloc を無理矢理置き換える Firefox 3 の --enable-jemalloc ビルドは，確かにボトムアップにがんばっているという印象を受けますが，例えば XPCOM を使った拡張を Visual C++ で作るとして，そのメモリアロケータも jemalloc に合わせるべしといった指針等はあるのでしょうか？ 別のコンパイラだった場合は？ そもそも拡張の作者達への情報提供は十分なのでしょうか？ "private bytes" に関する Stuart Parmenter さんの誤解の件といいどうも若干の不安が残ります．
なんてぼやきは，例の『プログラマーは「マシン語」を理解して初めて一人前？』問題にも通じるところがあるのかも．クロスプラットフォームプロジェクトは，各プラットフォームの特殊性を理解して初めて一人前，とつい端から言いたくなる症候群，かな．
まあ実際こういう話は楽しいですし，メモリアロケータの性能を試せるよいテストベンチができたと考えれば決して悪い話ではありません．
しかしつくづく思うのは，現代のブラウザって巨大アプリケーションだなぁと．「ブラウザとメーラーさえ動けばよい」なんていつの時代の話やら．「ブラウザが快適に動く環境なら，大抵のアプリケーションも快適に動く」の間違いじゃないでしょうかね．
*1:[http://www.tech-archive.net/Archive/Development/microsoft.public.win32.programmer.kernel/2004-06/0499.html:title=]
