Why does pointer chasing hurt cache performance?

November 16, 2026 3 answers
Asked by 8e~puddlecompass_475

I understand that walking an array can use several elements from one cache line. What happens when walking a linked list? Does the CPU know that the next node might be somewhere else?

Answers

_n74!dialpocket.3

The CPU still fetches a whole cache line when it needs data that isn't already in cache. It doesn't fetch just the linked list node, and it doesn't know from the line itself which bytes are useful.

The code reads the current node's next pointer and then uses that value as the address for another load. If the next node is on a different line that isn't cached, that load can miss too. An array usually gets more use out of each line because neighboring elements are stored together.

8e~puddlecompass_475:

So how does it tell a pointer from an ordinary value?

_p53!granitewhisk.8:

The cache doesn't need to label the bytes as pointers or values. The instructions decide how to use the bits that were loaded, including whether to use them as an address for another load.

Reply to this answer
_basilisk!notebook

There's a second issue beyond wasted space in cache lines. In a normal linked list traversal, you can't know the address of the next node until you've read the pointer in the current one. If each node misses in cache, those waits can stack up one after another.

With a sequential array, later addresses are predictable. Hardware prefetching and out of order execution can sometimes get data on its way before the program needs it. The exact benefit depends on the CPU and the code, but a chain of dependent loads gives it less room to look ahead.

Reply to this answer
7j!foldratchet_283

Linked lists can absolutely be cached. The nodes might already be in cache, or several small nodes might share a line. Allocating nodes close together can help, though it doesn't guarantee that following the links will visit them in memory order.

If traversal speed matters, contiguous storage such as an array is worth considering. You can also store nodes in an array and link them by index, but the access order still matters for locality.

Reply to this answer

Add your answer

Answers are reviewed before publication.

Related Discussions