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.
The concept of the stack is built into the CPU? That's news to me... I mean, I'm not a hardware guy so I guess I could have been misinformed, but I thought it was something the OS managed as a reserved chunk of main memory (like the heap).
Registers are built into the CPU, but that's a different thing than the stack.
In the x86 family anyway, it's kinda-sorta 'built in'. It is possible to avoid using the stack -- it's done in interrupt handlers which do not have a stack of their own and must avoid clobbering it -- but most code uses it fairly frequently and there are many auxiliary instructions that push and pop from the stack.
In addition to some explicit stack-related instructions like PUSH/POP, PUSHF/POPF, PUSHA/POPA, PUSHAD/POPAD and many others, certain other operations assume you have a valid stack and act on it. For example, the CALL function (used to call a procedure/function) will push a return address to the stack, and RET (used to return to the caller at the end of a procedure/method) will pop the return address to the stack and jump to it.
These instructions are fairly essential to the function calling conventions for typical code, enough that it's reasonable to say that the concept of the stack is 'built into' x86 processors.
Partly this is because the x86 processor is a beast with an instruction for everything. Other more RISCy architectures tend to not bake in the stack, and instead you use any general-purpose register as a stack pointer and manipulate it manually with regular instructions.
Lots of smaller microprocessors live by the stack. Aside from the typical JSR/RET stuff with pushing the program counter, you can also do very lightweight programming tricks with the stack pointer.
For example, you can pass arguments to an assembly subroutine by putting the data right after the JSR call. The called subroutine pulls the args by manipulating the stack pointer and the return will jump PC after the argument date.
You can also use stack pointer to briefly allocate a small amount of memory for scratch inside a routine instead of allocating heap or using globals. This is a big help on small micros where you might get a scratch register or two normally but now you need 4 or 8 bytes for a quick piece of work.
Yes I think it's better to say this in a more limited way: certain CPU instructions such as push, pop, and call manipulate the stack pointer register in a way that assumes common stack conventions.
One interesting thing is that the implementation of these instructions do specify the question of whether the stack grows up or down. On x86 these instructions subtract from rsp when they want to grow the stack, ergo on x86 the stack grows down.
I don't know about all architectures, but I took a peek at ARM and it has a stack pointer register and built-in instructions that use the stack. So that's Intel and at least one RISC cpu that assume a stack.
Of course, you can probably write programs with no stack, and never use the stack instructions, or even put them to other purposes. But there are probably performance reasons for having instructions that automatically manipulate a function call stack, and it would be hard to live without any functions.
It would quickly become painful to only transfer execution with JMP-instructions -- you'd need some way to keep track of either how to return, or where you'd be going next (this is exactly equivalent to only using GOTOs for control flow -- and as we know, considered harmful).
I suppose on x86 you could create a calling convention where you store a return address in a register or something -- but on 32bit you're already rather short on registers. It would probably be more (if still not really) sensible on amd64.
I only see this as viable for rather simple state-machine designs -- but I suppose you could also just generate machine code that read return addresses from an area of memory or something ("the tape" in Turing parlance).
While some architectures have some special instructions/registers for handling stacks I still wouldn't say it's built into CPUs. The direction in which a stack grows depends on the architecture. Some programming languages don't have one stack and one heap that grow into each other but instead several memory areas while still being single threaded (I think prolog or some logic oriented languages have such a more complicated concept).
Management of the stack is done by the program, not by the OS. How the program does it depends on the language and unless you use assembler it is hidden by the compiler. There is a calling convention, not one single way a call works. Some C compilers expose ways to define a different than the standard calling convention for a function. You might say that how a function call works is to much detail and not what you understand about how the stack works. Anyway, some languages have segmented stacks, meaning if a stack is used up a new stack is allocated and referred to by the old one (rust supported this at some point).
There are also languages that have different heaps per thread (rust for gc-ed objects). Per-thread heaps are a good idea because otherwise you would need to use some sort of synchronization for malloc and free, which defeats the purpose of threads. Usually this is done by reserving a memory area for a thread and only when this is exhausted and a new memory area needs to be allocated some sort of potentially blocking call (I think usually mmap?) for another area is called.
The call instruction on x86 automatically writes a return address to the stack, and I suspect that that's a standard instruction across architectures. That's sufficient to make my point that the CPU expects a stack.
Some architectures write the return address into a register and not onto the stack. The calling function has to preserve it's return address somehow, yes, but that isn't done for you (well, a compiler does it for you, but not an assembler). So if all parameters are passed via registers and the function does not need more memory than the registers provide for the calculation, then this kind of function does not need to access the stack at all.
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.