Polymorphic Memory Resources - Rokiのチラ裏

先日策定された C++17 から追加された Polymorphic Memory Rerouces についてのメモ。同提案でも言及されている通りstd::allocatorは、型にそのアロケータ情報を含む事で利用されるため、コンパイル時にしか指定することが出来ず、結果として同じ型のオブジェクトは同じアロケータしか持つことが出来なかった。これに対して<memory_resources>はポリモーフィックなランタイム動作を行うことで、同じ型のオブジェクトでも、異なるアロケータを持つことができるようにする*1。
C++17 から<memory_resource>ヘッダが追加され、std::pmr名前空間下にpolymorphic_allocator, memory_resource, pool_options, synchronized_pool_resource, unsynchronized_pool_resource, monotonic_buffer_resourceクラス、new_delete_resource, null_memory_resource, get_default_resource, set_default_resource関数が定義される。大元の提案は、N3525 *2、同提案の最終リビジョンは N3916 r2。以下は C++17(N4659) [mem.res.syn] から引用*3。

namespace std::pmr {
  // [mem.res.class], class memory_resource
  class memory_resource;

  bool operator==(const memory_resource& a, const memory_resource& b) noexcept;
  bool operator!=(const memory_resource& a, const memory_resource& b) noexcept;

  // [mem.poly.allocator.class], class template polymorphic_allocator
  template<class Tp> class polymorphic_allocator;

  template<class T1, class T2>
    bool operator==(const polymorphic_allocator<T1>& a,
                    const polymorphic_allocator<T2>& b) noexcept;
  template<class T1, class T2>
    bool operator!=(const polymorphic_allocator<T1>& a,
                    const polymorphic_allocator<T2>& b) noexcept;

  // [mem.res.global], global memory resources
  memory_resource* new_delete_resource() noexcept;
  memory_resource* null_memory_resource() noexcept;
  memory_resource* set_default_resource(memory_resource* r) noexcept;
  memory_resource* get_default_resource() noexcept;

  // [mem.res.pool], pool resource classes
  struct pool_options;
  class synchronized_pool_resource;
  class unsynchronized_pool_resource;
  class monotonic_buffer_resource;
}

Abstract base class `memory_resource`

Abstract base class memory_resource はブロックの割り当て及び割り当て解除ができるメモリリソースを記述する。これは純粋仮想関数である do_allocate, do_deallocate, do_is_equal をそれぞれ呼び出す関数 allocate*4, deallocate 及び is_equal を提供する。N4659/[mem.res.class] から引用。

namespace std::pmr {
  class memory_resource {
    static constexpr size_t max_align = alignof(max_align_t);   // exposition only

  public:
    virtual ~memory_resource();

    void* allocate(size_t bytes, size_t alignment = max_align);
    void deallocate(void* p, size_t bytes, size_t alignment = max_align);

    bool is_equal(const memory_resource& other) const noexcept;

  private:
    virtual void* do_allocate(size_t bytes, size_t alignment) = 0;
    virtual void do_deallocate(void* p, size_t bytes, size_t alignment) = 0;

    virtual bool do_is_equal(const memory_resource& other) const noexcept = 0;
  };
}

memory_resourceクラスを派生させ、各純粋仮想関数を実装する事でそれを共有メモリリソースとして使用できる。do_allocate関数はアロケートされた記憶領域へのポインタを返さなければならない。この時返された記憶領域のアラインメントがサポートされていない場合、指定されたアラインメントに揃えられ、それ以外の場合max_alignに揃えられる。要求されたサイズとアラインメントでメモリを割り当てることができない場合、適切な例外をスローしなければならない。

virtual void* do_allocate(size_t bytes, size_t alignment) = 0;

do_deallocate関数は、アロケートされた記憶域を破棄しなければならない。

virtual void do_deallocate(void* p, size_t bytes, size_t alignment) = 0;

do_is_equal関数は、このクラスからアロケートされたメモリを他のクラスからデアロケート出来る場合にtrueを返し、そうでない場合はfalseを返さなければならない。

virtual bool do_is_equal(const memory_resource& other) const noexcept = 0;

以下のように利用できる*5。

#include <memory_resource>

class X : public std::pmr::memory_resource {
protected:
    void* do_allocate(std::size_t bytes, [[maybe_unused]] std::size_t alignment) override { return ::operator new(bytes); }
    void do_deallocate(void* p, [[maybe_unused]] std::size_t bytes, [[maybe_unused]] std::size_t alignment) override { ::operator delete(p); }
    bool do_is_equal(const std::pmr::memory_resource& other) const noexcept override { return this == std::addressof(other); }
};

