システムプログラマのためのガベージコレクション (2023)
(bitbashing.io)- カーネルやドライバのように 性能と並行性 が重要なコードでも、メモリ解放は単純な
free()呼び出しで終わるものではなく、ロックなしの共有手法が必要になることがある - RCU(Read, Copy, Update) は、頻繁に読み取られまれに変更されるデータをコピーしたうえでポインタをアトミックに置き換え、読み取りパスを妨げない方式である
- 以前のバージョンを即座に
deleteすると、まだ読んでいるスレッドで use-after-free が発生しうるため、RCU は読み取り区間を追跡し、安全な時点まで解放を遅らせる - RCU は Linux で数万回使われており、Folly C++ ライブラリや Rust の
crossbeam-epochにもあり、使用中かどうかに応じて後で回収される という点で GC と同じような形を持つ - 手動メモリ管理が常により高速で予測可能だという二分法は弱く、
free()、参照カウント、OS のメモリ動作にもコストと不確実性があるため、現代的な GC もシステムプログラミングの道具になりうる
カーネルコードが RCU のような手法を使う理由
- オペレーティングシステムは、日々実行されるプログラムの中でも 性能感度 が高い部類に入る
- OS が高速になれば、ユーザーはより多くの計算を行えるため、カーネルやドライバの開発者はコード最適化に多くの努力を注ぐ
- オペレーティングシステムは、ユーザー空間のプロセスやスレッドだけでなく、カーネル自身の複数のスレッドやハードウェア割り込みハンドラまで扱わなければならない
- 待ち時間が増えるとユーザーの時間を奪うため、カーネルコードではロックなしでスレッド間のデータを共有するさまざまな手法が生まれてきた
RCU の基本動作
- RCU(Read, Copy, Update) は、非常によく読まれるがまれにしか書き換えられないデータに向いた方式である
- 現在接続されている USB デバイスの集合のように、ほとんど変わらないが変更されることはあるデータが例になる
- 変更はアトミックに行われなければならず、すでに読み取っている読者を妨げてはならない
- 書き手は共有状態を次の順序で更新する
- 既存データをポインタから読む
- 既存データをコピーし、必要な変更を適用して新しいバージョンを作る
- ポインタをアトミックに更新して新しいバージョンを指すようにする
- 読み手は共有ポインタを読むだけなので、読み取りパスは単純で待ちなしに動作する
- この方式は使いやすく wait-free だが、以前のバージョンを片付けなければ メモリリーク が発生する
すぐには解放できない以前のバージョン
- ポインタを新しいバージョンに切り替えた直後に以前のバージョンをすぐ
deleteすると、use-after-free の危険が生じる - ロックなしで動作するため、書き手はまだ以前のバージョンを読んでいる読者がいるかどうか分からない
- 読み手は
rcu_read_lock()とrcu_read_unlock()で読み取り側クリティカルセクションを示せる- 読み手は依然としてブロックされない
- 書き手は、それらの読者が抜けるまで以前のデータを削除しない
rcu_synchronize()はすべての読者がいなくなるまで待つのではなく、以前のバージョンを見る可能性がある 先行する読者 が終わるまで待てばよい- 新しいポインタを見た読者は新しいバージョンを使うので、以前のバージョンの寿命とは無関係である
遅延解放と GC の形
- 書き手が更新関数の中で待たなくても、以前のデータがいつか安全に解放されればコードは正しく動作する
rcu_defer(old)のような方式では、現在の読者がクリティカルセクションを抜けたあと、いつでもoldを解放できる- 専用スレッドが古い未参照バージョンを定期的に片付ける形は、世代別 GC に似ている
- RCU は思考実験ではなく、実際に広く使われている手法である
- Linux は RCU を数万回使用している
- Facebook の Folly C++ library には RCU が用意されている
- Rust では
crossbeam-epochという名前で使われ、人気のある並行性ライブラリの基盤になっている
- RCU が「本当の GC」かどうかという分類上の議論より重要なのは、メモリが 使用中かどうか に応じて後で回収される構造が GC と同じだという点にある
手動解放の隠れたコスト
- GC が手動メモリ管理より本質的に効率が低いという通念は、実装の詳細を見ると弱くなる
-
free()はタダではない- 汎用メモリアロケータは、カーネルから受け取ったページ、サイズ別バケット分割、使用中のバケットといった内部のグローバル状態を管理しなければならない
- 複数スレッドがアロケータ状態をロックしようとして競合が生じることがある
- jemalloc のようにスレッドローカルプールを持たせても、それを同期するための追加コードが必要になる
-
RAII と lifetime もアロケータのコストを消しはしない
- Rust の lifetime や C++ の RAII は、メモリ解放の自動化と正確性には役立つが、アロケータ内部構造の複雑さをなくすわけではない
- 多くのシナリオでは
shared_ptrやArcに戻らざるをえない - 参照カウントという追加メタデータが必要で、この値がコアとキャッシュの間を行き来してコストを生むことがある
- 生存性グラフの循環によってリークを起こすこともある
-
GC が提供できる最適化もある
- 移動式の世代別 GC はヒープを定期的に再圧縮する
- 割り当てはポインタを進めるのに近い形になり、高いスループットを出せる
- 逐次割り当ての局所性が良くなり、キャッシュ性能にも役立つ
メモリ管理制御に対する思い込み
- GC に反対する多くの開発者は ソフトリアルタイム システムを作っている
- ビデオゲームの FPS やストリーミングコーデックの圧縮性能のように、できるだけ高速な動作を望んでいる
- しかし、たまに 1 ミリ秒余計にかかっただけでシステムが壊れたり人が死んだりするようなハードな遅延要件ではない
- プログラマがメモリ管理がいつ起きるかを決められるという信念は、そう単純ではない
- オペレーティングシステムはハードウェアとの相互作用を抽象化する
- Linux はデフォルトではメモリ要求時にほとんど何もせず、実際に使おうとしたときにメモリを渡すことがある
madvise()、メモリマップド I/O、ファイルシステムキャッシュが絡むと、「何がいつ割り当てられたのか」に単純な答えはない- 悪い日には、単純なポインタアクセスがディスク I/O につながることすらある
- プログラマがメモリ管理のために停止するのに都合のよい時点を常に知っているという考えも限定的である
- ビデオゲームのロード画面のように明確な場合もある
- 多くのソフトウェアでは、より重要な作業で忙しくないときというのが唯一の答えになる
shared_ptrとArcを持つ個々のコードは、自分が最後の所有者になって後片付けを引き受けるかどうかを事前には分からない
free()を呼べばすぐメモリが OS に返るという信念も、常に正しいわけではない- メモリはページ単位で OS から割り当てられる
- アロケータは、プログラム終了までページを保持して再利用しようとすることが多い
- OS はスワップによってページを回収することもある
GC をシステムプログラミングの道具と見なせる理由
- すべてのソフトウェアが GC の恩恵を受けるわけではない
- しかし 2024 年に近い時点でも、システムプログラマの間での GC 議論は、誤った二分法と恐怖・不確実性・疑念に埋もれがちである
- GC を使う言語が手動メモリ管理言語より「明らかに」遅いという考えは、事実というより イデオロギー に近い
- 命に関わるシステムを作るチームでも、ほぼすべての行で割り当てを行う GC 言語でサブマイクロ秒のレイテンシを実現した例がある
- システムの一部が必ず
nクロックサイクル以内に実行されなければならないなら、その特定部分だけを非 GC コードやハードウェアに切り出すこともできる - GC は万能の解決策ではないが、恐れずに使える ツールボックスの中の道具 の一つである
1件のコメント
Hacker News のコメント
有望な現代的な並列ガベージコレクション手法としては、MPL または MaPLe と、その新しい Automatic Management of Parallelism が注目に値する
POPL 2024 distinguished paper award と ACM SIGPLAN dissertation award 2023 を受賞した要点は二つある: a) disentanglement に基づく、証明可能に効率的な並列ガベージコレクション、b) 証明可能に効率的な自動粒度制御
[1] MaPLe (MPL): https://github.com/MPLLang/mpl
[2] Automatic Parallelism Management: https://dl.acm.org/doi/10.1145/3632880
リンク先の論文もあるし、リージョンベースのメモリ管理の初期の利用者であり先駆者の一つだった MLKit もある
例えば、このようなアプローチで Go のガベージコレクションを大幅に高速化できるのか、それとも既存の言語設計上の問題にぶつかるのだろうか？
RCU のユースケースは説得力があるが、他の状況でのガベージコレクションの経験は良くなかった
この記事は、静的ライフタイムが動的ライフタイムより一般に優れているという主張というより、カスタムのメモリ管理ソリューションが最高の性能を出せるという主張のように読める
free()がメモリを OS に返すと信じているのではなく、アロケータに返すものだと見ている。これは OS に返すよりはるかに良く、システムコールは遅い。ただし mimalloc のように、解放されたメモリを次のmallocですぐ使わず、周期的にしか使えるようにしないこともある800バイトを割り当ててすぐ
freeする処理を100万回繰り返し、ユニークなポインタ数を数えると、glibc malloc は 1、jemalloc は 1、mimalloc は 4、Julia のガベージコレクタは 62767 だった62767個、約48MiBなので極端に悪いわけではないが、それでも自分のコンピュータの L3 キャッシュを押し出してしまう。ガベージコレクションを使うと、新しい割り当てはキャッシュではなく RAM から来ることがほぼ保証され、割り当ての多いコードの性能を壊す。メモリ管理そのものの速度だけでなく、それが渡したメモリでどれだけ速く作業できるかも重要
Julia でこれを示すベンチマークを投稿した: https://discourse.julialang.org/t/blog-post-rust-vs-julia-in...
malloc/free は、実際のワーキングメモリが十分小さければ、キャッシュにホットなまま残る機会を与える。mimalloc のようなアロケータも、圧縮ガベージコレクションのように連続した割り当てが近くに配置されるよう設計されており、私が見た mimalloc の4つのユニークポインタは 896 バイト間隔だった
圧縮ガベージコレクションの経験がもっとあれば、考え方はそれほど冷笑的ではなかったかもしれないが、ガベージコレクションは安全なメモリ管理のためには Rust の借用チェッカーのようなものよりはるかに複雑な解法だと思う。その複雑さはコンパイラとランタイムの開発者に押し付けられるので、ユーザーにはたいてい問題なく、性能に敏感でないコードを書くときには受け入れられるトレードオフだ。静的ライフタイムを持つ RAII も、よりカスタムなアプローチを必要としないコードには妥当なトレードオフであり、記事の例は明らかにカスタム解法が必要な場合だ
圧縮ガベージコレクションは、長時間実行されるプログラムではヒープ断片化が TLB キャッシュ項目とオブジェクト間の空き領域を無駄にするため、ほとんど常に malloc よりキャッシュ利用が良い。圧縮ガベージコレクションのバンプアロケータは
freeがメモリを回収しないので割り当てごとに新しいポインタを返すが、それらの割り当ては逐次的で、ヒープを消費し続けながら最新のオブジェクトだけを触る場合なら、依然としてキャッシュに残っている。アロケータとガベージコレクタの波及効果をベンチマークするのは極めて難しく、こうした合成ベンチマークはほぼすべて懐疑的に見ている人々が懸念しているのは、メモリをもう使っていないかどうかを突き止める過程が、リソースの使用を終えたとアロケータに直接伝えることより非効率で非決定的だという点だ。解放を遅らせること自体を心配している人は見たことがない
生きている集合全体を走査することはまれで、この30年でガベージコレクションのアルゴリズムは、ほとんど知性があると言える水準まで改良されてきたが、この文は人々が実際に問題にしている点を、意図的かどうかはともかく無視している。サービスでガベージコレクション問題が起きると、あちこちをチューニングして怒れる魂を影の世界へ送り返してくれることを願い、呪術師を呼ばなければならないような気分になる
ゴミに印を付け、もう使われなくなったときに通知を受ける方式なら、その過程全体が消える。ガベージコレクションではメモリ割り当てが非常に高速になり得るが、公平に比較するなら、マーキングと圧縮のコストも償却して含めるべきだ
もう一つの大きな問題は、同じ性能を得るために、一般にガベージコレクションは手動メモリ管理よりはるかに多くのメモリを要求することだ。参照がまだあるかを繰り返し重複確認するための余分な CPU も必要で、楽観的な圧縮のための追加のメモリコピーも受け入れなければならない
最後に、記事はライフタイムが不明確なとき Rust の Arc/Rc のような手動メモリ管理が必要になると批判しているが、ガベージコレクション言語でも finalizer が必ず呼ばれるとは信頼できず、外部リソースを閉じるために事実上まったく同じインフラを作る点は無視している
この論争はこの20〜30年で十分に繰り返されており、この記事は正当なガベージコレクションへの懸念をミームとして片付ける以外、新しく持ち込むものはないように見える。ミームは面白いので構わないが、答えは一般的な正解は存在しないということだ。システムの設計制約を満たすのに合った道具を使えばよい
それ以外のより長寿命な割り当ては、定義上キャッシュの観点では制御しにくい。局所性はガベージコレクションの大きな利点の一つであり、私の知る唯一の問題は stop-the-world のマーク/スイープだ。現代のガベージコレクションがバックグラウンドスレッドを持つことは知っているが、それでも stop-the-world イベントは発生すると理解している
free()がメモリをアロケータに返すというのは正しいが、長時間実行されるサーバーで メモリ断片化 に対処するのはまったく楽しくない特に slab アロケータが管理するページの内部断片化がそうで、よくある問題ではないが扱いにくい問題だ
幸い、ガベージコレクションがこのように都合よく作られた例と競争しなければならない領域は多くない
すべてのメモリを簡単にアリーナで扱える特殊な場合を除けば、優れたトレーシング・ガベージコレクションは、スループットではずっと以前に手動メモリ管理を上回っており、最近ではレイテンシへの影響も大多数のアプリケーションで十分受け入れられるものになっている
OpenJDK の ZGC は、一般的な停止時間が 2〜3 桁マイクロ秒単位で、妥当な割り当て率では最悪でも 1ms をほとんど超えず、OS が引き起こす停止と同程度の範囲にある
本当に重要なトレードオフはメモリ使用量だけだ。特殊なニッチ、つまりアリーナがあらゆるものにうまく合い、最悪レイテンシが低いマイクロ秒域に収まる場合を除けば、核心となる問いは一つだけだ。自分のアプリケーションはメモリ制約のある環境で動くのか、あるいは RAM 使用量を減らすために他のものを犠牲にする価値があるのか
そうしたコードで個々のオブジェクトの寿命を追跡するのは過剰だ。結局、メモリ管理は寿命に関するものであり、多数の個別の寿命より少数の個別の寿命の方が常に良い。手動であれ自動であれ、やるべきことが減るからだ
オブジェクトの寿命を考えなくてよいのは非常に便利であり、だからこそ優れたガベージコレクタの内部複雑性が相当なものであるにもかかわらず、ガベージコレクション言語は成功した
予測しにくいテールレイテンシや、さまざまな例外的状況の影響も受け続ける
ZGC は Shenandoah より停止回数が少ないように見え、そのため 1 回の停止でより多くの仕事をしているらしく、少し良い性能を示している
まだ本番環境でのテストは必要だが、これまでのところ ZGC、そして Java 21 以降の世代別 ZGC を使えば、ガベージコレクションによる停止はおおむね解決済みの問題のように見える
Jai の見方のように、メモリ割り当ては頻度の高い順に 4 つに分けられる: 1) 極めて短命で関数スタックに置けるもの、2) 短命で寿命がよく定義されており、フレーム/リクエスト単位のメモリアリーナに置けるもの、3) 長命で所有者がよく定義されており、サブシステム専用プールで管理できるもの、4) 長命で所有者が不明確なため動的メモリ管理が必要なもの
トレーシング・ガベージコレクションが一般に手動メモリ管理を上回ると主張するなら、あちこちで malloc/free を呼ぶシステムではなく、こうした観点を念頭に置いて書かれたシステムと比較すべきだ。現代の C++/Rust の慣行と比較すれば、より公平かもしれない
ほとんどのシステムではトレーシング・ガベージコレクションに依存する方がはるかに実用的である可能性が高い、という点には同意するが、それはまったく別の主張だ
この記事は RCU の動機付けをしたあと、急に方向転換して汎用ガベージコレクションを一般論として擁護し始める
トロイの木馬とまでは言わないが、かなり急激な転換に感じる
オブジェクトは 3 つの状態のいずれかにあり、可能な限り速く遷移する: active, obsolete but alive for old readers, deallocated
コードの書き方によっては、“obsolete-but-alive” オブジェクトを “new” 割り当てに安全に再利用できるかもしれないが、性能については完全には分析していない
ガベージコレクションの議論でよくあるように、いつ
shared_ptr/Arcに「後退」すべきかは非常に曖昧だ。実際には参照カウントを避けること、つまりすでに所有権があることを証明するか、間接参照そのものを避けることが、本格的な参照カウントベースのシステムの核心だ。何もしないことは、ガベージコレクションの「いつか何かをする」より当然ながら優れている私が使うソフトウェアには 2 つの場合がある。(1) 常にカスタムアロケータを使い、割り当てを避けるホットパス、(2) それ以外すべて
(1) ではガベージコレクションであろうとなかろうと違いはなく、私はそこから抜け道を用意する。(2) ではガベージコレクションは本当に便利で正しい
Java が現代的なガベージコレクタで成し遂げてきたことは印象的だが、彼らでさえ Valhalla を通じて、間接的に無割り当て/低割り当てコードの居場所があることを認めている
現代のユーザー向けOS、つまり特殊なRTOSではないOSには組み込みのガベージコレクションがある、という観察はここで少し外れている
私たちは単にそう呼ばず、メモリ管理と呼んでいるだけだ。組み込みのガベージコレクションがある言語を何と呼ぶか？ メモリ管理言語と呼ぶ
古い「上から下へ」実行されるCプログラムでは、こういう姿をよく見る。確保して、システムリソースは片付けるが、
freeは気にしない。プログラムが終了すればOSがそのメモリをすべて取り戻すのだから、なぜわざわざやるのかここには、プログラムとの隔離がより弱いOSレベルのガベージコレクタ、言語ランタイムのガベージコレクタのようにリソースを扱うOSを作る機会がある。だが通常、ガベージコレクション言語ではガベージコレクタがランタイムのほぼすべての行に複雑に絡み合っているため、あるOS向けのディストリビューションだけがその制御をOSに委ねるようにするのは現実的ではない
それでも惜しい。プログラムレベルのメモリ管理とOSレベルのメモリ管理の人為的な隔離によって生じる慢性的な問題を改善できる余地が大きいからだ
メモリを解放する唯一の理由は、長時間実行されるアプリケーションで、OSから新しいメモリをさらに取得せずに他の割り当てに再利用するためだ。一度実行して終わるコマンドラインツールでは通常必要ない
プロセスが仕事を終えたら終了するように設計されているなら、OSをガベージコレクタのように使える
しかし、実行中のプログラム内部でどのメモリが使われていないかをOSが知る方法は存在したことがない。難解な研究用OSくらいは例外かもしれない。だから、逃した機会というより、逃したと言われている対象が意味のある形では存在しないのだと思う
一方で、ごく単純で短命なプログラムを書くプログラミングスタイルは完全に正当だ。CLIツールとそれをスクリプトするスクリプト言語はそのように動作し、昔のWebサーバーもCGIなどでそのように動作していたし、今日でも十分に合理的なアプローチだ
(1) RCUから汎用のトレーシングガベージコレクションへ移る展開は、餌をまいておいてすり替えるように感じる
(2) 手動メモリ管理はmalloc/free呼び出しだけではなく、レイアウトに関するものだ。例えば、構造体配列の分離、インライン化、暗黙のオフセット、パッキングなどがある
「構造体の配列」のことを言っているように見えるが、タプル配列で実現でき、ターゲットに応じて自然に平坦化・正規化される。つまりネイティブターゲットでは構造体の配列になる
バイト単位で正確なレイアウトも定義でき[1]、主に他のソフトウェアとの連携やバイナリ形式のパースに使われる。代数的データ型をアンボックス化でき、まもなく代数的データ型の正確なエンコーディングまで制御できるようになる
Virgilはガベージコレクションを使用する
[1] https://github.com/titzer/virgil/blob/master/doc/tutorial/La...
現代のマネージド言語にメモリレイアウト制御が不足しているのは明らかだが、低レベル言語でも完璧には程遠く、影響を与える方法も確かにある
この記事で抜けている点の一つは、async/awaitがガベージコレクションと非常に相性がよいということだ
個人的な独特のスタイル上の理由でasync/awaitは嫌いだが、長くは語らない
TypeScript/JavaScriptではかなり使ったし、Dartでも使ったが、そこでは期待どおりに動作する
Rustでも使ったが、私の考えでは惨事だ。マルチスレッドランタイムでasync/awaitを使うために必要とされる種類のメモリ管理を無理やり押し込むのは地獄絵図だ
https://doc.rust-lang.org/std/pin/index.html
ガベージコレクションを擁護する多くの文章で抜け落ちている点がありますが、この記事もそう見えるように、メモリはリソースの一種にすぎません
特にシステムプログラミングでは、正しいコードはファイルハンドルやソケットなどの外部リソースも管理しなければなりません。ガベージコレクションはアプリケーションのメモリ部分だけを解決するため、こうした外部リソースの処理にはまったく役立ちません。むしろはるかに複雑にすることもあり、.NETで自明でないIDisposableを正しく実装するには何が必要かを見るだけでも分かります
RAIIや参照カウントのようなアプローチは、私の経験ではメモリと外部リソースを統一された形で扱うのをはるかに容易にし、正しいコードを書き、推論することも容易にします
とはいえ、ガベージコレクションに露骨に反対しているわけではありません。他のあらゆるものと同じく、長所と短所のある道具です。記事で述べられている「手動GC」RCUアプローチは、特定の作業には興味深いものです
ほとんどの理論的な計算モデルが無限メモリを仮定するのも偶然ではありません。OSカーネルやハードリアルタイムアプリケーションのような一部のソフトウェアでは処理能力も手動で割り当てますが、処理能力を手動割り当てすることを要求する言語はほとんどありません
同じような理由で、自動メモリ管理は計算を抽象化するうえで非常に有用です。サブルーチンのメモリ上の詳細を呼び出し元に漏らさないようにするものであり、CPU使用量についてもこうした詳細が表に出ることはまれです
自明でない計算はすべて、何らかの非定数量の処理とメモリを含みますが、I/Oは通常システムの端で起こります。I/O管理ももちろん非常に重要ですが、計算という概念と計算の抽象化における中心性という点では、処理とメモリほど核心的ではありません
たとえばRustは最終的にI/O安全性を備えるようになり、そのためUnixの
OwnedFdのようなファイルハンドルやWindowsのOwnedHandleのようなハンドルが、数値4のような整数ではなく、所有されるオブジェクトになりました表面的には、ハンドルに算術演算をしたり、予約値をセンチネルとして誤用したりする愚かなミスを避ける話のように見えますが、所有権モデルのおかげで、ハンドルに対して厄介な操作をしても明示的な所有権が生まれ、後の保守担当者にも透明になります
RAIIの価値を本当に強く感じました
ある言語にはRAIIがあり、ある言語はキーワードを提供し、ある言語はアリーナのような管理や暗黙的管理を持つラムダを提供します。ある言語は型システムの助けを少し受け、ある言語は上記を少しずつ混ぜ合わせます
さらに、システム開発者が静的解析器に頼る必要があるのと同じように、そうした言語の静的解析器も、型システムだけでは十分でない場合に見落としを検証してくれます
たとえばJavaのtry-with-resources文は、例外が発生してもリソースが安全に解放されることを保証します: https://docs.oracle.com/javase/tutorial/essential/exceptions...
こうした基本的な構成要素だけでも、かなり堅牢でリソース安全なシステムを作れます