【お掃除】ガーベジコレクションの実装方式を学ぶ【C# / Python】

ガーベジコレクション (GC) とは

ガーベジが占有するメモリを再利用可能にする処理のこと。実行環境と同時に起動される。

ガーベジ = ヒープ上に確保されたものの、どのポインタからも辿れないレコード。

要は、机の上（メモリ）を勝手に掃除してくれるありがたいやつ。

ちなみに、基本情報技術者試験での出題例もあったりする。

ネットでは「ガベージ」「ガーベジ」の表記ゆれが見られますが、英語の綴りは "Garbage" なので、「ガーベジ」の方が正しいんじゃないですかね？
IPAもそう言ってるし。

この記事で書くこと・書かないこと

C# と Python のガーベジコレクションの実装方式を学びます。
Javaは未履修なので書きません。他の人が書いてるのでそっち見てね。

雰囲気だけさらっと把握したい場合は、note として書いた部分（緑色の背景）を中心に読めば、苦しまずに済むかもしれません。

C# (.NET)

GCの方式

原文はMicrosoftの解説ページへ

.NETのガーベジコレクションでは、世代別GCが採用されており、また、実際のゴミ回収時には、Mark-Compact方式を用いています。

世代別GC (Generational Collection)

この節の引用元はこちら

C#の世代別GCでは、メモリ上の「管理ヒープ」を第0世代・第1世代・第2世代という3つの領域に分けて、オブジェクトの寿命に応じて効率よく管理しています。

思想

It's faster to compact the memory for a portion of the managed heap than for the entire managed heap.

「マネージヒープ全体をコンパクト化するより、一部だけをコンパクト化する方が高速」

コンパクト化とは、不要なオブジェクトを削除した後に残った生存オブジェクトをメモリの先頭に詰め直す処理です。

家全体を片付けするより、一部屋だけ片付けする方が早く終わるねってことです。

---

Newer objects have shorter lifetimes, and older objects have longer lifetimes.

「新しいオブジェクトは寿命が短く、古いオブジェクトは寿命が長い傾向にある」

一時的な変数などは、短い期間だけ使われてすぐ捨てられる傾向にあります。例えばこういった変数がすぐに捨てられます。

// バブルソートの一部
int temp = array[j]; // ここで作られる temp は短命（すぐ使われて捨てられる）
array[j] = array[j + 1];
array[j + 1] = temp;

昨日の夜に飲んだコーヒーのコップはわりかしすぐに片付けますが、ずっと押し入れに入っている家族アルバムはなかなか捨てませんよね。そういうイメージです。

---

Newer objects tend to be related to each other and accessed by the application around the same time.

「新しいオブジェクトは互いに関連している傾向があり、アプリケーションから同時期にアクセスされることが多い。」

例えば、こんなクラスたちがあったとしましょう。
Order を new すると同時に List と OrderItem がまとめて new されます。
そして、アプリは、この注文（Order）を処理する間、これらすべてを一緒に使います。

public class Order
{
    public string CustomerName;
    public List<OrderItem> Items;

    public Order(string name)
    {
        CustomerName = name;
        Items = new List<OrderItem>();  // ← 関連するオブジェクトを生成
        Items.Add(new OrderItem("Pen", 2));
        Items.Add(new OrderItem("Pineapple", 1));
        Items.Add(new OrderItem("Apple", 1));
    }
}

public class OrderItem
{
    public string Name;
    public int Quantity;

    public OrderItem(string name, int qty)
    {
        Name = name;
        Quantity = qty;
    }
}

料理をしようとして、以下のものを台所に出したとします。

• まな板
• 包丁
• ピーラー
• 野菜

これらは全部、同じタイミングで出され、同じタイミングで使われ、使い終わったらまとめて洗われて片付けられることになります。
「新しく同時に台所に出されたものは互いに関連している傾向があり、同時期に使用されることが多い」ということです。

世代別GCの方式

the managed heap is divided into three generations, 0, 1, and 2, so it can handle long-lived and short-lived objects separately. The garbage collector stores new objects in generation 0. Objects created early in the application's lifetime that survive collections are promoted and stored in generations 1 and 2. Because it's faster to compact a portion of the managed heap than the entire heap, this scheme allows the garbage collector to release the memory in a specific generation rather than release the memory for the entire managed heap each time it performs a collection.

