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.
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).
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... )
> No matter where you do this, you're assigning a variable
> on the stack.
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.
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.
(1) This step is a bit more complicated due to dynamically-linked libraries
Although call stacks aren't the main topic, it gives a really nice outline of them
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.
You might be interested in concatenative programming, effectively a modern functional take on Forth-like languages. Factor is a mature, dynamically typed concatenative language, with an excellent interactive environment reminiscent of Smalltalk. I have also been working on a statically typed concatenative language for a while now.
The underlying OS call is VirtualAlloc on Windows and brk/sbrk/mmap on Linux.
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.