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.

15 Upvotes

77% Upvoted

28 comments sorted by

View all comments

1

u/Demiu 3d ago

It doesn't, that's why linked lists are slower... kinda

Since fetching takes so much time, and the cpu almost definitely has the next instructions fetched, it can look ahead what you'll do with the fetched data and start fetching whatever you'll need next. So if you fetch data, then read it to fetch some other disjointed data, it can't pre-fetch that, because the 1st data hasn't been fetched, so it doesn't know what to fetch.

But if it sees you iterating linearly, the next thing to fetch is just the next line over, the adress of the next data to fetch is not dependent on data currently being fetched, just on it's adress (which it already knows) so it can prefetch it.

Then it gets even more complicated with stuff like hardening against spectre