(素晴らしい?) アロケータの追加 - アロケータの提案に関する考え

ポスト ジャクソンビル メーリングの C++ 標準委員会の論文が最近公開されました。STL のアロケータ モデルを扱う非常に興味深いものはほとんどありません。およびアロケータでの配列割り当て。

この投稿では、それらについてあなたと話し合い、それらのいくつかが受け入れられることを本当に望んでいる理由を説明したいと思います.最初の部分は、AllocatorAwareContainer のフォローアップでもあります。

P0177R1 - allocator_traits のクリーンアップ

私の以前の投稿の 1 つは AllocatorAwareContainer:Introduction and pitfalls of Propagate_on_container_XXX defaults でした。この投稿では、C++11 AllocatorAwareContainer の概念について説明し、propagate_on_container_XXX 「boolean typedef」を設定できます。

そのうちの 3 つがあります:

<リ>

propagate_on_container_copy_assignment :std::true_type の場合のみ AllocatorAwareContainer を割り当ててコピー アロケータもコピー割り当てします。

<リ>

propagate_on_container_move_assignment :コピー代入 typedef と同じですが、ムーブ代入用です。これが std::false_type の場合、パフォーマンスが低下することに注意してください （デフォルト！）。ムーブ代入は一部のポインターを変更することはできないため、独自のアロケーターを使用してメモリを割り当てる必要があります (アロケーターが「等しくない」場合)。

<リ>

propagate_on_container_swap :std::true_type の場合のみ 2 つの AllocatorAwareContainer を交換する アロケータも交換します。これが std::false_type の場合に注意してください (デフォルト)、「等しくない」アロケーターを使用して 2 つのコンテナーをスワップすると、未定義の動作が発生します。スワップはポインター スワップを実行できず、独自のアロケーターを使用してメモリを再度割り当てる必要があるためです。しかし、反復子の無効化を禁止する規則により、swap はそれを行うことができません。

以前の投稿は、これらの設計上の選択、特に「間違った」デフォルトに関する暴言のようなものでした.

10 月に普及した後、Alisdair Meredith から連絡がありました.彼は STL アロケータ モデルの大規模な支持者であり、この論文の著者でもあります.長いメールで、彼はデフォルトが何であるかを説明しました.

伝播はステートフル アロケーターにとってのみ重要であり、それらには 2 つの異なるモデルがあります。それらは提案でも説明されているので、2 番目のモデルから始めて、そこから引用します。

これは基本的に、私が元のブログ投稿で、より正式で、暴言を吐かないで言ったことです。 方法.アロケータはメモリに属しているため、割り当てを移動するのではなく、移動するという意味で常に移動する必要があります.メモリにとどまらないアロケータを使用する必要があるのはなぜですか?!

最初のモデルのおかげで、その通りです:

STL アロケーターは、割り当てられたオブジェクトの構築と破棄を制御できます。この機能により、アロケーター も制御できます。 メモリ内のオブジェクトが使用します。これにより、アロケータは自分自身をオブジェクトに渡すことができます。

たとえば、Bloomberg アロケーター モデルと Boost.Interprocess で使用されます。後者の場合、コンテナーの値の型によるすべての割り当ては、同じメモリ セグメントにある必要があります。

アロケーターもこのモデルのオブジェクトを保持する必要があります。そうしないと、寿命の問題が発生する可能性があります。

これは、ポリモーフィック メモリ リソース TS にも当てはまります。

そこでは、コンテナはリソースへのポインタを持っているだけです.アロケータがコンテナ間で自由に転送される場合、存続期間の推論はより困難になります.しかし、アロケータが1つのコンテナにとどまる場合、それは簡単です:リソースはコンテナオブジェクトと同じくらい存続する必要があります.

そのため、デフォルトがそのまま選択されています。

さて、紙自体に戻ります。そこで少し夢中になりました。

両方のモデルで、すべて propagate_on_container_XXX のいずれかであることに注意してください std::true_type のいずれかに設定されている 、つまり完全な伝播、または std::false_type 、つまり、伝播はありません。スワップ時に伝播を使用するモデルはありませんが、割り当てなどでは使用しません。

3 つすべてのカスタマイズをサポートすると、AllocatorAwareContainer が実装されます。 この論文は例を示しており、ここで私のアロケータ モデルを使用して人々をやる気にさせるために例を示しました.

