-
C++ Advent Calendar 2019
- 前の日 12/16(月) : (Aborted)
- 次の日 12/18(水) : メッシュクラスを自作した (@shohirose さん)
TL;DR
-
saberGC -- https://github.com/43x2/saberGC
- Naïve な マーク・アンド・スイープ による ガベージコレクション (GC) を実装しました。
- ポインタと非ポインタを区別する、いわゆる 正確な (exact/precise) GC です。
- アロケータとデアロケータのカスタマイズが可能です。
- オブジェクトは
shared_ptrやunique_ptrライクなインターフェースを持ちます。 - 静的記憶域を使わず、必要に応じて複数の GC インスタンスを使い分けることが可能です。
- ご意見やご感想をお待ちしております！
はじめに
会社の業務では何かと shared_ptr の出番が多いのですが、このクラスは 循環参照 を形成しないよう十分注意して利用する必要があります。
近いクラス間ならこの問題を回避することも容易ですが、実装が複雑化するにつれ、思いも寄らないところで循環してしまうことがあります。
こういうとき、GC があれば余計なこと気にしなくていいのになぁ･･･
･･･という動機から、今年のお盆休みに試作をしました。saberGC はそれをブラッシュアップしたものです。
ただし、あわよくば業務にも、ということは考えておらず、もっぱら趣味で作りました。
目標
- 可能な限り、C++ 標準ライブラリと似たようなインターフェースにしたい。
-
make_shared関数のように直接構築できるとか、スマートポインタ類 (shared_ptr/unique_ptr) と同様にアクセスできるとか。
-
- ガベージコレクションを 明示的に トリガーしたい。
- アプリケーションに隙間時間ができた際に一気にゴミをかき集めたい。
- メモリ確保・解放をカスタマイズしたい。
- カテゴリ別など、複数の GC インスタンスを生成・管理したい。
- 内部実装は後から
こっそり改善できるよう、ヘッダから隠したい。
設計
以上の目標を踏まえて、ユーザに露出しているクラスは以下のように定義しました (抜粋)。
class GC
{
public:
template <class T> class Object; // オブジェクトクラスの前方宣言
using allocator_type = std::function<void*(const std::size_t, const std::size_t)>;
using deallocator_type = std::function<void(void*)>;
GC();
GC(allocator_type allocator, deallocator_type deallocator);
GC(const GC&) = delete; // コピー構築不可
GC(GC&&);
~GC();
GC& operator=(const GC&) = delete; // コピー代入不可
GC& operator=(GC&&);
// 新しいオブジェクトを構築する
template <class T, class... Args> Object<T> new_object(Args&&... args);
// 利用されていないオブジェクトを明示的に破棄する
void collect();
};
template <class T>
class GC::Object
{
public:
Object();
Object(const Object&);
~Object();
Object& operator=(const Object& rhs);
T* get() const;
T& operator*() const;
T* operator->() const;
};
特別なことはなく、素直な定義だと思います。
この設計に基づき、必要なものを肉付けしていきました。
実装
ヘッダに書くものと書かないもの
テンプレートパラメータをとるクラス、関数等は、インスタンス化されるものが既知でない場合は定義をソースファイルに逃がすことができません。1
特に GC::Object<T> はテンプレートクラスですので、メンバ関数はすべてヘッダに定義する必要があります。
しかし GC::Object<T> クラスは生存管理のために内部で GC のシステムと密に連携する必要があり、その実装がヘッダに出てきてしまうのは避けたいところです。
そこで、GC::Object<T> の基底クラスとして GC::BaseObject クラスを定義し、GC 関連処理をそちらに移すことでヘッダから実装を隠すことができました。2
class GC::BaseObject
{
private:
BaseObject(); // GC システムとの連携処理をここに書く (具体的な実装はソースファイルに書ける)
...
};
template <class T>
class GC::Object : private GC::BaseObject
{
public:
Object(); // 内部で BaseObject のコンストラクタが呼び出される
...
};
正確な GC の実現
正確な GC は、ざっくり以下の 2 点によって実現しています。
- 新しくメモリを確保した際に、その領域のアドレスとサイズを記憶しておく。
-
GC::BaseObjectが作られるたびに、上記のどの領域に属するか調べる。3- 属する領域があれば、
GC::BaseObjectはその領域の 子オブジェクト である。 - 属する領域がなければ、
GC::BaseObjectは ルート集合 の 1 要素である。
- 属する領域があれば、
アドレスとサイズの記憶には std::map を利用していますが、このとき比較子に std::greater を使っているのがミソです。
デフォルトの std::less のままだと、領域の範囲チェックで lower_bound 関数を使ったときに正しく動作しません。
確保されているメモリ領域、ルート集合、子オブジェクトが分かれば、マーク・アンド・スイープ GC は簡単に実装できます。
実際、GC::Impl クラスの collect 関数は非常にシンプルな実装です。ぜひ中も追いかけてみてください。
アルゴリズムを変えたい？
今回実装した GC のアルゴリズムはかなり 素直な 実装であり、正直 “古くさい” と感じる方もいるかもしれません。
ただ、目標にも示したように、後からこっそり実装を変えることができる仕様にしてありますので、興味がある方はお好みのアルゴリズムに変えるのもよいと思います。
その場合、GC::Impl クラスの collect 関数と XXX_object 関数の実装を変更することになります。
また、コピー GC 等を採用する場合は、GC::Object<T> クラスの get 関数で得られるポインタを外部に保持されないようにする工夫 (運用？) が必要です。
現時点の問題点と課題
-
GC::Object<T>自体をnewやmake_shared等で構築すると、必ずルート集合に分類されてしまう。- 正確な GC を行うアルゴリズム上回避できない。
- ルート集合要素になった結果、意図せず寿命が延長されることはあるが、GC は問題なく動作するので、特に対策は考えない。
-
GC::Object<T>よりも前にGCの寿命がくるとプログラムが停止する。- 生存オブジェクトがあるため、
GC::Implクラスのデストラクタのアサーションに引っかかる。 - 現在対応中。
- 生存オブジェクトがあるため、
-
GC::Object<T>がムーブセマンティクスに対応していない。- ムーブ発生時点で元のオブジェクトを破棄しておくことで GC 負荷が若干改善する。
- 対応予定。
- 配列型に対応していない。
-
make_shared等のようにサイズを受け取って構築するインターフェースを設ける。 - 対応予定。
-
- 例外安全への対応が不十分である。
- 例外発生場所によっては内部状態が壊れる可能性がある。
- 対応予定。
- パフォーマンス計測・高速化
- 現状は作ってみただけで、実用に耐えうるかどうかは未知数。要検証。
- 遅い場合は内部で利用しているコンテナを軽量なものにすれば速くなる･･･かも。
奥付
記事には自分なりにしっかりと目を通してはいますが、誤字脱字、表現の誤りなどがありましたら、コメント欄にてご指摘くださると幸いです。
- 初稿 「C++ で GC を実装してみた」
- 2019/12/17
- 第 2 稿 (タイトル変わらず)
- 2019/12/19
- アドベントカレンダー 18 日目へのリンクを追加しました。