1

My limited understanding of the stack/heap is that reference types are put onto the heap (dynamically allocated), and value types are put on the stack.

Theoretically (as in a theoretical machine, compiler, programming language), is the stack a necessity? Couldn't all memory be placed onto the heap?

trincot
  • 317,000
  • 35
  • 244
  • 286
  • That would certainly make for interesting stack traces in debugging. The stack doesn't just store value types, it also maintains the call stack. – David Dec 13 '11 at 14:07
  • I would suggest that you have a look at [this][1] [1]: http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap – ChrisBD Dec 13 '11 at 14:09
  • @David, there's no inherent reason to have just one stack, with data and return addresses intermingled. The FORTH virtual machine defines two stacks, one for data, one for return addresses (and a few very-special-purpose words that manipulate data on the return stack). The Motorola 6809 had two stack pointers, and, based on knowing who was likely involved in the design, I still suspect the designer did it to make it easier to implement FORTH on the chip. – John R. Strohm Dec 13 '11 at 14:17

2 Answers2

2

In theory, you could do that. In practice, it would be a huge performance killer.

In "Hackers", Steven Levy tells the tale. At MIT, decades ago, before hardware stacks, writing a "decimal print" routine in under 50 instructions was the Holy Grail of hacking. Someone finally got there. Not too long after that, a new machine showed up, with a similar instruction set, except that it included a new instruction, PUSHJ, Push Return Address and Jump. PUSHJ pushed the return address onto a stack, instead of storing it at an absolute memory location (or in a register: same same - you have to store the register SOMEWHERE if you need to call something else). With PUSHJ, the decimal print could be written in 10 instructions.

Modern RISC theory eschews stack instructions in favor of registers, and forces programmers (or, more likely, compilers) to implement PUSHJ in software on every call. This is a performance hit, any way you cut it, because you WILL pay the added cost of manipulating the stack pointer in software (instruction fetches, register juggles, register increment/decrement).

John R. Strohm
  • 7,547
  • 2
  • 28
  • 33
0

A stack grows as things are added on to it, and shrinks as things are removed. Allocating things on the stack is therefore very efficient. It's a simple movement up the "stack" by the amount of bytes allocates.

Heap allocation is expensive conversely. That and the system also has to deal with memory fragmentation.

The downside to the stack is, of course, that it has a limited size. However, due to the speed and efficiency of pushing and popping things on the stack, it makes it a perfect candidate for calling functions and returning from them.

Moo-Juice
  • 38,257
  • 10
  • 78
  • 128