そのため、この論文では、3 つすべてを同じ値に設定する必要があると提案しています。これにより、実装が簡単になり、独自のモデルについて推論しやすくなります。また、これらの値が異なることを必要とする正常なモデルを実際に実装した人がいない可能性は非常に低いため、これは非破壊的な変更になります。

P0178R0 - アロケーターとスワップ

P0178R0 は、等しくないアロケーターへのスワップによって導入された未定義の動作の問題に対処します。

動機は明らかです:未定義の動作は悪い[要引用] ].また、swap のため、ジェネリック コードのジェネリック性が低くなります。

解決策は、(UB を使用して) メンバー スワップをそのまま維持することですが、名前空間のバージョンを次のように変更することです (論文から引用):

void swap(CONTAINER_TYPE & left, CONTAINER_TYPE & right) {
 if (allocators are compatible) {
 left.swap(right);
 }
 else if (allocator propagation traits are sane) {
 std::swap<TYPE>(left, right);
 }
 else {
 CONTAINER_TYPE tempLeft {std::move(right), left.get_allocator() };
 CONTAINER_TYPE tempRight{std::move(left ), right.get_allocator()};
 swap(left, tempLeft );
 swap(right, tempRight);
 }
}

「アロケーターに互換性がある」とは、それらが等しいことを意味します。つまり、他のアロケーターから割り当てられたメモリの割り当てを解除したり、スワップで伝播したりするために使用できます。この場合、狭いコントラクトとの高速スワップが呼び出されます (コントラクトが履行されるため)。

「アロケーターの伝播特性は正気」とは、スワップ特性 (または、上記の提案が受け入れられた場合) が同じであることを意味します。この場合、一時変数を使用した手動の一般的なより高価なスワップが使用されます。

「最後の手段」として、移動コンストラクターと他のアロケーターを介してコンテナーのコピーが作成されることに注意してください。その後、アロケーターが交換されます。

最後の 2 つのケースは以前は定義されていませんでしたが、現在は単に遅くなっています。

また、これらのケースでは反復子も無効になることに注意してください。

はい、スワップはイテレータを無効にしてはなりません - 「アロケータが等しくない場合を除いて」は、提案が言うことです.これは not 以前のコードは UB だったので、重大な変更です。

私は、この提案は問題の半分しか扱っていないと思います.すべてのスワップは広いコントラクトを持つようになりましたが、事後条件は異なります.今や完全に一般的なコードは、スワップがイテレータを無効にしないという事実に依存することはできません.

これは単に未定義の動作を別の動作と交換するだけです。

P0310R0 - アロケーターでのノードと配列の割り当ての分割

あまり技術的でないトピックでは、P0310R0 がノードとアレイの割り当てを分割することを提案しています。

STL アロケータの割り当て関数は次のようになります:

pointer allocate(size_type n, const void* hint = 0);

この関数は、n にメモリを割り当てます。 要素、つまりstd::allocator<int>::allocate(5) を呼び出す 5 のメモリを割り当てます int s、つまり 5 * sizeof(int) バイトのメモリ。

しかし、この関数は実際には 2 しなければなりません 非常に異なるもの!

<リ>

n = 1 の場合 単一にメモリを割り当てます エレメント。 ノードと呼ばれます このコンテキストでは、ノードの割り当てです。 .

<リ>

n > 1 の場合 配列にメモリを割り当てます 要素の。したがって、これは 配列の割り当て です .

アロケータのユースケースに応じて、多くの場合、ノード割り当てのみまたは配列割り当てのみを処理します。たとえば、std::list 内でアロケータを使用します。 およびその他のノードベースの STL コンテナーは、allocate(1) の呼び出しになります。 これらのコンテナーは、相互にリンクされた単一のノードに基づいているためです。一方、std::vector 内で使用すると、 std::vector であるため、配列の割り当てが発生します。 継続的な保存が必要です。

実際のところ、ノードの割り当ては多い ほとんどのアロケーターでの配列割り当てよりも単純です。たとえば、メモリ プールは設計されています。 ノード割り当ての場合、配列割り当てをノードに配置すると、パフォーマンスに大きな影響があります。

したがって、新しいアロケーター モデルを設計したとき、最初に行ったことの 1 つは、ノードと配列の割り当てを分割することでした。

この論文では、std::allocator_traits への 3 つの追加を提案することで、同様にそれを行います。 :

<リ>

