What you say about the stack being faster than the heap is not really true. In both cases you're doing a memory access, it doesn't matter whether the target address is read from %esp or from some other location. The only speed difference there could be based on whether the target memory page is cached or not, but the stack is not any faster per se than the heap. And in both case there's still the same exact "lookup" (dereference).
The stack is surely finite in size and more limited, but the size of the stack at any given point doesn't need to be constant at all. Programs can allocate arbitrary temporary buffer on the stack just fine. After all, all you're really doing is to just add/subtract an offset to %esp.
When you say you can read values from the top of the stack, I'd also add the fact that functions actually read any value from the local stack frame at any offset. The stack is not literally a FIFO: you can both push values as well as reading/writing to any of the existing values. Again, it's just a read/write to %esp + offset.
Same thing about the heap being slower, like in point 1). I think you should clarify that what's slow is the allocation process (and the GC tracking on managed languages), but the actual dereferencing is just as fast as the stack.
I'm not sure the phrasing is optimal when you say you can have "out of memory errors if your application tries to use more memory than the allocated heap". Out of memory exceptions errors arise when you have not enough space in the current addressing space to perform an operation, before actually allocating memory on the heap. For instance, if you're trying to allocate a block of a size such that there is not a large enough address range in the address space. But it's not like the heap is "allocated" from the start. It's just a segment in the virtual address space of a process. It might very well be possible that the same operation that failed could have instead been completed successfully if the allocated pages in the heap had been compacted beforehand.
I want to repeat it, the article is very well written and you did a great job, I'm just giving you my 2 cents here about a couple of details I noticed.
Thank you for the detailed feedback. I really appreciate it. Before I respond, let me put on a disclaimer 😉 I'm not a computer memory expert(I do not have a computer science background, I'm an electrical engineering major) so please bear with me.
Some of your points contradict what I have learned and what the language documentation regarding these concepts says. But I'm interested in learning more about your point of view, would you be kind enough to share some resources which detail these further, especially point 1 & 3.
Now, based on what I have learned and researched:
If we talk about absolute speed in terms of nanoseconds or less, the stack access should be faster than the heap access for various reasons. Heap is generally fragmented and the process needs to get a pointer address from the stack and look that up from the fragmented heap space. Some languages optimize the fragmentation during GC to reduce overhead. The same overhead is also present during normal operation though that is negligible. Now, to access from stack no pointer lookup is required as you just need to look at the block on top of the stack. So in terms of absolute speed, there is a difference as you need to get a pointer from the stack and fetch it from the heap. But I guess the difference is pretty negligible given the speed of the current hardware we have. Correct me if I'm wrong here, and would appreciate some resource explaining that.
Agree, and I believe I never said that this is not possible, I just said that any data stored on the stack must be finite in size(known at compile-time, hence no growing strings for example.
Well, this contradicts every definition of a stack I have seen, and so far I never found any resource which says that the stack memory is not FIFO. My understanding was that in order to read from the stack you need to pop it first. Now entire stack frames are pushed/popped and treated like individual blocks I believe and hence a function can read/write all its local values in any order in this block space, is that what you mean? If not, could you give me some reference explaining this in more detail?
same as 1, I'll update the post to say that I'm talking about the process of accessing the data on the heap and not heap itself, which I agree cannot be slower than stack as it's on the same RAM.
Agree, I think what I wrote might not be very generic and could have implications based on implementations used by the language as well. For example, in Java, you used to have the ability to control the max space that can be used for Heap and my point was more from such an angle. But you are right there are lot more factors to take into account. I'll try to explain more clearly in upcoming chapters so that it's more specific to how particular language behaves.
Again thank you very much for the detailed response. Look forward to learning more. I'll update the post to make some points clearer, let me know if you find it to be better
Hey, no problem, glad I could help, and I'm always interested in sparking up a discussion where everyone can hopefully learn something new 😄
To reply to your points:
Stack and heap are just two segments in the virtual address space of a process. They only real difference is the range of addresses they use, but they're fundamentally exactly the same: a given area in the virtual address space. Hence, the access time is exactly the same: in both case you'd still be dereferencing a pointer. I think you might be confusing what you see in a high level language (like Java, or even C) with what is actually happening at the hardware level (I mean in assembly). Even if you have a local value type variable in a function in Java, when you read it the CPU will still use a pointer to read it from the stack. The only difference is that the address in this case is automatically calculated by adding a certain offset to the %esp register, which is a CPU register that always points to the top of the stack. Whereas with an object in the heap you'd be manually keeping track of the reference to it (either via a raw pointer in C#, or through a managed pointer in a managed language like Java). The GC doesn't have anything to do with this, nor does the possible fragmentation of the heap itself. The moment you're trying to read any value from your virtual address space you're always going to just load a pointer to your target location (be it in the heap or the stack) and then dereference it. Actually, in assembly it's even the same exact instruction (mov, in general) - the CPU doesn't really care what segment that address belong to at all. What's more, in many languages (eg. C, C++, C#) you can even get pointers to local variables on the stack, and pass those to functions. Once you're inside a function, that function can't possibly know (nor does it care either) whether that pointer actually points to a variable in the heap or the stack, but again, that doesn't matter. It's the same exact behavior, and the speed is the same too. As I've mentioned, the heap is generally considered slower because people associate the actual allocation cost to it, and the garbage collection cost. But just reading/writing data to it is equally as fast as doing so on the stack.
I agree that the data on the stack must be finite in size (though the same could be said for the heap as well, the limit is just bigger but it's still finite), my point was that you don't need to know at compile time the amount of data stored on the stack at all. You could very much have a function that takes an int and then allocates a buffer of int on the stack, with a length equal to that input int. In that case you'd have absolutely no way of knowing the size of that buffer at compile time, and yet the buffer is created on the stack just fine.
Sure thing, you can read up here for instance. The stack is generally referred to as LIFO since that's the way new values are pushed and popped to it, including stack frames during function calls, but as I said you can actually read/write at any position in the stack at all times. There's a CPU register called %esp (Stack Pointer) which keeps the address to the top of the stack, and you can index any position in the stack by just adding an offset to that address and dereferencing it. For instance, consider this function and the resulting assembly x86:
// C codeintsumFour(inta,intb,intc,intd){returna+b+c+d;}// asm x86sumThree(Int32,Int32,Int32)0000:addedx,ecx// b += a0002:moveax,edx// Move b in %eax0004:addeax,[esp+0x8]// %eax += c0008:addeax,[esp+0x4]// %eax += d000c:ret
You can see that while the compiler is passing the a and b parameter through the ecx and edx registers to minimize memory access, the c and d parameters are passed through the stack, and they're being read with that [esp+0x4] and [esp+0x8] addresses, which are not the top of the stack. This happens all the time, eg. when you have many local parameters in a function that can't all fit in a register and need to be stored on the stack (which is much slower). Point is: you can read/write from any position within the stack with no problems, you're absolutely not limited to just the top value.
Hope this helps, let me know if there's anything else! 😄
Hey, thanks for the quick response. Actually I updated my comment above as I made a mistake there, right before you added this reply, could you take a look? I'll respond to this once you have seen the update to avoid any confusion.
I guess you are talking from a lower level, like assembly, point of view and I'm talking from a high-level language point of view.
Agree at a low level that it would be same, but since I'm talking about how languages handle memory, I think accessing Heap is still slower than accessing Stack at language level, might not be by much, but even if you count by instructions, it still has to do few more steps to read from heap compared to stack. Even a low-level language like Rust, for example, says the same. See this doc.rust-lang.org/1.30.0/book/firs...
The stack is very fast, and is where memory is allocated in Rust by default. But the allocation is local to a function call, and is limited in size. The heap, on the other hand, is slower, and is explicitly allocated by your program. But it’s effectively unlimited in size, and is globally accessible.
I'm talking about individual data(variables & constants) and it has to be finite at compile time for most languages(Java, Rust, Go, etc) to be on Stack and you cannot have buffers on the stack in these and since the language automatically manages these we have no control over this. I guess C/C++ is an exception when you manage memory yourself, but then again they are very low-level languages. So yes this is very much language-dependent I would say but holds for most languages IMO.
Yes, it makes absolute sense at a low level. At a higher level, its easier to talk of it as LIFO though as the inner process is not exposed to end users in most languages
The statement about the stack not being faster than the heap is only in the fact that at the moment you have the address, the time to read/write is the same. The problem is that semantically, the stack addresses are known (through the Stack Pointer and Frame Pointer as well). As the author said, there is no such thing as a Heap Pointer (it just doesn't make sense). In that regard, let's say we have 2 integers in C like this:
int a = 3;
int *b;
b = malloc(sizeof(int));
*b = 4;
First of all, it is clear that creating an element in the stack is way faster than the heap since malloc needs to find a place to put the continuous 32-bits (or 64-bits) free memory. This is because the stack just needs to look up the Stack pointer, add the element and move the stack pointer accordingly.
After that, modifying an element in the stack is easy since it is basically an offset of the Stack pointer. But for the heap, first, you need to find the pointer in the stack, from that pointer you get the address in the heap and then you can read or write at that address.
And I didn't talk about the difference between reading address by offset vs full address since a lot of CPU have instruction sets that are too small to handle the full address in one instruction.
In conclusion, Stack is faster than Heap only because of the Stack Pointer.
I believe there has been a misunderstanding here. If you go back and read my original comment, I've made it clear that when I said the stack was equally as fast as the heap, it was in direct read/write operations to a memory location in either of those two segments. You can't compare a read/write to a local value type variable to one to a reference variable, for obvious reasons - those are handled differently. And you can't take the overhead of a malloc call into consideration, or the garbage collection cost, that was completely besides my point, and I did mention that in my original message.
What I said was that reading or writing to a specific memory location has always the same performance, regardless of whether that memory location is situation, be it in the stack or the heap.
As a practical example. Suppose you allocate a buffer of int values on the stack, and one on the heap, and end up with two int* pointers. One points to the buffer in the stack, one in the heap. If you read/write to any of those two pointers, the operation will be exactly the same down to the assembly level, and the performance will be exactly the same too.
As another example, suppose you have a local value type variable, and you pass it by reference to another function. That function will have no way of knowing whether that reference points to a variable in some other stack frame, or to a memory location in the heap, and that makes absolutely no difference at all. Again, both cases are compiled to exactly the same instructions, it's just a pointer of some type anyway.
In conclusion, the speed of an operation is not intrinsically linked to where a value is located in the virtual memory address space, but just to how you're accessing that location.
I hope this clears things up regarding my original point on that 👍
EDIT: just to clarify, you do have a pointer lookup in both cases though. If you have a pointer to a heap location eg. in %ecx and want to read that value, you'll do movl eax, [ecx]. If you want to read the value at the top of the stack, you'll do movl eax, [esp]. In both cases the operation is exactly the same and you do have an address lookup just the same. So you saying that you never look addresses up when accessing the stack is just not the case. You're correct in saying that if you have a pointer on the heap stored on the stack you need two dereferences there, sure. But even in the best case scenario on the stack, you still need at least one anyway. And if you have a pointer in a given register, reading from that location has exactly the same cost no matter if it points to somewhere in the heap or the stack.
Your last edit is exactly the point, from a language point we care about cost of operation when we talk about speed, and the cost of operation for the stack is lower than heap and that is why we say stack is faster than the heap. The actual speed of writing/reading from any part of memory indeed is the same but for heap, there are more operations involved than stack when writing/reading value making the cost of operation higher for the heap.
Suppose you allocate a buffer of int values on the stack, and one on the heap, and end up with two int* pointers.
That is not true, since in the stack everything is offset of the stack pointer that is in the CPU registers. So, for example in ARM CPUs, it will take something like 3 instructions to retrieve any of the int in the buffer sitting in the stack. On the situation of the one on the heap, the first element will take something like 4 instructions since you need to set a register with the address you will find on the stack (the pointer of your heap buffer), and AFTER the other elements will be read AS FAST AS the stack since the other int element of the buffer are an offset of that value. And like I said earlier, if you have the address as a label, you will need 2 instructions to set your register before LDR/STR that memory block.
I think what you are trying to say is that at the time you have the address loaded in a register, the read time will be the same, which is true. The danger is that people might believe it is always the best solution to use the heap since it is so large, but doesn't account for the way it is handled. Embedded systems are very sensitive to this considering low frequency (very so often below 100 MHz), no OS and small memory footprint. The good practice, in that case, is only to use the heap with object allocated at startup so there is NO malloc anywhere, making sure the system stays deterministic. I know that in a 12-core i9 CPU clocks at 4GHz, the impact on most of the system people work (except OS for that matter, or video games) will be so negligible.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Nice article! 😊
I'll just throw in a couple feedbacks:
%espor from some other location. The only speed difference there could be based on whether the target memory page is cached or not, but the stack is not any faster per se than the heap. And in both case there's still the same exact "lookup" (dereference).%esp.%esp + offset.I want to repeat it, the article is very well written and you did a great job, I'm just giving you my 2 cents here about a couple of details I noticed.
Cheers!
Thank you for the detailed feedback. I really appreciate it. Before I respond, let me put on a disclaimer 😉 I'm not a computer memory expert(I do not have a computer science background, I'm an electrical engineering major) so please bear with me.
Some of your points contradict what I have learned and what the language documentation regarding these concepts says. But I'm interested in learning more about your point of view, would you be kind enough to share some resources which detail these further, especially point 1 & 3.
Now, based on what I have learned and researched:
If we talk about absolute speed in terms of nanoseconds or less, the stack access should be faster than the heap access for various reasons. Heap is generally fragmented and the process needs to get a pointer address from the stack and look that up from the fragmented heap space. Some languages optimize the fragmentation during GC to reduce overhead. The same overhead is also present during normal operation though that is negligible. Now, to access from stack no pointer lookup is required as you just need to look at the block on top of the stack. So in terms of absolute speed, there is a difference as you need to get a pointer from the stack and fetch it from the heap. But I guess the difference is pretty negligible given the speed of the current hardware we have. Correct me if I'm wrong here, and would appreciate some resource explaining that.
Agree, and I believe I never said that this is not possible, I just said that any data stored on the stack must be finite in size(known at compile-time, hence no growing strings for example.
Well, this contradicts every definition of a stack I have seen, and so far I never found any resource which says that the stack memory is not FIFO. My understanding was that in order to read from the stack you need to pop it first. Now entire stack frames are pushed/popped and treated like individual blocks I believe and hence a function can read/write all its local values in any order in this block space, is that what you mean? If not, could you give me some reference explaining this in more detail?
same as 1, I'll update the post to say that I'm talking about the process of accessing the data on the heap and not heap itself, which I agree cannot be slower than stack as it's on the same RAM.
Agree, I think what I wrote might not be very generic and could have implications based on implementations used by the language as well. For example, in Java, you used to have the ability to control the max space that can be used for Heap and my point was more from such an angle. But you are right there are lot more factors to take into account. I'll try to explain more clearly in upcoming chapters so that it's more specific to how particular language behaves.
Again thank you very much for the detailed response. Look forward to learning more. I'll update the post to make some points clearer, let me know if you find it to be better
Hey, no problem, glad I could help, and I'm always interested in sparking up a discussion where everyone can hopefully learn something new 😄
To reply to your points:
Stack and heap are just two segments in the virtual address space of a process. They only real difference is the range of addresses they use, but they're fundamentally exactly the same: a given area in the virtual address space. Hence, the access time is exactly the same: in both case you'd still be dereferencing a pointer. I think you might be confusing what you see in a high level language (like Java, or even C) with what is actually happening at the hardware level (I mean in assembly). Even if you have a local value type variable in a function in Java, when you read it the CPU will still use a pointer to read it from the stack. The only difference is that the address in this case is automatically calculated by adding a certain offset to the
%espregister, which is a CPU register that always points to the top of the stack. Whereas with an object in the heap you'd be manually keeping track of the reference to it (either via a raw pointer in C#, or through a managed pointer in a managed language like Java). The GC doesn't have anything to do with this, nor does the possible fragmentation of the heap itself. The moment you're trying to read any value from your virtual address space you're always going to just load a pointer to your target location (be it in the heap or the stack) and then dereference it. Actually, in assembly it's even the same exact instruction (mov, in general) - the CPU doesn't really care what segment that address belong to at all. What's more, in many languages (eg. C, C++, C#) you can even get pointers to local variables on the stack, and pass those to functions. Once you're inside a function, that function can't possibly know (nor does it care either) whether that pointer actually points to a variable in the heap or the stack, but again, that doesn't matter. It's the same exact behavior, and the speed is the same too. As I've mentioned, the heap is generally considered slower because people associate the actual allocation cost to it, and the garbage collection cost. But just reading/writing data to it is equally as fast as doing so on the stack.I agree that the data on the stack must be finite in size (though the same could be said for the heap as well, the limit is just bigger but it's still finite), my point was that you don't need to know at compile time the amount of data stored on the stack at all. You could very much have a function that takes an
intand then allocates a buffer ofinton the stack, with a length equal to that inputint. In that case you'd have absolutely no way of knowing the size of that buffer at compile time, and yet the buffer is created on the stack just fine.Sure thing, you can read up here for instance. The stack is generally referred to as LIFO since that's the way new values are pushed and popped to it, including stack frames during function calls, but as I said you can actually read/write at any position in the stack at all times. There's a CPU register called
%esp(Stack Pointer) which keeps the address to the top of the stack, and you can index any position in the stack by just adding an offset to that address and dereferencing it. For instance, consider this function and the resulting assembly x86:You can see that while the compiler is passing the
aandbparameter through theecxandedxregisters to minimize memory access, thecanddparameters are passed through the stack, and they're being read with that[esp+0x4]and[esp+0x8]addresses, which are not the top of the stack. This happens all the time, eg. when you have many local parameters in a function that can't all fit in a register and need to be stored on the stack (which is much slower). Point is: you can read/write from any position within the stack with no problems, you're absolutely not limited to just the top value.Hope this helps, let me know if there's anything else! 😄
Hey, thanks for the quick response. Actually I updated my comment above as I made a mistake there, right before you added this reply, could you take a look? I'll respond to this once you have seen the update to avoid any confusion.
I've seen the updates, but what I said in my last comment still applies, so it's fine, you can go ahead and read/reply to that one if you want 😊
Thanks again. I did learn something new now.
I guess you are talking from a lower level, like assembly, point of view and I'm talking from a high-level language point of view.
I'm talking about individual data(variables & constants) and it has to be finite at compile time for most languages(Java, Rust, Go, etc) to be on Stack and you cannot have buffers on the stack in these and since the language automatically manages these we have no control over this. I guess C/C++ is an exception when you manage memory yourself, but then again they are very low-level languages. So yes this is very much language-dependent I would say but holds for most languages IMO.
Yes, it makes absolute sense at a low level. At a higher level, its easier to talk of it as LIFO though as the inner process is not exposed to end users in most languages
The statement about the stack not being faster than the heap is only in the fact that at the moment you have the address, the time to read/write is the same. The problem is that semantically, the stack addresses are known (through the Stack Pointer and Frame Pointer as well). As the author said, there is no such thing as a Heap Pointer (it just doesn't make sense). In that regard, let's say we have 2 integers in C like this:
First of all, it is clear that creating an element in the stack is way faster than the heap since
mallocneeds to find a place to put the continuous 32-bits (or 64-bits) free memory. This is because the stack just needs to look up the Stack pointer, add the element and move the stack pointer accordingly.After that, modifying an element in the stack is easy since it is basically an offset of the Stack pointer. But for the heap, first, you need to find the pointer in the stack, from that pointer you get the address in the heap and then you can read or write at that address.
And I didn't talk about the difference between reading address by offset vs full address since a lot of CPU have instruction sets that are too small to handle the full address in one instruction.
In conclusion, Stack is faster than Heap only because of the Stack Pointer.
This is what I have been trying to say, but I think you said it better :)
I believe there has been a misunderstanding here. If you go back and read my original comment, I've made it clear that when I said the stack was equally as fast as the heap, it was in direct read/write operations to a memory location in either of those two segments. You can't compare a read/write to a local value type variable to one to a reference variable, for obvious reasons - those are handled differently. And you can't take the overhead of a
malloccall into consideration, or the garbage collection cost, that was completely besides my point, and I did mention that in my original message.What I said was that reading or writing to a specific memory location has always the same performance, regardless of whether that memory location is situation, be it in the stack or the heap.
As a practical example. Suppose you allocate a buffer of
intvalues on the stack, and one on the heap, and end up with twoint*pointers. One points to the buffer in the stack, one in the heap. If you read/write to any of those two pointers, the operation will be exactly the same down to the assembly level, and the performance will be exactly the same too.As another example, suppose you have a local value type variable, and you pass it by reference to another function. That function will have no way of knowing whether that reference points to a variable in some other stack frame, or to a memory location in the heap, and that makes absolutely no difference at all. Again, both cases are compiled to exactly the same instructions, it's just a pointer of some type anyway.
In conclusion, the speed of an operation is not intrinsically linked to where a value is located in the virtual memory address space, but just to how you're accessing that location.
I hope this clears things up regarding my original point on that 👍
EDIT: just to clarify, you do have a pointer lookup in both cases though. If you have a pointer to a heap location eg. in
%ecxand want to read that value, you'll domovl eax, [ecx]. If you want to read the value at the top of the stack, you'll domovl eax, [esp]. In both cases the operation is exactly the same and you do have an address lookup just the same. So you saying that you never look addresses up when accessing the stack is just not the case. You're correct in saying that if you have a pointer on the heap stored on the stack you need two dereferences there, sure. But even in the best case scenario on the stack, you still need at least one anyway. And if you have a pointer in a given register, reading from that location has exactly the same cost no matter if it points to somewhere in the heap or the stack.Your last edit is exactly the point, from a language point we care about cost of operation when we talk about speed, and the cost of operation for the stack is lower than heap and that is why we say stack is faster than the heap. The actual speed of writing/reading from any part of memory indeed is the same but for heap, there are more operations involved than stack when writing/reading value making the cost of operation higher for the heap.
That is not true, since in the stack everything is offset of the stack pointer that is in the CPU registers. So, for example in ARM CPUs, it will take something like 3 instructions to retrieve any of the int in the buffer sitting in the stack. On the situation of the one on the heap, the first element will take something like 4 instructions since you need to set a register with the address you will find on the stack (the pointer of your heap buffer), and AFTER the other elements will be read AS FAST AS the stack since the other int element of the buffer are an offset of that value. And like I said earlier, if you have the address as a label, you will need 2 instructions to set your register before LDR/STR that memory block.
I think what you are trying to say is that at the time you have the address loaded in a register, the read time will be the same, which is true. The danger is that people might believe it is always the best solution to use the heap since it is so large, but doesn't account for the way it is handled. Embedded systems are very sensitive to this considering low frequency (very so often below 100 MHz), no OS and small memory footprint. The good practice, in that case, is only to use the heap with object allocated at startup so there is NO malloc anywhere, making sure the system stays deterministic. I know that in a 12-core i9 CPU clocks at 4GHz, the impact on most of the system people work (except OS for that matter, or video games) will be so negligible.