本稿は、ブダペストで開かれたイベント「 RuPy 」で、Pat Shaughnessyが披露したプレゼンの内容をまとめたものです。 プレゼンの映像はここ から視聴できます。 本稿は当初、 同氏の個人ブログ に投稿されましたが、同氏の了承を得て、Codeshipに再掲載します。

このイベントは「RubyとPython」に関するカンファレンスなので、RubyとPythonでは、ガベージコレクション（以下「GC」）の動作がどう違うのかを比較すると面白いだろうと私は思いました。

ただしその本題に入る前に、そもそもなぜ、GCを取り上げるのかについてお話しします。正直言って、すごく魅力的な、わくわくするテーマではないですよね？　皆さんの中でGCと聞いて、心がときめいた方はいらっしゃいますか？　［実はこのカンファレンス出席者の中で、ここで手を挙げた人は数名いました！］

Rubyコミュニティで最近、RubyのGC設定を変更すると、単体テストの速度が向上するというブログ記事を見かけました。素晴らしいことだと思います。テストの実行速度が上がったり、アプリケーションの実行中にGCのために処理が一時停止する回数が減ったりするのは、いいことには違いないのですが、なぜか私にとっては、GCはあまり心ひかれるものがありませんでした。一見、退屈で無味乾燥な技術というイメージがあるからです。

でも実は、ガベージコレクションは魅力的なトピックです。GCアルゴリズムは、コンピュータ科学の歴史の中で重要な位置を占めているだけでなく、最先端の研究テーマでもあります。例えば、MRI Rubyで使われているMark and Sweepアルゴリズムは50年以上前からあるのに対して、Rubyの実装の一種であるRubiniusで採用しているGCアルゴリズムはごく最近、2008年に発明されたものです。

にもかかわらず、「ガベージコレクション」という名前のために、誤解を受けている部分があります。

命の鼓動を刻むアプリケーションの心臓部

GCシステムの役割は、単なる「ガベージコレクション（＝ごみ集め）」にとどまりません。実は、3つの重要なタスクを実行しています。そのタスクを以下に挙げます。

• 新規オブジェクトのメモリへの割り当て
• ガベージオブジェクトの特定
• ガベージオブジェクトからのメモリの解放

ここで、アプリケーションを人体だと考えましょう。アプリケーションのために書かれた洗練されたコード、ビジネスロジック、アルゴリズムは全部まとめて脳、すなわちアプリケーションのインテリジェンス（知性）に当たるでしょう。

この例えで言えば、GCはどの器官に当てはまると、皆さんは思いますか？　［ここでRuPyの参加者からは「腎臓」「白血球」など、面白い回答が次々に寄せられました］

私は、GCこそアプリケーションの命の鼓動を刻む心臓だと思います。心臓が血液と栄養を体内の隅々まで送り届けるのと同様に、ガベージコレクタも、アプリケーションが使用するメモリとオブジェクトを供給するからです。

もし心臓の拍動が止まったら、人間は数秒で死に至ります。仮にガベージコレクタが停止したり実行速度が極端に落ちたりすると、これは動脈が詰まるようなものですから、アプリケーション自体の実行速度が落ちて、結果的にはアプリケーションが停止する場合すらあります。

GCは派手な働きをしているようには見えませんが、実はアプリケーションがじわじわと絶命するのを防いでいるのです。
ここをクリックしてツイート

簡単な例

実例を使って理論をじっくりと理解するのは、どんな場合にも有用なアプローチです。従ってここでも簡単なクラスを使って、PythonとRubyで書かれたコードを取り上げて考えます。

ところで、RubyとPythonのコードを比べるとこんなに似ているという点に、私は驚きました。RubyとPythonは、同一の処理に対するコードの記述方法は、ほんの少ししか違いがありません。しかし、それぞれの言語の内部処理の方法も、コードと同様に非常に似ているのでしょうか。

freelist（空きリスト）

上記の例で Node.new(1) を呼び出した時、Rubyは厳密に言うとどんな動作をするのでしょうか。Rubyは新しいオブジェクトを作成する時、どのように処理を進めるのでしょう。

驚いたことに、ほとんど何もしていません。実際には、コードの実行を始めるずっと前に、Rubyは前もって何千ものオブジェクトを作成し、連結リスト上に配置します。この連結リストをfreelistといいます。以下の図は、freelistの概念的なイメージを示したものです。

上記の図で白い四角は、Rubyが事前に作成したオブジェクトで、未使用のものを示しています。Node.newを呼び出すと、Rubyは単純に、その中からオブジェクトを1つ取り出して、コードに渡します。

