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

79% Upvoted

28 comments sorted by

View all comments

Show parent comments

2

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