いろいろなGCについての研究を解説してくれる本。

最近のAndroid周りはGCとアロケータの改善が著しく、そうした議論にちゃんとついていけるようになる為に一度しっかり勉強したいなぁ、と思ってたので読む事に。

なお自分は、世代別GCあたりから実際を具体的には想像出来なくなるレベル。

1章イントロ

並列と並行

どっちがどっちかすぐわからなくなるのでメモ。

並列はstop the worldするが、GC時に複数スレッドが動く、というもの。

並行GCはミューテータとコレクタの実行がconcurrentに行われる。

これ、書いてて気づいたが英語ならparallelとconcurrentなのか。英語の方がいいな…

スマホが無い

1.3のスケーラビリティとポータビリティ、でマルチコアはデスクトップやノートPCでも一般的となった、と言っていて、スマホへの言及が無い。

まぁいいか、と読み進めると、1.5の実験手法で、コールドスタート効果を無視せよ、と書いてあるが、スマホではコールドスタートの速度はすごく重要なのでそれをベンチマークから取り除いて良いかは自明じゃない。この辺はスマホかどうかの差は大きそうだよなぁ。

日本語版は2016年となっているが、原書は2012年。仕方ないかー。

メモ

「ミューテータのリード、ライト操作」のところで、フィールド、srcのiがRootsの時、srcをRootsと書くとあるが、どういう意味だろう。

Rootsの定義は「ミューテータが他のオブジェクトを経由することなく直接的にアクセス可能な記憶領域にあるポインタ」となっている。

srcのiのアンパサンドがRoots、と書いてあるので、参照先がRootsという意味では無いな。このiフィールドのアドレス自体が「直接アクセス可能な領域にあるポインタ」という事か。分かったようなわからんような。

シーケンスを列と訳すのはわかりにくいなぁ。順序つけて並べた物を表すらしい。

多重集合は順番は関係ないのか。Pythonのリスト表記だがあくまでmultisetな訳ね。注意が必要だな。

第一章、雑感

読み終わったので雑感など。用語の説明などは日本語だと読みにくいな、と感じる。和訳が悪いというよりも、こういう説明を日本語で読む事があまり無いのでスムーズに読めないのだよな。原書の1/4くらいの価格だったので和書を買ってしまったが、込み入った内容は日本語は意外と辛いな…

細かいアルゴリズムが延々と続くのかと警戒してたが、意外と読み物的な部分の分量が多い。といってもちゃんとアルゴリズムの解説もありそうだし、なかなか良いバランスの本かもしれない。

イントロは最後の用語のところだけ一気に難しくなるが、実例無しで用語を語られても良く分からないので、適当に流し読みしつつ先に進むのが良いんじゃないか、とおもってそう進めてみる。

思ったよりも面白く読めてる。たまにはこういう技術書読むのもいいな。

第二章マークアンドスイープ

第二章から具体的なアルゴリズムの話にはいる。といっても前半はstop the worldの間に一スレッドでコレクトする、という前提でのアルゴリズムの解説。

マークアンドスイープは二回くらい実装した事があるのでそれなりに分かるつもり。

2.1を読んだ感想

アルゴリズムの解説だが、すごく読みやすい。知らない人が読んでわかるとは思えない部分もちょくちょくあるが、この本を読む時点でこの辺の事は知ってる、という前提なのだろうな。

アルゴリズムの自然言語での解説が結構多くて、スラスラ読める。いいね。

メモ

3色抽象化。黒は子供を見つけ終わった状態で、孫より先はまだ見つけてなくてもOK。

2.4のビットマップマーキング、セットアソシアティブ方式だと同じスロットになるからダメ、とか説明無しで書かれてて読者に前提とする要求水準にしびれるな。

2.4のPintezisとDetlefsのアルゴリズムの説明はわかりやすく書かれているな。疑似コードの詳細の省き方と自然言語による説明のバランスが絶妙。これは良く出来てるね。

2.5は遅延スイープ。このアルゴリズム説明も良く書けている。法2のK乗でマークする奴の一周回った時の説明か良く分からないな。「そのため、これらは浮動ごみであり、マークルーチンによって辿られる事はない」という奴。

例えば256だとして、256だけ過去のGCサイクルでマークされたから浮動ゴミ、とはどういう意味だろう？256サイクルの間生き残ったオブジェクトは256になるのでは無いの？

2章の感想

