【寄り道】Javascriptにおけるガベージコレクションとマークアンドスイープアルゴリズムについて

:::note warn
※初めに言っておきますが、厳密さはあまり追求してません
:::
# 概要（用語の確認など）
**ガベージコレクション（Garbage Collection）**

プログラムが仕様しなくなったメモリ領域を自動的に解放する仕組みである。これにより、私達開発者はメモリ管理を手動で行う必要がなくなり、メモリリークや不要なメモリ消費を防ぐ事が出来るよって話。また、ガベージコレクションをしてくれるプログラム処理群をガベージコレクタっていったりもする。

（Javascriptなどの高水準言語は自動でやってくれるが、C言語などの低レイヤ寄りの言語はfree()関数などでいちいち解放しないといけません・・・！~~組み込みシステム苦手な記憶が！！！ヤバい！！！頭痛が！！！~~）

**マークアンドスイープ（後ほど詳細記述）**
上記のガベージコレクションを行う際のアルゴリズム
参照カウントにおける循環参照問題を回避して、不要なオブジェクトを確実に廃棄できる。また、参照カウントを使わない分、ガベージコレクタが動作していない間はめっちゃ速いらしい。


---
### 仮想メモリ空間（ざっくりバージョン）
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3575047/a54c19ea-716e-31f3-b7a7-e44e70027b18.png)


**スタック領域**
いわゆるLIFO(Last in,First Out)
プログラムが自由に確保や解放を決める事が難しい。
関数の呼び出しやその一時的なデータを保存する領域。
入れ子構造と相性がいいよ。という話。
具体例
・関数を実行する際に渡される引数や戻り値はここに保存される。
・関数内のローカル変数もここに保存される。

**ヒープ領域**
動的に確保と解放を繰り返せるメモリ領域。（ツリー上のデータ構造もヒープと呼ぶが勘違いしないように）
ソフトウェアが確保や解放を自由に決める事が出来る。また、順序は存在しない。
具体例
・プログラムが動的に生成するデータ（配列やオブジェクトなど）
・先ほどのC言語でいうとmallocやfreeで関与する部分がここになる。

**データセグメント**
グローバル変数や静的変数を保存する領域。
具体例
・グローバル変数。
・javascriptあんまり関係ないけどオブジェクト志向ではお馴染みのstatic変数とかもここ。

**テキストセグメント（コード領域）**
プログラムコード自体を保存する領域。
具体例
・実際に動く命令(バイナリーコード)
・プログラム中にある関数や命令文などは全てここに格納される。

# マインアンドスイープの実装

## 手順
①マーク(Mark)
現在プログラムで生きているオブジェクトを見つける。これを**マーク**と呼ぶ。

・スタートポイントとしてグローバル変数や現在実行中の変数など、プログラムから参照されているオブジェクトを探す。
・これらのオブジェクトに**マーク**を付けそのオブジェクトが参照している他のオブジェクトも再帰的に探してマークを付けていく。
・これらを繰り返す事でプログラムがまだ使っている全てのオブジェクトがマークされる。

②スイープ(Sweep)
次に、マークされていないプログラムやオブジェクトをメモリから取り除く。
・メモリ全体をチェックしてマークされていないオブジェクトを発見。
・それらをSweeeeeeeeeeeeeeep!!!!!!!
```
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.marked = false; // マークフラグ
  }
}

class GarbageCollector {
  constructor() {
    this.objects = []; // 管理するオブジェクトのリスト
  }

  add(obj) {
    this.objects.push(obj);
  }

  mark(root) {
    if (root && !root.marked) {
      root.marked = true;
      if (root.next) {
        this.mark(root.next);
      }
    }
  }

  sweep() {
    this.objects = this.objects.filter((obj) => obj.marked);
    // マークをリセット
    this.objects.forEach((obj) => (obj.marked = false));
  }

  collect(root) {
    this.mark(root);
    this.sweep();
  }
}

// 使用例
let gc = new GarbageCollector();

let a = new Node("A");
let b = new Node("B");
let c = new Node("C");

a.next = b;
b.next = c;

gc.add(a);
gc.add(b);
gc.add(c);

console.log(
  "Before GC:",
  gc.objects.map((obj) => obj.value)
); // ['A', 'B', 'C']

// ルートからAとBしか参照しないようにする
a.next = b;
b.next = null;

gc.collect(a);

console.log(
  "After GC:",
  gc.objects.map((obj) => obj.value)
); // ['A', 'B']

```

### ここからわかること
・nodeクラス
簡単なオブジェクトを持つ。valueやnext（他のノード）を持ち参照もできる。

・GarbageCollectorクラス
objects配列で管理するオブジェクトを保持。
markメソッドで生きているオブジェクトにマークを付ける。
sweepメソッドでマークされていないオブジェクトを削除。
collectメソッドでマークフェーズとスイープフェーズを実行。

・使用例
オブジェクトA、B、Cを作成し、AがBを、BがCを参照する。
ガベージコレクターにこれらを追加する。
最初は全てのオブジェクトが存在している。
次に、BがCを参照しないようにして、Cが不要になるとガベージコレクションを実行する。
結果として、Cがメモリから削除される仕組み。



### 実際は・・・・？
原則ガベージコレクション自体は参照カウントよりも処理時間が掛かるため、通例的に工夫がされている。
・メモリが全体的に不足してきたなーって時
・システムが何も動いていない時
・プログラムから明示的な指令があった時（JavaのSystem.gc()メソッドや.NET FrameworkのSystem.GC.Collect()メソッドなど）

# 参考文献(いずれも参照日は2024年12月1日)
[ヒープ領域とは？スタック領域との違いや具体的な管理方法を解説！](https://it-trend.jp/development_tools/article/32-0041)

[ガベージコレクション-Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%AC%E3%83%99%E3%83%BC%E3%82%B8%E3%82%B3%E3%83%AC%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3)

[マーク・アンド・スイープ-Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%AF%E3%83%BB%E3%82%A2%E3%83%B3%E3%83%89%E3%83%BB%E3%82%B9%E3%82%A4%E3%83%BC%E3%83%97)

[マークスイープガベージコレクションを実装してみた#Ruby -Qiita](https://qiita.com/imaharu/items/71dc68d8b40094afef56)

[仮想記憶-Wikipedia](https://ja.wikipedia.org/wiki/%E4%BB%AE%E6%83%B3%E8%A8%98%E6%86%B6)
# 最後に
最後までお読みいただき、ありがとうございます！
もし何か間違いや不備がございましたら、ぜひご遠慮なくご指摘いただけますと幸いです。