allocate_node() /deallocate_node() 関数:これらは、1 つのノードを割り当てるために最適化されています。メンバー関数または allocate(1) に転送します .これは大きな変更ではありません。アロケーターは n で分岐できます。 ノード固有または配列固有の割り当てを行うための引数。これも私が行っていることです。

<リ>

ブール typedef node_allocation_only :デフォルトは std::false_type です 、std::true_type にオーバーライドできます . std::true_type の場合 、アロケーターはノードの割り当てのみを提供し、それを使用して配列を割り当てようとするとエラーになります ( allocate() を呼び出してはいけないと思います) ).これも大きな変更ではなく、実行時のアサーションの失敗をコンパイル時のエラーに変換するだけです.

では、ノードと配列の割り当てが分割されていない場合、大きな変更点は何でしょうか?

メモリ プールは、特定のサイズのノードを非常に高速に割り当てるように最適化されています。しかし、特定の問題があります。私のライブラリを例として考えてみましょう:

#include <foonathan/memory/container.hpp>
#include <foonathan/memory/memory_pool.hpp>

namespace memory = foonathan::memory;

...

memory::memory_pool<> pool(???, 4096u);
memory::list<int, memory::memory_pool<>> list(pool);
// ^^^^ equivalent to: std::list<int, memory::std_allocator<int, memory::memory_pool<>>> list(pool);
// just a convenience typedef

上記のコード スニペットは std::list を作成します memory_pool のコンストラクター 2 つの引数を取ります。最初の引数はプール内の各ノードのサイズで、2 番目の引数はその初期容量です。

2 つ目は 4KiB に設定しましたが、ノード サイズはどれくらいですか?

sizeof(int) ?いいえ、各リスト ノードにはポインターのオーバーヘッドがあります。

だから sizeof(int) + 2 * sizeof(void*) ?たぶん、配置と他のものに依存します.

2 * (sizeof(int) + 2 * sizeof(void*) を使用するだけです 安全ですか?

しかし、ツリー構造のノードはどうでしょうか?2 つの子 + 1 つの親?

それともハッシュマップのノードですか?単一の連結リスト?二重連結リスト？木?

答えは、ノードのサイズがわからないということです。これは実装定義ですが、プール アロケータを適切に使用するには、少なくともそのサイズが必要です!

この基本に対処するには STLの問題で、この論文はネストされたnode_typeを提案しています typedef.これは、ノード コンテナーによって使用されるノードです。

これで ??? を置き換えることができます sizeof(memory::list<int, memory::memory_pool<>>::node_type) で .

そしてそれ この提案の大きな変更点です!

完全を期すために:

ノードサイズのデバッグ機能を使用してサイズを取得することもできます。ライブラリをビルドすると、ノード サイズを取得して使用できる定数を生成するコード ジェネレータが実行されます。上記の場合は memory::list_node_size<int>::value です。 .しかし、それは機能しますが™、非常に醜く、Allocator used はノード タイプに何らかの影響を与えます。

交換する時が待ちきれません!

結論

特にノードの提案は、本当に コンテナ ノード タイプへのアクセスを取得すると、私の人生は とても

スワップに関連付けられた UB を取り除こうとするのと同じように、アロケーターの特性をクリーンアップすることも素晴らしいことです。これらの変更が C++11 にあった場合、それについてブログ記事を書く必要はなかったでしょう。言語が必要です。

割り当てを扱う他のいくつかの提案もあります:

<リ>

P00211 - 動的割り当てのためのアロケータ対応ライブラリ ラッパー:allocate_shared() に相当するものを提案する簡単な論文 std::unique_ptr の場合 および生のポインター。また、allocator_deleter std::unique_ptr の場合 そして、生のポインターの割り当て解除関数.foonathan/memory は、RawAllocators に対して同等のスマート ポインター機能を提供します。 アロケーターから生のポインターを取得することは、スマート ポインターの使用を奨励するのは難しいはずです。

<リ>

P0035R1 - オーバーアラインされたデータの動的メモリ割り当て:このペーパーでは、new でオーバーアラインされたデータのサポートを追加したいと考えています。 新しい ::operator new を提供することによって アライメント値を取ります。言うことはあまりありません - 実現させましょう!

<リ>

おそらく、私が見逃した、またはカバーしたくない他のもの.

適切な論文が受け入れられれば、アロケータに関する C++ の将来は本当に素晴らしいものになるでしょう。