5 ms·

This is great - I'm self taught and have been working for years with no idea what the stack is - I'd love one for this "heap" thing I keep hearing about, as wel

This is great - I'm self taught and have been working for years with no idea what the stack is - I'd love one for this "heap" thing I keep hearing about, as well.

__david__ 11y ago
The heap is basically the memory that isn't your program code, your stack, or the space reserved by the compiler for your global variables (speaking of C, here). The heap memory traditionally gets allocated from a unix kernel with a syscall called sbrk(), which adds on to one end of the heap so that it stays one big contiguous chunk of memory. Traditionally, the heap begins at the opposite end of memory from the stack and grows towards it (some CPU's stacks grow up and some grow down). This may not be the case any more on 64 bit machines, since 64 bit address space is so big. Technically it's up to your app to use that memory as it pleases. Of course, 99.9999% of programs use the standard C library functions malloc() and free() (or "new" and "delete") which handle all this for you, and keep track of which chunks of memory are in use. They're also cross platform so you don't have to worry about what the system API in Windows is for low level memory allocation. But you don't have to use them if you really don't want to (though in that case be careful calling shared library functions that might call malloc() behind your back).
cbd1984 11y ago
A heap is a data structure used by the malloc() and free() functions to find appropriately-sized chunks of RAM to give to the rest of the program. The defining feature of heap-allocated memory is that it's persistent up the call stack; a common newbie error in C is to return a pointer to something allocated on the stack, which will become invalid the instant the other function sees it: If a() calls b(), everything in b()'s section of the call stack is cleaned up when b() returns to a(), so if a() tries to dereference a pointer to something b() allocated on the stack, the program will die. The flip side is that programmers have to manage this by hand, which is the cause of memory leaks. Garbage collection is used to mitigate this; to, at the very least, turn a program from one with quickly-growing memory usage into one with slow-growing memory usage.
- colejohnson66 11y ago
  Technically (at least on x86 and ARM), if b() allocates memory on the stack and returns a pointer to a(), as long as the pointer is dereferned immediately after the call the b(), the value should still be the same. It's not something you should count on (and purposely relying on it is a sin), but it won't kill your program. http://ideone.com/oIZXTY http://ideone.com/oIZXTY
  - shultays 11y ago
    It is an undefined behavior. It is very likely that something will go wrong, especially when optimizations are on. It is something you should never really on.
- greenleafjacob 11y ago
  Why would the program die? It can work depending on what happens between the invocations [1]. [1]: http://codepad.org/Z7Ojq9ml http://codepad.org/Z7Ojq9ml
DanielBMarkham 11y ago
This is a good comment because lots of folks confuse the heap and the stack. Let's say you assign a variable in c, like so int i = 0; No matter where you do this, you're assigning a variable on the stack. A location on the stack is set aside and your variable goes in there. This works great for small-ish things that you keep around to work on, but sometimes you want a big thing -- or you want something that lives on after the function dies. In this case, you create something on the heap. In this case, you tell the computer to set aside a chunk of memory somewhere else -- the heap -- and let you store things there. You can continue using this location after your function is completed. For an integer, it'd look like this. int* j = malloc(sizeof(int)); So if you have a function creating bitmaps, you might have a lot of local (stack) variables, and you'd probably either create or use a pointer to a big hunk of memory where you kept all the bits for the bitmap (heap) One way of thinking about it is if you're using a stack variable, only one piece of information gets stored in the computer -- the value. If you're using a heap variable, you're actually creating and storing two pieces of information, the value (on the heap), and a pointer to the value (on the stack). (hat tip to StackOverlow for the nice example http://stackoverflow.com/questions/6770596/memory-allocation-in-stack-and-heap http://stackoverflow.com/questions/6770596/memory-allocation... )
- kibwen 11y ago
  > No matter where you do this, you're assigning a variable > on the stack. In the C standard this is referred to as "automatic storage duration", and it can be weird to some (though obvious in retrospect) to consider that C actually features automatic memory reclamation (albeit limited). The important insight is that if you have a piece of memory that's scoped to a function, it's so trivial to free that memory that even C does it for you automatically. This is important because of what happens when you want to take this one step further: is it possible to make this same property apply to memory that's allocated on the heap rather than the stack? For one, there's escape analysis, which is a static analysis that tries to determine if a piece of heap-allocated memory has the potential to leave a function's scope. If not, then you can allocate that memory on the stack instead without changing the semantics of your program. Go does this, and it's an important optimization for reducing GC traffic. A step beyond that is linear typing (or maybe call it unique ownership), which is a static analysis that extends the "automatic storage duration" concept with one additional feature: a function can now hand off a piece of memory for some other function to free at the end of its scope. With this concept it's now possible to extend automatic storage duration to heap-allocated values as well, meaning you need neither a garbage collector nor explicit `free` calls. Rust does this, and it's one of the fundamental pillars of the language.