Class Template `polymorphic_allocator<T>`

N4659/[mem.poly.allocator.class] から引用。

namespace std::pmr {
  template<class Tp>
    class polymorphic_allocator {
      memory_resource* memory_rsrc;     // exposition only

    public:
      using value_type = Tp;

      // [mem.poly.allocator.ctor], constructors
      polymorphic_allocator() noexcept;
      polymorphic_allocator(memory_resource* r);

      polymorphic_allocator(const polymorphic_allocator& other) = default;

      template<class U>
        polymorphic_allocator(const polymorphic_allocator<U>& other) noexcept;

      polymorphic_allocator& operator=(const polymorphic_allocator& rhs) = delete;

      // [mem.poly.allocator.mem], member functions
      Tp* allocate(size_t n);
      void deallocate(Tp* p, size_t n);

      template<class T, class... Args>
        void construct(T* p, Args&&... args);

      template<class T1, class T2, class... Args1, class... Args2>
        void construct(pair<T1, T2>* p, piecewise_construct_t,
                       tuple<Args1...> x, tuple<Args2...> y);
      template<class T1, class T2>
        void construct(pair<T1, T2>* p);
      template<class T1, class T2, class U, class V>
        void construct(pair<T1, T2>* p, U&& x, V&& y);
      template<class T1, class T2, class U, class V>
        void construct(pair<T1, T2>* p, const pair<U, V>& pr);
      template<class T1, class T2, class U, class V>
        void construct(pair<T1, T2>* p, pair<U, V>&& pr);

      template<class T>
        void destroy(T* p);

      polymorphic_allocator select_on_container_copy_construction() const;

      memory_resource* resource() const;
    };
}

インタフェースから見てわかるように、クラスpolymorphic_allocator<T>はアロケータの必要用件、インタフェースに合わせて上記のmemory_resourceをラップするクラスである。コンストラクタにはメモリリソースのポインタを渡す。上述したクラスXを例えば次のように利用できる。

template <class T>
using poly_vector = std::vector<T, std::pmr::polymorphic_allocator<T>>;

int main()
{
    auto r = std::make_unique<X>();
    std::pmr::polymorphic_allocator<int> pa(r.get());
    [[maybe_unused]] poly_vector<int> v(pa);
}

尚、std::pmr::polymorphic_allocatorはデフォルトコンストラクトする事ができ、その場合内部のメモリリソースは下記で説明されているstd::pmr::set_default_resourceによってデフォルトのメモリリソースが設定されない限り、std::pmr::new_delete_resourceの戻り値に設定され、そうでない場合、std::pmr::set_default_resourceで設定されたメモリリソースが設定される。

Access to program-wide `memory_resource` objects

以下に示す関数らは、一般的なメモリリソースを提供する。

`new_delete_resource`

memory_resource* new_delete_resource() noexcept;

new_delete_resourceは上述したクラスXと同じ役割を果たすメモリリソースへのポインタを返す。つまり、::operator newと::operator deleteを利用してメモリをアロケート、デアロケートするメモリリソースへのポインタが返される。この関数は、何度呼び出しても同じ値が返される。次の例は、std::vectorのアロケート、デアロケートにおいて、上述のメモリリソースXのアロケート、デアロケートと似たように*6振る舞う。

std::pmr::polymorphic_allocator<int> pa(std::pmr::new_delete_resource());
[[maybe_unused]] poly_vector<int> v(pa);

assert(std::pmr::new_delete_resource() == std::pmr::new_delete_resource());

尚、この時返されるポインタpがis_equal(r)と呼び出した時、&r == pが返される。

auto p = pmr::new_delete_resource();
assert(p->is_equal(*p));

`null_memory_resource`

memory_resource* null_memory_resource() noexcept;

これは、allocateが呼び出された時に常にstd::bad_alloc例外を送出し、失敗するメモリリソースへのポインタを返す。これは、1つのメモリリソースが、別のメモリリソースに依存するようなメモリリソースのチェーンの終わりを設定するのに便利に利用できる。一番初めのメモリリソースが、自身のメモリプールを使い果たす事を予測できないような状況で null なメモリリソースを仕様してヒープから誤ってメモリをアロケートしてしまうというような事を回避できる。

try {
    std::pmr::polymorphic_allocator<int> pa(pmr::null_memory_resource());
    [[maybe_unused]] typename decltype(pa)::value_type* p = pa.allocate(1); // always throw std::bad_alloc
} catch (const std::exception& e) {
    std::cerr << e.what() << std::endl;
}

`set_default_resource`

memory_resource* set_default_resource(memory_resource* r) noexcept;

これは、r が null でない限りデフォルトメモリリソースをrに設定する。そうでない場合、デフォルトメモリリソースをstd::pmr::new_delete_resourceの戻り値に設定する。

inline std::pmr::memory_resource* X_resource()
{
    static X resource;
    return static_cast<std::pmr::memory_resource*>(&resource);
}

std::pmr::set_default_resource(X_resource());
std::pmr::polymorphic_allocator<int> pa1;
assert(pa1.resource() == X_resource());
    
std::pmr::set_default_resource(nullptr);
std::pmr::polymorphic_allocator<int> pa2;
assert(pa2.resource() == std::pmr::new_delete_resource());

`get_default_resource`

memory_resource* get_default_resource() noexcept;

これは、現在のデフォルトメモリリソースポインタの値を返す。

assert(std::pmr::get_default_resource() == std::pmr::new_delete_resource());
std::pmr::set_default_resource(X_resource());
assert(std::pmr::get_default_resource() == X_resource());

Pool resource classes

以下に示すクラスらは、標準的なプールリソースを提供する。

`synchronized_pool_resource`, `unsynchronized_pool_resource`

これらはまとめてプールリソースと呼ばれる。プールリソースは以下のような特徴を持つ。

アロケートされた記憶域を所有し、アロケートされたブロックの一部、または全てに対してdeallocateが呼び出されなくても破棄時に自動的に解放される汎用リソースである。
プールリソースは、プールの集合によって構成され、異なるブロックサイズの要求を処理する。それぞれ個々のプールは、一様なサイズのブロックに分割されたチャンクの集合を管理し、do_allocateの呼び出しを介して返される。do_allocate(size, alignment)への各呼び出しは少なくともsizeバイトを扱うプールにディスパッチされる。
特定のプールが使い尽くされた時に、そのプールからブロックを割り当てると上流アロケータ( $upstream\ allocator$ )*7から追加のメモリチャンクが割り当てられ、プールが補充される。連続した補充ごとに得られるチャンクサイズは幾何級数的に増加する*8。
任意のプールの最大ブロックサイズを超えるアロケーション要求は、上流アロケータから直接実行される。
pool_options構造体をプールリソースコンストラクタに渡して、最大ブロックサイズと最大チャンクサイズを調整することができる。

synchronized_pool_resourceは、外部同期なしで複数のスレッドからアクセスすることができ、同期コストを削減するためにスレッド固有のプールを持つことができる。unsynchronized_pool_resourceクラスは、複数のスレッドから同時にアクセスすることはできないが、シングルスレッドアプリケーションのような同期コストを払う必要のない場面では最適である。以下に、二つのクラスのインタフェースを N4659/[mem.res.pool.overview] から引用する。

namespace std::pmr {
  struct pool_options {
    size_t max_blocks_per_chunk = 0;
    size_t largest_required_pool_block = 0;
  };

  class synchronized_pool_resource : public memory_resource {
  public:
    synchronized_pool_resource(const pool_options& opts, memory_resource* upstream);

    synchronized_pool_resource()
        : synchronized_pool_resource(pool_options(), get_default_resource()) {}
    explicit synchronized_pool_resource(memory_resource* upstream)
        : synchronized_pool_resource(pool_options(), upstream) {}
    explicit synchronized_pool_resource(const pool_options& opts)
        : synchronized_pool_resource(opts, get_default_resource()) {}

    synchronized_pool_resource(const synchronized_pool_resource&) = delete;
    virtual ~synchronized_pool_resource();

    synchronized_pool_resource& operator=(const synchronized_pool_resource&) = delete;

    void release();
    memory_resource* upstream_resource() const;
    pool_options options() const;

  protected:
    void* do_allocate(size_t bytes, size_t alignment) override;
    void do_deallocate(void* p, size_t bytes, size_t alignment) override;

    bool do_is_equal(const memory_resource& other) const noexcept override;
  };

  class unsynchronized_pool_resource : public memory_resource {
  public:
    unsynchronized_pool_resource(const pool_options& opts, memory_resource* upstream);

    unsynchronized_pool_resource()
        : unsynchronized_pool_resource(pool_options(), get_default_resource()) {}
    explicit unsynchronized_pool_resource(memory_resource* upstream)
        : unsynchronized_pool_resource(pool_options(), upstream) {}
    explicit unsynchronized_pool_resource(const pool_options& opts)
        : unsynchronized_pool_resource(opts, get_default_resource()) {}