2章はマークアンドスイープ。基礎となるアルゴリズムは1ページくらいの簡単な解説で終わっていて、それに対する改善案がいくつか紹介されている。改善案の方が分量は多い。

ちょうど基礎的な奴くらいは知ってるが改善案はしらない自分には勉強になった。メモリのフラグメンテーションやキャッシュライン周りの話はそれなりに携わった事があるので、書いてある字面以上に多くを学べた気がする。

一方でマークアンドスイープを実装した事が無いと、この記述では簡素過ぎて難しさが良く分からないだろうなぁ。だから「GCとか概要くらいしか知らないし、ここらで本格的に勉強するか！」という人向けの本にはなってない。ただ自分にはこれでいいかな。

もっと難しくて不親切な本を予想してたので、良い意味で裏切られた。論文の参照が列挙されてるだけ、とかかと思ってたが、良く要点だけを解説している。素晴らしい。ベテラン向けにはこういう技術書を書きたいものやね。

3章マークコンパクト

コンパクションというとコピーGCくらいしか知らなかったので、初めて読むアルゴリズムという事になる。

といってもオブジェクトを動かす事があるのはpinningとかしてれば知ってるので、言われてみれば当然こういうアルゴリズムもあるはずやね。

それにしてもコンパクションを圧縮と訳すのはやめてほしいなぁ。compress っほいやん。定訳なのかもしれないが、批判の対象が変わるだけで迷惑な事には変わりない。

メモ

3.1 ツーフィンガー

めっさ簡単でびっくりした。なるほど、これでいいのか。

マークコンパクトは実装した事無いが、ハンドルのコンパクションは結構実務で格闘してた時期があるので、解説はよく理解出来る。人生何が役に立つかわからんね。

3.2 Lisp2アルゴリズム。上書きがこれで平気かはちょっと考える必要があるが、考えれば分かるくらいには詳しく書いてある。良いね。

この位のシンプルさなら自分でも実装出来そうだな。

freeのnextはallocatorとセットで考えないと分からないよなぁ。直交してる、とかいう概念が直交してる事はほとんどないな。

要所に入る改善案の一言コメントとその論文への参照もいいね。何年、と書いてあるので、いつくらいの時代だとどのくらい高度なのかが分かるし。そうそう、こういう本を読みたかった、という感じ。

ちょこちょこ日本語の文のつながりがおかしいが、疑似コードがあるおかげで意味の曖昧さは解消出来ている。擬似コードと文章の説明のバランスが絶妙だね。疑似コードもこれでは明らかに動かない、足りない重要な処理がたくさんあるが、アイデアを伝える事は出来てる。これはなかなか良い説明方法だな。

3.3はスレッデッドコンパクション。初耳。なかなか凝ったアルゴリズムで結構難しい。説明も後方参照の説明が不十分に思うが、たぶん後方参照を見つけたらまたスレッド化するんだよね。

内部ポインタに対応出来ない、と書いてあるが、内部ポインタってなんじゃろ？

3.4 ワンパスアルゴリズム。これは早そう。 3章の中ではこれが一番だな。2004年と2006年か。CLRくらいの世代か。まぁまぁ新しいな。

アルゴリズム3-4はマークのビットマップはすでに出来ているが、オフセットは出来てない、という前提。この辺はちょっとわかりにくいね。

アドレスからブロックを求めるのはコンパクションのコードでは良く出てくるので、この辺のコードは自分でも書けそうなくらいは理解出来た。

アルゴリズムの説明でちゃんと重要なケースを具体例に解説するのが素晴らしい。「ブロック2内の最初のマーク付きオブジェクトを考えてみよう」とか、「oldと書かれたオブジェクトを考えてみよう」みたいに。ちゃんと手計算出来る図を用意して、説明と自分の理解があってるかを確認出来る。これは名著だな。

3章読み終わり

大変勉強になった。内部ポインタがtwo finger以外使えない、という記述の意味は最後まで分からなかったが、他は割と理解出来たと思うし、発明が多くて読んでて楽しいね。

コンプレッサはアルゴリズムの名前なんだろうが、項タイトルは「ワンパスアルゴリズム」になってるのでちょっと分かりにくい。こういう言葉の説明がちょっと分かりにくいところがいくつかあるが、アルゴリズムの解説が大変分かりやすく書かれているのでその欠点は吹き飛ぶな。

コンプレッサをちゃんと理解出来ればこの章は十分な気がした。他のは使わないだろうし。

