82

次のブログには、リンクリストに対する配列の利点に関する記述があります。

アレイのキャッシュの局所性は優れているため、パフォーマンスにかなり大きな違いが生じる可能性があります。

どういう意味ですか？キャッシュの局所性がパフォーマンスに大きなメリットをもたらす方法がわかりません。

4

2 に答える 2

125

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

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

大きな構造体の配列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、再びメモリに移動する必要があります。

于 2012-08-22T03:00:10.853 に答える
14

通常、配列を使用する場合は、互いに近いアイテムにアクセスします。これは、アレイに順番にアクセスする場合に特に当てはまります。

メモリにアクセスすると、そのチャンクがさまざまなレベルでキャッシュされます。 キャッシュの局所性とは、連続する操作がキャッシュ内にあり、したがってより高速である可能性を指します。配列では、シーケンシャル要素アクセスがキャッシュ内にある可能性を最大化します。

リストの場合、反例として、リストに順番に表示されるアイテムが実際にメモリ内で互いに近くに配置されるという保証はありません。これは、キャッシュヒットが少なくなり、パフォーマンスが低下することを意味します。

于 2012-08-22T03:01:17.630 に答える