リンクされたリストのデータ構造とそのバリアント スキップリストは、並列ハードウェアでキャッシュに適しているとよく読んでいます。これは何を意味するのでしょうか ？どなたか分かりやすく教えてください。
編集：コンテキストは このリンクにあります。
質問する
893 次
1 に答える
7
リンクされたリストのデータ構造とそのバリアントスキップリストはキャッシュフレンドリーであるとよく読みます
リンクされたリストおよび同様の構造は、各ノードがメモリ内でランダムに配置される可能性があり、多くのキャッシュ ミスが発生する可能性があるため、CPU キャッシュ フレンドリーではありません。
比較すると、ArrayList はすべての参照をメモリ内で順番に保持するため、キャッシュ ライン (通常は 64 バイト長) が読み込まれると、一度に 16 の参照を読み込むことができます。
注: List が参照するオブジェクトは、メモリ内でランダムに配置される可能性があり、これを制御することはできません。:|
質問の記事より。
リンクされたリストは、同時トラバーサルと更新に適しているだけでなく、並列ハードウェア上でのキャッシュにも適しています。たとえば、1 つのスレッドがノードを削除する場合、その後リストを読み取る他のすべてのコアに転送する必要がある唯一のメモリは、2 つの隣接するノードを含むメモリです。
これが話していることは、リンクされたリストが一度に複数のスレッドによって変更された場合 ( LinkedListJava ではサポートされていないもの)、変更されたリストのノードのみがキャッシュの一貫性を保つ必要があるということです。比較すると、ArrayList の途中または先頭にある要素を削除または追加する場合は、すべての参照を更新する必要があります。これは非効率的であることが知られているため、いずれにせよ避けるのが最善です。
これに最も近い Java の例はConcurrentLinkedQueue、同時追加と削除をサポートするものです。問題は、キャッシュに関して開始点と終了点を更新できることによって得られる利点が、このアクションがはるかに重要なゴミを作成するという事実によって失われることです。ただし、それでもそれほど重要ではありません。
ArrayBlockingQueue を使用すると、参照がメモリ内で連続しているため、キャッシュとガベージの動作が向上し、ArrayList のようにシャッフルする必要がなく、エントリを追加するためにガベージを作成しません。(残念ながらtake()オブジェクトを作成します:P)
于 2012-08-30T10:38:57.677 に答える