真面目な和訳

管理ヒープは0、1、2の3つの世代に分けられ、長寿命オブジェクトと短寿命オブジェクトを別々に扱うことができます。
ガーベジ・コレクタは新しいオブジェクトを第0世代に格納し、アプリケーションのライフタイムの初期に作成され、コレクションを生き残ったオブジェクトは昇格し、第1世代と第2世代に格納されます。
ヒープ全体よりも管理ヒープの一部をコンパクトにする方が速いため、この方式では、ガーベジコレクタがコレクションを実行するたびに管理ヒープ全体のメモリを解放するのではなく、特定の世代のメモリを解放することができます。

超かみ砕くと...

部屋をテーブル（第0世代）と、棚（第1世代）と、押し入れ（第2世代）に分けるよ。新しいものを買ってきたら、一旦はテーブルに置くけど、テーブルに置いたもののうち、捨てなかったものは棚、そして最終的には押し入れへと収納していくよ。

家全体を掃除するより、一部だけを掃除する方が速いから、普段は必要なところだけを掃除するね。

テーブルは頻繁に掃除しなきゃだけど、押し入れは年末の大掃除だけでいいかな～。

ヒープ領域を以下のように分割します。

世代	名前	内容
Gen 0	第0世代	新しく生成されたオブジェクトが置かれる領域。 もっとも頻繁にGCが走る。
Gen 1	第1世代	Gen 0のGCで生き残ったオブジェクトが昇格されて置かれる。 中間の寿命帯。
Gen 2	第2世代	長寿命オブジェクトが属する領域。最もGC頻度が低い。
Gen 3	LOH	巨大なオブジェクト（C#の場合は85KB以上）が置かれる領域。 GCはGen2と一緒に行われる。 LOH は Large Object Heap の略称。

オブジェクトを生成した際のフロー図はこのようになります。

フロー図説明

アプリケーションが新しいオブジェクトを生成すると、そのオブジェクトは「世代 0」と呼ばれる最も若い領域に配置されます。新しいオブジェクトの配置には空き領域が必要ですが、もし世代 0 に十分な空きがなければ、まず世代 0 に対して GC が実行されます。

世代 0 の GC を行っても空きが不足している場合は、次の段階として世代 1 までの GC が実行されます。

それでもなおメモリが不足している場合には、最終段階として世代 2 の GC、すなわちフル GC が行われます。このGCでは、世代0・1・2すべてのオブジェクトが対象となり、最大限の不要メモリ回収を試みます。

GC 実行時の動作 (Mark-Compact)

前節では、GC を実行するタイミングや領域について解説しました。ここでは、GC 実行の時の動作について解説していきます。大きく分けると次の３つのフェーズがあります。

この節の引用元はこちら

段階	呼称	説明
1	Mark Phase	生存している（ = 参照されている）オブジェクトを検出し、 それらをリストアップする。
2	Relocate Phase	コンパクション（メモリ圧縮）の準備として、 移動対象のオブジェクトの参照を書き換える
3	Compact Phase	死んだオブジェクトが占めていた領域を回収し、 生きているオブジェクトを詰めて、断片化を防ぐ。

押し入れの掃除をしよう！
押し入れの中のもののうち、残したいものには「必要」のラベルを貼っていくよ。「必要」のラベルを付けなかったものは捨てて、「必要」のラベルを付けたものは、押し入れの奥にギュッと詰め直しちゃおう。
これで、入口付近にまとまった空きスペースができて、新しく入ってくる荷物をスムーズに収納できるようになるね！

Mark Phase

Microsoftの解説ページには、詳細な動作は記載されていないので、ここでは、一般的な GC の動作を説明します。動作の詳細は下記の参考文献を当たってください。
参考文献：Andrew W. Appel 著, 神林 靖・滝本 宗宏 訳『最新コンパイラ構成技法』翔泳社(2009), pp.247–252.

プログラム変数（root）からたどれるヒープ領域上のデータに「必要」のラベルを貼っていきます。

C#みたく書くならこうでしょうか。（関数名は私の方で勝手に付けたので、実際のものとは異なります。）
結局のところは、root から深さ優先でたどっていき、到達できたオブジェクトにマークを付けているだけに過ぎません。

MarkPhase

