c++ - 連続メモリ内のオブジェクトから連結リストを作成する

Question

非常に近くに格納されているオブジェクトを反復処理したい (キャッシュ ミスを減らすため)。すべてのオブジェクトが連続して配置されるようにベクトルを作成し、X への参照を使用してリンク リストを作成することでこれを達成できるという点で、私は正しいでしょうか? このようにして、リストの先頭にすばやく挿入できます。リスト要素を反復処理すると、それらはすべて同じベクトルからのものであるため、互いに離れすぎませんか?

Answer 1

短い答えはイエスです。Vector は、継続的なメモリ ストレージにより、連結リストよりもニーズに適しています。ベクトルの反復とその要素のフェッチは、通常、ベクトル内の項目が大きすぎない場合、リンクされたリストよりもはるかに高速です。

Answer 2

ストレージ内の各アイテムへのランダム アクセスが必要ですか、それともシーケンシャル アクセスが必要ですか。メモリ ストレージの大きさ、要素の数は? 最長の要素の大きさは?

ストレージにアクセスする方法はたくさんありますが、

• ストレージの raw シーケンシャル トラバーサル
• 次の要素へのポインタで各ストレージ要素を拡張します
• 次の要素へのオフセット (スキップ カウント) を使用して、各ストレージ要素を拡張します。
• ポインターの別の配列 (ベクトル) をストレージに作成する
• ストレージへのオフセットを持つ別の配列 (ベクトル) を作成します

Answer 3

リンクされたリストのノードを保存するために使用std::vectorすることは、一定時間で途中から要素を削除し、空のスペースを再利用し、要素を前に挿入できるようにする必要がある場合など、いくつかのコンテキストでは非常に便利で効率的な戦略になる可能性があります。 /middle 一定時間で、トラバーサル順序が挿入順序と一致し、適度にキャッシュに適したアクセス パターンを保持し、64 ビットでのリンクのメモリ使用量を半分にします。

template <class T>
struct Node
{
     // Stores the memory for the element stored in the node.
     typename std::aligned_storage<sizeof(T), alignof(T)>::type data;

     // Points to previous node in the array or previous
     // free node in the array if the node has been removed.
     // Stores -1 if there is no previous node.
     int32_t prev;

     // Points to next node in the array or next free
     // node in the array if the node has been removed.
     // Stores -1 if there is no next node.
     int32_t next;
};

template <class T>
struct List
{
    // Stores all the nodes contiguously.
    std::vector<Node<T>> nodes;

    // Points to the first node in the list.
    // Stores -1 if the list is empty.
    int32_t head;

    // Points to the first free node in the list.
    // Stores -1 if the free list is empty.
    int32_t free_head;
};

std::vectorメモリ アロケータとして

この場合、事実上std::vector、ノード メモリ アロケータに変換し、たとえば、絶対アドレスを格納する 64 ビット ポインタを、配列への相対インデックスを格納する 32 ビット インデックスに変換します。

ただし、上の図でわかるように、このソリューションの欠点は (少し混乱している場合は申し訳ありませんが、この図は消去して再挿入した後に何が起こるかを表しています)、途中から要素を消去し、空のスペースを再挿入して再利用すると、元の挿入順序で要素をトラバースし続けることはできますが、リンクをたどるとメモリ内でジグザグに前後に移動し始める可能性があるため、より多くのキャッシュ ミスが発生し始めます (完全なシーケンシャル アクセス パターンで配列をトラバースしなくなります)。中央に挿入すると同じことが起こります (これにより一定時間で実行できますが、中央のノードが配列の後ろに割り当てられ、参照の局所性が低下する可能性があります)。

最適化パス

したがって、これらのタイプの「ハイブリッド」配列/リンクリストソリューションには、要素を削除して途中から挿入するほど、空間的局所性が低下するという欠点がある傾向があります。prevそれを軽減する方法は、時折リストの「最適化コピー/スワップ」を作成することです。これにより、空間的局所性が復元され、すべてのリンクが配列内の前のインデックスを指しているポイントに戻り、すべてのnextリンクが次を指しています。

それでもいつもよりずっといい

それにもかかわらず、これらの「最適化パス」がなくても、汎用アロケーターを使用してノードが割り当てられるリンクリストよりも、中間からの削除と再挿入を何度も繰り返した後でも、キャッシュミスがはるかに少なくなる傾向があります。後者の場合、ノードはメモリ内のいたるところに散らばり、アクセスするすべてのノードでキャッシュミスが発生する可能性があり、リンクリストが多くの用途で特に非効率的であるという悪評に遭遇するのはそのときです。ケース。また、64 ビット マシンで 64 ビット ポインターの代わりに 32 ビット インデックスを使用する利点も得られます (実際に何十億ものノードが必要な場合を除く)。これにより、リンクのメモリ使用量が半分になります。

インデックス付きリンク リスト

私はリンクされたリストをよく使用しますが、常にこのようなソリューションを使用し、ノードを連続した配列に格納します (すべてのノードを格納する 1 つの連続したバッファ、またはそれぞれ 256 ノードを格納する一連の連続したバッファのいずれか)。絶対ポインタではなく相対インデックスを使用してノードを指します。リンクされたリストをこのように使用すると、実際にははるかに効率的になります。

メモリ プール

32 ビットの時代には、メモリ プールをstd::allocatorこの目的に適合するフリー リストのように使用していましたが、64 ビット ハードウェアが普及してからは、ポインタのサイズがメモリ使用量で 2 倍になり、はるかに便利であることがわかりました。類似の「メモリ アロケータ」および相対 32 ビット インデックスとして、ランダム アクセス データ構造の使用を開始します。リストに格納する要素が 3 つの単精度浮動小数点数 (12 バイト) だけである場合、ポインターのサイズを半分にすることは些細な違いとは言えません。私が見つけた最大の実用的な煩わしさは、すべてのインデックスを操作する必要があり、参照先のデータを直接取得できないことです。これは、リンクのメモリ使用量が 2 倍になり、std::vector

スワップアンドポップバック

トラバーサルの順序を気にせず、インデックスの無効化も気にせず、一定時間内にどこにでも挿入できる必要がない場合、このデータ構造はあまり役に立ちません。その場合、はるかに便利なのは、削除したい途中の要素を最後の and と交換する vector を使用することですpop_back。この構造の主な利点は、リスト内の任意の場所からの一定時間の削除と、リスト内の任意の場所への一定時間の挿入を維持しながら、同時に元の挿入順序で、合理的にキャッシュに適した方法でトラバースできることです。