SWE Internship@Chrome Memory Tokyo

2021年10月4日 15:08

2021/07/19 - 2021/10/01にGoogle SWEインターンに参加しました！
2年前のSTEP教育プログラム，STEPインターンを経て，Returning Offerを受けて戻ってきた形になります．
今回はオープンソースのChromeへの配属だったということで，「社外への公開についてですが〜オープンソースなので全部大丈夫です😊」と言われました．せっかくの良い機会なので，記憶が鮮明なうちに成果をまとめてみたいと思い，初めてnoteを書いています．

メモリチーム周りでは，Partition Alloc EverywhereとかMiraclePtrとか色んなプロジェクトが動いているみたいですが，私が取り組んだプロジェクトは主に2つです．

- Converting ListHashSet to LinkedHashSet
- Making ImageResourceObserver and DisplayItemClient GarbageCollectedMixin

プロジェクトの中で一番お世話になった単語はOilpan（とそれに類する言葉）でした．Blinkというweb platformのrendering engineがあって，そこで使われているガベージコレクションシステムをOilpanと呼びます（BlinkGC design）．最初Oilpanって聞いた時はフライパンみたいだなあとか思っていたんですが，車のエンジンの部品？にそういうのがあるんですね．v8チームとかその周りで車にちなんだネーミングをしているみたいで，そういうのも良いなと思いました．

Converting ListHashSet to LinkedHashSet

一言で表すと，似たようなコンテナが2種類あって紛らわしいからListHashSetに別れを告げよう，というプロジェクトです．

third_party/blink/renderer/platform/wtf の中にあるBlink用に最適化されたコンテナの中にあるListHashSetとLinkedHashSetというほぼ同じなOrderedSetがある状態がかれこれ5年も続いていました（Tracking Bug）．

どちらもLinkedListのような機能を内部で持っているのですが，その実装に違いがあります．
ListHashSetはHashTableの中にNodeポインタを持っていて，Nodeのメモリは別々に確保されるのに対して，LinkedHashSetはVector上にNodeのメモリを確保するようなLinkedListと，Vectorへのインデックスを引くのに使うHashMapの２つのコンテナで構成されています．

歴史的にはListHashSetの方が先にあって，LinkedHashSetはHeap-friendlyなクラスとして導入されています．WeakMemberのサポートというのが肝で，「オブジェクトへの所有権を持ちたくないけどポインタは持ちたい」ときに使うのがWeakMemberなのですが，ListHashSetだとNodeが別々にアロケートされているのもあって難しいんですね．WeakCallbackを登録しなくちゃいけないけどその中で他のオブジェクトには触りたくないし，そもそもWeakCallbackが多いとパフォーマンスに影響があるからなるべく少なくしたい，などの事情があり，Vectorのおかげでよりシンプルに実現できるLinkedHashSetが生き延びる権利を得たというわけです．

さて，そんなわけで私のミッションは残っているListHashSetをLinkedHashSetに置き換えることでした．

ただ機械的に置き換える（これとか）だけではなく，そこに潜む障害を一つ一つクリアしていく必要がありました．具体的には次の通りです．

- Custom HashFunctions / HashTranslator (ListHashSetにあってLinkedHashSetにはない機能をサポートする)
- Modification during Iteration (Iteration中にコンテナの変更をしている部分をなんとかする)

Custom HashFunctions / HashTranslator

違うタイプのオブジェクト同士を比較できるようにするための便利ツールです．Setの中に含まれるか知りたいときは普通その中に入っている値そのものを引数に取りますが，これを使ってカスタムなKey-ValueをセットすることでLinkedHashSetをHashMapみたいに使うことができるとイメージしてもらえれば良いと思います，（Hostがこんな風に説明したらいいんじゃないって提案してくれました）

この実装が私にとっては初めてのことだらけで大変でした．完成形を見ると「結局テンプレート引数付け足しただけじゃん」って感じなのですが．
「テンプレートって，あの，色んな型に対応できるやつですよね！」くらいのふんわりした理解しかなかったのもあって，最初にコードを読み解くところで説明に追いつけず頭がパンクしました．テンプレート引数を7個も取るクラスがあったり，いつの間にかtypedefが定義されていたり，ファイルを超えて対応を取るのにとても苦戦しました．そもそもどうやって辿るのかわからない私のために，CodeSearchを一緒に見て，どうなっているのか時間をかけて教えてもらいながら，こんなことに時間使わせて申し訳ないなあという気持ちとありがたい気持ちを両方感じていました．

