December 28, 2003

Perl、Java、Ruby における GC アルゴリズム

[ Perl ]

オライリー・ジャパンから『続・初めてのPerl Perlオブジェクト、リファレンス、モジュール』が出ました。(12/29発売ですが、もう売ってました。) 早速購入、1/3 ぐらい読みました。

Perlの入門書として個人的にいちおししているラマ本こと『初めてのPerl』の続編という形で出版された、この続・始めてのPerlは、表紙の動物が南アメリカラクダ科の"アルパカ"なので、アルパカ本と呼ぶことにします。

さて、アルパカ本、内容の方は、ラマ本ではあまり触れられなかった、少し高度な内容にフィーチャーされた本。オブジェクト、リファレンス、モジュールについて、初めてそれに触れるプログラマがしっかりと理解できるように、丁寧に解説されています。和訳も結構良くて、読みやすいです。

全体を通したレビューはまた後日に書くとして、Perl のメモリ管理の方法としてのリファレンスカウント、その解説部分にちょっとひっかかる箇所がありました。44ページ 第4章 「リファレンスとスコープ」の一文、

Perlは、今後リリースされるバージョンで、リファレンスカウントに加え、ガベージコレクション (garbage collection) を導入することが予想されます。

リファレンスカウントというのは、あるデータ構造やオブジェクトがあった際、それらを参照するリファレンスの数を内部で換算して、その数が 0 になったらメモリから実体を破棄するという仕組みです。何がひっかかったかというと、この書き方だと、リファレンスカウントとガベージコレクションは別の仕組み/概念だと思わされてしまうのではないかという点。

ガベージコレクション(GC)は、使われなくなったメモリを自動的に検出して解放してくれる機能ですが、その具体的なアルゴリズムの実装には色々な方式があり、その中の一つがリファレンスカウント式GCだと理解しています。ここで書かれているリファレンスカウントとは、Perl の GC 機能そのものであり、今後のバージョンで導入云々というのは間違った記述なのではないかなあ。と、僕はあまりその辺りの話は詳しくないので、宮川さんにも聞いてみたのですが、そう言っていました。

Perl の GC は現在、リファレンスカウント式GCが採用されているということで、じゃあ他の言語はどうなんだろうと、Java についてぐぐってみると、'Java Programming Information' に、まとまった記述がありました。

Java の場合、GC のアルゴリズムにどういった方式のものが使われているかは VM に依存するようですが、一般的には世代別コピー式GCというのが採用されているようです。リファレンスカウント式GC は、仕組みがシンプルで分かりやすい反面、相互参照が原因で参照を切ることができずにメモリリークを引き起す場合があるなど、割と致命的な欠点を持っているようですが、世代別コピー式GCは、ある局面でのGCの停止時間を犠牲にしつつ、その辺の欠点をうまく回避したアルゴリズム、ということでしょうか。なんだか、難しそうなお話です。

Ruby はマークアンドスイープ方式。(Ruby Hacking Guide ガベージコレクションより)

Ruby の GC はマークアンドスイープと呼ばれる方式を使っている。この方式では、確実にデータがあることがわかっているアドレスからポインタをたどっていき(マーク)、到達できなかったポインタをもう使われていないものとみなして解放する(スイープ)。

マークアンドスイープ方式の欠点は、先の Java Programming Information によれば

・ヒープサイズに応じてGC時間が増大する
・スラッシング(thrashing)…ヒープの残量が少ない時には,GCを頻繁に繰り返してしまう

といったものが挙げられるのだそうです。ふむふむ。(分かった振り)

LL Saturday におけるまつもとさんプレゼンで、Ruby 1.9.0 で世代別GCを取り込むという話があったのを思い出しました。(検索すると、すでに現行バージョンに対するパッチなんかもあるみたい) 1.9.0 は新しい実装の実験的なバージョンと言っていたので、世代別GCが安定版として採用されるのは 2.0 からということになるのでしょう。

ふう、お腹一杯。

Posted by naoya at December 28, 2003 03:19 AM | トラックバック (0)  b_entry.gif
トラックバック [0件]
TrackBack URL: http://mt.bloghackers.net/mt/suck-tbspams.cgi/733
コメント [3件]

ちなみにPythonのGCはこんな感じです。
http://arctrix.com/nas/python/gc/

[1] Posted by: とおりすがり at December 29, 2003 11:22 AM [返信]

原書の方には次のように記載がありますね:

A future version of Perl is likely to use garbage collection in addition to or instead of referencing counting. Until then, you must be careful to not create circular references, or if you do, break the circle before the variables go out of scope.

「参照数に加えて、あるいはその代わりにガベージコレクションを用いるかもしれない」。あまり訳としては変わらない気もしますが。

[2] Posted by: mya at December 29, 2003 11:46 AM [返信]

>>1 とおりすがり さん

お、Python 情報ありがとうございます。

このドキュメントだと Python も Perl と同じ方式
のようですね。将来的には変更したいような旨が
ありますが、現行バージョンもそうなのでしょうか。

>>2 mya さん

おお、原文どうなっているか見たかったのです。
ありがとうございます。

確かに訳としては変わらないですね...。誤記なのか、
意図的なものなのかちょっとよくわかりませんね。

[3] Posted by: naoya at December 29, 2003 11:55 PM [返信]