メモリ割り当て 基礎
C++ のあらゆる new、C のあらゆる malloc、 Rust のあらゆる Box::new は最終的に OS にメモリを要求し、それを刻む。 5 セクションで全体像を組み立てる:スタック vs ヒープと brk / mmap がどうヒープを実際に伸ばすか;malloc & freeの内部 + 対話的ヒープレイアウト;現代のjemalloc / tcmalloc / mimalloc とそれらが存在する理由;断片化 —— 内部、外部、リーク;最後にクイックリファレンス。
スタック vs ヒープ —— そしてヒープが実際にどう成長するか
各プロセスは両方を持つ。スタックは安く、自動、有界; ヒープは柔軟、手動、すべてのアロケータが住む場所。 カーネルは要求に応じて意外に異なる 2 つの syscall でヒープを成長させる。
スタックは固定領域(Linux で デフォルト 8 MB)、関数呼び出しで下方向に成長し、 返却で上方向に縮む。割り当ては本質的に無料 —— rsp をデクリメントするだけ。 解放も無料 —— 返却時に rsp をインクリメントするだけですべてを破棄する。 罠はスタック上の各バイトが関数が返った瞬間に消えること; コピーなしには関数呼び出しを跨いでスタックデータを共有できない。 そしてサイズ上限は硬い:オーバーフローすると SIGSEGV(時にカーネルガードページ経由)。
ヒープは他のすべて。関数呼び出しより長生きする必要があるもの、 コンパイル時にサイズが分からないもの、ランタイムに成長または縮小するもの —— すべてヒープに住む。C の malloc、C++ の new、 Java と JS のオブジェクト割り当て、Rust の Box、Go のエスケープした値 —— 全部ヒープ。
カーネルがヒープにメモリを与える方法
プロセスのヒープを成長させる 2 つの syscall:
brk(とsbrk):古典的な Unix。 data segment 境界を新しい高水位にセットし、古い水位と新水位の間のすべてのアドレスが有効になる。 アロケータは小型割り当てに使う、なぜなら一度に数 KB ずつ成長 / 縮小するのが安いから。MAP_ANONYMOUS付きのmmap: アドレス空間のどこかに新しいファイルレスな VMA を作成。 アロケータは大型割り当てに使う(glibc のデフォルト閾値 128 KB)、 なぜなら free 時にカーネルへ独立に返せるから。
違いは運用上重要。brk はヒープの上からのみメモリを解放できる —— top-of-heap 水位に小さな割り当てがあると、その下のすべてが free されても ヒープ全体がマップされたまま。mmap 割り当ての領域は任意の順序で munmap できる。 これが小オブジェクトを多く割り当てる長寿命プロセスがしばしば ps に メモリリークしているように見える理由 —— ワーキングセットが成長していなくても: glibc アロケータは brk 割り当てヒープを OS に返せない。
RSS vs VSZ
VSZ は仮想サイズ —— 総マップアドレス空間。RSS(resident set size)は今 RAM にある実際の物理ページ。 VSZ 2 GB、RSS 100 MB のプロセスは 2 GB の仮想メモリを割り当てているが、 100 MB 分のページしか触れていない。RSS が物理 RAM をコストする; VSZ はそれがページテーブルが安く記述できるもの(4 KB ページで ~256 GB)を 超えたときのみ真の懸念になる。
コンパイラも助ける
現代のコンパイラは escape analysis を行う: ヒープ割り当てが現在の関数を「エスケープ」しない(フィールドに格納されない、返されない、 保持し得る何かに渡されない)場合、コンパイラはそれをスタックに引き上げられる。 Go は積極的にやる;C++ と Rust は小型型のインライン化 + 死コード除去経由でやる; Java の JIT は「scalar replacement」としてやる。結果として、これらの言語のイディオマティック コードはしばしばホットループでヒープに触れずに走る、ソースがどう見えても。
要点。「スタック:安い、有界、関数ローカル。 ヒープ:柔軟、手動、アロケータの領域。カーネルはヒープを brk(小 / 速 / 容易に返せない) または MAP_ANONYMOUS 付き mmap(大 / munmap 可能)経由で成長させる。 RSS は消費される物理メモリ;VSZ はマップされた仮想空間 —— 前者が RAM をコストするもの。」
malloc と free が実際に何をするか
アロケータの仕事は OS が与えた連続スラブを要求サイズの片に切り、 どの片が生きているかを追跡し、free されたものをリサイクルし、 スラブが尽きたら成長させること。複雑性の大半は断片化との戦いにある。
malloc(n) は n バイトの未初期化メモリへのポインタを返す。free(p) はアロケータにそのポインタがもう使われないと伝える。 この 2 つの呼び出しの間、アロケータは:(1)適切なサイズの free チャンクを見つけ、 (2)free 時にチャンクサイズが分かるよう簿記を記録し、 (3)アラインされたメモリを返す(SSE 互換のため典型的に 16 バイトアライン)、責任を負う。
Free リストとサイズクラス
最も単純なアロケータは free チャンクの単一連結リストを保持し、 十分大きいもの(first-fit)、または収まる最小(best-fit)を見つけるためにそれを歩く。 両方とも割り当てごとに O(n)、規模感ではひどい。実アロケータはサイズクラスを使う: サイズで割り当てをバケット化(典型的に 2 の冪または 16、24、32、48、64 ... のような 他の幾何数列)し、バケットごとに別個の free リストを維持する。 割り当てが O(1) になる:要求を最近接のサイズクラスに切り上げ、そのバケットの free リストの先頭をポップ。
コスト:内部断片化(internal fragmentation)。 17 バイト割り当てが 24 に切り上げられると、割り当てごとに 7 バイト無駄になる。 数百万割り当てで積み重なる。現代アロケータはより細粒度なサイズクラス (jemalloc は数 KB まで ~40 バケット)を使って内部無駄を 10% 未満に抑える。
結合(coalescing)
チャンクが free されると、アロケータは隣も free かチェックする; そうなら、それらを 1 つの大きな free チャンクにマージする。 この結合(coalescing)が外部断片化が無限に複合するのを防ぐ。 標準実装は各チャンクの末尾に小さなフッタを置き、結合が前のチャンクのヘッダを 後ろ向きに歩いて O(1) で見つけられるようにする。
割り当てごとのヘッダがどこに住むか
malloc から得たポインタの直前に、アロケータは数バイトのメタデータ (典型的に 8–16 バイト)を隠す —— チャンクサイズと 1〜2 つのフラグを記録する。これは意味する: (1)あらゆる割り当てに少なくともそれだけのオーバーヘッドがある —— 小型割り当ては比率的に無駄; (2)割り当ての末尾を越えて書くと次のチャンクのヘッダを破壊する、 次の割り当て / free でのみ検出され、バグから遠く離れている; (3)free(p) は p の直前のバイトを見てサイズを知る。
なぜ C 組み込みの malloc が滅多に最良の選択でないか
glibc の malloc(ptmalloc)は多くのワークロードで OK だが、 3 軸で専門アロケータに負ける:マルチスレッドのスケーリング (per-thread arena、次節)、OS へのメモリ返却(粘る)、 競合下のテールレイテンシ(アロケータ内部のロック)。 規模感のあるプロダクションコードは LD_PRELOAD 経由でほぼ常に jemalloc、tcmalloc、または mimalloc で置き換える —— 典型的に 10–30% のスループット勝利、99 パーセンタイルレイテンシで劇的改善がしばしば。
要点。「malloc は free チャンクを見つけ、ヘッダを打ち、返す。free はそれを free リストに戻し、隣との結合を試みる。実アロケータは サイズクラスでバケット化して O(1)、バケットごとに free リストを維持する。 最も難しい問題は外部断片化 —— 総 free は最大連続 free と同じではなく、 小さな穴が時間とともに蓄積する。」
jemalloc、tcmalloc、mimalloc —— 現代アロケータが存在する理由
シングルスレッド malloc は本質的に解決された問題。32+ コアでのマルチスレッド malloc は違う —— 3 つの画期的なアロケータがそれぞれトレードオフ空間で異なる設計点を刻んだ。
スレッド競合問題
素朴なアロケータはデータ構造をロックで包む。1 スレッドなら問題ない; 32 スレッドがタイトなループで全員 malloc を呼ぶと、 ロックがボトルネックになり、アロケータは 1 スレッドより良くスケールしない。 2008 年以前の glibc malloc がまさにこの問題を持っていた。
皆が落ち着いた修正:per-thread キャッシュ(または arena)。 各スレッドが小さなローカル free チャンクプールを保持し、 ロックなしで割り当てを処理できる。ローカルプールが枯渇または溢れたら、 スレッドはグローバルプールと同期する —— ただし稀。 簿記はより複雑(per-thread 状態、周期的バランシング、グローバルティアでのロック)、 しかし一般ケースの割り当てはロックフリー。
jemalloc
元々 FreeBSD 由来(2005)、Facebook(現 Meta)が ~2009 年に彼らのバックエンドに採用。 per-thread キャッシュ(tcache)が少数のグローバル arena(典型的に CPU 数の 4 倍)で裏付けられる。割り当ては ~14 KB まで ~40 バケットに サイズクラス分類される;より大きいものは別個の slab システムを通る。 断片化制御(洗練された結合)と OS へのメモリ返却(積極的 purging)で強い。 高割り当てレートサーバワークロードの業界デフォルト; Rust の最近までのデフォルト、Redis の多くのビルドでのデフォルト。
tcmalloc
Google の貢献(~2006、2019 年に「tcmalloc next generation」として書き直し)。 オリジナルバリアントは per-thread キャッシュ + グローバル pageheap + サイズクラスごとの CentralFreeList を使う。短寿命小型割り当てに最適化 (Google のトレースがハッシュテーブル churn と protobuf オブジェクトに支配されるワークロード)。 サンプリングベースのプロファイラを持ち、pprof 互換のヒーププロファイルを無料で与える。
mimalloc
Microsoft Research、2019 年。3 つの中で最新、クリーンな実装 (アロケータ全体で ~6000 LOC)と言語ランタイムへの組み込みのファーストクラスサポートのために設計された。 ページごとの free リストを持つ per-thread ヒープで、「割り当てたスレッドと違うスレッドで free」 (async ランタイムとメッセージパッシングシステムで一般的)ケース向けに 明示的に設計されている点で際立つ。データ局所性のストーリーが異常に良い —— 兄弟割り当てがアドレス空間で近くに留まり、キャッシュ挙動を助ける。 マクロベンチマークで jemalloc/tcmalloc とおおむね競争力がある; あるものでより良く、別ものでより悪い。
いつ切り替えるか
デフォルトの glibc malloc は多くの CLI ツールとシングルスレッドワークロードに OK。次の場合に上記の 1 つに切り替える:
- 高割り当てレートのマルチスレッドサーバ。per-thread キャッシュが 16+ スレッドで 2–5× スループット改善を与える。
- 安定したワーキングセットにもかかわらず RSS が時間とともに成長。glibc はメモリ返却に苦労する;jemalloc は
madvise(MADV_DONTNEED)経由で積極的に purge。 - テールレイテンシが重要。アロケータロック競合は他のものと相関しない p99 スパイクとして現れる。
- ヒーププロファイリングが必要。tcmalloc の pprof 統合は再コンパイルなしで割り当てがどこで起こるかを見つける最も簡単な方法。
切り替えは通常コマンドラインに LD_PRELOAD=/path/to/libjemalloc.soを加えるか、依存としてリンクする。コード変更は不要。
要点。「シングルスレッド malloc は解決された。マルチスレッドの スケーリングには per-thread キャッシュが必要:jemalloc(FB のデフォルト、断片化制御が最良)、 tcmalloc(Google の、プロファイリングが最良)、mimalloc(Microsoft の、クロススレッド free と 埋め込みに最良)。LD_PRELOAD 経由の切り替えはしばしば 10–30% のスループット + より低い p99 レイテンシを無料で与える。」
断片化、リーク、その違い
プロセスのメモリが無制限に成長する 3 つの異なる方法、それぞれ異なるメカニズムと異なる修正。 それらを混同するのがメモリデバッグ混乱の最多原因。
内部断片化(internal fragmentation)
17 バイトを要求してアロケータが 24 を与える。無駄な 7 バイトは内部断片化: あなたの割り当てに属するが、使えない。サイズクラス丸め(あらゆる現代アロケータ)と アラインメント要件(malloc されたメモリは通常 16 バイトアライン)が原因。 汎用ワークロードの典型的な無駄:総割り当てメモリの 5–15%。 粗いサイズクラスを持つ安いアロケータはより多く無駄にする;細粒度のものは少ない。
修正:サイズクラス認識のアロケータ(jemalloc、mimalloc)を選ぶ; 「クラス境界の直下」の異なる割り当てを多く避ける (65 バイト struct は jemalloc で 80 に丸まる —— 可能なら 64 に詰める)。
外部断片化(external fragmentation)
ヒープには合計で多くの free バイトがあるが、新しい要求に十分大きな単一連続チャンクがない。 §2 の HeapAllocator demo が基本ケースを示す。アロケータは要求を失敗させる(稀)か、 カーネルにより多くのメモリを要求してヒープを拡張する(一般的 —— そのメモリは 既存の断片が多くの小型要求を吸収できたとしても RSS を成長させる)、いずれか。
修正:結合が助ける(あらゆる実アロケータがそれを行う)。サイズクラスごとの free リストは クラス内の断片化を防ぐが、クラス間のものを許す。混合割り当てサイズの長寿命プロセスは 必然的にいくらかを蓄積する —— 問題はレート。プロセス再起動は粗野な修正で広く使われる (プロダクションでのローリング再起動)。
メモリリーク
アプリケーションがメモリを割り当て、すべての参照を失うが、free を呼ばない。 古典的原因:C/C++ で free を忘れる;参照カウントデータでのサイクル (Rust の Rc、Python の参照カウント);追い出しなしの成長キャッシュ; 無界キュー。純効果:RSS は同時負荷ではなくワークロードに単調に成長する。
ガベージコレクション言語は古典的なリークを持たないが保持バグを持つ: グローバルキャッシュ、大型オブジェクト上のクロージャをキャプチャするイベントリスナ、 無界に成長する静的マップ。C リークと同じ運用症状。 ヒープダンプ(jmap、V8 の heap snapshot)が保持ルートを特定する。
区別する方法
- RSS がスループットとともに上昇し、プラトーする。内部断片化の可能性が高い —— ワークロードが成長したので総割り当てが成長したが、 各チャンククラスはよく利用されている。アロケータ切り替えが助けるかも; そうでなければ予算化する。
- 安定したスループットでも RSS が数時間 / 数日かけてゆっくり上昇。外部断片化。アロケータがヒープを再圧縮できないので、brk 割り当てページが 大半未使用でもマップされたまま残る。OS へ purge するアロケータに切り替える (デフォルト設定の jemalloc)。
- RSS が累積処理済みリクエストに線形に上昇、決してプラトーしない。リーク。リクエストごとの何らかの割り当てが free されない。 ツール:C/C++ に
valgrind --leak-check=full; コンパイル言語に ASan(-fsanitize=address); ヒーププロファイラ(jemalloc の、tcmalloc の、V8 の)が割り当てサイトをサンプリングする。
RSS = max() 問題
RSS は成長するのみ(または同じまま) —— ほぼ縮まない。アロケータがページに触れたら それは RSS にあり、ページは明示的な madvise または munmapでのみカーネルに返される。だからワーキングセットの短いスパイクでも、 プロセスの長期 RSS を高いままにしうる。現代のアロケータはこれを緩和するために バックグラウンド purge スレッドを走らせる;古いものはしない。
要点。「内部断片化:サイズクラスバケットが持つよりも少ないバイトを要求、 残りは無駄だが一貫している(典型的に 5–15%)。外部断片化:総 free は問題ないが 連続チャンクが収まらない —— 時間とともに成長、結合と積極的 purge で緩和。 リーク:free を呼ばない、累積作業に単調に成長。RSS 対時間グラフの形が診断。」
クイックリファレンス
冷たく説明できる価値のある 6 つの核心問題と、コードレビューで一目で見抜くべき 5 つの赤旗。
スタックとヒープ割り当ての違いは?
スタック:割り当ては rsp をデクリメント(コストゼロ); メモリは関数が返るまでのみ生存;有界サイズ(Linux で ~8 MB)。 ヒープ:アロケータが free チャンクを見つけ、ヘッダを打ち、返す; メモリは free まで持続;仮想アドレス空間でのみ制限される。 関数呼び出しより長生きするものはすべてヒープに行く。
プロセスのヒープを成長させる 2 つの syscall は?
brk(と sbrk)は data segment 境界を動かし、 ヒープを連続的に成長させる。安いが、メモリは上から OS へのみ返せる —— 上に小さな割り当てがあると、その下のヒープ全体がマップされたまま。mmap MAP_ANONYMOUS は独立した VMA を作成;任意の順序でmunmap できる。glibc はデフォルトで小型割り当てに brk を、 > 128 KB に mmap を使う。
なぜ jemalloc / tcmalloc / mimalloc は glibc malloc より速いか?
per-thread キャッシュ。glibc のデフォルト(ptmalloc)はミューテックスでロックされた arena を使う; 多くのスレッドからの競合下でロックがボトルネックになる。jemalloc、tcmalloc、mimalloc はそれぞれ各スレッドにロックフリーで処理できる private な free チャンクキャッシュを与える。 一般ケースで割り当てが O(1) かつ競合フリーになる。16+ スレッドでスループット勝利は 2–5×。
RSS と VSZ の違いは?
RSS(resident set size)はプロセスに現在割り当てられた物理メモリ。 VSZ(virtual size)は総マップ仮想アドレス空間 —— まだ触れていない部分(ページテーブルではまだゼロ)とディスクにスワップされた部分を含む。 RSS が RAM をコストする;VSZ はページテーブル自体を膨れ上がらせるほど巨大なときのみ重要。 1 TB VSZ + 200 MB RSS のプロセスは問題ない。
内部断片化、外部断片化、メモリリークを区別。
内部:17 バイトを要求しアロケータが 24 を与える; 余分な 7 は無駄だが「使用中」とカウントされる。安定したオーバーヘッド(典型的に 5–15%)。外部:合計で多くの free バイト、しかし単一連続実行が十分大きくない; ヒープが時間とともに成長する。リーク:割り当てが free されない; RSS は累積作業に単調に成長する。RSS 対時間グラフ上の異なる形;異なる修正。
malloc ではなく直接 mmap を選ぶのはいつか?
3 ケース:(1)OS への返却を容易にしたい非常に大きな割り当て(マルチ MB)—— 直接 mmap がアロケータの判断に頼るよりクリーン;(2)プロセス間共有メモリ —— ファイルまたは shm 領域上の MAP_SHARED 付き mmap; (3)read/write オーバーヘッドではなく OS のデマンドページングが 欲しいメモリマップファイル。それ以外は、アロケータに任せる。
コードレビューの赤旗
- ホット内側ループ内の malloc/free。各呼び出しが ~50 ns に 潜在的なロック競合を加える。割り当てを外に持ち出す、プールを使う、または 有界な場合は
alloca/VLA でスタック割り当てする。 - 似たサイズの小型割り当てが多い。per-thread キャッシュがあっても、 チャンクごとのオーバーヘッドが支配する。arena アロケータか slab を使う。
- 追い出しポリシーのない長寿命キャッシュ。特にガベージコレクション言語で、無界の
HashMap/dict/Mapは「到達可能」であってもメモリリークに見える。LRU を使うかサイズを制限する。 - 同一プロセス内に多くの異なる固定サイズアロケータを混在。各々が独自の簿記オーバーヘッドを持つ。統合する。
- デフォルトの glibc malloc で、割り当てたのと異なるスレッドから
freeを呼ぶ。ptmalloc の arena はこのパターンで悪く劣化する;それ向けに設計された mimalloc または jemalloc に切り替える。