4章コピーGC

名前だけ知ってるコピーGC

メモ

4.1 二分空間コピーGC。シンプルだがまぁまぁコードはちゃんと読まないと分からないな。

Cheney走査は日本語の解説がおかしい気がするが、アイデア自体がシンプルなので本当はどういう物かは予想出来る。

Moonのアルゴリズムも雰囲気は分かる。

オンラインオブジェクト再構成法はなかなか良さそうだな。2004年か。この辺の世代はサーバーサイドVM早くなってきたなぁ、という印象あったが、GCの進歩も関係してるかもなぁ。

2006年あたりまで来るともう相当洗練されているね。

コピーGCって素人目には単純で無駄が多いからあんまときめかないけど、メリット多いよな。アロケーション早いは確かに良さそう。

読み終わった。4章も擬似コードと文章の解説が絶妙で、図なども適切で、アルゴリズムの精緻さを考えると驚くほどわかり易かった。コピーGC、お話レベルでしか知らなかったが、やれば実装出来そうだな、くらいには理解出来たし、2006年くらいまでの進歩もまぁまぁちゃんと理解出来た気がする。

5章リファレンスカウント

リファレンスカウントに一つ章を割いている、という事に驚いたが、5.1以外はたしかにGCだな、という内容。

メモ

リファレンスカウント、重い重い言われるがそんな重いイメージ無い。だが確かに理由を説明されると遅いはずだな、という気もする。リファレンスカウント使ってるシステムはランタイムが小さいので他のオーバーヘッドとかが影響してるのかもなぁ。

「時代」という単語が定義されているがすぐ忘れるのでメモ。プログラムの実行を区間に区切るときの、区間の事らしい。 epochとも言う。

延期型リファレンスカウントはヒープの走査が必要になるのであんまリファレンスカウントのお手軽さは無いな。なお、ルートはヒープ以外のオブジェクトへの参照全部でスタックとかグローバル変数とか。

5.4 併合型参照カウント

併合型参照カウント法はアルゴリズム5-3を見ても良く分からないので、5-4のあとの例まで読み進めてから考える方が良い。

最初の参照と最後の参照だけ分かればリファレンスカウントの更新は出来る、そして最後の値は今オブジェクトに入ってるから最初の値だけ記録しておけば良い、という事やね。

競合が起きても大丈夫、のくだりは良く分からないな。

スレッドAでログに書きはじめる
スレッドBでログに書き始める
スレッドAがオブジェクトを変更

で、スレッドBのログに最初のエントリじゃない物が入ってしまうと思うのだが。

いや、アルゴリズム5-3の12行目の時点でdirtyじゃないのなら、11行目はdirtyじゃなかったのが保証されているから追い越しは出来ないか。

ログに間違ったエントリが書かれる事はあるが、それを参照する事は無いな。納得した。

5.5 循環参照カウント法

リサイクラーはなかなかコードが複雑で、読むのは大変だな。ただ理解してしまえばストレートではある。

最後がdecrementだったら循環ゴミ候補として紫に塗る。 markCandidatesでは紫な物の内部ポインタを全部デクリメントして灰色にする。子供も再帰的に。 scanBlackで元に戻す。

AddRef-Releaseで育った身としてはRelease を無意識にデクリメントで読んでしまうのが辛いが、releaseはrcがゼロのときに呼ばれる。

76行目のコメントはたぶん誤植だな。これはフリーリストじゃない。

図5-3のaからのケースの解説を追ってみよう。

灰色に塗るのはmarkGrayのみか。で、子供はgrayでもrcのデクリメントはやる（Yが0になる理由）。5-3 aから頭の中でmarkGrayして、bになるのを確認。

あれ？Aは-1になるような？いや、最初Aはデクリメントしないのか。

Aを灰色にし、子供のrcをデクリメントしてmarkGrayする。これでB-0（なんか名前が無いが）Y-1となる
Bを灰色にし、子供のrcをデクリメント、これでA-0, X-1となる、XはmarkGrayでさらに処理される
Xは灰色になり、Y-0となる。
Yが灰色になる。Z-0となりZは灰色へ
そのあともう一度YのmarkGrayが呼ばれるが、何もしない

でbになる。

X以外は0なので、scanでは、YやZは一時的に白になりうる。だがXは黒なので、その子供は全部黒になるから、黒で上書きされる。＞本文に説明もあった。良いね。