    unsynchronized_pool_resource(const unsynchronized_pool_resource&) = delete;
    virtual ~unsynchronized_pool_resource();

    unsynchronized_pool_resource& operator=(const unsynchronized_pool_resource&) = delete;

    void release();
    memory_resource* upstream_resource() const;
    pool_options options() const;

  protected:
    void* do_allocate(size_t bytes, size_t alignment) override;
    void do_deallocate(void* p, size_t bytes, size_t alignment) override;

    bool do_is_equal(const memory_resource& other) const noexcept override;
  };
}

pool_optionsは前述した通り、プールリソース用のコンストラクターオプションとして利用する事ができ、そのように構成されている。pool_optionsには二つのデータメンバが用意されているが、プールリソースの動作に対する各データメンバの効果は以下の通りである。

size_t max_blocks_per_chunk;: プールを補充するために上流メモリリソースから一度に割り当てられるブロックの最大数を指定する。size_t max_blocks_per_chunk;の値が 0 であるか、実装定義の制限値よりも大きい場合は、その制限が代わりに使用される。実装では、この変数で指定されている値よりも小さい値を使用する事があり、プールごとに異なる値を使用する可能性がある。
size_t largest_required_pool_block;: プールする最大ブロックサイズを指定する。この値よりも大きな単一のブロックを割り当てる操作は、上流メモリリソースから直接割り当てられる。0 であるか、実装定義の制限値よりも大きい場合は、その制限が代わりに使用される。実装では、この変数で指定した閾値を超えた閾値を選択する事ができる。

以下のように使用できる。

std::pmr::synchronized_pool_resource pool1;
[[maybe_unused]] std::pmr::synchronized_pool_resource pool2(X_resource());
[[maybe_unused]] std::pmr::synchronized_pool_resource pool3(std::pmr::pool_options{ 0, 0 });
[[maybe_unused]] std::pmr::synchronized_pool_resource pool4(std::pmr::pool_options{ 0, 0 }, X_resource());

std::pmr::polymorphic_allocator<int> pa(pool1);

poly_vector<int> v(pa);

Class `monotonic_buffer_resource`

これは、上流メモリリソースから十分な大きさのストレージを確保し、各オブジェクトが必要とするサイズに切り分けて返すメモリリソースである。特徴として、std::pmr::monotonic_buffer_resource自身が破棄されるまで、一度占有されたメモリ空間は解放される事はない。これは、全てのメモリリソースオブジェクトが破棄された時に一括して解放される状況で、高速なメモリアロケーションを実現する事を目的とした専用メモリリソースである。加えて、以下の性質がある。

deallocateが呼び出されても、何もしない。よって、消費されるメモリ量はリソースが破棄されるまで単調増加する。
プログラムは、メモリ要求を満たすためにアロケータが使用する初期バッファを指定する事ができる。
初期バッファ(存在する場合)が使い果たされると、初期バッファは、構築時に供給される上流メモリリソースから追加のバッファを取得する。各追加バッファは、幾何学的な進行に従って、前のバッファよりも大きくなる。
一度に1つの制御スレッドからのアクセスを意図している。すなわち、allocateとdeallocateの呼び出しは互いに同期しない。つまりスレッドセーフでない。
アロケートされたブロックのいくつかに対してデアロケート処理が呼び出されていなくても、割り振られたメモリーをデストラクト時に解放する。

以下にstd::pmr::monotonic_buffer_resourceクラスのインタフェースを N4659/[mem.res.monotonic.buffer] から引用する。

namespace std::pmr {
  class monotonic_buffer_resource : public memory_resource {
    memory_resource* upstream_rsrc;     // exposition only
    void* current_buffer;               // exposition only
    size_t next_buffer_size;            // exposition only

  public:
    explicit monotonic_buffer_resource(memory_resource* upstream);
    monotonic_buffer_resource(size_t initial_size, memory_resource* upstream);
    monotonic_buffer_resource(void* buffer, size_t buffer_size, memory_resource* upstream);

    monotonic_buffer_resource()
        : monotonic_buffer_resource(get_default_resource()) {}
    explicit monotonic_buffer_resource(size_t initial_size)
        : monotonic_buffer_resource(initial_size, get_default_resource()) {}
    monotonic_buffer_resource(void* buffer, size_t buffer_size)
        : monotonic_buffer_resource(buffer, buffer_size, get_default_resource()) {}

    monotonic_buffer_resource(const monotonic_buffer_resource&) = delete;

    virtual ~monotonic_buffer_resource();

