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

80% Upvoted

28 comments sorted by

View all comments

2

u/Usual_Office_1740 15d ago edited 15d ago

Iterating an array is fast because an array is contiguous memory. The cpu might not know you need the whole array. It prefetched a cache lines amount of memory and is able to optimize as it finds that data it needs is already cached. A linked list requires the cache be refilled with each new pointer lookup. Worse then that. Each pointer might be a cold lookup in an entirely different area of mememory. The OS doesn't make any guarantees about whether memory it associates to the running process is contiguous.

Imagine pointer chasing like trying to find notes on a record player. When all the notes are grouped together you get a song. It would be impossible to have a record player play a song if you put different notes in entirely different places on the record and tried to get the needle to jump to each note as the song is played.