void DFS(object? x) // 深さ優先探索
{
    // マネージドヒープ上の参照型かどうか
    if (!IsOnManagedHeap(x))
        return;

    // すでにマーク済みなら何もしない（再訪問防止）
    if (IsMarked(x))
        return;

    Mark(x); // オブジェクトに「生きている」ラベルを付ける

    // xのフィールドを再帰的に探索していく
    foreach (var field in GetReferenceFields(x))
    {
        object? referenced = field.GetValue(x);
        DFS(referenced);
    }
}

// GCの開始点：すべてのrootから始める
void MarkPhase()
{
    foreach (var root in EnumerateRoots())
    {
        DFS(root);
    }
}

ここで生じる疑問――
「.NETにおいてマークはどこに付与されているのか？」

.NET ランタイム（CoreCLR）の内部実装では、オブジェクトヘッダー内にマークビットが定義されています。具体的には、CoreCLR の object.hファイル内に、以下の定義が存在しています。

object.h

#define MARKED_BIT 0x1

言い換えれば、マークはオブジェクト自身の中に埋め込まれているということです。

---

Relocate Phase (Plan Phase)

ここでは、生き残るオブジェクトをメモリ上で移動させる準備をしていきます。
推測ではありますが、この部分が該当すると思われます。

お引越しの準備みたいなものです。
次の家の住所（移転先）を決めたら、電力会社や水道局にもあらかじめその移転先を伝えておきましょう。
先に伝えておかないと、電気も水道も使えませんからね。

この部分においてもMicrosoftの解説ページには、詳細な動作は記載されていないので、一般的な GC における Forwarding Pointer の説明をします。動作の詳細は下記の参考文献を当たってください。
参考文献：Andrew W. Appel 著, 神林 靖・滝本 宗宏 訳『最新コンパイラ構成技法』翔泳社(2009), pp.253–258.

GC で生き残ったオブジェクトは、次の世代の領域や、ヒープ内のより若い位置に移動されます。そのため、オブジェクトのアドレスは変わります。

このとき、そのオブジェクトを参照している他のオブジェクトやスタック上の変数が古いアドレスを指したままだと、移動後のオブジェクトにたどり着くことができず、参照が壊れてしまいます。

そこで、「このオブジェクトはここに移りますよ」という情報を、元のアドレスにフォワーディングポインタとして記録しておきます。これにより、他の参照を新しいアドレスに更新することが可能になります。

これをマークされた各オブジェクトで行います。

---

Compact Phase

Relocate Phase で決めた移動先に、オブジェクトを実際にコピーして、メモリを連続化していきます。
これにより、フラグメンテーション（断片化）を防ぐことができます。
使用されなくなったオブジェクトに占有されていた領域はここで解放されます。

要は、実際に押し入れの奥にギュッと詰め直す作業です。

---

実際に動作を確認してみる

GC Class

実際にコードを書いていく前に、ガーベジコレクションを扱う System.GC クラスのメソッドについて記載しておきます。

Methods

Collect()

すべての世代のGCを直ちに強制実行します。

Collect(Int32)

世代 0 から指定世代までのGCを直ちに強制実行します。

CollectionCount(int generation)

指定した世代において、GC が何回実行されたかを返します。

GetGeneration(Object)

指定したオブジェクトの現在の世代番号を返します。

GetTotalMemory(Boolean)

断片化している領域を除いてヒープサイズを取得します。
GC の発生を待つ場合は引数として true を渡してください。

WaitForPendingFinalizers()

回収されるオブジェクトのファイナライザがすべて完了まで待機します。

---

オブジェクトを生成して、そのオブジェクトが世代０から世代２へと進んでいく動作を確認するコードを書いてみます。

コードと出力結果

GCGenerationFlow

using System;

class GCGenerationFlow
{
    const int Length = 3;

    static void WriteGen(List<object> objects)
    {
        for (int i = 0; i < Length; i++)
        {
            Console.WriteLine($"Object {i} - Gen: {GC.GetGeneration(objects[i])}");
        }
    }

