記憶體階層與效能
走訪上述鏈結串列的處理，比讀取相同元素數量的陣列容易大幅變慢，其原因為下列何者？
struct node { int val; struct node *next; };
for (p = head; p != NULL; p = p->next)
sum += p->val;- A因為在讀取目前元素之前無法得知下一個元素的位址，未命中只能一個接一個依序發生
- B因為規定鏈結串列的元素完全不會進入快取
- C因為使用指標的處理一定會使CPU的分支預測失敗
查看答案與解析
正確答案：A. 因為在讀取目前元素之前無法得知下一個元素的位址，未命中只能一個接一個依序發生
在鏈結串列中，要讀取p->next之後才知道下一個元素的位址。若元素散布在記憶體上，每次存取都會發生未命中，而且因為不知道下一個位址，無法讓多個未命中重疊，主記憶體的等待時間會在每個元素上完整地累加。若是陣列，下一個位址可由計算得知，預取與未命中的重疊便能發揮作用。鏈結串列的元素同樣會進入快取，迴圈的分支也容易預測，並非一定失敗。
- A. 正確。無法得知下一個位址，未命中的等待時間會逐一累加。
- B. 鏈結串列的元素同樣會進入快取。
- C. 迴圈的分支有規律，預測並非一定失敗。