有給を駆使し一足早くクリスマス休暇に突入、ヒャッホイ Ingress やるぜーと 意気込んでいた矢先ノロウイルスにやられダウンした。かなしい。鎮まれ俺の胃袋・・・ そんな腹痛日和の気晴らしとして今日は Garbage Collection Advent Calendar に参加してみることにしました。 Advent Calendar 初体験につきよくわかってないけど勝手に参加していいんですよね？
GC というとジェネレーショナルだのパラレルコンカレントだのといった話が目立ちがちだけれど、 現実の問題というかブラウザを相手にするとそれ以外の細々とした面倒が目につく。 GC つき言語 (JavaScript) のコードと C++ で書かれたコードとの連携は最たる面倒の１つ。 たとえば WebKit の DOM は C++ で実装されており、 C++ のオブジェクトは JavaScript 処理系の GC に追跡されていない。かわりに C++ 固有の参照カウント方式で管理されている。 こいつら C++ オブジェクトをどうやって JavaScript と混ぜるかは、一部ブラウザ開発者を悩ませてきた。
ラッパーオブジェクト
C++ のオブジェクトに JavaScript オブジェクトの姿を与えるのは ラッパーオブジェクト の仕事だ。
ラッパーオブジェクトは C++ のオブジェクトと対になる JavaScript オブジェクトで、対応する C++ オブジェクトへのポインタをこっそり持っている。
ラッパーオブジェクトは、C++ オブジェクトを JavaScript の世界に持ち出す際、必要に応じて作られる。
たとえば window オブジェクトのラッパーオブジェクトはプログラムの開始直後から存在するけれど、 window.document のラッパーオブジェクトや
window.document.getElementById("foo") が返す戻り値のラッパーオブジェクトは、アクセスされたときに初めて作られる。
ラッパーオブジェクトは自身に紐付く C++ オブジェクトへのポインタを受け取った際、その参照カウントを増やす。 そして自分が GC で回収されるときに 同じ参照カウントを減らす。つまりラッパーは C++ オブジェクトを 所有 している。
反対に、C++ オブジェクトも対応するラッパーオブジェクトへの参照を持っている。
ある C++ オブジェクトに対応するラッパーオブジェクトがわからないと、
たとえば document.body.firstChild を呼び出すたびに .body や .firstChild に呼応して
新しいラッパーが作られてしまい、意味的にも性能上も不都合がある。
ある C++ オブジェクトに対応する既存のラッパーがわかればそれを再利用できる。新しいラッパーをつくらずに済む。
ややこしいので今は理解しなくてもいいけれど、細かい話として C++ オブジェクトからラッパーオブジェクトへの参照は 弱参照 である。 つまり、C++ のオブジェクトが生きていてもそのラッパーは GC に回収されることがある。しかしこれは場合によっては都合が悪いため、 色々と小細工をして JavaScript から不整合が見えないようがんばっている。そのへんはあとで詳しく説明したい。
古の循環参照問題
昔々、ウェブプログラマによく知られた JavaScript のメモリリークパターンがあった。 それは JavaScript と C++ をまたいだ循環参照を作るというもの。 典型的にはイベントハンドラの関数がクロージャをつくるときに起きた。
var target = document.getElementById("t");
target.onclick = function() { // This closure refers |target|.
target.innerHTML = "I'm leaked!";
};
このコードは以下のように循環を持った参照構造をつくる。
このとき、素朴な実装だと JavaScript の GC は C++ 側の参照構造を知らず、 C++ は JavaScript 側の参照構造を知らない。 いくつかの古いブラウザでは、この循環参照がメモリリークにつながった。 もっとも今は昔。最近のブラウザにこの問題はない。みなそれぞれに直っている。
WebKit/V8 の場合、一部の参照を弱参照にすることで循環を絶ち、問題を回避している。 具体的には C++ のイベントハンドラ(=C++ オブジェクト)から 対応する JavaScript のイベントハンドラ(=関数)への参照が、弱参照としてマークされている。
弱参照を使うと、今度は意図せずイベントハンドラ関数が回収されてしまいそうに見える。 そこでノードのラッパーから関数に向かう参照を足し、回収を防いでいる。 この参照は V8 の “implicit reference” という仕組みで足されており、JavaScript からは見えない。
ツリー構造と参照カウント
ここで一旦 JavaScript から離れ、C++ の参照カウントと DOM ツリーの関係について考えてみたい。 C++ の参照カウンタなんて簡単なものだけれど、DOM にはちょっとだけ面倒なところがある。 洞窟のナゾナゾ対決に備え知っておきたい。循環してるのにリークしない、マークもスイープもいらない寿命管理ってなーんだ？
DOM のツリー構造は、各ノードが親子兄弟子どもたちへの参照を持っている。
このとき、DOM 実装はどうやって参照カウントを上げ下げしているのだろうか。 すべての参照を、強い(カウントを増やす)参照とみなすのはうまくいかない。 あっというまに循環参照ができてしまう。
かわりにツリーをコレクションと捉え、 コンテナたる Document オブジェクトが各ノードの所有権を持つと考えることはできるか。 これもダメそう。Document から切り離されたノードの寿命をどう扱えばいいのかわからない。
たぶん参照カウントを頼る限り決定版の答えはないのだが、 WebKit では 親から子への参照は所有(=強い参照)とみなす というルールに従っている。
これはまあまあうまくいく。(現物は TreeShared.h 参照。)
ただし子が親の寿命に責任を持たないせいで、子が生きているのに親が逝ってしまうケースがある。 問題がおきうるのは、DOM ノードの参照カウントが親だけでなくどこか別のところ(たとえばラッパーオブジェクト)から増やされたとき。
とはいえ普通に DOM を使っている限り、親の失踪を目にすることはない。 がんばって変なコードを書くと JavaScript からこの消し過ぎ現象を観察することはできる。 暇なひとはパスルだと思って試してみてください。 (ちゃんと動くブラウザもあるのでチャレンジャーは Chrome 系列でおためしを。)
隠れたオブジェクトグラフ
さて、C++ の DOM ツリーは親が子に責任を持つことでその寿命をつなぎとめた。 けれど JavaScript の処理系はそんな苦労を知らない。 以下のように繋がれた C++ DOM ツリーとラッパーオブジェクトについて考えてみよう。
JavaScript の世界に限ると、ラッパーオブジェクト WX は ルートセットから 辿れる場所にない。
このまま GC が起こると WX は回収されてしまう。
(C++ 側の生死は助けにならない。C++ オブジェクトからラッパーへの参照は弱参照だったのを思い出して欲しい。)
ウェブプログラマにとって、これは期待通りの動きではない。
WX は、ルートセットに含まれるは別のラッパーオブジェクト WY から、たとえば wy.firstChild.lastChild のように到達できる。
ルートセットから到達できるオブジェクトが回収されてしまうなんて GC にあるまじき失態！総解放して民意を問え！といいたくなる。
こうした問題がおこるのは、.firstChild や .lastChild といった DOM ツリーの参照構造が C++ の中に 隠れており、
JavaScript の処理系からは見えないからだ。マークやスイープをしようにも、参照が見えないことにはオブジェクトをたどりようがない。
オブジェクト同士の参照構造を GC 用語で オブジェクトグラフ という。(と書きつつ釈迦に説法感は拭えない・・・。） C++ のオブジェクトグラフが JavaScript の処理系から隠れているせいで、 意味的には到達可能なオブジェクトが処理系の GC に回収されてしまう。 DOM ノードの過剰回収問題を一般化するとそんなふうに説明できる。
Object Group
うっかり回収を防ぐため、C++ 側は JavaScript 処理系にオブジェクトグラフを包み隠さず教えたい。 V8 はそのために手段をいくつか用意しており、その中でも WebKit は主に Object Group と呼ばれる仕組みを使っている。
Object Group は、互いに到達可能なひとまとまりの JavaScript オブジェクトを表す。 たとえばある DOM ツリーに対応するラッパーオブジェクトたちは、C++ のオブジェクトを通じて互いに到達可能である。 したがってそれらのラッパーオブジェクトはひとつの Object Group を構成する。
V8 には V8::AddObjectGroup() という API があり、
この API を通じて処理系に Object Group、 つまり隠れたオブジェクトグラフの輪郭を教えることができる。
この API は毎 GC の直前に呼び出す流儀。
隠れたオブジェクトグラフをインクリメンタルに同期し続けるのではなく、
必要なタイミングで一度に情報を伝える。
WebKit は全てのラッパーオブジェクトを追跡している。 そして GC の開始を知らせるコールバックが呼ばれるたび、Object Group を計算しては V8 に教えている。
Object Group の計算は C++ のオブジェクトグラフを使う・・・要するに DOM ツリーを C++ の中でトラバースする。 基本的には DOM サブツリーのルートをキーとしてラッパーを分類するだけ。 (ただコードはまあまあややこしい。できれば近づきたくない感じ。 興味のある人は WebCore/binding/v8 のあたりを覗いてみるとよい。)
V8::AddObjectGroup() のようなバッチでオブジェクトグラフを開示する仕組みははいかにも DOM 向けに足した風情があり、
良し悪しはさておき他の言語処理系ではあまり見られないアイデアな気がする。
若年層の憂鬱
というわけで Object Group の活躍により無事 C++ の闇は暴かれ、世界に平和とメモリが戻ったのでした。めでたしめでたし・・・と 締めくくってもいいけれど、暇なひと向けにもう少し続きがある - 国民が成功と栄華に酔いタダ飯に舌鼓を打っていたある夜、傷だらけの兵士が国境の門を叩いた。 「GC が…」息絶え絶えの男はうめくように告げる。「GC が固まるのです！」
V8 は世代別 GC を実装しており、JavaScript 処理系の中だと GC による停止時間は短い方のはずだ。その GC が固まるとは聞きずてならない。どんなダメなアプリなのかそれは？ と問い詰めるも、原因は身内に潜んでいた。なんと Object Group の実装が世代別 GC をサポートしておらず、 結果として DOM のラッパーオブジェクトは世代別 GC の恩恵を受けていなかったのである。
Object Group に所属しうるオブジェクトは Dependent なオブジェクトとしてマークされる。（正確にはハンドルをマークするんだけど細かい話なので割愛。） Dependent とマークされたオブジェクトは minor GC で回収されない。 Major GC に至り C++ から Object Group の報告を受けたあと、ようやく回収される。 そして DOM のノード(のラッパーオブジェクト)はすべて dependent であるため、minor GC で回収されない。 Minor GC ではラッパーでない普通の JavaScdript オブジェクトと、 隠れたオブジェクトグラフを持たない一部のラッパーだけが回収されていた。
世代の壁と言語の壁
これはひどい話な気もするけれど、処理系として実装したくないのもわかる。 世代別 GC では世代をまたぐ参照を記録し、minor GC の際に古い世代から参照されているオブジェクトを保護する。 世代をまたぐ参照の保守は面倒な仕事で、Write Barrier だの Remember Set だの補助的なデータ構造やフックを使いこなさないといけない。 そんな繊細な仕事を、野蛮な C++ の世界にどうやって伝えればいいだろう。 具体的には世代別 GC に対応した Object Group の API はどうなるのか。見当がつかない。 世代をまたぐだけでも大変なのに、更に言語をまたげなんて無理難題にも程がある。
DOM に対する minor GC の不在がどれだけ性能に響くかはアプリケーションのコード次第だ。 たとえばゲームなんかは停止時間を気にするだろうけれど、ゲームなら Canvas しか使わず DOM のオブジェクトは少ないかもしれない。 そんなアプリケーションでは普通の JavaScript オブジェクトが支配的だろう。 一方で描画に DOM と CSS を多用するタイプのゲームもある。 それはどのくらい一般的で、そのときラッパーの比率はどれくらいなのか？
ゲーム以外のウェブアプリケーションでもインパクトは不透明だ。 表示に使う DOM は長い寿命を持ちすぐには回収されないから、minor GC は関係ない。 DOM を作ってはすぐに捨てるようなコードがどれだけあるのだろう？
などと私が DOM 用 minor GC 不在の言い訳を思い描いている間に、 私の隣の隣の隣に座っているエンジニアは問題解決にあたった。 結果として最近の Chrome Canary では DOM のラッパーオブジェクトも minor GC で回収されるようになったらしい。 直した当人はナントカスプレッドシートのスクロールがプチフリしなくなった！と喜んでいた。 ナントカスプレッドシートも困っていたとは、言い訳全然説得力ない。言い訳より直すが易しということですか・・・。 そのほか minor GC によるこまめな回収が効いて、メモリのピーク使用量も小さくなったという。
Eden
さて、DOM ラッパーに対する minor GC はいかにして実現されたのだろうか。 細かい話は Object Group の実装なんかもわからないとしんどいので割愛するとして、 (興味がある人は 該当チェックイン からリンクされている TL;DR なドキュメントをご覧ください。) おおまかな方針を説明するとこうなる: C++ のオブジェクトに「このオブジェクトのラッパーは minor GC で回収できるかも」とマークすること。
Minor GC の回収対象となるヒープ領域のひとつを、GC 業界 (というか Lars Bak) の慣習で Eden と呼ぶ。
Eden 云々は V8 という特定 JavaScript 実装のコンセプトであり、これまで WebKit の C++ オブジェクトがそれを意識することはなかった。
しかしこの修正で追加された Eden フラグによって、
C++ オブジェクトが自身(のラッパー)の世代を知るようになり、マイナー GC を意識して Object Group を作る道が開けた。
(なおフラグの名前が 中二すぎる わかりづらいという指摘があり、今はもうちょっと説明的な名前になっている。残念。)
V8 側にも変更があり、「minor GC で回収できるかもしれない Object Group 候補」をあらわす Partially Dependent というオブジェクト(ハンドル)のフラグが増えた。 Partially dependent なオブジェクトは minor GC の際に Object Group を考慮した上で可能なら回収される。
WebKit 側に話を戻すと、minor GC 用 Object Group を計算する際、アルゴリズムは Eden なラッパーのある DOM ツリーをトラバースする。 そしてツリー内に Eden でないノードがいたらその Object Group 候補は回収を諦める。Eden でない古い世代から参照できる(かもしれない)からだ。
ここで GC マニアが好きそうな細部を補足したい。このアルゴリズムは少しだけ保守的に倒されている。 V8 をはじめとするる世代別 GC は、多くが minor GC の対象として Eden と Young という風に複数世代のヒープを持つ。 (stackoverflow に簡単な解説があった。) このアルゴリズムでは Object Group の候補を一番最初のヒープ領域である Eden に絞っている。 隣接する Young 世代の partially dependent オブジェクトは minor GC で回収しない。
ドキュメントによると、実装の単純さを優先してこうなったという。 たしかに Eden なオブジェクトだけが相手なら、オブジェクトの生成直後にマークをつければ済む。アンマークは生成後最初の GC コールバックでやればいい。 オブジェクトのヒープ種別など、あまり表に出したくない細部を V8 API に晒さずに済むのは大きな利点に見える。
実験した範囲ではこれでも十分効果はあるそうな。
Behind the Scenes
WebKit と V8 (や JavaScriptCore) をつなぎあわあせるモジュールを binding という。 もともと私は binding のことを何も知らなかったのだけれど、件の隣の隣の隣のエンジニアが binding の高速化をする話を聞いているうちにまあまあ理解が進み、 そのあと自分でも雑用がてらちょくちょく binding コードをいじって概観がわかってきた。 そこで忘れないうちになにかメモしておこうと腹痛ついでに今日の記事を書いた。 といっても 8 割くらいはそのエンジニアからの孫引きなんだけど。
上でざっと説明した世代別 Object Group アルゴリズムは問題の割にまあまあシンプルで感心する。 この結論にたどり着くまでにはだいぶ苦労していた。 いくつかの古いアルゴリズムはエッジケースに問題があり、パズル脳の同僚に撃墜された。 別のバージョンは正しく動いたそうだが、 WebKit の DOM の寿命管理にややこしいコードを押し込もうとして反発を受けた。 ドキュメントはその説得に失敗した旨を恨みがましく書いているけど、 誰にもデバッグできそうにないややこしいコードだったので説得できないのは仕方ないと思う。 説得を拒んだ WebKit のシニアエンジニアたちは正しい。
わたしはそうした失敗を目にして「これはなんとか予想みたいな呪われた問題に踏み込んでいるのでは・・・」と 他人ごとながら心配していた。ところがいつの間にか解決していてびびったのだった。 個人的にはけっこうな成果だとおもうけれど本人はいまいち宣伝する気が無さそうなのでひっそりここで宣伝しておく。 いや個人の意見で勤務先の見解ではありませんけどね。休暇中だしね。
ふつうの解決
Object Group やその世代別対応は、アーキテクチャ上の限界を大脳的資源を濫用して乗り切る一種の富豪的デザインだった。 ただ普通に考えてもうちょっと穏当なアプローチでなんとかした方がいいことも世の中多いですよね・・・と考えてしまう。 大脳的資源って枯渇しがちじゃん？
穏当に一般化するとしたら、隠れたオブジェクトグラフの問題にはどんなアプローチがありうるだろう。
C++ 側の支援: GC によるオブジェクトグラフのトラバーサルをフックできるようにして、GC が C++ のグラフを通り抜けられるようにする方法。 JavaScriptCore なんかはこれ。（ただ他にも色々やってそうではある。） C++ のオブジェクトをマークできないかぎり任意のグラフをトラバースはできなそうだけど、 DOM のようにトポロジをツリーと仮定できるなら手軽で悪くない気がする。
アロケータの統合: もうちょっと頑張る方向の１つが、ホスト言語(C++とか)とゲスト言語(JavaScriptとか)で同じ GC を使うというのもの。 Boehm GC なんかはそのためのツールキットだと言える。 Flash というか AVM2 もだいたいそんなアプローチだったはず。 Mozilla も一度はこの方向に舵を切ろうとしたがうまく行かなかった(と認識している)。 最初からこの方針でいくと決めてデザインしないとたぶん辛い。 あと世代別みたいな入り組んだ GC とくっつけるのは大変になりがち。
ホスト言語の切り離しと最小化: C++ のオブジェクトグラフを見せるのはダメだよね、という路線。とても正しい。Java はまあまあこの路線ではなかろうか。 Mozilla の実験的ブラウザ実装 Servo も同じ方向性で、 DOM の実装にピュア JavaScript の dom.js を使おうとしている。 Rust といい、もう C++ はいやだという心の叫びが伝わってきて共感する。
それにしても、これは人々が思い悩むに値する問題なのか。 ウェブブラウザは 20 世紀末から今世紀初頭にかけて天高く積み上げてしまった 技術的負債の崩壊を食い止めつつ更なる bet をしている手前こんなことになってるけれど、 良心的な暮らしをしていれば心悩ますことのない問題にも見える。 JVM/CLR 上の言語にはそもそもこういう苦労はないわけだからね。
WinRT やあんどろなど managed と native がまじった負債仲間の界隈がどうしているか、 気になるような近づきたくないような心境でございます。
写真: