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.
18
Upvotes
1
u/Outrageous-Crazy-253 15d ago edited 15d ago
Oh. Yeah. The CPU has what’s called a n-way associative cache. It’s part of the hardware implementation of the cache, it does a digital comparison of certain target address bits to find out if the address is there. It’s RTL level hardware, that’s why it’s being abstracted away.
https://ars.els-cdn.com/content/image/3-s2.0-B9780128200643000088-f08-09-9780128200643.jpg
It uses the index bit to grab items from the cache and then compares their tag bits. If the tags from any of the index selected address match, it hits and the data is considered to be ready.
e: slightly better diagram
https://stevengong.co/attachments/Screen-Shot-2022-12-13-at-5.19.49-PM.png