mikekchar 11y ago
Things like the stack and heap and many other things (like memory mapped I/O, interrupts, etc) are often taught in first year university courses under a name like "introduction to computer organization". There are many online courses you can do for free, or you can simply go to a book store and pick up a text book. Although none of it is something that you desperately need in order to work as a programmer these days, it's one of those things that will undoubtedly be useful almost every day, so I highly recommend it. As for the heap, I noticed another description, but I'll have a go at describing it in a slightly different way. Back in the old days you had a big chunk of contiguous memory. It started at address 0 and ended at address 65535 (if you were lucky enough to have 64K of RAM!). As you saw in the article, you need to set aside some of that memory for the stack. In most languages that are compiled to machine language, the stack holds storage for variables local to a function as well as the function return address (the object that holds all the information for one function is called a "stack frame"). As others have said, other organizations are possible, but this is the most common. Allocating memory on the stack is ideal because it is really easy to allocate and deallocate. When you enter a new function, you look at how big each of the local variables are and you simply move the "stack pointer" that many bytes (either up or down, depending on the architecture of the machine). When the function is finished, you simply move the stack pointer back to the start of that stack frame. Super easy and super fast. The problem is that as soon as your function finishes, the variable is deallocated. So let's say you have a function that loads a picture from disk. You make a big array in your picture loading function, put the picture data in it and return it from the function... uh oh... As soon as the function ends, the memory is deallocated :-(. That data is "gone" (what's worse is that the data is still there, so it will appear to work until the stack grows big enough to overwrite that data -- at which point your picture will be corrupted). So we need a way to allocate memory that will stick around until we tell the system that it is not needed any more. That's what the heap is. I can call a system function (usually called "malloc", which stands for "memory allocate") and say "I want 4K of memory". It finds a contiguous chunk of 4K of memory, makes a note that the memory is in use and then gives me a pointer to it. I can then use that pointer to write into the memory. The system will not allocate any memory in that area unless I tell it to "free" the memory (usually with a call to something called "free"). After that it can be used again. The place the system looks for in the memory for this kind of allocation is called the heap. So you can imagine the big block of memory in a computer is divided up into at least 2 sections: the stack and the heap. Often a computer system will put them at the opposite sides of the memory so that you can grow the stack as much as possible. So I might start the stack at 65535 and grow downward. And I might start allocating the heap from 0 upwards. In practice there are other things you need to reserve memory/addresses for, so this is not how it really works, but you get the idea. Many programmers like allocating from the heap because it is easy. You don't have to worry about the scope of your program. You allocate a variable and it is there until you tell it to go away. But there are a couple of problems. First, if you forget to free the memory, it never goes away. This is called a "memory leak". Also, you might accidentally try to use the memory after you freed it, resulting in the same corruption noted earlier. But there is yet another problem. Let's imagine that I allocated 1024 40 byte strings. That will take up 40K (almost all of my memory on this hypothetical old machine). Let's say that every second string is only needed at the beginning of the program, so let's free them all. That frees up 20K. However, the heap is now "fragmented". It has 40 bytes allocated, 40 bytes unallocated, 40 bytes allocated, 40 bytes unallocated... If I want to allocate 45 bytes, I will have to walk through 512 unallocated blocks, noting that each is too small, before I decide to allocate at the end. This is very slow. If there isn't a 45 byte chunk available, then my memory allocation will fail, even though I have 20K of free memory. So, for many old timers like me, we favoured allocating on the stack. This leads to fast, efficient, safe code that is also surprisingly elegant. Unfortunately, it is also hard to design ;-) These days, operating systems do a lot behind the scenes to make sure that you don't fragment your heap too much, etc, etc. Modern interpreted languages use garbage collection and allocate on the heap incrementally -- as if it were stack allocation. Occasionally they wander through and deallocate unused variables and compact the heap. Some of the algorithms used are very sophisticated and quick. I keep thinking about designing a functional language with stack allocation, though... It appeals to my roots ;-). Hope that description helps. Keep in mind that many details will be incorrect for any specific system. I mostly just tried to make the description simple, not accurate.
waiseristy 11y ago
You might also like this https://www.youtube.com/watch?v=1S0aBV-Waeo https://www.youtube.com/watch?v=1S0aBV-Waeo Although call stacks aren't the main topic, it gives a really nice outline of them
mattlutze 11y ago
It's cool to see a bunch of really thorough, great answers here. The summary I use to keep them straight: When a program starts, it asks the operating system for memory to store the program and all its initial data. The heap is the part of memory nothing is using yet -- it's just a heap of memory over in the corner for you to use later if you need it. As well, I think about storing data in 2 ways: A. When you only need the data as long as the current function is executing, you declare a variable in that function, and the OS includes it in the calculation for how big to make that function's stack. You use it then it gets cleared out when the function is done. B. When you need the data to exist after the current function is done executing, but don't want to pass the data itself around as returns and arguments for other functions, you can ask the OS to give you part of that heap of memory to store the data in. But clearing heap data requires attention. Since we don't have the simplicity of clearing it when the function finishes, we generally have to keep track of what's been stored on the heap and make sure to free it up when we no longer need it. Some languages implement a garbage control process to track and clear no-longer-needed heap memory for us, but really the more you have on the heap, the less memory available to other programs on the computer, which isn't cool. If you remember back to the days of needing to restart Firefox after half a day because that one open tab was somehow using 1.8GB of your RAM, it's an example of what happens when a lot of things are allocated to the heap and aren't freed.
- teabee89 11y ago
  That Firefox anecdote is ironically funny. I now experience the same thing with Chrome, except it's for disk space backed memory. So every day I have my "Your startup disk is almost full" warning. I then quit Chrome to see 10-15Gb of disk space freed up. Recently I managed to get more space on my disk so thankfully I won't see it for a while, but still...
