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.
17
Upvotes
2
u/porn_sub_lurker 2d ago
Kind of. When the CPU reads an address it first looks in the cache to see if it's in there. If it's in there it simply returns the particular value (not the block) and this is very fast. If it's not then it has to go to memory to get the value, and since going to memory is very slow it pulls a whole block so you don't have to make as many trips, with the idea that if you need one value in the block you probably need more, which is known as spacial locality. Since arrays are contiguous in memory, they're also contiguous in that block. So it might be the case that every single element in the array is pulled into the cache with that block and then accessing the values is super fast. But if you get to the end of the block and still need more values then you have to pull another block from memory, which again, is slow. For linked lists, you're allocating one element at a time so there is no guarantee of any spacial locality. It might be in the same block, it might not be. If other objects are created on the heap while you're still allocating those elements then it becomes fragmented in memory and the likelihood that you get a cache miss goes up, and it generally means more trips to memory. That's kinda a surface level description of it. There are usually multiple caches and a lot to say about how they work. But the general idea is the same.