動的メモリ確保なしで派生クラスを格納できるクラスを作った

久方ぶりにdomain-specificでないコードを書いた気がする。

Qiitaに基本的なアイデアだけ書いたので、こちらでは少し立ち入った話をする。

tl;dr

先に最大サイズを決めておくことで、そのサイズ以下のオブジェクトを格納できるクラスを作った。 格納できるクラスはあるBaseクラスから派生している必要がある。

github.com

背景

Boost.PolyCollectionが解決しようとした問題と同様のものに出くわしているとする。 これは、派生クラスを基底クラスへのポインタとして格納していったとき、毎回newするので、重い操作である 動的メモリ確保を何度も何度もするようになる上、派生クラスのオブジェクトの実体がメモリ上に散らばってしまうことで キャッシュヒット率が低下し、またアクセスの度にポインタを経由するオーバーヘッドが入り、 かつ10秒以内に全ての処理が終わってくれないと怒り狂ったユーザーによってあなたの生命が奪われかねないという状況だ。

以前見た通り、Boost.PolyCollectionは型情報から派生クラスへのマップを持って、派生クラスはそれぞれに特有の std::vectorのようなメモリ上に連続して配置されるコンテナに格納しておき、不思議な力でそのコンテナ全てを なめ尽くせるようなイテレータを作成することで解決している。実際、彼らのベンチマーク結果からは2倍前後の高速化が見て取れる。

だが、Boost.PolyCollectionはその性質上イテレーションの順序を変えてしまう。また、「派生クラスのコンテナ」という形で 提供されており、派生クラスを一つずつ別々に別のクラスに格納し、それを格納したい場合などには適用できない。もちろん設計を 変えれば可能だが、そのために意味と少しずれそうな設計にするのはよろしくないだろう。

別の解決策として真っ先に思いつくのはvariantだ。これは格納する可能性のある全ての型を先に与えておき、 その中で最も大きな型を格納できるだけのメモリを確保する。このサイズは静的に決まるので、variantのサイズも静的に決まる。 後は、来たものを内部ストレージに格納し、必要に応じて関数をディスパッチしたりキャストしたり持っている型を教えてやれば良い。

しかし、例えば格納するべきクラスは全て何らかの基底クラスから派生していて、しかも大量にあるとしたらどうだろう。 それを全てvariantのテンプレート引数に書くよりは、素直にBaseポインタによって解決したいと思わないだろうか。 だが、基底クラスへのポインタを使う場合先に述べたオーバーヘッドが付き纏う。

ところで、話は変わるがstatic_anyというクラスを作った人がいる。

github.com

anyは動的型のクラスで、代入された型を格納できるだけのサイズのメモリ領域を毎回動的に確保し、型情報を管理し、 動的型付け言語の持つ利便性と同等のものを提供する。しかし、これも基底クラスポインタによる解決と同様のオーバーヘッドを、 全く同じ理由から持つことになる。

このstatic_anyクラスは、入れられるオブジェクトの最大サイズを先に決めておき、「何でも」代入できるという利便性を 「最大サイズを超えない限り何でも」に変更することで、このオーバーヘッドを取り除いたものだ。若干の柔軟性を犠牲に、 かなりの高速化を達成している。やはりメモリアロケーションは遅い。

ここでこのクラスのことを思い出したのだ。これはvariantに比べると殆ど何でも入れられる上に、anyに比べると高速になっている。 このanyに少しばかりの制限を加えて、「ある型から派生しており、最大サイズを超えない限り何でも」入れられるようにしたクラスは、 anyと違って格納しているものは全て共通の基底クラスから派生しているはずなのでBaseへのポインタを自明に取ることができるため、 速度を殺さないどころか型チェックのオーバーヘッドを排除できるだろう。

これが着想の経緯だ。

実装

基本的には、実装は単純だ。

template<typename Base, std::size_t Size>
class base_storage
{
  public:
    constexpr static std::size_t capacity = Size;
    using base_type = Base;

  public:

    template<typename T>
    base_storage(T&& val)
    {
        using value_type = typename std::remove_cv<
            typename std::remove_reference<T>::type>::type;
        new(storage_) value_type(std::forward<T>(val));
    }

    ~base_storage() noexcept {this->base_ptr()->~base_type();}

    base_type* base_ptr() noexcept
    {return reinterpret_cast<base_type*>(std::addressof(storage_));}

  private:
    typename std::aligned_storage<capacity>::type storage_;
};

骨格としてはこれで足りるだろう。コンストラクタは、placement newによって内部ストレージに値を書き込む。 デストラクタは派生クラスがデストラクタをオーバーライドしていると信じて基底クラスのデストラクタを呼び出す。 基底クラスへのポインタの値が欲しい場合、単に内部ストレージの先頭をキャストして返す。 中には派生クラスしか入っていないはずだし、それは先頭から詰まっているはずなので問題ない。

少し便利にしていこう。コンストラクタに関係ない値を渡してしまったときにはコンパイルエラーになってほしい。 static_assertか、std::enable_ifを使えるだろう。型が派生しているかどうかは、std::is_base_ofに よって判定することにした。これはprivate継承でもtrue_typeになるので微妙な気持ちになるが、まあないよりは良い。