    static void Main()
    {
        Console.WriteLine("=== GC Generation Test ===\n");

        List<object> objects = [];

        // オブジェクトを生成する
        for (int i = 0; i < Length; i++)
        {
            var obj = new object();
            objects.Add(obj);
        }
        
        // 生成したオブジェクトは世代 0 に置かれる
        WriteGen(objects);

        // 世代 0 の GC を実行する
        Console.WriteLine("\nCalling GC.Collect(0)...\n");
        GC.Collect(0);

        // 世代 0 の GC を実行したので、オブジェクトは世代 1 に移る
        WriteGen(objects);

        // もう一度世代 0 の GC を実行する
        Console.WriteLine("\nCalling GC.Collect(0) again...\n");
        GC.Collect(0);

        // 世代 0 の GC を実行しただけなので、オブジェクトは世代 1 のまま
        WriteGen(objects);

        // 世代 1 の GC を実行する
        Console.WriteLine("\nCalling GC.Collect(1)...\n");
        GC.Collect(1);

        // 世代 1 の GC を実行したので、オブジェクトは世代 2 に移る
        WriteGen(objects);

        // 全世代の GC を実行する
        Console.WriteLine("\nCalling GC.Collect(2)...\n");
        GC.Collect();

        // GC で生き残った世代 2 のオブジェクトは世代 2 のまま
        WriteGen(objects);
    }
}

Output

=== GC Generation Test ===

Object 0 - Gen: 0
Object 1 - Gen: 0
Object 2 - Gen: 0

Calling GC.Collect(0)...

Object 0 - Gen: 1
Object 1 - Gen: 1
Object 2 - Gen: 1

Calling GC.Collect(0) again...

Object 0 - Gen: 1
Object 1 - Gen: 1
Object 2 - Gen: 1

Calling GC.Collect(1)...

Object 0 - Gen: 2
Object 1 - Gen: 2
Object 2 - Gen: 2

Calling GC.Collect(2)...

Object 0 - Gen: 2
Object 1 - Gen: 2
Object 2 - Gen: 2

Python

GCの方式

原文はPythonのドキュメントへ

循環ガベージコレクタはPythonの参照カウントを補うためのもの

という一文にあるように、Python では、参照カウント方式 をメインとしており、この参照カウント方式の弱点を補うために、世代別GCも使用されています。
世代別GCについては、上記（C# の部分）で説明しているため、そちらを参照してください。

参照カウント方式 (Reference Counts)

Pythonのドキュメントには、詳細な動作は記載されていないので、ここでは、 GC の一般的な動作を説明します。動作の詳細は下記の参考文献を当たってください。
参考文献：Andrew W. Appel 著, 神林 靖・滝本 宗宏 訳『最新コンパイラ構成技法』翔泳社(2009), pp.252–253.

参照カウント方式では、各レコードが何個の参照を受けているかを数えておきます（参照カウント）。この参照カウントが０になったら、どこからも参照を受けていないことになり、すなわちゴミと判断できます。

オブジェクトごとに参照カウントを1つ持てばよく、処理も単純です。
オブジェクトの参照カウントが0になった瞬間にメモリが解放されるので、全ヒープの走査も不要です。

Instagramのフォロー機能を思い浮かべるとよいかもしれません。
ただし、普通のInstagramと違うところは、「自分のことをフォローしている人がいないアカウントはゴミとして削除される」ということですね。

---

参照カウントの問題点

計算コストが高い

上の図において、プログラマーが行いたいことは、

x.f_i ← q

のみです。しかし、実際には、カウントを正確に増減させる都合上、

\displaylines{
z ← x.f_i \\
c ← z.count \\
c ← c-1 \\
z.count ← c \\
\mathrm{if} \quad c = 0 : \quad \mathrm{call \quad putOnFreelist} \\
x.f_i ← q \\
c ← q.count \\
c ← c+1 \\
q.count ← c \\
}

と、かなりの手数を踏まないといけません。

---

循環参照を回収できない

複数のオブジェクトが、互いを参照している場合（循環参照, cyclic reference）、外から使われていないのにも関わらず、参照カウントが0にならないため回収できません。
よって、参照カウントだけでは「誰も使ってない」と判断できず、メモリに残り続けてしまいます。

なので、Python では、参照カウント方式だけを用いるのではなく、補助的に世代別GC（Pythonのドキュメントでは循環ガーベジコレクタと呼称されている）を使用しているというわけです。

---

弱参照 (weak reference)

弱参照とは、参照カウントを増やすことなく、オブジェクトを参照する方法です。

たとえば、キャッシュに使われたりします。

weakref_cache

import weakref

