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

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

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

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

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

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

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