5章、おもったより勉強になった！

リファレンスカウントなんて大して学ぶ事も無いだろう、と思ったら、なかなか研究されてて高度な方法がいろいろあった。

またその複雑さを思うと、この本の解説はとても良く出来ていて感心した。アルゴリズムを記述するだけじゃなくて、具体的な場合をいろいろ見て、図を入れて解説する、というのは見習いたい姿勢だ。

5章までで基礎となる手法を一通り解説した事になり、ここからはそれぞれの手法の比較やより進んだ手法の話となる模様。楽しみ。

6章ガベージコレクション間の比較

6章は（おそらく）この先に向けて、異なるGCの手法を比較するための注意点とか、類似点を強調する為のリファレンスカウントの不動点に着目する見方などを解説する。

なかなか読むのが大変だが、この時点では大した話は無いので特にノートに書くべき事も無し。

7章メモリ割り付け

この章は割と自分が詳しいのでそんなに分からない事も無い。だが日本語訳が分からないのでそこだけメモ。

逐次割り付け: 端から順番に割り付けるだけ。

隔離フィット割り付け: サイズごとのフリーリストを用いる方式。

フィボナッチのところはこれ誤植か。

8章ヒープの分割

この章は文章による説明ばかりで、この日本語が微妙なので分かりにくい。まぁあまり気にせず先に進んで良い気もする。今は8.2の、なぜヒープを分割するか、を読んでるが、意味の分からない文がちょくちょくある。

9章世代別ガベージコレクション

そろそろ最初の方に出てきた用語を忘れつつあるのでたまに確認。

mark/cons比。初出のところでは、コレクタとミューテータの消費時間の比、と書いてある。だが名前とその後の説明からすると、アロケートとして行った仕事、つまりアロケート出来たサイズ総量と、コレクタがマークしたサイズ、つまりコレクタが舐めたサイズの総量の比っぽいな。

若い世代だけのGC

若い世代のGCは、若い世代の領域のサイズに比例する時間で出来る、と書いてあるが、他の世代からの参照をトラックする為には全領域をなめないといけないような？でもそれじゃ世代別の意味が無いよな。どうなってるんだろう？

世代をまたがる参照を、ミューテータにオーバーヘッドを課してトラックする、とある。へぇ。どんな感じなのかな？

9.1 二世代の簡単な例

remember setという物で外からの参照をトラックし、それはライトバリアでチェックするらしい。全参照のライトでバリアが入るのか！それは気をつけないと遅そうだなぁ。

世代をアドレスなりタグなりで判定出来れば大多数は単なる算術チェックに出来るか。世代をまたぐと遅そうだな。例えばold世代に配列があり、大量のyoungの要素を足す、とかなるとやばそう。このへんはなにか工夫が要りそうね。

こういう具体例を出すのはこの本の良い所だよな。なんとなく言葉だけで解説されると良く分からない部分もこうやって見ていくと明らかになる。

AppelスタイルのGC

10章で良く比較対象として出てくるので軽くメモ。1989年のStandard ML用のGC。（9.7、ロケーション4805）

年長、コピー予備、年少と空き、の3つに分けられる。コピー予備は年長に移動する時の部分は必要無いので、普通の方式よりは少し少なく出来て、結果として年少世代の領域を広くできる。

9章読みおわり

さすがに世代別GCは詳しい。どんな物があるかとか全然知らなかったので良い勉強になった。静的解析周りがお話程度で実際のアルゴリズムとかの解説が無いのは残念だが、静的解析自体を一般化するのが難しいので仕方ないかなぁ。ただAndroidはプロファイル情報を使えるので夢は広がるね。

old世代のGCが結局遅いのは、Androidのような対話環境だと致命的だとおもうので、もっと対策が入ってるんだろうなぁ。この辺興味出てきたので、そのうち現在のAndroidについて調べたい気持ちが高まった。

この辺まで来ると、大分モダンなGCの原型というか、現在のGCはこの延長だろうな、という感じがしてくる内容になってる。昔CLRのGCがヤング世代からold世代に入る、とかを簡単なコードで確認するのが流行ったが、当時の記憶と大分整合的な実装に思うし論文も2004年とかが多いので、whidbeyのあたりはこの辺だったのだろうな。

10章、そのほかのヒープ分割スキーム

世代以外の基準でヒープの領域を分ける、という手法についての章。

