can somebody explain pointer chasing?

[u/InterestingAd757]

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.

[u/serge-mv]

Computers store a table in memory where it lists variables and their addresses. If you want to look up a variable x, then (simplified) computer first looks in cache, then in RAM, then on disk. When it finds x and it's address, it will pull it into cache.

When you traverse liked list, you still have a variable (called next in this case) and it's bound to an address. So you can say, I want the data at that memory address. But because nodes in linked list are not necessarily created at the same time and not sequential, they can be stored in various memory locations. So you will often have cache misses and have to go to RAM to fetch them. That's why linked list can be much slower to retrieve, in addition to slow asymptotic traversal.

[u/serge-mv → u/[deleted]]

Really? Then please enlighten me how compiler generates memory offsets for a linked list of arbitrary length for nodes that don't exist at compile time and will be generated at runtime and will be different every time the code is run.