なぜアルゴリズムを学ぶのか

GCによる停止時間が長くなり、アプリケーションの処理時間が短くなると、業務に使える時間が短くなってしまいます。その問題を解決するために、GCをチューニングすることで、アプリケーションの停止時間を短くすることが考えられます。

その際大事なのは、GCのアルゴルズムを把握しておくことです。

GCのチューニングを行うときは、GCで行われている処理の内、どの処理に時間がかかっているかをモニタリング⇒分析⇒チューニングする、という流れになります。しかし、GCのアルゴリズムを知らないと、モニタリング結果を見てもどこに問題があるかがわからず、分析やチューニングを行うことができません。

今回は、以下の4つのアルゴリズムをご紹介します。

• マーク＆スイープGC
• コンパクション
• コピーGC
• 世代別GC

GCのアルゴリズムはJVMの実装によって異なりますが、多くの場合、上記4つのアルゴリズムが組み合わされて実装されています。

GCを2つのフェーズに分けて実行する ～マーク＆スイープGC

これまでの連載からイメージしやすいGCアルゴリズムは、マーク＆スイープGCでしょう。マーク＆スイープGCでは、GCを以下の2つのフェーズに分けて実行します。

1つ目のフェーズ

⇒ゴミとなっていないオブジェクトを探す（マークフェーズ）

2つ目のフェーズ

⇒ゴミとなったオブジェクトを削除するフェーズ（スイープフェーズ）

マークフェーズでは、ヒープ内にあるオブジェクトの参照をたどっていき、生きてるオブジェクトをマークしていきます。JVMは、マークフェーズが終わったときにマークされていないものを死んだオブジェクトとして判定します。

スイープフェーズでは、マークが付いていないオブジェクトを回収することで、ヒープ領域を開放します。スイープフェーズが終わると、死んだオブジェクトに割り当てられていた領域が、新たなオブジェクトに割り当てられるようになります。

マーク＆スイープGCでは、死んだオブジェクトをスイープした領域がそのまま空き領域になります。そのため、ヒープの中に空き領域が点在してしまいます。この空き領域は、新たなオブジェクトを割り当てる際に、空いている領域のサイズまでのオブジェクトしか生成できません。そのように、空き容量が点在することを「断片化」と言います。

断片化が多発してしまうと、どのような問題があるのでしょうか？

まず、ヒープの空き容量があったとしても、オブジェクトが生成できる場所が限定されてしまい、このオブジェクトが入る空き領域を探すのに時間がかかります。さらに最悪のケースでは、オブジェクトを生成できる場所が見つからなくなると、アプリケーションが予期せず停止してしまうかもしれません。

バラバラに配置されていたオブジェクトを連続して配置する ～コンパクション

ヒープ内にバラバラに配置されていたオブジェクトを、ヒープの一端に連続して配置することが考えれます。この動作を「コンパクション」と呼びます。

コンパクションにより、空き領域をつなげられ、オブジェクトを生成する場所をかんたんに見つけられます。

GCと同時にコンパクションを実行する ～コピーGC

断片化の対策としてコンパクションを解説しましたが、そもそもヒープが断片化しないGCアルゴリズムはあるのでしょうか？

その答えが「コピーGC」です。コピーGCでは、GCと同時にコンパクションと同じ処理を行っているため、ヒープが断片化することはありません。

マーク＆スイープGCでは、ヒープを1部屋として使用していました。一方、コピーGCでは、ヒープをFrom領域とTo領域の2つに分けて使用します。

アプリケーションが新たなオブジェクトを生成すると、“⁠必ず⁠”From領域に新たなオブジェクトを割り当てます。アプリケーションは“⁠絶対に⁠”To領域を使えません。

それでは、To領域はどのような場合に使われるのでしょうか？

答えは「コピーGCの実行中」です。

アプリケーションが実行されると、From領域の残り空き容量が少なくなっていきます。そうすると、JVMはコピーGCを行います。

コピーGCは、From領域にあるオブジェクトのうち、生きているオブジェクトを探します。生きてるオブジェクトが見つかると、そのオブジェクトをTo領域の端から順にコピーしていきます。

From領域をすべて探し終わると、すべての生きているオブジェクトはTo領域にコピーされ、From領域は空になります。しかし、アプリケーションはTo領域を使うことができないため、To領域にコピーされた生きているオブジェクトにアクセスすることができません。そのため、このままではアプリケーションが正常に動作することができなくなってしまいます。

この問題を解消するために、コピーGCでは、領域の名前を変更する動作が行われます。具体的には、これまでTo領域であった領域がFrom領域になり、これまでFrom領域だった領域がTo領域となります。アプリケーションは、これまでTo領域だった新しいFrom領域にアクセスすることで、コピーされた生きてるオブジェクトにアクセスすることも、オブジェクトを生成することもできるようになります。

コピーGCでは、GC時にTo領域の前から順に使用されていきます。これにより、前述したように、GCと同時にコンパクションと同じ処理を行われ、ヒープが断片化することはありません。そのようなメリットがある一方、コピーGCには弱点もあります。アプリケーションはFrom領域しか使用できないため、使用できる容量が半分となってしまうのです。

「一世代ヒープ」の問題を考える

これまでのように、すべてのオブジェクトをGC対象とすることを「一世代ヒープ」と言います。一世代ヒープでは、起動時に生成されたオブジェクトも、GC間際に生成されたオブジェクトも同じヒープに格納されています。

アプリケーションでは、多くのオブジェクトはわずかな時間だけ利用され、長時間利用されるオブジェクトはごく少数です。

一世代GCでは、ヒープサイズが大きくなるとヒープに格納されるオブジェクト数が増え、GCの時間が長くなり、アプリケーションの停止時間が長くなってしまいます。

「世代別ヒープ」でGCの時間を減らす

では、ヒープサイズを大きくしても停止時間をできるかぎり短くするには、どうしたらいいのでしょうか？

答えは、わずかな時間だけ利用されるオブジェクトと長時間利用されるオブジェクトを分けて管理・GCし、GC対象となるオブジェクトを限定すれば、GCの時間を減らすことです。

そのような考え方を取り入れたのが「世代別ヒープ」です。

世代別ヒープでは、オブジェクトがGCされた回数を年齢（age）と呼びます。また、若い領域をYoung領域、古い領域をOld領域と表現することもあります。

若い領域には、オブジェクトが生成されてから間もないオブジェクトが格納されます。古い領域には、オブジェクトが生成されてから、一定回数GCが行われたオブジェクトが格納されます。

アプリケーションがオブジェクトを生成すると、若い領域のヒープを割り当てます（※⁠）⁠。

若い領域がいっぱいになると、若い世代のGCが行われます。若い領域にある死んだオブジェクトはここで解放されますが、若い領域にある生きたオブジェクトがある一定回数のGCを経験すると、若い領域から古い領域へコピーされます。

若い領域のヒープがいっぱいになると、若い領域だけをGCすることで、対象となるヒープやオブジェクトが少なくなります。

こうすることで、一世代で管理する場合に比べてGC時間が短くなり、アプリケーションの停止時間も短くなるのです。

若い領域のGCで一時的に使用されるオブジェクトを解放することで、古い領域に移動するオブジェクトは少なくなり、古い領域のGCが行われる回数を削減することができます。

今回で、HotspotやJRockitなど、JVMの実装に問われないGCの基礎知識は終わりになります。次回は、Hotspot JVMではこれらの実装がどのようになっているかをご紹介します。

※）

ただし、JVMの実装によっては、大きすぎるサイズのオブジェクトが古い領域にいきなり割り当てられることもありますのでご注意ください。