メモリ階層と性能
上の連結リストをたどる処理が、同じ数の要素をもつ配列を順に読むより大幅に遅くなりやすい理由はどれか。
struct node { int val; struct node *next; };
for (p = head; p != NULL; p = p->next)
sum += p->val;- A次の要素のアドレスが今の要素を読むまで分からず、ミスが1つずつ順番に起こるから
- B連結リストの要素はキャッシュに一切入らない決まりになっているから
- Cポインタを使う処理では、CPUの分岐予測が必ず失敗するから
答えと解説を見る
正解：A. 次の要素のアドレスが今の要素を読むまで分からず、ミスが1つずつ順番に起こるから
連結リストでは、次の要素のアドレスがp->nextを読んで初めて分かります。要素がメモリ上に散らばっているとアクセスのたびにミスが起こり、しかも次のアドレスが分からないので複数のミスを重ねられず、主記憶の待ち時間が1要素ごとにまるごと積み重なります。配列なら次のアドレスが計算で分かり、プリフェッチやミスの重ね合わせが働きます。連結リストの要素もキャッシュには入り、ループの分岐は予測しやすく必ず失敗するわけではありません。
- A. 正しい。次のアドレスが分からず、ミスの待ち時間が1つずつ積み重なります。
- B. 連結リストの要素もキャッシュに入ります。
- C. ループの分岐は規則的で、予測が必ず失敗するわけではありません。