カスタムアロケータを使用してstd :: listキャッシュをフレンドリにするには？

Question

私の毎日の仕事の間、私はいつもチームの上級メンバーによってキャッシュフレンドリーではないことを知らされていますので、私はvectorにすべきです。私はlistが連続していないので、メモリの割り当てがメモリ全体に分散していることを理解しています。

しかし、非常に多くの場合、list（またはmap）という機能が必要です。だから私は自分自身のアロケータを書くことができるかどうか疑問に思っています。これはvectorの下にあります。私がpush_backになるたびに、私自身のアロケータは、割り当てられた1つあたりの新しいアイテムを割り当てますvector。

list/mapを移動すると、キャッシュのローカリティは保持されます。

これはあなたの誰かにとって意味がありますか？

Answer 1

std::listとstd :: set（私はリストではなく、マップではなく、リストの代わりに設定する必要があると信じています）、どちらも内部用のallocatorを使用します。 メモリのブロックを事前に割り当てて、オブジェクトとコンテナを作成するために使用できます。あなたがGoogleの場合、いくつかを見つけるでしょう。この場合、代わりにあなたのオブジェクトは "メモリ全体に散らばって"あなたの記憶のブロックの周りに散らばっています。キャッシュにブロックが収まると、いくらか改善されます。しかし、それは完全にあなたの問題を解決することはありません。

問題の説明から、実際にはdequeが必要です。 Dequeは配列のリストとして実装されています。ベクトルとリストの間に妥協点があります。反復処理にはキャッシュが使いやすく、挿入するとすぐに配列になります。

したがって、カスタムアロケータまたは両端キューのいずれかを選択できます。これは、コレクションのサイズによって異なります。