10.1はラージオブジェクト。トレッドミル方式。コピーをつなぎ直しで実現する。

10.2はトポロジカルコレクタ。参照関係などに基づいてヒープの領域を分ける。 train GCというのが解説されている。仕組みは理解できるが、いまいち良さが分からない。

Cheny走査

この章でちょくちょく出てくるので見直し。二分空間コピーGCの一種で、ワークリストの実装方法。4.1で登場。

二分空間コピーGCは新しい空間にコピーしたあとに、古い方のオブジェクトに転送先のアドレスを書き込んでおく。

Cheney走査では、worklistを、to空間でまだ処理してないもっとも先頭のアドレスをさすscanだけで処理する。 scanとfreeの間が灰色オブジェクトとなる。 scanを処理してコピーする時はfreeを進める事になるのか。

10.2 スレッドローカルコレクタは良く分からなかった

文での解説ばかりで詳細が良く分からなかった。あまり理解出来てないと思う。

スレッドローカルにGCが出来れば良さそうとは思うのだが、あまり決定版は無いのかしら？この辺、現在の結論を教えて欲しいな。

10.3 マークスイープとコピー方式のハイブリッド

全体としては、ヒープをブロックに分けて、普段はマークスイープするがたまにブロック単位でコピーGCする、という節。

ブロック単位にしておくとスレッドローカルな割当てを高速化出来たりする。

一方でマークスイープは全体にやるので、別にインクリメンタルという訳でも無い（のが多い）。手法がいっぱい出てくるので簡単に名前くらいメモしておく。

LangとDupontの方法は輪番で管理して、fromの隣に空きのtoを配置してコピーGCする。この輪を回していく事で一周すると全部圧縮できる。

Spoonhowerはブロックごとの生存予測を用いて、ブロックごとにマークスイースするかコピーGCするかを決める。

Detleftsのガベージ優先法は良く分からなかった。だが上2つの物に似てる。JDK7で将来的には並行マークスイープGCを置き換えるべく入れられたらしい（2004）。

immixはライン単位で管理してアロケートする事で高速な割当てとブロック単位のコピーGCの組み合わせ。

Dismpseyらはフリーリストに可変長を許す事で断片化を避ける。

Sachindranらはマークは全体にするけどコピーは一ブロックだけやる、というモデル。

10.5 隠し参照カウント法

old を参照カウントで扱う、という手法。いろいろ前のが出てくるので軽く思い出す為にメモ。

隔離フィットはサイズごとに別々のフリーリスト用いるallocation方法（普通の奴）。

延期型参照カウントは、スタックとレジスタからの参照カウントを延期する手法。ヒープへの書き込みはカウントする。

カウントがゼロになっても回収せず、ゼロカウント表に入れて、あとでストップザ・ワールドしてゼロカウント表のオブジェクトにルートからの参照があるかを探して、無かったら回収する。これは一時的にルートからの参照をaddRefでカウント上げて、ZCTの中でゼロのを探して回収し、そのあとルートからの参照をdeRefすることで実現。

10章はなかなかしんどかった

読み終わったので感想を。 10章はいろいろなアルゴリズムが延々と出てきて、なかなか読むのが進まなくて辛かった。一つ一つはそんな難しい訳でも無いのだが、見た目のページ数よりも内容が多い。

ただ、この辺まで来ると過去の章の内容も踏まえた割と高度な物が多く出てきて、それをちゃんと理解できるので、自分の成長は感じられて良い。

11章ランタイムインターフェース

それなりに難しいがあまりメモすべきことも無く進んで、11.2のレジスタ内のポインタの発見まで来た所で難しくてつまる。

いわゆるスタックウォークのコードなのだが。

図11-2が理解出来れば良さそうなので、ちょっとメモをとりつつ頑張ってみる。

図 11-2 a レジスタからポインタ探す所の図

5, 6, 7, 8と上に戻っていく。 Regsは対応する右側の箱の、入ってきた時のレジスタの状態になっている。

Restoreには右の箱の下の状態にする為に必要なレジスタの差分が書いてある。

calleeSavedRegsとはなんだろう？例えば6を見る。これはgの中のどこかで保存したレジスタで、保存する前の値がスロット1に入ってる、という意味だな。つまりRegsを戻すのに必要な情報か。

では6を見直そう。まず5の状態で来る。 IPのcalleeSavedSegsの一覧を取得すると、r2はスロット1にある、と言われる。

