Memory Hierarchy
Why does traversing the linked list above tend to be much slower than reading an array with the same number of elements in order?
struct node { int val; struct node *next; };
for (p = head; p != NULL; p = p->next)
sum += p->val;- AThe next element's address is unknown until the current one is read, so misses occur one after another
- BLinked-list elements are, by rule, never placed in the cache
- CThe CPU's branch prediction always fails in code that uses pointers
Show answer and explanation
Answer: A. The next element's address is unknown until the current one is read, so misses occur one after another
In a linked list the next element's address is known only after reading p->next. If elements are scattered in memory, each access misses, and since the next address is unknown, misses cannot overlap, so the full memory latency piles up element by element. With an array the next address can be computed, so prefetching and overlapping misses work. Linked-list elements are cached like any data, and the loop branch is predictable rather than always mispredicted.
- A. Correct. The next address is unknown, so miss latencies accumulate one by one.
- B. Linked-list elements are cached like any other data.
- C. The loop branch is regular, and prediction does not always fail.