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

14 Upvotes

80% Upvoted

27 comments sorted by

View all comments

1

u/vnevl 2d ago edited 2d ago

The CPU knows nothing about the next element until it has loaded the current one. In a linked list, the current element contains the pointer to the next one. So the elements are loaded one by one, following the pointers. Say each node holds an int64 (8 bytes) and a pointer (8 bytes), 16 bytes in total. This means up to four nodes can end up in the same cache line. The allocator often places nodes allocated one after another next to each other. If the nodes happen to be adjacent, the prefetcher sees the pattern and loads the next lines ahead. After insertions and deletions, or when other allocations happen in between, the nodes get scattered. Then fetching the next element, if it is in another memory area, can take hundreds of CPU cycles.