template<typename T, typename std::enable_if<
    std::is_base_of<base_type, typename std::remove_cv<
    typename std::remove_reference<T>::type>::type>,
    std::nullptr_t>::type = nullptr>
base_storage(T&& val)
{
     using value_t = typename std::remove_cv<
        typename std::remove_reference<T>::type>::type;
    new(std::addressof(storage_)) value_t(std::forward<T>(val));
}

長い。以下のようなエイリアスによって短縮しよう。

template<typename T>
using unwrapped_t = typename std::remove_cv<
    typename std::remove_reference<T>::type>::type;

これを使えば、

template<typename T, typename std::enable_if<
    std::is_base_of<base_type, unwrapped_t<T>>,
    std::nullptr_t>::type = nullptr>
base_storage(T&& val)
{
    using value_t = unwrapped_t<T>;
    new(std::addressof(storage_)) value_t(std::forward<T>(val));
}

少しだけ短くなった。

できれば、サイズ超過の時もコンパイルエラーになってほしい。実行時にbad_allocが投げられてもまあ良いのだが、 コンパイル時に気付けることは気付けた方がよい。

template<typename T, typename std::enable_if<
    std::is_base_of<base_type, unwrapped_t<T>>,
    std::nullptr_t>::type = nullptr>
base_storage(T&& val)
{
    using value_t = unwrapped_t<T>;
    static_assert(sizeof(value_t) <= capacity,
                  "base_storage: size exceed");
    new(std::addressof(storage_)) value_t(std::forward<T>(val));
}

というわけだ。emplaceoperator=も同様にできる。

困るのがコピーである。これは単に内部ストレージをコピーすればいいという話ではない。例えば、std::vectorのような動的配列クラスを考えてみてほしい。 このようなクラスは配列の先頭ポインタを持ち、同時に自身が確保している配列の所有権を握っているだろう。 なので、このクラスのデストラクタは自身の確保した配列のための領域を正しく破棄するだろう。 もしこれがbase_storageに入っており、base_storageのコピー時にbase_storage::storage_だけコピーしたとしたら何が起きるだろうか。 その場合、2つの動的配列クラスのインスタンスが誕生し、その2つが同じ配列を指すポインタを持ち、 その両方が自分が所有権を持っていると思っている、という状況が完成する。 このままでは所有権が曖昧になり、既にdeleteされた領域を再度deleteするはめになってしまう。 なので、基本的には中身のクラスはディープコピーしなければならず、つまりコピーコンストラクタを呼ばねばならない。

ちなみにそうならないもの(memcpy相当の処理によって奇妙なことにならないもの)をtrivially copyableだと呼んでいる、と私は認識している。

さて、この問題を解決するためには、コピーのときにはそれぞれのコピーコンストラクタを呼ばねばならないわけだ。 だが動的型情報から型そのものを取り出す方法を私は知らない。動的型情報なのだからそれを静的な型情報に変換する方法はないのではないか。 となると、何かのハンドルを内部的に持っておき、コピーはそのハンドルを介して行う、という作戦をとるしかないだろう。 ちなみにこのテクニックはstatic_anyで使われていたものと基本的に同一である。

template<typename T>
void replicator(void* lhs, void* rhs)
{
    new(reinterpret_cast<T*>(lhs)) T(*reinterpret_cast<T*>(rhs));
}

std::function<void(void*, void*)> handle_copy = &replicator<T>;
handle_copy(std::addressof(this->storage_), std::addressof(rhs.storage_));

実際にはstd::functionでなく関数ポインタを使っている。ファンクタとの相互運用が必要なわけでもないし、 std::functionは確か呼び出す度に中身が空でないかチェックしていた気がするからだ。もししているならそれはオーバーヘッドだ。 nullチェックは手ですることにする。というのも、どうせストレージが空かどうかを知る必要があるからだ。 そのためにフラグを追加するのも、ハンドルが設定されているかどうかを調べるのも変わらない。

というわけで、ややこしい部分は全て終わったことになる。 ついでに、trivially copyableな型なら、このハンドラの分のオーバーヘッドを消せるわけだ。 その場合、空チェックすら省けば、メモリをちょうど指定された量しか消費しないクラスが作れる。 空チェックがないのをどの程度重く受け取るかだが、私はとりあえず今はその必要性を感じられずにいる。

あとがき

と、この話を同僚にしたところ、「アドベントカレンダーまで取っておけばよかったのに」と言われた。 これはある程度の真実を含んでいる。今年アドベントカレンダーをやるとしたら私はネタはあるだろうか。 そもそもC++アドベントカレンダー2017は開催されるだろうか。

でもそんなことを言っていたらブログを数カ月放置することにもなりかねないのだ。 まあまだ開始まで1ヶ月もあるので、何か思いついたり何か知ったりするチャンスはたくさんある。 今度何か思いついたら、それは隠しておいてもいいかもしれない。