2

Is it just one of those "that's the way the language works" questions? EDIT:

Why does dynamic memory allow the size of arrays to be allocated during runtime?

Why can't I just use a variable called from the stack, as opposed to a variable called from the heap? They are both variables, one is just called from a different place and has to be manually freed and created. Variables created in the stack can change during runtime right?

moonbeamer2234
  • 351
  • 1
  • 3
  • 12
  • 2
    Dynamic allocation allows you to pick the size of the array at runtime. The size of stack allocated objects must be known at compile time. – juanchopanza Jun 22 '13 at 12:31
  • You can't manipulate the size of an array during runtime, whether it's dynamically allocated or not. – Tomer Arazy Jun 22 '13 at 12:32
  • 5
    @juanchopanza - not true (at least not in current standard). You can do something like `int a[n]` where `n` is a parameter passed to a function – Tomer Arazy Jun 22 '13 at 12:33
  • 1
    Please separate the premises from the question. Write your thoughts clearly as sentences and put a question mark on the actual question only. It's hard to tell what exactly you've understood and what you're asking. – Theodoros Chatzigiannakis Jun 22 '13 at 12:34
  • @juanchopanza Wrong as of C99. –  Jun 22 '13 at 12:35
  • 1
    @TomerArazy Huh, ever used `realloc()`? –  Jun 22 '13 at 12:35
  • "You could be wondering the difference between declaring a normal array and assigning dynamic memory to a pointer, as we have just done. The most important difference is that the size of an array has to be a constant value, which limits its size to what we decide at the moment of designing the program, before its execution, whereas the dynamic memory allocation allows us to assign memory during the execution of the program (runtime) using any variable or constant value as its size." -cplusplus.org @TomerArazy Am I misunderstanding what they were saying? – moonbeamer2234 Jun 22 '13 at 12:36
  • 1
    @TomerArazy In the current C standard, yes. Not in the current C++ standard, and not in the version of the C standard (C89 / "ANSI") many projects still limit themselves to, for better or for worse. –  Jun 22 '13 at 12:36
  • yea. you can determine the size of a dynamically allocated array at runtime. But once that is decided and the space is allocated for you, you can't change its size anymore. But maybe you can use a linked list to increase size? – 0x64 Jun 22 '13 at 12:38
  • @TomerArazy Right. My comment was referring to C++. I didn't even see the C tag! – juanchopanza Jun 22 '13 at 13:33
  • @user1907736: that's the exact opposite; talking only about standard functions, you can't get the size of a dynamically allocated memory block, but you can resize it using `realloc` (although this *may* result in moving the block in memory). – Matteo Italia Jun 22 '13 at 13:38

3 Answers3

5

Why can't I just use a variable called from the stack, as opposed to a variable called from the heap?

Heap allocation give you more control over memory.

Also, there are limitations, when it comes to stack variables.

//warning : applies only to PCs, may not be true for other architecthures I'm not familiar with. (mips, motorola 68000, etc. Anything that is not x86-related, bascially).

Variables created in the stack can change during runtime right?

Their SIZE can't change.

  1. Stack has limited size. Size is decided by operating system AND compiler. If stack becomes too big, program dies because of stack overflow. Classic example:

    int main(int argc, char** argv){
    char buffer[1024*1024*64];
    buffer[0] = 0;
    return 0;
}

    This program will crash if compiled with default settings on windows and it should crash on linux as well. That's because default stack size is 1 MB on 32bit windows and 8 MB on 32 bit linux (system may change this, though, using ulimit), and 64-megabyte array won't fit on stack.

  2. If your varaible is located between two other variables on stack, you can't change its size, no matter what. At least on x86/64 cpus.

  3. You can, in theory, increase size of stack array if it is the last thing on stack. (if I remember correctly, there was possibly non-standard C function called alloca that could allocate arrays on stack). However, you'll still hit stack size limit.

To understand WHY there are such limits, you need to step back from C++, and learn a bit of assembly. Try to find a book that covers segments (data/code/stack), explains where function return addresses are stored, and, preferably, tells you about protected mode. That should help.

Of course, there is a bit of a problem. Assembly knowledge will help only for particular family of CPUs. Different CPU with C++ compiler may use different rules.

--update--

Why does dynamic memory allow the size of arrays to be allocated during runtime?

Depending on arch, stack size might be more or less fixed. You have some memory area reserved for stack, say at addresses 0x00100000..0x00200000 and all variables locaated on stack will be somewhere in this area. Location of new variables is determined by (if I remember correctly) "stack pointer", which moves in direction determined by CPU. Whenyou add new variable on stack, stack pointer moves (direction of movement determined by CPU) by size variable, and variable will be located in addresses between old and new memory position. Because stack space can be limited, and because variables are adjacent (plus function return addresses are also stored on stack) you can't suddenly jam 2GB array in the middle of it. The main problem is not actually limited size, but variables being adjacent to each other.

Now, HEAP is different. Heap allocation, in theory, can return you any address from within entire address space, but in practice some addresses will be reserved (on 32bit windows you have only 2..3GB available out of entire 4GB space, for example). Because you have MUCH more space available, and because allocated blocks don't have to be adjacent, you can freely allocate big array and (in theory) even resize them (in practice functions like realloc probably just make new array, copy old contents into new array, then kill old array).