class Item:
    def __init__(self, name):
        self.name = name
    def __del__(self):
        print(f"{self.name} destroyed")

cache = weakref.WeakValueDictionary()

# 複数の一時的なオブジェクトをキャッシュに入れる
# WeakValueDictionaryなので、キャッシュ値が使用されなくなった場合には自動的に破棄される
for name in ["a", "b", "c"]:

    obj = Item(name) # name == "c" のときは、ここで b の参照がなくなり、b が破棄される
    
    cache[name] = obj
    
    if name == "a":
        hold_a = obj  # "a" だけ強参照を残す
        
    print(f"Cache : {list(cache.keys())}")
   
del obj # c の参照がなくなり、c が破棄される

print(f"Cache before deleting hold_a : {list(cache.keys())}")

del hold_a # 唯一の強参照だった hold_a をここで del する
   
print(f"Final Cache : {list(cache.keys())}")
 

output

Cache : ['a']
Cache : ['a', 'b']
b destroyed
Cache : ['a', 'c']
c destroyed
Cache before deleting hold_a : ['a']
a destroyed
Final Cache : []

また、GUIの親子関係などで、親が子を、子が親を参照する状況では、子→親の参照を弱参照にすることで、循環参照を避けることができます。

なお、参照元オブジェクトが削除されると、弱参照はNoneを返すようになります。

実際に動作を確認してみる

sys.getrefcount を用いて、参照カウントを確認してみます。

sys.getrefcountには次のような記載があります。

The count returned is generally one higher than you might expect, because it includes the (temporary) reference as an argument to getrefcount().

この関数に渡された引数自体が一時的な参照となるため、返されるカウントは、1 大きくなります。

reference_count

import sys
import weakref

class Tracker:
    def __init__(self, name):
        self.name = name
        print(f"[Init] Create {self.name}")

    def __del__(self):
        print(f"[Del] Delete {self.name}")

print("\n=== Start ===")

# オブジェクト生成
obj = Tracker("A")
print(f"[Info] id(obj) = {id(obj)}")

# ここでの refcountは 2 になる
# ユーザーが保持している変数（obj）と getrefcount() の引数（一時的な参照）
print(f"[Info] refcount = {sys.getrefcount(obj)}")

# 弱参照を作って、解放されたか確認できるようにする
wref = weakref.ref(obj)

print(f"[Info] weakref is alive? {wref() is not None}")

print("--- delete strong refs ---")
del obj

print(f"[Info] weakref is alive? {wref() is not None}")

print("=== End ===\n")

output

=== Start ===
[Init] Create A
[Info] id(obj) = 2193393433760
[Info] refcount = 2
[Info] weakref is alive? True
--- delete strong refs ---
[Del] Delete A
[Info] weakref is alive? False
=== End ===

del objによって、objへの参照がなくなり、解放されていることが見て取れますね。

---

意図的に循環参照を発生させる

cycle

import gc
import sys

class Node:
    def __init__(self):
        self.ref = self  # 自分自身を参照

# GCを無効化
gc.disable()

# 循環参照するオブジェクトを100000個生成
nodes = [Node() for _ in range(100000)]

print("Before deletion:", sys.getallocatedblocks())

# 一部のノードの参照カウントを表示（先頭3つだけ）
import sys
for i in range(3):
    print(f"refcount of nodes[{i}] = {sys.getrefcount(nodes[i]) - 1}")

# 参照を削除
del nodes

print("After deletion:", sys.getallocatedblocks())

# 再度GC有効化して明示的に回収
gc.enable()
gc.collect()

print("After gc.collect():", sys.getallocatedblocks())

output

Before deletion: 317308
refcount of nodes[0] = 2
refcount of nodes[1] = 2
refcount of nodes[2] = 2
After deletion: 317308
After gc.collect(): 17223

自分自身を参照しているため、del nodesをしても、参照カウントが０にならず、

After deletion: 317308

と、メモリ内に残り続けています。それを gc.collect() で世代別GCを実行してあげることで、しっかり解放されていることが分かります。

未調査事項（いずれ更新するかもしれない事項）

なぜ、Pythonでは、2つのガベージコレクション方式を併用しているのか？世代別GCのみで良いのでは？

まとめ

元気が出たら書く

最後に

現実の部屋でも自動的にゴミ回収してほしい。