[解決済み] なぜキャッシュの局所性がアレイの性能に影響するのか？

質問

次のような ブログ には、リンクリストに対する配列の優位性についての記述があります。

配列はより良いキャッシュの局所性を持っており、パフォーマンスにおいてかなり大きな違いを生み出すことができます。

どういう意味ですか？キャッシュの局所性がどのように大きなパフォーマンス上の利点をもたらすのか理解できないのですが。

どのように解決するのですか?

私の回答を参照してください。 空間的および時間的な局所性について .

特に、配列は連続したメモリブロックなので、大きな塊は最初のアクセスでキャッシュにロードされます。 このため、配列の将来の要素にアクセスするのが比較的速くなります。 一方、リンクリストは必ずしも連続したメモリブロックではないので、キャッシュミスが多くなる可能性があり、アクセスにかかる時間が長くなります。

以下のような配列のメモリレイアウトを考えてみましょう。 data とリンクされたリスト l_data 大きな構造体の

Address      Contents       | Address      Contents
ffff 0000    data[0]        | ffff 1000    l_data
ffff 0040    data[1]        |   ....
ffff 0080    data[2]        | ffff 3460    l_data->next
ffff 00c0    data[3]        |   ....
ffff 0100    data[4]        | ffff 8dc0    l_data->next->next
                            | ffff 8e00    l_data->next->next->next
                            |   ....
                            | ffff 8f00    l_data->next->next->next->next

この配列をループする場合、最初のアクセスは ffff 0000 への最初のアクセスでは、メモリにアクセスして取り出す必要があります（CPU サイクルでは非常に遅い処理です）。 しかし、最初のアクセスの後、配列の残りの部分はキャッシュに格納され、その後のアクセスははるかに速くなります。 リンクリストの場合、最初のアクセスは ffff 1000 への最初のアクセスも、メモリに移動する必要があります。 残念ながら、プロセッサはこの場所を直接囲むメモリをキャッシュし、例えば ffff 2000 . 見ての通り、これは実際にはリストの他のどの要素も捕捉しません。 l_data->next にアクセスしようとすると、またもやメモリにアクセスしなければならないことになります。