左端の四角がグレーになっているのは、コードで使用するために、Rubyがアクティブにしたオブジェクトを示しています。残りの白い四角は、未使用のオブジェクトです。この図はもちろん、説明のために実際の状況をかなり簡素化しています。実際には、Rubyはもう1つのオブジェクトを使って、文字列「ABC」を保持し、3番目のオブジェクトも使ってnodeのクラス定義を保持し、さらに他のオブジェクトも使って、コードの解析結果、抽象構文木（AST）の内容などを保持します。

Node.new を再び呼び出すと、Rubyは単純に、別のオブジェクトをコードに渡します。

事前に作成したオブジェクトの連結リストを利用する、この簡素なアルゴリズムは、コンピュータ科学者の間では伝説となっているJohn McCarthyがLISPの最初の実装に取り組む中で、50年以上前に発明したものです。

LISPは最初の関数型プログラミング言語であっただけではなく、コンピュータ科学を大きく進歩させた画期的な要素が幾つも含まれていました。

ガベージコレクションを利用して、アプリケーションのメモリを自動的に管理するという概念もその1つです。

Rubyの標準バージョンは、「MatzのRubyインタープリタ」（MRI）という別名もありますが、これには、John McCarthyが1960年に作成したLISPの実装で採用されているものとよく似たGCアルゴリズムが使われています。つまり良くも悪くも、Rubyは53年間、同じGCアルゴリズムを使い続けています。LISPと同じように、Rubyもオブジェクトをコードの実行前に作成して、コードで新しいオブジェクトや値を割り当てると、そのオブジェクトをコードに渡します。

