6 ms·

What and where are the stack and heap?

85 points by gs7 13y ago

terhechte 13y ago
Uli Kusterer has a really good, very graphical, description in his "Masters of the Void" series, too: http://masters-of-the-void.com/book5.htm http://masters-of-the-void.com/book5.htm
com2kid 13y ago
I'd argue against there being "only 1 heap". Only one OS provided heap, sure, but in C++ it is quite common to overload new and allocate into a separate statically declared buffer. (See: Video games!" And, as usual, no mention was made of static allocations! :(
- kabdib 13y ago
  Oh yes. Heaps for allocating textures. Object-type-specific heaps for things like sounds and models. "Smart" heaps that can invalidate their contents under memory pressure (and maybe automatically bring stuff back in, possibly speculatively). Heaps that are good for lots of small allocations. Heaps that either do or do not allow multiple threads to use them. Heaps that are position-independent and that can be used in shared memory buffers (which can be mapped to different addresses in different processes). I could go on. I wrote a lot of the memory management stuff for the Apple Newton, and it had several types of heaps: - A common "Macintosh-like" heap with both fixed and sliding blocks (even with a VM system managing the page for you, fragmentation matters when memory is tight). Most threads played in this heap, and keeping it sane was kind of hard. - A couple of heaps for the kernel, for managing its objects (it's been a while, I don't remember why there was more than one). - A heap that could supply (limited) amounts of memory for interrupt handlers. - The NewtonScript object heap (owned by the NewtonScript environment). I'm pretty sure there were a couple more heaps, but I've forgotten the details. Our main worry was fragmentation, and I'd say that things probably weren't segmented enough and that we needed even more heaps than we shipped with. A heap is just a data structure. Ain't nothing magic.
  - yongjik 13y ago
    I wouldn't call a heap a "data structure", though. It will lead to mighty confusion, as heap-the-data-structure has nothing to do with heap-in-which-you-allocate-memory.
- flatline 13y ago
  The CLR has at least two that I'm aware of, the "regular" heap (not sure if it has a special name) and the Large Object Heap. Pretty sure there are unmanaged heaps associated with a single .NET process as well -- certainly there are if you are mucking around with things like managed C++.
- closer 13y ago
  )
derefr 13y ago
If this article is news for you, this might be a helpful corollary: Threads and processes are both units of execution. (A unit of execution is like a virtual processor -- a separate instruction pointer that makes its way through your code, doing computations and following jumps.) Both threads and processes have their own stacks. You reserve a new stack when you fork(), or when you spawn a thread. But only processes have their own heaps. In fact, this is the defining distinction between threads and processes: if you're sharing your heap with other execution-units, you're a thread; if you have your own isolated heap, you're a separate process.
- fiatmoney 13y ago
  You can also mmap a chunk of memory and share it between processes.
  - blibble 13y ago
    also there's nothing stopping a thread having its own logical heap. grandparent is confusing the concept of address space and heap.
    - derefr 13y ago
      Address spaces are just an implementation detail. You can have both processes and threads on an architecture without any such concept. The point -- the theory -- behind processes, is to separate your heap from your neighbor's heap, so pointers in your heap pointing at addresses in theirs won't be valid, or vice-versa. You could do this with virtual-memory mapping, memory segmentation, tagged pointers, domain-taint as static type checking, etc. and you'd get the same result. Why only the heap? Since pointers on the stack can only (coherently) point into the same stack, or to the heap--and pointers on the heap can't point back into any stack--then stacks are already isolated. (Registers follow the same isolation rules as stack entries, if you want a register-machine.) The reason you want to isolate your heap in the first place, the benefit you get, is that an isolated heap is an isolated graph for any garbage-collection system to pass over, and an isolated set-of-blocks-of-bytes for an exception to throw out or the OOM killer to discard. As soon as you have an isolated heap, in other words, you get all the practical advantages that come with running in a separate process. If you implement a bytecode interpreter that can concurrently switch between several instruction pointers with their own stacks, then you've implemented green-threads. If each of those instruction pointers also has their own heap, you've implemented virtual processes.