そこでr2のレジスタの状態を復元する訳だが、この時に復元前の値を入れておくのがRestoreか。

わかった気がする。7も見てみよう。うん、あってそうだ。

図11-2 b 上から下へ

10からどうやって11を作るかに着目する。まず左のRestoreの中を見るとレジスタの内容を更新できる。

次に11の二段目は、このIPのpointerSlotsとpointerRegsを表している。この情報から、funcを適用すべき、つまりピーするべきレジスタが分かる。この場合はrとqが処理されるか。そして処理されたレジスタはDoneに入るんだな。なるほど。

13に進んで見る。Restoreからレジスタを再現する。r2だけが書き換えられてる。 r1はDoneに入ったまま。

で、gのIPからpointerSlotsとpointerRegsを取って、r1はDoneに入ってるので処理せず、r2は処理する。そしてlocalsの4のsも処理する。

これで全リファレンスの移動が出来そうか？必要なのは上から潜っていく為に必要なフレームの情報で、基本的にはそこまでのコンテキストと、その時点のレジスタやスタックの状態の2つを知れば、再現出来そう。

11章もなかなかしんどい

割とページ数が多く、なかなか進んでる感じがしなくてしんどい章だった。そんなに難しいという程でも無いのだが、適度に歯ごたえもある感じでサラサラは読めないし。

ただGCの理解という点では大分理解が深まった気がする。 GCセーフポイントとかそこで必要な情報とか、この辺を見ないとアルゴリズムを説明されてもどう実装するか良く分からんからね。

12章ファイナライザと弱参照

a到達可能がややこしいので、少しメモしておく。

aを具体的に5としてみる。

5*到達可能とは、あるオブジェクトが5以上の強さを持つ参照だけで構成された経路をたどって到達可能であること。

5到達可能は、5*到達可能かつ6*到達可能で無い時、つまりなるべく大きい物だけの経路を探した時に、その経路の最小値で5を含む、という事か。

数字が大きい方が強い、つまり強参照側になるのだな。

5到達可能、という事は、例えば6-7-6-8-5-7-6とかだな。 5より上しか無くて、5を含む。

つまり鎖の一番弱い所が5、という事か。

では弱到達可能というと、一番弱い所がソフト参照以上な経路は無い、という事だな。つまり弱参照を経由してしか到達出来ない、という事か（もっと弱いのはありえるとして）。

12章の感想

文章による説明が多い章だったので、日本語のおかしさの被害が多かった。知ってる話題の復習にはなるが、知らない話題をこれで学ぼう、という気にはならない。和訳の品質は低めだなぁ。ダメという程では無いが。

章としてはファイナライゼーションと弱参照だけなので短いが、弱参照はかなり突っ込んで解説されている。並行プログラムのこの手の話題は辛いねぇ。

13章並行プログラミングの準備

ロックフリーがオブストラクションフリーより達成が簡単と書いてあるが、定義からそれはおかしいのでは？とThe Art of multiprocessor programmingを見直すが、やはりロックフリーならばオブストラクションフリーだな。

この章はロックフリーのキューとかの話題が多いが、この本で学ぶ気はあまり起こらない内容である。しかも、自分が他の本でちゃんと習得済み、と言えない話題なので、どうすべきか悩ましい。

一応最後まで読んだが、細かい落とし穴をちゃんと理解しているとは言えない感じで、どうしよっかなぁ、と思ってる。

とりあえず先に進んでみて、この章の内容が必要そうだったらちゃんと並列プログラミングの本を読み直すか、ここでこの本をギブアップするかを判断しないといけないなもしれない。

ウェイトフリー

他のスレッドの動作に関わらず、すべてのスレッドが常に進行出来ること。

ロックフリー

infinitely often some method call finishes in a finite number of steps、が定義らしい。

最初のinfinitely oftenというのは、続けていればすべてのメソッドがやがて終わる、という事か。

オブストラクションフリー

どの時点でも、その時点から特定のスレッドだけを回せば有限ステップでそのスレッドがおわる事。

starvation

一つのスレッドがロックを待って永遠に止まる事。

14章並列GCは良く分からなかった

一応一通り読んだのだが、どうも個々のアルゴリズムが良く分からなかった。難しいというのもあるし、疑似コードや図が少ないというのもある。

全体的に論文のサマリーだけ見てるような分からなさがあった。ただ頑張って何度も読み直すという気も起こらないので、表面だけなぞって先に進む。

