c++ - リンクされたリストのキャッシュ - 可能ですか?

Question

配列は、x86_64 アーキテクチャのキャッシング メカニズムをキャッシュ ラインに適合させることで完全に活用できることを知っています。リンクされたリストは、ポインターによってリンクされた一連の構造体/オブジェクトです。そのような構造でキャッシュシステムを利用することは可能ですか? リンクされたリストのオブジェクトは、メモリ内のどこにでも割り当てることができます

Answer 1

リンクされたリストのエントリがどこにでもあることは事実ですが、 「どこにでも」ある必要はありません。たとえば、「ゾーン」からそれらを割り当てることができます。一度に多数の連続するエントリを割り当て、それらを「連続する空きエントリ」のリストにまとめてから、それらを分割します。必要に応じて別のゾーンフルを割り当てます。あまりきれいではないいくつかのトリックを使用すると、解放されたエントリを最終的に再線形化することができます。

ただし、ほとんどの場合、このすべての努力を実際に行う価値はありません。

Answer 2

リンクされたリスト要素ごとに複数のエントリを持つことができます。つまり、各要素のエントリの小さな配列です。これにより、リストの動的な性質を維持しながら、いくつかのエントリをキャッシュできます。

これは展開されたリストであり、あなたが求めているものを提供します。

Answer 3

おそらく、連結リストの 1 つの要素に複数のデータ エントリを含めることができます。たとえば、以下の構造体を検討してください。

struct myll{
    int data[16];
    char valid[16/8];
    struct myll* next;
}

このようにして、ノードごとに 16 エントリとして粒度を作成します。ただし、別のノードを使用して 16 を超えるエントリを追加し、「有効な」フラグを使用して削除するオプションがまだあります。実装するのは少し面倒ですが、要件によって異なります。

いくつかのファイルシステムでは、多少似たメカニズムが使用されていると思います。