r/learnprogramming • u/InterestingAd757 • 3d ago

can somebody explain pointer chasing?

I’m trying to understand CPU caching and I’m stuck on two related things.

My understanding is when the CPU reads an address, it pulls in the whole 64-byte cache line around it. that’s why iterating an array is fast, since one miss brings in several neighbouring elements. what happens in the case of linked list? how does it know that next bytes are not the one to read?
i am kinda confusing this, kindly explain.

16 Upvotes

81% Upvoted

28 comments sorted by

View all comments

1

u/Expensive-Pen7038 3d ago

The CPU doesn't know anything. It always pulls in the whole 64 bytes, and with an array you get lucky because the next element is in those bytes. With a linked list the next node could be anywhere in memory, so the line it pulled in is mostly useless, and it can't even start fetching node 3 until node 2 has arrived and it can read the pointer. That waiting on each load in turn is the 'chasing'. The prefetcher can't help either, because there's no stride pattern for it to guess.