ただ13章の内容が思ったより役に立った。 13章の内容のおかげで、どの辺で問題が出そうかの雰囲気が分かる。これが分からないと完全に読む意味無さそうだった事を思うと、13章の内容はちゃんと理解出来なくても一通り目を通しておくべきだった模様。

15章並行GC

15章もあまり消化出来た感じはしない。ただどういう問題が発生してどういうバリアで解決出来るのか、という、エグゼクティブ・サマリー程度の理解は得られた。現時点の自分の実力ではこのくらいの理解が限界かなぁ。

15.2 バリア技法

あとででてくるので簡単にメモ。

Writeは

src[i] = ref

という操作をする時のバリア。

Readは

ref = src [i]

という操作をする時のバリア。

また、灰色の色付け、というのは、黒だったら黒のまま（shadeという操作）。

灰色ミューテータ用バリア

Steeleのバリア。Writeの時、src が黒でrefが白ならsrcを灰色に戻す。もっとも精確。

Boehmのバリア。Writeの時、srcが黒ならsrcを灰色に戻す。

Dijkstraのバリア。Writeの時、srcが黒ならrefを灰色に色付け。refがあとで削除されても白と判定出来ないので、Steeleのバリアより精度が低い。（その分境界を戻さないメリットがある）

黒いミューテータ用バリア

Bakerのバリア。Read時に、srcが灰色だったらrefも灰色に色付け。

Appel のバリア。Read時に、srcが灰色だったらsrcをscan してから読み出す。

Abraham and Patelのバリア。Write時にsrcが白か灰色なら、古いsrc[i]を灰色に色付けしてから書き込む。

16章並行マークスイープ

15章より難しくなるのかと思って、なかば諦めながら読んでいたら、内容は15章より優しいな。マークスイープは移動が無いおかげで、並行GCとしては簡単な部類になるが、15章は一般的な場合だったからか。

表16-2がKindleでかなり壊れてたので正誤表を翔泳社のサイトで確認してみたが、一箇所しか誤植の訂正が無いな。もっとあった気がするんだが、Kindle版のエラッタは無い、という事かなぁ。

16.3 割り付け

ここでいくつかの方式が出てきて、あとで言及があるので簡単にメモ。

Kung and songの方式。マーキングフェーズの間は黒で、それ以外は白で割り付ける。

Steeleの方式。新しいオブジェクトの初期化時に参照フィールドの値が分かってる前提で、マーキング時は、参照が全部白でなければ黒で割り付け、どれかが白なら白で割り付ける。

スイープ時は現在のスイープの場所によって白か黒に分けて、フリーなセルがfrom空間から割り付けられるなら白、それ以外は黒で割り付ける。

16章は意外とちゃんと分かった

15章があまり分からなかったので半分諦めながら読んでたが、意外と良く分かった。 16章は15章の簡単なケースの具体例になってるので、15章を見直す必要がちょこちょこあって、この過程で15章の理解も深まった。

15章が分からなくても諦めずに16章まで読むのがいいね。

17章以降

17章は並行コピーおよび並行圧縮

理解度が浅く別段メモする事も無かったのでそのまま読み終わってしまった。

マルチバージョンのあたりは良く分かってない。誰が次のバージョンを作るのかが良く分からなかった。

その他、書いてある事はわかるのだが、

その処理が無いとどういうまずい事が起こるのか
どうしてその処理なら問題無いのか

という一番キモとなる所を理解出来ない。この辺は今の自分の理解度では仕方ないかなぁ。

18章は並行リファレンスカウント。併合型を復習したら字面は理解出来たが、これでなんで別のスレッドが書き換える問題に対処出来てるのかが良く分からない。これは17章と一緒。ただ疑似コードの疑似度合いもこれまでの章より高くて、理解出来てないのは自分のせいだけでも無い気がする。

全体の感想

読み終わった〜！なかなか大変だったが、無事読み終わった。前半はまぁまぁちゃんと理解出来て、後半は概要とかお話程度の理解の所が半分くらいはあった。全体的には7割くらいの消化率かしら？まぁ良く頑張った方じゃないか。

お話的な概要の理解は、まぁまぁ悪くないというか、そもそも普通はその程度の理解で十分という気がする。むしろちゃんと理解出来た所がそれなりにある所がこの本の特殊性といえる。そういう訳で後半が概要程度の理解にとどまったのもそこまでネガティブな印象は無い。

