2017-05-23

References will be Garbage

技術メモ知見

参照カウント方式のメモリ管理機構ではメモリ解放のプロセスを分散できるために、他のメモリ管理と比べて目に見える停止時間が少ない。ただ、純粋な参照カウント方式では全てのオブジェクトの状態を管理することは難しくて、例えば循環参照などの問題が発生する。歴史は色々あるのでそうした問題解決方法について少し調べたものをまとめてみた。 GCハンドブックなどを見れば一通り書いてあるので、気になったら書籍を参考にしてもらえればと思ったり。

循環参照の解決

参照を持っていればオブジェクトは破棄されない。そのため参照カウント方式のメモリ管理機構では参照の状態が循環状態になるとオブジェクトは一生解放されないという問題点がある。以下はReferenceクラスのインスタンス変数としてお互いを参照している例である。この状態ではa, bそれぞれ他のオブジェクトからの参照が残っているため、参照カウント方式のメモリ管理ではどちらも解放されない。（rubyっぽく書いているが一応疑似コード）

class Reference
  instance_var :ref
end

a = classA.new
b = classB.new

a.ref = b
b.ref = a

弱参照と強参照

一つの手段として参照に強弱を持たせる。それぞれ強参照、弱参照と呼び、強参照は一般的な参照と似たようなもので。参照されている先のオブジェクトは参照が残っている限り破棄されない。対して、弱参照は参照先から強参照が消えると破棄される。つまり破棄を防ぐ強制力を持たない。

対策としてしばしば参照カウント方式のメモリ管理機構には弱参照の概念が導入される。例えば、イミュータブルな参照を弱参照で扱ったり、強弱両方の参照記法を用意し、プログラマに明示させるなどの方法がある。

もともと手動管理であったり、静的にメモリを管理できる機構が備わっている場合は負担は少ないだろうけど、記述のミスが原因でメモリリークを引き起こしたりする可能性があるため若干怖い節がある。

ちなみにC++11以降ではスマートポインタ、objective-cではARC（Auto reference count）、RustではArc・Rcが似たような機能を持っている。

ガベージコレクション（GC）の分散

また、別の対策としてあるのが、別のGCを導入することである。例えば Mark and sweep を導入し、使用未使用の状態をフラグで管理することで循環参照状態のオブジェクトを発見、破棄できる。

逆に Mark and sweep のみの構成ではMarkフェーズ、sweepフェーズの負荷が大きく、プログラムに停止時間を与える可能性がある。そのため、参照カウントを用いて適度にオブジェクトの破棄を進めつつ、参照カウントで破棄できないオブジェクトをまとめて破棄する。互いの欠点を補いつつ複数のアルゴリズムでGCしていくのは一般的な手段であると言える。

例えば、Python2.2では参照カウント方式のGCと Mark and sweep を組み合わせてメモリ管理を動的に行っている。最近あったその手の話では、instagramがWebサーバーへのリクエスト時にMark and sweepによるGCを停止させ、参照カウントのみでメモリ管理を一時的に行うことで性能を向上させるなどの工夫があった。*1

参照カウントのトレードオフ

闇雲に参照カウントを入れればフルGCの機会が減って性能が向上するわけでもない。オブジェクトの参照をカウントするにはそれ専用の領域が必要になる。すなわち、オブジェクトが確保するヒープ領域には最大オブジェクト数分のカウントが可能な領域が余分に確保される。余分に確保されるということはヒープ領域をフルに活用できるない。フルに活用できないのであればメジャーGCの頻度は向上するだろう。結局、参照カウントによって分散できるはずが、総フルGC時間が長くなってしまい、逆に性能が悪化する恐れがある。

そこで例えば、参照カウント用のビット数を絞る方法なども考えられる。例えば、ビット数を1ビットとして参照カウントをし、2つ以上の参照があった場合には参照カウントによるGCを諦め、他のGCに処理を移譲する。こういった方法は一般的なオブジェクトの生存期間や参照の数について統計やベンチマークを行い、言語やフレームワーク、設計の特性からビット数を工夫することで性能は向上する可能性がある。

*1:https://engineering.instagram.com/dismissing-python-garbage-collection-at-instagram-4dca40b29172

2016-12-11

(故)insLTのチラ裏 #coinsLT

この記事は LT Advent Calendar 2016 - Adventar 11日目の記事です。前回は id: yagamian_sobaya さんの「今年やったLT」でした。次回の記事は間が空いていて謎なので、更新され次第追記したいと思います。

こんにちは id: everysick です。現在は筑波大学の情報科学類でほのぼの生活しています。今回は coinsLT について1, 2年前に何をしていたのか、今はなぜ開催されていないのかなどの話をだらだら書き、引き継ぎたい旨を伝えたいと思います。色々端折りつつ時系列を追って説明していくと思うので、よろしくお願いします。

ちなみにcoinsLTに関して、私は書類出したりconnpassを編集していた主催側の人間であったことだけ明記しておきます。

