やっぱりガベージコレクタについて考える

アロケータの自作

やはりmallocやnewをしたあとfreeするのは時間がかかるようなので、もしも数多くのfreeが必要なデータを扱う場合はなるべくfreeしないで再利用する方がいいようです。

そうなるとメモリープールの実装が必要となります。この際アライメント等を意識して高速化する必要があります。メモリへのアクセスはCPUの演算速度に比べて極端に遅いからです。

このような管理をしていく内に断片化が発生するはずです。空きメモリを連結したり、移動したりしてでフラグをする必要があります。この際、使っていないオブジェクトを削除するようにすればガベージコレクタのできあがりです。というわけで前回のえせガベージコレクタを改め、自由な型をメモリプールから切り出して、使用しなくなったら再利用するようなガベージコレクタを作ろうと思います。

特徴は以下の通り :

1. メモリプールから任意の型のデータを切り出せる
2. 切り出したデータは(a)親オブジェクトと(b)子オブジェクトに分別される。
親オブジェクトとは、そのデータがスコープを抜けたとき破棄されるオブジェクトである。
子オブジェクトとは、親オブジェクトがあってそのオブジェクトが削除されると付随して削除されるオブジェクトである。スコープを抜けても削除される。
3. 適当なタイミングで(あるいは自主的に)全ての親オブジェクトから辿って、辿れない子オブジェクトを削除する。
4. 適当なタイミングでデフラグする。

テストケース

スコープを抜けたら即時解放

struct C {
	C(int x) { }
};

{
	Item<int> item = mm.make<int>(); // 親
	Item<C> item2 = mm.make<C>(10); // 親
} // ここで解放

関数には参照で渡す。

void func(Item<int>& item) {
	// 関与しない
}

{
	Item<int> item = mm.make<int>(); // 親
	func(std::move(item)); // 参照で渡す
} // ここで解放

コピーとムーブ

このままではunique_ptrと同じである。shared_ptrのようにコピーやムーブが可能である。この実装には参照カウント方式を用いるしかない;

{
	Item<int> item2; // デフォルト
	
	{
		Item<int> item = mm.make<int>(10);
		item2 = item; // コピーが可能
	} // itemは解放されない
} // ここでitem(item2)が解放される

ムーブするとそれ以降そのオブジェクトは使用不可能な状態となる。

{
	Item<int> item2; // デフォルト
	
	{
		Item<int> item = mm.make<int>(10);
		item2 = item; // コピーが可能
	} // itemは解放されない
} // ここでitem(item2)が解放される

{
	Item<int> item2; // デフォルト
	
	{
		Item<int> item = mm.make<int>(10);
		// ムーブすることでitemはもう参照されないから解放される
		item2 = move(item);
	} // itemは既に解放(候補に)されている
} // ここでitem(item2)が解放される

子の追加

コンストラクタとしてItem& parentを呼び出すmake_parentメンバ関数を用いてクラス内で用いる子要素を追加していく。親がいなくなったら子も道連れになるべきである。これは参照カウントとは別で、マーク&スイープ方式によって管理される。

理想的な動作は次の通り。正確にはスコープを抜けると親のItemがなくなり子が参照されなくなるためMarkされずsweep時に解放されることになる。

struct C {
	C(Item<C>& parent) : chiled(mm.make<C>()) {
		parent.addChild(child);
	}
	Item<C> child; // 子
}

{
	Item<C> parent = mm.make_parent<C>(); // 親
} // 親も子も解放される

ところで外部から子が参照されている場合は子を削除してはいけない。これは、子が親の子として定義されたときに参照カウントを1減らすことによって実装できそうである。

struct C {
	C(Item<C>& parent) : chiled(mm.make<C>()) {
		parent.addChild(child);
	}
	Item<C> child; // 子
}

Item<C> child;
{
	Item<C> parent = mm.make_parent<C>(); // 親
	// ここで子が参照できる
	child = parent->child;
} // 親だけ解放される

誰かの親の子として登録されればその親の寿命にあわされるだけである。というのも、その後マークされる可能性があるためである。

struct C {
	C(Item<C>& parent) : chiled(mm.make<C>()) {
		parent.addChild(child);
	}
	Item<C> child; // 子
}

struct AC {
	AC(Item<AC>& parent, Item<C>& child) : chiled(child) {
		parent.addChild(child);
	}
	Item<C> child; // 上の子と同じ子
}

Item<AC> another_parent;
{
	Item<C> parent = mm.make_parent<C>(); // 親
	another_parent = mm.make_parent<AC>(parent->child); // 別の親
} // 親は解放されるが、別の親は解放されない
// 子は別の親とともに残る

親の子は別の親の子でもあるため、別の親の子としてマークされsweep時に生き残る。このようにスコープを抜けたからといって即解放されるわけではない。

要素の参照等

ポインタのように振る舞いたいのでoperator*()やoperator->()を定義する。

Item<int> item;
*item = 10; // データの代入
Item<C> item2;
item2->data = 100; // データの代入

要素の明示的マーク/解放

次のsweep時に削除されないように明示的にマーク/解放できる。基本的にはしなくて良い。

Item<int> item;
item.mark();
item.free();

要素の連続領域確保

配列として確保できる。

Item<int[4]> item;
item[0] = 0; // データの代入

きままにブログ

プログラミングを主とした私のメモ帳です。寂しいのでコメントください笑