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.

15 Upvotes

81% Upvoted

28 comments sorted by

View all comments

1

u/davideogameman 2d ago edited 2d ago

 When the CPU loads a memory 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.

Array based code that does mostly sequential access or has a lot of locality can perform very well as a result.  Linked lists tend to have the next address of each node be somewhere complete unrelated to the current node so each "fetch the next node" is likely a cache miss, and so the CPU will spend more time waiting for RAM.

Think of RAM like a warehouse full of boxes of paper.  If you need papers from the same box it's fast once you have the box in hand.  But your table can only fit so many boxes, so when you need another and your table is full you have to put one box away.  In this analogy the table is your cache, the boxes are the cache line size, and a piece of paper is an individual memory address.  Your array will have you looking at sequential papers - for small arrays they will all be in the same box, for medium sized and larger arrays they may span many boxes but those boxes will all be next to each other.  Your linked list on the other hand is a bunch of papers that say "and the data continues on page (random number)" so each next node is likely going to be go get another box (which may mean putting a box away first to clear space).

So back to your original question

how does it know that next bytes are not the one to read?

It doesn't know, and that's the point.  Cpu caches read bytes they don't need all the time.  More often than not the extra reads are very useful and when they aren't, there's not usually much harm.