CLはこれとこれです．

Modification during Iteration

ListHashSetではfor文を回している途中に挿入/削除が可能なのに対して，LinkedHashSetは裏にVectorがあるためできないことになっています．
そこで，そのような使われ方に対してどうにかiteratorの無効化を防ぐ必要があります．

1. Vectorにコピーしておき，Vector上でiteratorを進める

LinkedHashSetの中身をVectorに入れておけば，LinkedHashSet上にはiteratorがいないので，挿入/削除をしてbacking-vectorがリアロケートされても大丈夫という論理です．

2. Copy-On-Writeなクラスを実装する

1の解決策では，そもそもコピーをするコストがかかるのと，そもそも挿入/削除が起こらないケースでは無駄になる欠点があります．
実際，auto-generatedなコードの中にこれを含めたところ，パフォーマンスに影響があり，テンプレートをいじろうと思ったらreviewerにそれ汚いからやめて（意訳）と言われました．そこでCopy-On-Writeの登場です．

最初からはコピーしないけれど，その代わりにオリジナルのコンテナ上をiterateしている数を記録しておいて，挿入/削除が呼ばれたらそのカウンターをチェックして，もしそれが0より大きかったらコピーして対処するものです．コピーしたものが新たに操作可能なコンテナとして使われるように交換してあげることで，元々のコンテナのiteratorは安全に使い続けることができます．iteratorが新しい操作を加えようとしてもさらなるコピーは必要なく最小限のコストで済ませることができます（CL）．

あと実はLinkedHashSetじゃなくて（パフォーマンスを確認した上で）Vectorのwrapperクラスとして実装したので，コードサイズを小さくできたところも良かった点です．

3. Modification during Iterationを認めてしまう

さて，これで無事解決できたかのように見えたのですが，最後に強いラスボスが待っていました．というのも，古いコンテナをiterateしていると，変更を反映し続けた状態でiterateしたい場合には対応できない問題があるからです．大体の場合はもともとあるコンテナの要素で一回ずつやりたいことがある，で済んでいたのに，後回しにしたい要素を適宜後ろに動かしながら前から順番に処理していくケースがありました．毎回iteratorを計算し直す手も考えましたが，LinkedListでそれをするとO(N)になってしまうし，vectorを使うにしても挿入/削除に伴うコピーコストがある，と打つ手がなくなってしまいました．

そこで，最終手段「LinkedHashSetではiteration中の変更ができない」を無理矢理「LinkedHashSetでもiteration中に変更ができる」に仕様変更をしました．「変更ができない」をより正確に表現すると，「変更ができるように書き換えると安全じゃなくなる可能性があって，そもそも期待される動作が保証できるとは言えない」あるいは「安全に変更ができるように書き換えるのはできなくはないかもしれないけど労力がかかりそう，本当にできるかどうかちょっと分からない」という感じになるでしょうか．
つまり，あまり望ましい変更ではなかったのですが，ListHashSetをコンテナから取り除く目的のためには仕方ないという判断でした．iteratorのフィールドとしてポインタを持つ代わりにインデックスにすることと，今までiteratorを無効にしていた部分を丸ごと無くすことで，目的を達成することができました（CL）．

このサポートが必要なのは1ケースだけで，ごく限られたところでしか使われておらず（それもあって呼び出し元の変更は労力に見合わないと判断），そのうち新しいロジックにまとまる予定らしいので，それが早いうちに実現してmodification checkが復活することを願っています．

ついに5年間のバグに終止符が打たれました！！（CL）

1000行を超えるファイルを一気に消すという，とても気持ちの良い経験をさせてもらいました．
今，Code Searchで"ListHashSet"と検索しても何も出てきません！と言いたいところですが数年前に更新されなくなった謎ファイル2個だけヒットするみたいです（ちょっと悲しい）．でも，ほぼ何も出てきません！

Making ImageResourceObserver and DisplayItemClient GarbageCollectedMixin

一言で表すと，せっかくガベージコレクション使うようにしたクラスの継承元がまだガベージコレクション使うようになってないのは危ないから直そうね，というプロジェクトです．