Rubyで採用されているガベージコレクションのアルゴリズムは、53年前から変わっていないことを知っていましたか？　―@patshaughnessyのツイートより
[ここをクリックしてツイート](https://twitter.com/share?text=%22Did+you+know+Ruby+uses+a+53-yr-old+algorithm+for+garbage+collection%3F%22+%E2%80%93+via+%40patshaughnessy&url=http://blog.codeship.com/visualizing-garbage-collection-ruby-python/)

Pythonでのオブジェクトの割り当て

ここまでは、Rubyはオブジェクトをコードの実行前に作成して、freelistに保存するというところを皆さんと一緒に見てきました。ではPythonはどうでしょう。

Pythonも様々な理由（リストなど特定のオブジェクトを再利用する）から、内部でfreelistを利用していますが、新規のオブジェクトや値をメモリに割り当てる通常の方法は、Rubyとは異なります。

ここでは、Pythonでnodeオブジェクトを作成する場合を考えます。

コード側でオブジェクトを新規作成すると、PythonはRubyと違って、オペレーティングシステム（OS）に対して、直接メモリを要求します。（実はPythonでは、OSヒープの上層に抽象化レイヤを追加して、メモリ割り当てシステムを自前で実装しています。ただし今回は時間の都合で、この点について詳しい説明はしません。）

2つ目のオブジェクトを作成すると、Pythonは再び、OSにメモリの割り当てを増やすように要求します。

この動作も十分シンプルに見えます。オブジェクトを作成する瞬間にPythonは時間を取って、コードが使用するメモリを見つけて割り当てます。

Rubyデベロッパーは散らかった家に住んでいるようなもの

Rubyに話を戻します。

Ruby では、コードが次々とオブジェクトを割り当てると、freelistのオブジェクトが使用されます。そのため、freelistは下記のように短くなります。

さらに短くなると下記になります。

Rubyでn1に新たな値を指定すると古い値はそのまま放置されます。Node ABCやJKL、MNOはメモリに残ります。Rubyではコード内にある使用しない古いオブジェクトをすぐに一掃しません。

Rubyの開発者からみると、まるで洋服が床に落ちていたり、食器が流しに溜まっていたりする、整頓されていない家に住んでいるようなものです。Rubyで開発する場合、未使用のガベージオブジェクトが存在する環境での作業を強いられます。

Python開発者は綺麗好きな同居人と住んでいる

PythonではGCは異なる動作をします。先ほどの3つのPythonのnodeを使ってみましょう。

Pythonでオブジェクトを作成すると、Cの構造体の内部に参照カウントと呼ばれる整数が保存されます。ここで設定される参照カウントの初期値は1です。

参照カウントに設定されている値が1のとき、ここでは下記の3つのオブジェクト全てに対して、ポインタまたは参照が1つずつ設定されていることを意味します。この状況で新しいnode JKLを作成すると仮定します。

新しいnode JKLを作成すると、前回オブジェクトを作成したときと同様に、JKLへの参照カウントも1に設定されます。ただしここで、 n1 が指す参照先がABCからDEFに変更されたことに注目してください。従って、ABCの参照カウントが0になります。

この時、PythonではGCが起動されます。オブジェクトの参照カウントが0になると直ちにオブジェクトへの参照を解放し、メモリ領域をOSに返します。

Pythonでは、node ABCが使用していたメモリ領域を取り戻します。Rubyでは、古いオブジェクトを放置したまま、メモリ領域を解放しません。

このGCアルゴリズムは 参照カウント と呼ばれています。1960年にGeorge Collinsによって発明されたものです。偶然ではないのですが同年に、John McCarthyがfreelistアルゴリズムを発明しました。

Mike Bernstein が、 Gotham Ruby Conference での素晴らしい GCのプレゼン で述べたように、「1960年はGCの当たり年でした」。

Pythonの開発者はまるで、散らかるとすぐに片付けてくれるルームメートのいる整理整頓された家に住んでいるようなものです。使用済みの皿やコップを置いた途端に、誰かが食洗機に入れてくれるような感じです。

次の例では、 n2 が n1 と同じnodeを参照するように設定します。

DEFの参照カウントがデクリメントされ、node DEFはGCとして処理されます。ここでは、 n1 と n2 の両方のポインタがJKLを指しているため、JKLへの参照カウントは2になります。

Ruby のMark and Sweepアルゴリズム

散らかった家はいずれごみでいっぱいになり、普通の生活に支障をきたすことになります。Rubyでプログラムの実行を続けると、やがてfreelistを使い切ってしまいます。

Rubyが事前に作成しておいたオブジェクトをアプリケーションが全て使い切ったので（四角が全てグレー）、freelistにはオブジェクト（白い四角）が残っていません。

このとき、RubyではMcCarthyが発明したMark and Sweepという別のアルゴリズムが使われます。まず、Rubyは「stop the world」方式を使用してアプリケーションの実行を止めます。次にRubyは、ポインタ、変数、コード側でオブジェクトやそれ以外の値を指すように指定した参照の全てに対して、「stop the world」処理をループで反復します。また、仮想マシンが使用している内部ポインタに対しても、同じ処理を繰り返します。そして、現在使用しているポインタが指している各オブジェクトにマーク（ mark ）を付けます。下記では、そのマークを付けられたオブジェクトをMとしました。

「M」の付いた３つのオブジェクトは生きています。アプリによって使用されているアクティブなオブジェクトです。Rubyは、内部的にどのオブジェクトがマークされていて、どのオブジェクトがマークされていないかを フリービットマップ で管理しています。

UNIXのコピーオンライトの最適化機能を最大に活用するため、Rubyはフリービットマップを別のメモリ領域に格納します。詳しく知りたい場合は、私の記事 「Why You Should Be Excited About Garbage Collection in Ruby 2.0.」 をお読みください。

マークされたオブジェクトが生きている場合、マークされていない残りのオブジェクトはごみとなります。つまり、コードでは使用していないということになります。下記では、ごみとなるオブジェクトを白い四角で表しています。

次に、Rubyは使用されていないごみであるオブジェクトをfreelistから 一掃(sweep) します。

この内部処理はかなり高速で実行されます。Rubyは実際にオブジェクトをあちこちにコピーして回らず、内部ポインタを調整して新しい連結リストを作成するので、GCはfreelistに戻ることになります。

これで、次回オブジェクトを作成した時に、ごみオブジェクトだったものを未使用のオブジェクトとして、コード側に返すことが可能になります。Rubyでは、オブジェクトは生まれ変わり、何回でも復活することができます。

Mark and Sweepと参照カウント

一見、PythonのGCアルゴリズムはRubyのものより優れているように思えます。整理整頓した家に住めるのに、散らかった家に進んで住む人はいません。Pythonのアルゴリズムがあるのに、オブジェクトを一掃するたびにアプリを止めてしまうRubyをあえて使う理由はありません。

しかし、参照カウントは見た目ほど単純ではありません。参照カウントをGCアルゴリズムに採用しない言語がある理由は下記のとおりです。

• 第一は導入の難しさにあります。各オブジェクト内に参照カウントを置く領域を確保しなければなりません。必要な容量が大きくなるという意味で、これが若干デメリットとなります。さらには、変数や参照を変更するといった単純な作業も、Pythonでは、カウンタのインクリメントやデクリメントを行ってオブジェクトを解放しなればならないため、複雑な作業となってしまいます。
• 第二に動きが遅くなってしまうことにあります。PythonのGCはアプリケーションを実行するタイミングに合わせて（まるで使用済みの食器を次々と流しにいれるように）スムーズに実行されますが、速いとは限りません。Pythonは常に参照カウントを更新しています。そのため、例えば多くの要素を含むリストのような、大規模な構造体のデータの利用をやめてしまうと、多数のオブジェクトを一度に解放しなければならなくなります。すると参照カウントのデクリメントは、再帰的な反復を伴う複雑な処理になることがあります。
• 最後に、必ずしも正常に機能するとは限りません。私の次の記事で述べますが、参照カウントは循環参照を含むデータ構造には使えません。

次回

次週、プレゼンの後半をまとめる予定です。Pythonがどう循環データ構造を処理するのか、Ruby2.1でGCがどう動作するのかを説明したいと思います。