    monotonic_buffer_resource& operator=(const monotonic_buffer_resource&) = delete;

    void release();
    memory_resource* upstream_resource() const;

  protected:
    void* do_allocate(size_t bytes, size_t alignment) override;
    void do_deallocate(void* p, size_t bytes, size_t alignment) override;

    bool do_is_equal(const memory_resource& other) const noexcept override;
  };
}

以下の様に利用できる。

constexpr std::size_t buff_size = 1024;
auto buf = std::make_unique<unsigned char[]>(buff_size);

std::pmr::monotonic_buffer_resource mbr1; // #1
[[maybe_unused]] std::pmr::monotonic_buffer_resource mbr2(X_resource()); // #2
[[maybe_unused]] std::pmr::monotonic_buffer_resource mbr3(buff_size, std::pmr::get_default_resource()); //#3
[[maybe_unused]] std::pmr::monotonic_buffer_resource mbr4(buf.get(), buff_size); // #4
[[maybe_unused]] std::pmr::monotonic_buffer_resource mbr5(buf.get(), buff_size, std::pmr::get_default_resource()); // #5

std::pmr::polymorphic_allocator<int> pa(mbr1);
poly_vector<int> v(pa);

#1 では $current\ buffer$ を nullptr に設定し、 $next\ buffer\ size$ を実装定義のサイズに設定し、上流メモリリソースをデフォルトメモリリソースから設定する。#2 では任意のメモリリソースを受け取っている。 #3 はそれに加えて $next\ buffer\ size$ を少なくともbuff_sizeに設定する。#4 では、 $current\ buffer$ を buf.get() の戻り値に設定し、 $next\ buffer\ size$ を少なくともbuff_sizeに設定する。#5 はそれに加えて上流メモリリソースをstd::pmr::get_default_resourceの戻り値に設定している。
尚、std::pmr::monotoric_buffer_resource::do_is_equalは N4659/[mem.res.monotonic.buffer.mem] で次の様にダウンキャストを行うと述べられている(執筆時最新のドラフト(C++20) N4713/[mem.res.monotonic.buffer.mem]でも同様)。

bool do_is_equal(const memory_resource& other) const noexcept override;

Returns:this == dynamic_cast(&other)

しかし、この比較処理はオブジェクトの等価判定ではなくアドレスの等価判定であるため、このようなダウンキャストは余分である。これは先に挙げたstd::pmr::synchronized_pool_resource::do_is_equal と std::pmr::unsynchronized_pool_resource::do_is_equal にも見られ、既に LWG に報告されている。

Aliases for container classes

これまで例として利用してきたpoly_vectorエイリアステンプレートと同じエイリアステンプレートが標準からも提供される。

namespace std {
namespace pmr {

template <class T>
using vector<T> = std::vector<T, polymorphic_allocator<T>>;

} // namespace pmr
} // namespace std

上記の様なエイリアステンプレートが提供されるライブラリーらは以下の通りである*9

string
deque
forward_list
list
vector
map
set
unorderd_map
unorderd_set
regex

*1:「オブジェクトの型はメモリを取得するために使用するアロケータと独立しなければならない」と述べられている(N3916 r2/3)。

*2:この提案ではアロケータで Type Erasure を利用することでインタフェースを改善し、動的にアロケータを使えるようにするというものだった

*3:p0790r0 では memory_resource クラスに strong_equality の space ship operator を定義する提案がされている。それと伴い memory_resource クラスを基底とする三つのクラスも自ずと strong_equality となる。

*4:C++20 では、P0600R1 によって nodiscard 属性が指定される

*5:簡単のため、アラインメントのチェック、例外送出などの処理を行なっていないが、実際の利用では厳密なチェックと例外送出を行う事が望ましい。例えば、アラインメントが 0 と等しい、または 2 の冪乗であるかをチェックしそれに応じて max_align を返すなどの処理が考えられる。

*6:前述した通り、X ではアラインメントの整合性チェックとそれに応じた例外処理を省いている点で異なる

*7:これは、コンストラクト時に指定されるメモリリソースが利用される。コンストラクト時に指定しない場合、デフォルトメモリリソースが利用される。

*8:チャンク単位でメモリを割り当てる事で、メモリ内で連続したアロケーションを獲得できる機会を増やす。これはフラグメンテーションの防止につながる。

*9:P0220r1 -> n4562 参照。

Abstract base class memory_resource

Class Template polymorphic_allocator<T>

Access to program-wide memory_­resource objects

new_delete_resource

null_memory_resource

set_default_resource

get_default_resource