このエントリの作成が7月10日となってて今日は9月4日なので、二ヶ月弱か。まぁまぁコンスタントに読んでたと思うが、結構掛かったなぁ。

並行GCと並列GCは、この本を読むまでどう実装するか全然分かってなかったが、ReadとWriteのバリアを差し込む、という基本は理解出来たと思う。この辺の感覚的な理解が得られたのは大きな収穫と思う。

また、昨今の複雑なGCも、元になってる重要な奴というのがあって、それらはそれなりにちゃんと消化出来たと思う。本格的に勉強しなきゃいけなくなった時に勉強出来る程度の理解には到達したのでは無いか。

Androidの話は全然無くて、この辺はここ数年のトレンドからは離れてるなぁ、という気がする。本としては2010年くらいが最後になっているが、AndroidのGCがこの本であつかってるレベルでの先進的な領域に入ってきたのはたぶんNとかあたりと思うので、ここ2〜3年程度の話だろう。という事で2010年止まりなのはちょっと古いな、と思う。最近の話も知りたいね。

訳はいまいちだがダメという程でも無い。ただそれなりの頻度で何を言いたいか良く分からない日本語には遭遇する。直訳として間違えてはいないのだろうが、意味は分からない、みたいなの。結構多くて辛い。

英語版を読んでないから推測ではあるが、同じ値段なら英語版をオススメする。ただ今回は半額セールで買ったので、同じシチュエーションでもう一度買うとしたら、やはり日本語版を買うと思う。逆に言えばその程度にはちゃんと書かれてる。

要所要所でテクニカルタームと思える物の元の英語が載ってない。これはググる時に困るのでつけてほしかったなぁ。全体的に翻訳の評価は低い。だがこの本を翻訳したという事自体はなかなか有益な仕事をしたとおもうので、そこは高く評価したい。きっとそうしなければ私の目に触れる事もなかっただろうし。そこは感謝。

少し繰り返しになるが、読み始める前の状態と読んだあとの状態について簡単に書いておこう。

もともとの簡単な保守的mark sweep実装した事はあってコピーGCやgenerational GCはお話程度の理解、という状態から、コピーやgenerational GCは頑張れば実装出来そうな所までは理解は進み、並行、並列、リアルタイム周りの様々なアルゴリズムはお話程度には理解出来たし、もう少しちゃんと理解出来たのもいくつかはある。まぁGC実装する人では無いのだからこの位知ってれば十分かな、というくらいは理解出来た。

後半は前のアルゴリズムの改善版、みたいなのが続くので、突然最新版を見ても良く分からない。だが現在はちゃんと順を追って一通りは見たので、必要になったら戻って復習しつつちゃんと理解出来るくらいの所には居るんじゃないか。

読むのには並列プログラミングの結構な理解やレジスタとかのハードウェア的な事への結構な理解を要求されるので、かなり難しい本と思う。しかもそれらの知識がさらっと言及されるので、知らない人が見ると知らないという事実に気付かずに、なんだか良く分からない、という事になりそう。実際自分もそういう場所が何箇所かあった。こんな難しい本を良く出したもんだ、と感心する。

最近は機械学習や数学の本を読んでばかり居たので、結構本格的な技術書を読むのは久しぶりだったが、思った以上に勉強になった。もうちょっと技術書も読んだ方がいいよなぁ、と心を入れ替えた。難しいけれど良い本でした。読んで良かった。

AndroidのGCの話

少しググったが、論文は良いのが無さそう。 IOの動画もいくつかあった気がするが、あんまり詳細は分からないんだよなぁ。

今軽く探した中では、公式ドキュメントの所の解説が一番詳細な気がする。

Debugging ART Garbage Collection

前にも読んだ事があるが、今読むと理解が進むな。ただIOではもうちょっと新しい話がいくつかあった気がする。まぁいい。

基本はconcurrent Mark and Sweep（CMS）だそうで。スレッドごとにallocationバッファはあり、generationalだが普段は移動はしない。裏に行った時にcompactionする、との事。なかなかいいね。

stickyじゃないpartial なCMSについては説明が無いな。どう動かすんだろう？ homogeneous space compactionとかの事かしら？これはスレッドローカルなアロケーションバッファ用のcopy GCのように見える。

cardへの言及があるが、card使ってるのかしら？この辺は詳細が分からないな。

1章 イントロ