mtdewcmu 13y ago
The stack is a concept that's built into the CPU to handle function calls. Every time you call a function, there is a return address that needs to be stored. Since you need to hang on to a return address for every function that is currently in progress, and you use them in the reverse order that they were stored, what you need is exactly a stack. The stack is usually (always?) located at the top of memory and grows down. In addition to return addresses, it can be used to store data associated with an in-progress function, like arguments, local variables, and cpu state data that needs to be temporarily stored. So that's the stack. The concept of the heap, on the other hand, isn't built into the CPU, and is sort of a vague abstraction implemented by programming languages. The first thing to know about how it differs from the stack: it's not a stack. Stack reads and writes follow LIFO; reads and writes to the heap can potentially be in any order. The heap is usually (always?) located close to the bottom of memory, and grows up. So the stack and heap grow toward each other. At the lowest level, the heap is basically just memory that can be used as the application sees fit. Data on the heap isn't inherently tied to an in-progress function call, so it can last indefinitely (at least, until the process ends). The programming language or the C library typically provide a means to subdivide the heap memory into discrete blocks as needed in response to an explicit or implicit memory allocation request (e.g. malloc(), new), and keep track of what memory is available and what is currently allocated. Differences between the stack and the heap: * the stack is limited in size, so it is easy to overflow and crash if you try to store too much data there. the heap, in contrast, is designed to grow as much as needed * the stack is managed primarily by instructions built into the cpu. the heap is managed by library calls and system calls * the difference in speed between the two refers to the speed of allocating or freeing a chunk. the stack can inherently do this quickly, because the location for the memory is predetermined. since the heap can do allocations and deallocations in any order, finding memory for blocks is inherently more complicated and slower. * since the fundamental purpose of the stack is to store data about in-progress functions, it follows that every executing thread has its own stack and usually only accesses its own. the heap, on the other hand, has no association to a thread of execution, which consequently means that multiple threads can share the same heap, and locking and synchronization must come into play when the heap metadata has to change. The locking is typically transparent, but the net result is to make allocations and deallocations even slower in threaded code.
pramodliv1 13y ago
I remember the first time when I worked on multithreaded C++ project. I allocated a structure on the stack and passed its address to a queue which was received by another thread and the inevitable segfault happened. My mistake provided a lot of laughs for the entire team. Also see http://stackoverflow.com/questions/8468210/stack-vs-heap-c http://stackoverflow.com/questions/8468210/stack-vs-heap-c
- ksk 13y ago
  I understand what you meant but to be a bit pedantic, you can freely allocate structures on the stack and pass it around. You might have heard of a few of them .. cout, cin :P
losethos 13y ago
If you have an 8Gig machine, stack might be 0x1E0000000. The stack cannot grow. The heap is the same sort of address. The code heap, however, is 0x7F000000. TempleOS is 100% identity-mapped. Think about that for a long time. The stack in one task is different from every other task. Memory gets fragmented. You cannot grow the stack. TempleOS is ring-0-only. You don't have higher half kernel addresses. TempleOS places all code in the lowest 2Gig addresses, known as the "code heap".

85 points by gs7 13y ago

Uli Kusterer has a really good, very graphical, description in his "Masters of the Void" series, too: http://masters-of-the-void.com/book5.htm http://masters-of-the-void.com/book5.htm

com2kid 13y ago

I'd argue against there being "only 1 heap". Only one OS provided heap, sure, but in C++ it is quite common to overload new and allocate into a separate statically declared buffer. (See: Video games!" And, as usual, no mention was made of static allocations! :(

kabdib 13y ago
Oh yes. Heaps for allocating textures. Object-type-specific heaps for things like sounds and models. "Smart" heaps that can invalidate their contents under memory pressure (and maybe automatically bring stuff back in, possibly speculatively). Heaps that are good for lots of small allocations. Heaps that either do or do not allow multiple threads to use them. Heaps that are position-independent and that can be used in shared memory buffers (which can be mapped to different addresses in different processes). I could go on. I wrote a lot of the memory management stuff for the Apple Newton, and it had several types of heaps: - A common "Macintosh-like" heap with both fixed and sliding blocks (even with a VM system managing the page for you, fragmentation matters when memory is tight). Most threads played in this heap, and keeping it sane was kind of hard. - A couple of heaps for the kernel, for managing its objects (it's been a while, I don't remember why there was more than one). - A heap that could supply (limited) amounts of memory for interrupt handlers. - The NewtonScript object heap (owned by the NewtonScript environment). I'm pretty sure there were a couple more heaps, but I've forgotten the details. Our main worry was fragmentation, and I'd say that things probably weren't segmented enough and that we needed even more heaps than we shipped with. A heap is just a data structure. Ain't nothing magic.
- yongjik 13y ago
  I wouldn't call a heap a "data structure", though. It will lead to mighty confusion, as heap-the-data-structure has nothing to do with heap-in-which-you-allocate-memory.
flatline 13y ago
The CLR has at least two that I'm aware of, the "regular" heap (not sure if it has a special name) and the Large Object Heap. Pretty sure there are unmanaged heaps associated with a single .NET process as well -- certainly there are if you are mucking around with things like managed C++.
closer 13y ago
)

derefr 13y ago