- kd5bjo 11y ago
  One slight correction: all of the memory setup is done by the operating system before the program starts at all. An executable file is basically a memory dump -- to start the program, the OS sets up some virtual memory space, copies the program into it(1), and then jumps to a predefined spot in the memory it just copied. (1) This step is a bit more complicated due to dynamically-linked libraries

This is great - I'm self taught and have been working for years with no idea what the stack is - I'd love one for this "heap" thing I keep hearing about, as well.

__david__ 11y ago

The heap is basically the memory that isn't your program code, your stack, or the space reserved by the compiler for your global variables (speaking of C, here). The heap memory traditionally gets allocated from a unix kernel with a syscall called sbrk(), which adds on to one end of the heap so that it stays one big contiguous chunk of memory. Traditionally, the heap begins at the opposite end of memory from the stack and grows towards it (some CPU's stacks grow up and some grow down). This may not be the case any more on 64 bit machines, since 64 bit address space is so big. Technically it's up to your app to use that memory as it pleases. Of course, 99.9999% of programs use the standard C library functions malloc() and free() (or "new" and "delete") which handle all this for you, and keep track of which chunks of memory are in use. They're also cross platform so you don't have to worry about what the system API in Windows is for low level memory allocation. But you don't have to use them if you really don't want to (though in that case be careful calling shared library functions that might call malloc() behind your back).

cbd1984 11y ago

A heap is a data structure used by the malloc() and free() functions to find appropriately-sized chunks of RAM to give to the rest of the program. The defining feature of heap-allocated memory is that it's persistent up the call stack; a common newbie error in C is to return a pointer to something allocated on the stack, which will become invalid the instant the other function sees it: If a() calls b(), everything in b()'s section of the call stack is cleaned up when b() returns to a(), so if a() tries to dereference a pointer to something b() allocated on the stack, the program will die. The flip side is that programmers have to manage this by hand, which is the cause of memory leaks. Garbage collection is used to mitigate this; to, at the very least, turn a program from one with quickly-growing memory usage into one with slow-growing memory usage.

colejohnson66 11y ago
Technically (at least on x86 and ARM), if b() allocates memory on the stack and returns a pointer to a(), as long as the pointer is dereferned immediately after the call the b(), the value should still be the same. It's not something you should count on (and purposely relying on it is a sin), but it won't kill your program. http://ideone.com/oIZXTY http://ideone.com/oIZXTY
- shultays 11y ago
  It is an undefined behavior. It is very likely that something will go wrong, especially when optimizations are on. It is something you should never really on.
