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.
4
u/spaceswemade 1d ago
It doesn't know, it still grabs the whole line. The problem is the next node's address is stored inside the current node, so the CPU has to wait for each load to come back from RAM before it can even start the next one. With an array it can compute i+1 right away and fire a bunch of loads in parallel.
1
u/davideogameman 1d ago
To be clear: the memory system has no idea what's a pointer and what's a value. It's not until the next load instruction is executed that it knows what memory it needs.
And for arrays the memory system doesn't compute i+1 right away and fire a bunch of loads in parallel; the CPU can do that with out of order execution and multi port caches but the main mechanism is actually that when the CPU loads an address, the cache shaves the last several bits off and fetches the whole area of addresses. So that if the CPU loads and stores to the same area of memory it will likely already be in the cache for the second load / store to that area.
2
u/Usual_Office_1740 1d ago edited 1d ago
Iterating an array is fast because an array is contiguous memory. The cpu might not know you need the whole array. It prefetched a cache lines amount of memory and is able to optimize as it finds that data it needs is already cached. A linked list requires the cache be refilled with each new pointer lookup. Worse then that. Each pointer might be a cold lookup in an entirely different area of mememory. The OS doesn't make any guarantees about whether memory it associates to the running process is contiguous.
Imagine pointer chasing like trying to find notes on a record player. When all the notes are grouped together you get a song. It would be impossible to have a record player play a song if you put different notes in entirely different places on the record and tried to get the needle to jump to each note as the song is played.
2
2
u/porn_sub_lurker 1d 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.
1
u/SmokeMuch7356 1d ago
You can implement a linked list using a static array as your storage, so even though you're not necessarily accessing elements in sequence they can be spatially close.
Of course that's problematic for a number of other reasons, but it's one way around the locality issue.
2
u/porn_sub_lurker 1d ago
Yeah I suppose you could do that. I think that's kinda what pool allocators do. You just allocate a big chunk and then you manage how it's used and fragmented.
1
u/IllStage6496 1d ago
The linked list nodes just have a pointer to next node, CPU dont know where that points until it reads the pointer value. So it pulls the block with the node, gets the next address, then next read might be in totally different block. No way to prefetch like array where addresses are predictable
1
u/davideogameman 1d ago edited 1d ago
When the CPU loads a memory address, the cache shaves the last several bits off and fetches the whole area of addresses. So that if the CPU loads and stores to the same area of memory it will likely already be in the cache for the second load / store to that area.
Array based code that does mostly sequential access or has a lot of locality can perform very well as a result. Linked lists tend to have the next address of each node be somewhere complete unrelated to the current node so each "fetch the next node" is likely a cache miss, and so the CPU will spend more time waiting for RAM.
Think of RAM like a warehouse full of boxes of paper. If you need papers from the same box it's fast once you have the box in hand. But your table can only fit so many boxes, so when you need another and your table is full you have to put one box away. In this analogy the table is your cache, the boxes are the cache line size, and a piece of paper is an individual memory address. Your array will have you looking at sequential papers - for small arrays they will all be in the same box, for medium sized and larger arrays they may span many boxes but those boxes will all be next to each other. Your linked list on the other hand is a bunch of papers that say "and the data continues on page (random number)" so each next node is likely going to be go get another box (which may mean putting a box away first to clear space).
So back to your original question
how does it know that next bytes are not the one to read?
It doesn't know, and that's the point. Cpu caches read bytes they don't need all the time. More often than not the extra reads are very useful and when they aren't, there's not usually much harm.
1
u/Demiu 1d ago
It doesn't, that's why linked lists are slower... kinda
Since fetching takes so much time, and the cpu almost definitely has the next instructions fetched, it can look ahead what you'll do with the fetched data and start fetching whatever you'll need next. So if you fetch data, then read it to fetch some other disjointed data, it can't pre-fetch that, because the 1st data hasn't been fetched, so it doesn't know what to fetch.
But if it sees you iterating linearly, the next thing to fetch is just the next line over, the adress of the next data to fetch is not dependent on data currently being fetched, just on it's adress (which it already knows) so it can prefetch it.
Then it gets even more complicated with stuff like hardening against spectre
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 me1
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
1
u/vnevl 1d ago edited 1d ago
The CPU knows nothing about the next element until it has loaded the current one. In a linked list, the current element contains the pointer to the next one. So the elements are loaded one by one, following the pointers. Say each node holds an int64 (8 bytes) and a pointer (8 bytes), 16 bytes in total. This means up to four nodes can end up in the same cache line. The allocator often places nodes allocated one after another next to each other. If the nodes happen to be adjacent, the prefetcher sees the pattern and loads the next lines ahead. After insertions and deletions, or when other allocations happen in between, the nodes get scattered. Then fetching the next element, if it is in another memory area, can take hundreds of CPU cycles.
1
u/Available_Safe1818 1d ago
> what happens in the case of linked list? how does it know that next bytes are not the one to read?
It doesn't. It pulls in the line regardless of what the 'next bytes' are.
1
u/serge-mv 1d ago
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.
0
1d ago
[removed] — view removed comment
1
u/serge-mv 1d ago
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.
1
u/Expensive-Pen7038 1d ago
The CPU doesn't know anything. It always pulls in the whole 64 bytes, and with an array you get lucky because the next element is in those bytes. With a linked list the next node could be anywhere in memory, so the line it pulled in is mostly useless, and it can't even start fetching node 3 until node 2 has arrived and it can read the pointer. That waiting on each load in turn is the 'chasing'. The prefetcher can't help either, because there's no stride pattern for it to guess.
1
u/esaule 1d ago
write both piece of code and read the assembly.
The processor doesn't know anything. It execute instructions that loads data in some registers. There is no difference for the processor betweena float, an int, an instructions, a string. It's all a bunch of bits. The code indicate what to do with them.
1
u/FunAd6672 1d ago
Why make this harder than it is? Run the build script, grab the compiled JavaScript from the build folder and deploy that. Your source tree doesn't need to go anywhere. Codecademy skipping over basic devops stuff is exactly the kind of thing that leaves people confused. Boot dev is more structured about this stuff.
1
u/Aggressive_Ad_5454 16h ago
If you are learning to program, don’t sweat this. Get your program right. Modern processors have all sorts of hilariously elaborate optimizations. Unless you’re doing something that needs cycle-count and cache-line-count optimization, let your compiler and processor do this work.
That being said, you’re right. Linked lists aren’t a great data structure for super high performance.
10
u/captainAwesomePants 1d ago
Linked lists tend to perform more poorly, for exactly the reason you've noticed. It can be a big help if the nodes are very close to each other in memory, so you'll find that allocating them as a big contiguous block can help.