JavaScriptのマークアンドスイープアルゴリズムとは？仕組みと動作原理をわかりやすく解説

マークアンドスイープ（Mark and Sweep）アルゴリズムとは

マークアンドスイープアルゴリズムは、JavaScriptにおける主要なガベージコレクション手法の一つです。このアルゴリズムの最大の特徴は、「不要になったオブジェクト」ではなく「到達不可能なオブジェクト」を探し出すという点にあります。従来の参照カウント方式のアルゴリズムを改良したものであり、循環参照などの問題にも対応できる点が大きな強みです。

アルゴリズムの3つの重要ステップ

マークアンドスイープアルゴリズムは、以下の3つの重要なステップで動作します。

• ルート（Root）の特定： 一般的にルートとは、コード内で使用されるグローバル変数を指します。JavaScriptでは、windowオブジェクトがルートとして機能します。このアルゴリズムは、グローバルオブジェクトであるルートを起点として、各オブジェクトが「到達可能かどうか」を判定します。
• ルートからの子孫オブジェクトの監視： アルゴリズムはすべてのルート、およびそこから参照される子オブジェクトを順に追跡します。この過程で、到達可能なオブジェクトには「マーク」が付けられ、条件に基づいて到達不可能なオブジェクトは「未マーク」として識別されます。
• 未マークオブジェクトの回収： 未マーク、つまり到達不可能と判断されたオブジェクトはガベージコレクションの対象となり、メモリが解放されます。

マークフェーズ（Mark Phase）

マークフェーズでは、どの要素がマークされ、どの要素が未マークになっているかを確認できます。例えば、オブジェクトobj1にプロパティhelloを割り当てた場合を見てみましょう。

例1

var obj1 = {
pro1: "hello" // ルートから到達可能なため、マークされる
}

この場合、アルゴリズムが使用するルート（グローバルオブジェクト）はobj1およびそのプロパティhelloに到達できます。そのため、これらはマークされます。

次に、このオブジェクトにnullを代入した場合を考えてみます。

例2

obj1 = null // nullはマークされる（到達可能）。helloは未マークになる（到達不可能）

新しく代入されたnullはマークされ、以前割り当てられていたプロパティhelloは未マークになります。つまり、マークフェーズの終了時点で、nullが代入されたオブジェクトはマーク済み、プロパティhelloを持っていたオブジェクトは未マーク（到達不可能）であると結論づけられます。

スイープフェーズ（Sweep Phase）

名前の通り、スイープフェーズでは到達不可能なオブジェクトを「掃き清め（sweep）」ます。マークフェーズでプロパティhelloを持つオブジェクトが未マークになり、到達不可能と判断されました。到達不可能なオブジェクトはガベージコレクションの対象となるため、このフェーズでメモリが解放されます。

なお、マークアンドスイープアルゴリズムは、プログラムから直接・間接的にアクセス可能なオブジェクト群全体を追跡することから、「トレーシングガベージコレクタ（tracing garbage collector）」とも呼ばれています。

循環参照はもはや問題ではない

マークアンドスイープの優れた点は、循環参照の問題を解決できることです。次の例を見てみましょう。

例

function f() {
   var obj1 = {};
   var obj2 = {};
   obj1.p = obj2; // obj1がobj2を参照
   obj2.p = obj1; // obj2がobj1を参照。ここで循環参照が発生する
}
f();

関数呼び出しが終了して戻ると、obj1とobj2は互いに参照し合っていますが、それらを参照する外部の到達可能なオブジェクトは存在しなくなります。そのため、両オブジェクトはガベージコレクションの対象となり、ガベージコレクタによってメモリが解放されます。参照カウント方式では循環参照によりメモリリークが発生する可能性がありましたが、マークアンドスイープではこの問題が解消されています。

制限事項

一方で、手動でメモリ解放のタイミングや対象を決められると便利な場面もあります。オブジェクトのメモリを解放するには、そのオブジェクトを明示的に到達不可能な状態にする必要があります。しかし現時点のJavaScriptでは、開発者が明示的にガベージコレクションをトリガーすることはできません。これはマークアンドスイープアルゴリズムにおける一つの制限事項と言えるでしょう。