greenleafjacob 11y ago
Why would the program die? It can work depending on what happens between the invocations [1]. [1]: http://codepad.org/Z7Ojq9ml http://codepad.org/Z7Ojq9ml

DanielBMarkham 11y ago

This is a good comment because lots of folks confuse the heap and the stack. Let's say you assign a variable in c, like so int i = 0; No matter where you do this, you're assigning a variable on the stack. A location on the stack is set aside and your variable goes in there. This works great for small-ish things that you keep around to work on, but sometimes you want a big thing -- or you want something that lives on after the function dies. In this case, you create something on the heap. In this case, you tell the computer to set aside a chunk of memory somewhere else -- the heap -- and let you store things there. You can continue using this location after your function is completed. For an integer, it'd look like this. int* j = malloc(sizeof(int)); So if you have a function creating bitmaps, you might have a lot of local (stack) variables, and you'd probably either create or use a pointer to a big hunk of memory where you kept all the bits for the bitmap (heap) One way of thinking about it is if you're using a stack variable, only one piece of information gets stored in the computer -- the value. If you're using a heap variable, you're actually creating and storing two pieces of information, the value (on the heap), and a pointer to the value (on the stack). (hat tip to StackOverlow for the nice example http://stackoverflow.com/questions/6770596/memory-allocation-in-stack-and-heap http://stackoverflow.com/questions/6770596/memory-allocation... )

kibwen 11y ago
> No matter where you do this, you're assigning a variable > on the stack. In the C standard this is referred to as "automatic storage duration", and it can be weird to some (though obvious in retrospect) to consider that C actually features automatic memory reclamation (albeit limited). The important insight is that if you have a piece of memory that's scoped to a function, it's so trivial to free that memory that even C does it for you automatically. This is important because of what happens when you want to take this one step further: is it possible to make this same property apply to memory that's allocated on the heap rather than the stack? For one, there's escape analysis, which is a static analysis that tries to determine if a piece of heap-allocated memory has the potential to leave a function's scope. If not, then you can allocate that memory on the stack instead without changing the semantics of your program. Go does this, and it's an important optimization for reducing GC traffic. A step beyond that is linear typing (or maybe call it unique ownership), which is a static analysis that extends the "automatic storage duration" concept with one additional feature: a function can now hand off a piece of memory for some other function to free at the end of its scope. With this concept it's now possible to extend automatic storage duration to heap-allocated values as well, meaning you need neither a garbage collector nor explicit `free` calls. Rust does this, and it's one of the fundamental pillars of the language.

mikekchar 11y ago