LayoutObjectというクラスがOilpanizationされたのですが，継承元クラスであるImageResourceObserverとDisplayItemClientがまだOilpanizationされていない問題がありました．なぜ問題かというと，Oilpanにのっていないオブジェクトが，Oilpanにのっているオブジェクトへのポインタを持つことができてしまう状態にあったからです．

class Foo : public GarbageCollected<Foo>,
            public Bar 
{}

class Hoge {
    Bar* bar_ = MakeGarbageCollected<Foo>
}

「せっかくOilpan使ってるのにそれじゃ意味ないじゃん！」がこのプロジェクトのモチベーションです．

この二つのクラスをGarbageCollectedにするためには，そのチャイルドクラスたちをGarbageCollectedにする必要があります．ImageResourceObserverは少なかったのですが，DisplayItemClientは10個くらいあってそもそもボリューム的に大変でした．

GarbageCollectedを継承して，Traceメソッドを足して，適切にメモリ確保してあげるのが大まかな流れでしたが，単純にいかないところがやりがいを感じられて良かったです．

例えばOilpanにのったオブジェクトをHeapCollectionにのせるときはMember使っておけばいいんでしょ？と思っていると，GarbageCollectされたオブジェクトにアクセスしてしまうので，WeakMemberを使う必要がありました．また，Destructorの中では他のオブジェクトにアクセスするのは禁止されているので，Destroy()を追加してそれをオブジェクトが使われなくなる時に漏れなく呼ぶような変更を加えたり，USING_PRE_FINALIZER()マクロ（他のオブジェクトに触れるようになる）で使われていた関数が要らなくなったことを確認して消したりしました．
他にも，知らないうちにPersistentを使って作ってしまっていたCycle Referenceによるメモリリークの発見に手こずったり，プラグインのバグを踏んだり，最後の最後でダイヤモンド継承という初めて聞く概念に悩まされたりとなかなかスムーズにはいきませんでした．

準備中のCLを残したままファイナルプレゼンを迎え，その夜ようやくsubmitした結果，ImageResourceObserverとDisplayItemClientはどちらもGarbageCollecredMixinを継承し，LayoutObjectは安全にOilpanizationされました（CL）．めでたしめでたし．

（と，完璧なように見せかけて，最終日にまた問題が発生してしまったので，後は社員さんが修正してくれると信じています．（※後日追記: おかげさまで修正され、relandされていました！）最終日だから機器の返却手続きしたりお別れメール書いたりドキュメントまとめ直したり遊んだり←していたらバグ修正に取り組む時間がなくなってしまいました笑）

インターン期間中にmergeされたCLたち

感想など

とりあえずつらつらと文章に起こしてみましたが，図がないとやっぱり理解しづらいかもしれませんね．というわけでプレゼンで使ったスライドも置いておきます．
2つのプロジェクトともチャレンジングで色んなファイルを触れるようなプロジェクトだったので，たくさんのReviewer（Tokyo Office以外も）にお世話になりました．C++も前より詳しくなれたし，Gitスキルも成長したし（内部ツールじゃないから今後も直接役に立つ！），テストの構成やデバッグの仕方を学んだり，パフォーマンスをはかって分析したり，デザインドキュメントを作ったりと盛りだくさんの経験でした．
インターンのHost / Co-Hostには毎日丁寧に面倒を見ていただけて，本当に恵まれました！

プロジェクト以外にも，チームミーティングと別にGame Timeがあったり，インターンLunch / Coffee timeが定期的にあったり，インターンイベントとして謎解きやスイーツ作りをしたり，全く見知らぬ人とマッチングするCoffee timeに参加してみたり，Language Swapプログラムで英語の会話練習をしてみたりと，色んな思い出ができました．
他のインターン生たちも面白そうなプロジェクトをやっていて，すごいなあというのが伝わってきて，とても刺激になりました．

フルリモートインターンということで最初は探り探りな状態で，慣れるのに時間はかかってしまいましたが，11週間，楽しいインターンライフを送ることができました．
「オフィスが開いたら遊びに行かせてください」とお話ししたGooglerごとに頼んでいた気がしますが，お世話になった方々と今度は直接お話ししたいです．
皆さん，本当にありがとうございました！

この記事が気に入ったらサポートをしてみませんか？