ガベージコレクション(5) - コピーGCとコンパクション

当連載もようやく100回目を迎えた。Objective-Cの話題だけで100回続くとは、正直自分でも驚いている。まだObjective-C 2.0やデザインパターンの残りの話題があるので、今しばらくお付き合いしてほしい。

今回もガベージコレクションの話だ。Objective-Cのガベージコレクションの特徴として、コピーは行わなず、したがってコンパクションも行わない、という点を挙げることができる。このことについて説明しよう。

コピーガベージコレクションとは

まず、コピーガベージコレクションについて説明しよう。前回、Objective-Cのガベージコレクションは、マーク・アンド・スイープ方式を使うということを話した。これは、必ず残さなくてはいけないオブジェクトから始めて、そこから参照されているオブジェクトをたどって印を付けていく、という方法だ。

ここで、ちょっと別の考え方をしてみよう。まず、メモリ領域を2つに分ける。1つは天国だ。もう1つは地獄とする。そしてマーク・アンド・スイープのガベージコレクションを行うとき、必要なオブジェクトには印を付ける代わりに、天国のメモリ領域へとコピーしよう。そのオブジェクトが参照しているオブジェクトも、順次天国へとコピーしていく。すると、地獄には不必要なオブジェクトのみが残るはずなので、最後に地獄にあるオブジェクトを破棄する。

これがコピーガベージコレクションの考え方だ。この手法では、ガベージコレクションを行うと、オブジェクトのメモリ領域が移動することになる。このようなメモリ管理の動作は、ポインタへの直接のアクセスを許さないタイプの言語であれば、プログラマから隠蔽することができるだろう。だが、C言語やObjective-Cのように、ポインタを自由に触れる言語では導入が困難である。したがって、Objective-Cのガベージコレクションでは、コピーは使われていない。

コンパクションとは

コピーガベージコレクションは、ちょっと考えてみると、コピーのコストがとても大きくて効率が悪そうである。だが、嬉しい副次的な効果がある。それが、コンパクションと呼ばれるものだ。

英語のcompactionは、圧縮する、またはコンパクトにするといった意味だ。では、計算機科学の文脈でコンパクションという単語が出てきたとき、何を圧縮するかと言えば"メモリ領域"になる。散らかったメモリ領域を圧縮してきれいに片付けるのが、コンパクションだ。

もう少し具体的に説明していこう。アプリケーションを起動して、さまざまな処理を行ったとする。処理が進むにつれて、メモリの確保と解放を繰り返し、メモリ領域は虫食い状態になっているだろう。これでは連続したメモリ領域がなくなり、大きなメモリ領域を、総計では余裕があるにも関わらず、確保できないということが起きてしまう。

これを解決するには、メモリを移動して虫食い状態を押しつぶしてしまえばいい。これが、コンパクションだ。ハードディスクの断片化を解消するデフラグテーションという処理があるが、それのメモリ版だと考えてもらえばいい。コンパクションを行うことで、メモリ領域を有効に活用することができる。

さて、ここでコピーガベージコレクションを思い出してほしい。この手法ではオブジェクトのメモリ領域の移動が発生するので、ガベージコレクションと同時にコンパクションを行うこともできるのだ。これがコピーガベージコレクションの大きな利点となる。

コンパクションの利点は、大きいメモリ領域を確保することだけではない。コンピュータの動作には、「局所性」があるということが経験的に知られている。たとえば、あるオブジェクトに着目したとき、そのオブジェクトが参照しているオブジェクトは、すぐ近くのメモリ領域にあることが多い。これはメモリ領域の局所性だ。

そこで、コンピュータのアーキテクチャは局所性があることを前提に設計されている。逆に言えば、オブジェクトのメモリ配置を局所的にしておくと、より高いパフォーマンスが得られることが期待できるのだ。コンパクションは、このアドバンテージを利用しようとしているわけだ。

ハンドルの功罪

少し話はそれるが、コンパクションの話をすると、昔からのMacプログラマは思い出すことがあるだろう。ハンドルのことだ。

1984年に初代のMacintoshが登場したとき、今となっては信じられないことだが、RAMは128kしかなかった。当時としては大きいメモリだったが、それでもGUIを持つOSを動かすには少なすぎる。メモリ領域を最大限有効に活用することが求められた。

そこで、コンパクションのようなメモリ領域の移動が実現されていた。この場合、アプリケーションはメモリ領域を確保しても、そのポインタを直接参照しない。いったんOSがそのポインタ値を保持し、アプリケーションはその「ポインタ変数のアドレス」を使うのだ。これがハンドルと呼ばれるものだ。実体としては、ポインタのポインタになる。メモリ領域のアドレスを直接参照しないので、OSが自由にその領域を動かすことができる。動かした後は、ポインタ値を更新しておけばいいのだ。

たしかにこれでコンパクションは実現できる。ただ困るのは、このメモリの移動がいつ発生するか、わからなかったことだ。さらに、プログラミング言語はC言語だったので、結局ポインタは使えてしまう。いくらハンドルを経由しても、実際にメモリ領域にアクセスするときはポインタを使うことになる。これでは、メモリ領域が動いた瞬間にクラッシュしてしまう。そこで、ポインタを使ってアクセスするときは、メモリ領域が動かないようにハンドルのロックを行う必要があり、非常にややこしいプログラミングになってしまった。

このような事情で、昔のMacプログラミングは慎重というか、トリッキーで名人芸的な技巧が求められることになった。昔のMacは不安定だと陰口を叩かれたが、その一因はハンドルにあったのではないかと思っている。

Mac OS Xに移行する際に、ハンドルは撤廃された。だがそれと同時にコンパクションもなくなってしまった。現在コンパクションを行う言語が増えているのを見ると、皮肉に感じてしまう。もし将来、コンピュータのアーキテクチャがさらにメモリコンパクションを指向するようになった場合、Objective-CおよびCocoaは再び大きな変革を迫られるのかもしれない。