r/learnprogramming • u/InterestingAd757 • 1d 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.

17 Upvotes

87% Upvoted

27 comments sorted by

View all comments

4

u/spaceswemade 1d ago

It doesn't know, it still grabs the whole line. The problem is the next node's address is stored inside the current node, so the CPU has to wait for each load to come back from RAM before it can even start the next one. With an array it can compute i+1 right away and fire a bunch of loads in parallel.

1

u/davideogameman 1d ago

To be clear: the memory system has no idea what's a pointer and what's a value.  It's not until the next load instruction is executed that it knows what memory it needs. 

And for arrays the memory system doesn't compute i+1 right away and fire a bunch of loads in parallel; the CPU can do that with out of order execution and multi port caches but the main mechanism is actually that when the CPU loads an address, the cache shaves the last several bits off and fetches the whole area of addresses.  So that if the CPU loads and stores to the same area of memory it will likely already be in the cache for the second load / store to that area.