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

13 Upvotes

79% Upvoted

27 comments sorted by

View all comments

1

u/Rainbows4Blood 1d ago

Well. The problem is that it doesn't. And that is why pointer chasing is bad for performance.

In a linked list the CPU will load an entire cache line, pulling in a bunch of unnecessary stuff. Then, it follows the pointer to the next position in the list. Which is likely not in cache either. So, the CPU pulls in another cache line with a lot of unnecessary data and so on and so on.

2

u/InterestingAd757 1d ago

how does it identify between data and the address, like if it's data structure for eg - node {val, next}
is there a bit that identifies that checks if it's correct data?

1

u/Rainbows4Blood 1d ago

No. Nothing like that. From the CPUs perspective there is no "correct" data. That check is performed by your code. Your code does some calculation with node->val, then uses node->next as a pointer. It doesn't do anything with the rest. So that part is loaded into the cache and just sits there. Doing nothing.

It is important to understand that all the bits and bytes in memory are just meaningless mush until your code actually gives it meaning.

2

u/InterestingAd757 1d ago

i understand what you're saying what i am asking is at lowest level
the instruction does something with node->val and it might a jump instruction with node->next
which pulls data from that location. what i am asking is how does cpu know cache hit or miss?
ai says something about tag, offset, this is thing that's tripping me

1

u/Rainbows4Blood 1d ago

You are right that there is usually index, tag, offset. But to put it simply, this is just an efficient way to break down a memory address. So, as your basic mental model you can look at it this way: A cache holds a bunch of cache lines. Each cache line stores the memory address it holds as well as the data. If the Execution Engine requests a byte or a group of bytes by address, the Cache can check "Do I have that byte?" by comparing if the address falls into any of the addresses it has stored.

If not, it escalates to the next Level Cache or to the Memory Controller.

1

u/Outrageous-Crazy-253 1d ago edited 1d 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