Why can't we allocate dynamic memory on the stack?

Question

Allocating stuff on the stack is awesome because than we have RAII and don't have to worry about memory leaks and such. However sometimes we must allocate on the heap:

• If the data is really big (recommended) - because the stack is small.

• If the size of the data to be allocated is only known at runtime (dynamic allocation).

Two questions:

1. Why can't we allocate dynamic memory (i.e. memory of size that is only known at runtime) on the stack?

2. Why can we only refer to memory on the heap through pointers, while memory on the stack can be referred to via a normal variable? I.e. Thing t;.

Edit: I know some compilers support Variable Length Arrays - which is dynamically allocated stack memory. But that's really an exception to the general rule. I'm interested in understanding the fundamental reasons for why generally, we can't allocate dynamic memory on the stack - the technical reasons for it and the rational behind it.

Answer 1

Why can't we allocate dynamic memory (i.e. memory of size that is only known at runtime) on the stack?

It's more complicated to achieve this. The size of each stack frame is burned-in to your compiled program as a consequence of the sort of instructions the finished executable needs to contain in order to work. The layout and whatnot of your function-local variables, for example, is literally hard-coded into your program through the register and memory addresses it describes in its low-level assembly code: "variables" don't actually exist in the executable. To let the quantity and size of these "variables" change between compilation runs greatly complicates this process, though it's not completely impossible (as you've discovered, with non-standard variable-length arrays).

Why can we only refer to memory on the heap through pointers, while memory on the stack can be referred to via a normal variable

This is just a consequence of the syntax. C++'s "normal" variables happen to be those with automatic or static storage duration. The designers of the language could technically have made it so that you can write something like Thing t = new Thing and just use a t all day, but they did not; again, this would have been more difficult to implement. How do you distinguish between the different types of objects, then? Remember, your compiled executable has to remember to auto-destruct one kind and not the other.

I'd love to go into the details of precisely why and why not these things are difficult, as I believe that's what you're after here. Unfortunately, my knowledge of assembly is too limited.

Answer 2

Why can't we allocate dynamic memory (i.e. memory of size that is only known at runtime) on the stack?

Technically, this is possible. But not approved by the C++ standard. Variable length arrays(VLA) allows you to create dynamic size constructs on stack memory. Most compilers allow this as compiler extension.

example:

int array[n];

//where n is only known at run-time

Why can we only refer to memory on the heap through pointers, while memory on the stack can be referred to via a normal variable? I.e. Thing t;.

We can. Whether you do it or not depends on implementation details of a particular task at hand.

example:

int i;
int *ptr = &i;

Answer 3

We can allocate variable length space dynamically on stack memory by using function _alloca. This function allocates memory from the program stack. It simply takes number of bytes to be allocated and return void* to the allocated space just as malloc call. This allocated memory will be freed automatically on function exit.

So it need not to be freed explicitly. One has to keep in mind about allocation size here, as stack overflow exception may occur. Stack overflow exception handling can be used for such calls. In case of stack overflow exception one can use _resetstkoflw() to restore it back.

So our new code with _alloca would be :

 int NewFunctionA()
 {
  char* pszLineBuffer = (char*) _alloca(1024*sizeof(char));
  …..
  // Program logic
   ….
 //no need to free szLineBuffer
 return 1;
}

Answer 4

Every variable that has a name, after compilation, becomes a dereferenced pointer whose address value is computed by adding (depending on the platform, may be "subtracting"...) an "offset value" to a stack-pointer (a register that contains the address the stack actually is reaching: usually "current function return address" is stored there).

int i,j,k;

becomes

(SP-12) ;i
(SP-8) ;j
(SP-4) ;k

To let this "sum" to be efficient, the offsets have to be constant, so that they can be encode directly in the instruction op-code:

k=i+j;

become

MOV (SP-12),A;   i-->>A
ADD A,(SP-8) ;   A+=j
MOV A,(SP-4) ;   A-->>k

You see here how 4,8 and 12 are now "code", not "data".

That implies that a variable that comes after another requires that "other" to retain a fixed compile-time defined size.

Dynamically declared arrays can be an exception, but they can only be that last variable of a function. Otherwise, all the variables that follows will have an offset that have to be adjusted run-time after that array allocation.

This creates the complication that dereferencing the addresses requires arithmetic (not just a plain offset) or the capability to modify the opcode as variables are declared (self modifying code).

Both the solution becomes sub-optimal in term of performance, since all can break the locality of the addressing, or add more calculation for each variable access.

Answer 5

Why can't we allocate dynamic memory (i.e. memory of size that is only known at runtime) on the stack?

You can with Microsoft compilers using _alloca() or _malloca(). For gcc, it's alloca()

I'm not sure it's part of the C / C++ standards, but variations of alloca() are included with many compilers. If you need aligned allocation, such a "n" bytes of memory starting on a "m" byte boundary (where m is a power of 2), you can allocate n+m bytes of memory, add m to the pointer and mask off the lower bits. Example to allocate hex 1000 bytes of memory on a hex 100 boundary. You don't need to preserve the value returned by _alloca() since it's stack memory and automatically freed when the function exits.

char *p;
    p = _alloca(0x1000+0x100);
    (size_t)p = ((size_t)0x100 + (size_t)p) & ~(size_t)0xff;

Answer 6

Most important reason is that Memory used can be deallocated in any order but stack requires deallocation of memory in a fixed order i.e LIFO order.Hence practically it would be difficult to implement this.