Please note that there are additional hidden details. For example, addresses returned to you by heap allocation functions are not physical addresses, but virtual addresses, and in reality OS can move your program in physical memory around, while (virtual) addresses used within program will remain unchanged.

That's why I suggest to read assembly book. you don't have to learn assembly in depth, but having some general idea of what happens behind the scenes, will certainly help.

SigTerm
  • 26,089
  • 6
  • 66
  • 115
  • 2
    By the way, on x86 runtime stack allocation can prevent optimizations, in particular "omit stack frame pointer". If each function knows in advance how much data it will have on the stack, the stack frame pointer is redundant: the position of each local variable can be calculated with fixed offsets from the stack pointer, so EBP can be used as an extra general purpose register and stack frame setup/cleanup code can be omitted; this is not the case with runtime stack allocation, which needs EBP-addressing. See also http://stackoverflow.com/questions/4343850/variable-length-array-penalty-cost – Matteo Italia Jun 22 '13 at 13:22
  • I would like to point out that some languages and compilers have introduced segmented stacks a while ago; while they may not work with extremely large stack allocations they do allow not hitting a stack-overflow error even on very deep recursions as you are given the use of all available memory on your system. – Matthieu M. Jun 22 '13 at 14:27
  • @MatthieuM.: That's why I added "Different CPU may use different rules". Regarding languages/compilers... I have not heard of such C++ compilers. Perhaps I simply don't know about them. As for another languages, I do not think it is relevant here. Post is marked as C/C++, and AFAIK C++ normally translates to machine code and uses native stack. If another language uses different kind of stack, that'll be non-native stack created specifically for this language. In other words - completely different story. – SigTerm Jun 22 '13 at 15:16
  • @SigTerm: actually, there is no mention of stack in C++; so it does apply to C++ as well, though it might require changing the ABI. Both Haskell and Rust compile to machine code and use a native *segmented* stack, there is no contradiction here. However all the methods I've seen up until now did introduce some overhead, though the best case is for the program seems to be intercepting segmentation faults (or some other kind of OS signal) and extending the stack then (note: the stack might not be extensible, in which case you need a linked-list structure for the stack). – Matthieu M. Jun 22 '13 at 16:53
3

The main reason for using the heap is not that you can use a variable amount of it. The main use is that it allows the memory to persist after a particular function finishes.

The standard for C99 and later (but not C++, although I believe some compilers (g++?) do have extensions that allow it, at least sometimes) allows "variable length arrays" in functions, but like fixed size arrays, they "disappear" when the function ends.

In the standard for C++, all arrays have to have a "known (constant) length at compile time". You have to use the heap to create something that isn't of constant length, known at compile time. It is "the way the language works".

Having said that, there is a reasonable reason for it as well. Stack space is very limited, and it's in fact quite "dangerous" to run out of stack, because there is NOTHING the program can do about that - it crashes, and there is no safe/reasonable way to recover. Running out of heapspace can be handled (there's a C++ exception thrown, but at least the program can display some reasonable error message, and perhaps continue in some way, even if it didn't succeed with what it was trying to do when it ran out of heapspace).

Of course, the "C++ way" is to not write code that manipulates array sizes manually, but use one of the pre-defined container types, such as std::vector and such like.

Edit Note that once an array is allocated from the heap, it remains whatever size it was when it was allocated. What can be done to alter its size is to allocate ANOTHER lump of memory, for a second array, of a different size, and then copy the contents of the "old" array into the "new" array - and as long as this is done in a way where the code can only ever see the "current" value of the array address [pointer to first element], nobody will know that it wasn't the same array.

Mats Petersson
  • 126,704
  • 14
  • 140
  • 227
0

The stack is limited in size and anything on it is gone when your function returns since the stack pointer is changed. Heap memory can be much larger and will live for as long as the application is running or someone calls a function to deallocate the memory.

However on Windows it still possible to allocate "dynamically sized" memory on the stack using alloca. This will be cleared in the same way any other stack based locals are cleared, hence you do not have to explicitly free the memory.

See here: http://msdn.microsoft.com/en-US/library/wb1s57t5(v=vs.80).aspx

paulm
  • 5,629
  • 7
  • 47
  • 70
  • "and is cleared when your function returns". Incorrect, stack pointer value changes, but the stack is not cleared. "alloca", but it is not possible to reallocate it, because there is no realloca – SigTerm Jun 22 '13 at 13:48
  • _alloca allocates size bytes from the program stack. The allocated space is automatically freed when the calling function exits (not when the allocation merely passes out of scope). Therefore, do not pass the pointer value returned by _alloca as an argument to free – paulm Jun 22 '13 at 13:52
  • So what I actually meant was that the function locals/alloc are cleared when the function returns – paulm Jun 22 '13 at 13:53
  • @pualm: also incorrect. Previously stored data still sits at the same address unchanged. Of course, it'll be overwritten by next stack operation, but it is not "cleared". The only thing that happens is that stack pointer changes, and that's it. – SigTerm Jun 22 '13 at 14:05