If this article is news for you, this might be a helpful corollary: Threads and processes are both units of execution. (A unit of execution is like a virtual processor -- a separate instruction pointer that makes its way through your code, doing computations and following jumps.) Both threads and processes have their own stacks. You reserve a new stack when you fork(), or when you spawn a thread. But only processes have their own heaps. In fact, this is the defining distinction between threads and processes: if you're sharing your heap with other execution-units, you're a thread; if you have your own isolated heap, you're a separate process.

fiatmoney 13y ago
You can also mmap a chunk of memory and share it between processes.
- blibble 13y ago
  also there's nothing stopping a thread having its own logical heap. grandparent is confusing the concept of address space and heap.
  - derefr 13y ago
    Address spaces are just an implementation detail. You can have both processes and threads on an architecture without any such concept. The point -- the theory -- behind processes, is to separate your heap from your neighbor's heap, so pointers in your heap pointing at addresses in theirs won't be valid, or vice-versa. You could do this with virtual-memory mapping, memory segmentation, tagged pointers, domain-taint as static type checking, etc. and you'd get the same result. Why only the heap? Since pointers on the stack can only (coherently) point into the same stack, or to the heap--and pointers on the heap can't point back into any stack--then stacks are already isolated. (Registers follow the same isolation rules as stack entries, if you want a register-machine.) The reason you want to isolate your heap in the first place, the benefit you get, is that an isolated heap is an isolated graph for any garbage-collection system to pass over, and an isolated set-of-blocks-of-bytes for an exception to throw out or the OOM killer to discard. As soon as you have an isolated heap, in other words, you get all the practical advantages that come with running in a separate process. If you implement a bytecode interpreter that can concurrently switch between several instruction pointers with their own stacks, then you've implemented green-threads. If each of those instruction pointers also has their own heap, you've implemented virtual processes.

mtdewcmu 13y ago

The stack is a concept that's built into the CPU to handle function calls. Every time you call a function, there is a return address that needs to be stored. Since you need to hang on to a return address for every function that is currently in progress, and you use them in the reverse order that they were stored, what you need is exactly a stack. The stack is usually (always?) located at the top of memory and grows down. In addition to return addresses, it can be used to store data associated with an in-progress function, like arguments, local variables, and cpu state data that needs to be temporarily stored. So that's the stack. The concept of the heap, on the other hand, isn't built into the CPU, and is sort of a vague abstraction implemented by programming languages. The first thing to know about how it differs from the stack: it's not a stack. Stack reads and writes follow LIFO; reads and writes to the heap can potentially be in any order. The heap is usually (always?) located close to the bottom of memory, and grows up. So the stack and heap grow toward each other. At the lowest level, the heap is basically just memory that can be used as the application sees fit. Data on the heap isn't inherently tied to an in-progress function call, so it can last indefinitely (at least, until the process ends). The programming language or the C library typically provide a means to subdivide the heap memory into discrete blocks as needed in response to an explicit or implicit memory allocation request (e.g. malloc(), new), and keep track of what memory is available and what is currently allocated. Differences between the stack and the heap: * the stack is limited in size, so it is easy to overflow and crash if you try to store too much data there. the heap, in contrast, is designed to grow as much as needed * the stack is managed primarily by instructions built into the cpu. the heap is managed by library calls and system calls * the difference in speed between the two refers to the speed of allocating or freeing a chunk. the stack can inherently do this quickly, because the location for the memory is predetermined. since the heap can do allocations and deallocations in any order, finding memory for blocks is inherently more complicated and slower. * since the fundamental purpose of the stack is to store data about in-progress functions, it follows that every executing thread has its own stack and usually only accesses its own. the heap, on the other hand, has no association to a thread of execution, which consequently means that multiple threads can share the same heap, and locking and synchronization must come into play when the heap metadata has to change. The locking is typically transparent, but the net result is to make allocations and deallocations even slower in threaded code.

pramodliv1 13y ago

I remember the first time when I worked on multithreaded C++ project. I allocated a structure on the stack and passed its address to a queue which was received by another thread and the inevitable segfault happened. My mistake provided a lot of laughs for the entire team. Also see http://stackoverflow.com/questions/8468210/stack-vs-heap-c http://stackoverflow.com/questions/8468210/stack-vs-heap-c

ksk 13y ago
I understand what you meant but to be a bit pedantic, you can freely allocate structures on the stack and pass it around. You might have heard of a few of them .. cout, cin :P

losethos 13y ago

If you have an 8Gig machine, stack might be 0x1E0000000. The stack cannot grow. The heap is the same sort of address. The code heap, however, is 0x7F000000. TempleOS is 100% identity-mapped. Think about that for a long time. The stack in one task is different from every other task. Memory gets fragmented. You cannot grow the stack. TempleOS is ring-0-only. You don't have higher half kernel addresses. TempleOS places all code in the lowest 2Gig addresses, known as the "code heap".