Things like the stack and heap and many other things (like memory mapped I/O, interrupts, etc) are often taught in first year university courses under a name like "introduction to computer organization". There are many online courses you can do for free, or you can simply go to a book store and pick up a text book. Although none of it is something that you desperately need in order to work as a programmer these days, it's one of those things that will undoubtedly be useful almost every day, so I highly recommend it. As for the heap, I noticed another description, but I'll have a go at describing it in a slightly different way. Back in the old days you had a big chunk of contiguous memory. It started at address 0 and ended at address 65535 (if you were lucky enough to have 64K of RAM!). As you saw in the article, you need to set aside some of that memory for the stack. In most languages that are compiled to machine language, the stack holds storage for variables local to a function as well as the function return address (the object that holds all the information for one function is called a "stack frame"). As others have said, other organizations are possible, but this is the most common. Allocating memory on the stack is ideal because it is really easy to allocate and deallocate. When you enter a new function, you look at how big each of the local variables are and you simply move the "stack pointer" that many bytes (either up or down, depending on the architecture of the machine). When the function is finished, you simply move the stack pointer back to the start of that stack frame. Super easy and super fast. The problem is that as soon as your function finishes, the variable is deallocated. So let's say you have a function that loads a picture from disk. You make a big array in your picture loading function, put the picture data in it and return it from the function... uh oh... As soon as the function ends, the memory is deallocated :-(. That data is "gone" (what's worse is that the data is still there, so it will appear to work until the stack grows big enough to overwrite that data -- at which point your picture will be corrupted). So we need a way to allocate memory that will stick around until we tell the system that it is not needed any more. That's what the heap is. I can call a system function (usually called "malloc", which stands for "memory allocate") and say "I want 4K of memory". It finds a contiguous chunk of 4K of memory, makes a note that the memory is in use and then gives me a pointer to it. I can then use that pointer to write into the memory. The system will not allocate any memory in that area unless I tell it to "free" the memory (usually with a call to something called "free"). After that it can be used again. The place the system looks for in the memory for this kind of allocation is called the heap. So you can imagine the big block of memory in a computer is divided up into at least 2 sections: the stack and the heap. Often a computer system will put them at the opposite sides of the memory so that you can grow the stack as much as possible. So I might start the stack at 65535 and grow downward. And I might start allocating the heap from 0 upwards. In practice there are other things you need to reserve memory/addresses for, so this is not how it really works, but you get the idea. Many programmers like allocating from the heap because it is easy. You don't have to worry about the scope of your program. You allocate a variable and it is there until you tell it to go away. But there are a couple of problems. First, if you forget to free the memory, it never goes away. This is called a "memory leak". Also, you might accidentally try to use the memory after you freed it, resulting in the same corruption noted earlier. But there is yet another problem. Let's imagine that I allocated 1024 40 byte strings. That will take up 40K (almost all of my memory on this hypothetical old machine). Let's say that every second string is only needed at the beginning of the program, so let's free them all. That frees up 20K. However, the heap is now "fragmented". It has 40 bytes allocated, 40 bytes unallocated, 40 bytes allocated, 40 bytes unallocated... If I want to allocate 45 bytes, I will have to walk through 512 unallocated blocks, noting that each is too small, before I decide to allocate at the end. This is very slow. If there isn't a 45 byte chunk available, then my memory allocation will fail, even though I have 20K of free memory. So, for many old timers like me, we favoured allocating on the stack. This leads to fast, efficient, safe code that is also surprisingly elegant. Unfortunately, it is also hard to design ;-) These days, operating systems do a lot behind the scenes to make sure that you don't fragment your heap too much, etc, etc. Modern interpreted languages use garbage collection and allocate on the heap incrementally -- as if it were stack allocation. Occasionally they wander through and deallocate unused variables and compact the heap. Some of the algorithms used are very sophisticated and quick. I keep thinking about designing a functional language with stack allocation, though... It appeals to my roots ;-). Hope that description helps. Keep in mind that many details will be incorrect for any specific system. I mostly just tried to make the description simple, not accurate.

waiseristy 11y ago

You might also like this https://www.youtube.com/watch?v=1S0aBV-Waeo https://www.youtube.com/watch?v=1S0aBV-Waeo Although call stacks aren't the main topic, it gives a really nice outline of them

mattlutze 11y ago

It's cool to see a bunch of really thorough, great answers here. The summary I use to keep them straight: When a program starts, it asks the operating system for memory to store the program and all its initial data. The heap is the part of memory nothing is using yet -- it's just a heap of memory over in the corner for you to use later if you need it. As well, I think about storing data in 2 ways: A. When you only need the data as long as the current function is executing, you declare a variable in that function, and the OS includes it in the calculation for how big to make that function's stack. You use it then it gets cleared out when the function is done. B. When you need the data to exist after the current function is done executing, but don't want to pass the data itself around as returns and arguments for other functions, you can ask the OS to give you part of that heap of memory to store the data in. But clearing heap data requires attention. Since we don't have the simplicity of clearing it when the function finishes, we generally have to keep track of what's been stored on the heap and make sure to free it up when we no longer need it. Some languages implement a garbage control process to track and clear no-longer-needed heap memory for us, but really the more you have on the heap, the less memory available to other programs on the computer, which isn't cool. If you remember back to the days of needing to restart Firefox after half a day because that one open tab was somehow using 1.8GB of your RAM, it's an example of what happens when a lot of things are allocated to the heap and aren't freed.

teabee89 11y ago
That Firefox anecdote is ironically funny. I now experience the same thing with Chrome, except it's for disk space backed memory. So every day I have my "Your startup disk is almost full" warning. I then quit Chrome to see 10-15Gb of disk space freed up. Recently I managed to get more space on my disk so thankfully I won't see it for a while, but still...
kd5bjo 11y ago
One slight correction: all of the memory setup is done by the operating system before the program starts at all. An executable file is basically a memory dump -- to start the program, the OS sets up some virtual memory space, copies the program into it(1), and then jumps to a predefined spot in the memory it just copied. (1) This step is a bit more complicated due to dynamically-linked libraries