皆さんは筑波大学を知っていて、LTが何なのかというのもご存知かと思います。筑波大学でのLTは学類ごとに任意の学生が開催しており、coinsLTも情報科学類*1のLTとして開催をしていました。学類ごとと言ってもほぼ非公式*2であり、発表時間が長いなどLTとしてグレーなイベントもありました。学類LT文化の発祥は正しく語れないような気がするので話題にしませんが、少なくともcoinsLTではありません。

coinsLTが発足したのは2014年5月ごろ、当時mastやesysがLTを開催している中、coinsLTがあってもいいよねなどの話があり*3、その年に入学したての複数名で適当な団体名をでっちあげて開催を決定しました。開催の際に教員の署名が必要なのですが、当時特に宛もなかったため、クラス担当の教員へお願いしたところ「問題は起こさないでね…？」とのことであっさり貰えていた記憶があります。そんなこんなで開催が一月後に決定したんですが、登壇者を募う、当日投影用のプロジェクターやマイクを確保する、発表題目を登壇者から集めてタイムテーブルを作る、開催の周知をするなど、ちょっと手間がかかったりしました。

LT自体は盛況で、#11回まで開催が続いていたのですが、主催者がなんらかの事情で忙しくなるなどのことがあり、 2015-12-02 の開催をもって一年ほど開かれていません。

長くなりましたが本題はここからで、旧オーガナイザーによってcoinsLTは現在名前をオープンに貸し出していて、 forkしてPullrequestを送るだけ*4で開催可能になっています。

github.com

しかし開催するっていっても何を準備する必要があるのかなど、結局面倒くさいことは共有していないわけで、そういうところを書くので、若い力で盛り上げてほしいというのがこの記事の目的です。

開催ノウハウ

まず前提として、主催一人は完全に厳しいので、3人ほど集めると良いです。ただ、当日配信したい場合などはもっと人が必要だと思います。機材脈のある人、喋れる人、開催周知できる人、書類仕事できそうな人などですかね。

開催に向けて難しいことは3つほどあるのでそれぞれ書いていきます。

書類

教室を借りたり会を開催したりするのには学生事務へ事前に申請が必要です。「学生集会願」という書類を手に入れて申請し、空いている教室を確保するなどのことをします。書類には以下のような項目を記載する必要があったような気がします。

参加人数
割りと適当でもどうなかなるので、前回のconnpassの人数でも書いておきましょう。余談ですが、なんだかんだconnpassなどで集めた人数の3倍は集まるのでその気持ちでいましょう。
開催日時/開催教室
実は教室は別途借りる必要があるのですが、書類提出時にしか借りられないため、日程と教室の確保は気をつけましょう。また、教室が閉まる時間は21時と固定されているので、放課後の開催はぎりぎりにならないようにしましょう。おすすめの教室は3A402です。広いし全席電源あるし階段教室で見通しが良いからです。
責任者名
オーガナイザーの名前でも書くといいでしょう。
開催概要
概要などが適当であったり、遊戯目的での開催であることが記載してあると（教員や事務に）嫌な顔をされる恐れがあります。できるだけ真面目な文章でLTの概要をまとめつつ、「情報科学に関する理解や知識を〜」などと書いておくと良いと思います。

ちなみにconnpassなどは日付と教室が決定するまで適当な未来に時間を設定しておいて開催の気持ちを表明しておくと良いと思います。逆に日付や教室を先に周知するとリスケが面倒だったりするため、書類先行をおすすめします。

署名

実は「学生集会願」には教員の署名を貰わなければならないため、学生だけで開催することができません。過去開催では御二方の教員に署名をお願いし、承諾をいただいていますが、そもそもこんな怪しい会に関して誰でも署名をしてくれるわけではありません。 できるだけ仲の良い、物分りの良さそうな教員の方にお願いしましょう。 （深い意味はありません）

道具

教室の貸出が決定しても備品を借りることは難しいです。なんと学生には貸出をしてくれないのです。大まかに必要なものは4つあります。ただ、教室によってもしかしたら元々置いてあるものを使えるかもしれませんが、破損するなど問題になると大学生活に支障がでるため、できるだけ避けましょう。

プロジェクターと周辺ケーブル
本来教室にあるものは使えないので、自前で用意する必要があります。また、ケーブル類はPCまでの長さが必要なので下見をして長さを把握しておきましょう。
マイクと周辺ケーブル
生の声だと厳しい場合があるため、マイク・周辺ケーブルを用意して使用できるかテストも行いましょう。
喋る人
司会進行
タイムキーパー
5分経ったら強制終了させるために時間を見る人と合図をしてなんらかの音を用意する人が必要です。

ざっと書きましたが、たぶん最低限これくらい知っておくと開催できるかと思います。何か不明点がありましたら、コメントやリプライを送っていただければお答えします。雑な気持ちでやっていくのが重要です。