Stack and heap – dynamic allocation question

Sources usually mention that dynamically created variables are allocated on the heap, while functions’ variables on the stack. Also the ones on the stack cease to exist automatically when e.g. the function which contains the variable exits. If I understand correctly, data fields of class are on the heap.
I do not understand, what is meant by ‘dynamic’? As I see it, when the code is running, anything being created is created dynamically on the fly, be it function variables or objects with variables inside them. I would be glad for simple explanation. Thanks

I agree that “dynamic” is a poor choice of words, but we’re stuck with it now. It basically means the memory allocation is done explicitly by the programmer, using something like new or malloc, instead of automatically by the programming language, as in a function’s local variables.

In most contexts, “dynamic” refers to memory that the programmer explicitly allocates, as opposed to the memory that is allocated as the normal part of entering a function (reserving space for parameters, local variables, etc.).

Let’s take the following C function as an example:

void foo(int x, int y)
{
  int z;
  char *str = NULL;
  ...
  str = malloc(sizeof *str * y);
  ...
  free(str);
}

When we enter the function, space is automatically reserved on the stack for x, y, z, and the str pointer (remember stack elements are allocated in last-in, first-out order). Moreover, the amount of space to reserve for each object is fixed at compile time (based on the sizes of the respective types). If you look at the stack frame, it will look something like this (assume int and char * are all the same size):


+--------+
|        | <-- y           STACK BOTTOM
+--------+
|        | <-- x
+--------+
|        | <-- z
+--------+
|        | <--str          STACK TOP
+--------+

When we exit the function, all the elements between “STACK BOTTOM” and “STACK TOP” will be popped (deallocated).

I do not control memory allocation at this level; this is all done automatically for me when I enter and leave the function. However, within the function I want to allocate some memory for str to point to. Moreover, the amount of memory I want to allocate isn’t fixed, but is determined at runtime from the value of the y parameter. The malloc call reserves some memory from the heap (an area of memory distinct from the stack, which is managed differently as well) and assigns the address of that memory to str. That memory stays allocated until I explicitly release it with a call to free; if I don’t do so before the function exits, the str variable gets deallocated (meaning I lose my reference to that dynamically-allocated block), but the memory it points to does not (this is known as a memory leak; once I lose my reference to the dynamic block, I can’t free it).

Java behaves ever so slightly differently:

public void foo(int x, int y)
{
  int z;
  String str = new String(); // don't need to specify a length as with malloc
  ...
}

Similar to C, Java will reserve space on the stack for each of x, y, z, and a str pointer (yes, Java uses pointers under the hood, it just doesn’t expose pointer operations to the programmer). Similar to C, the new operator reserves memory for the String object on the heap at runtime. Unlike C, Java monitors objects on the heap to see if they are being referenced by anyone (such as the str variable). Once the Java function exits, all references to the dynamic memory cease to exist, and an automatic garbage collector will eventually deallocate that memory, so I don’t have to explicitly free it (in fact, Java doesn’t provide an equivalent to the free function).

You should think of the stack as an optimization, an implementation detail. Unfortunately, the abstraction that is memory management tends to be leaky. Some languages leak it a lot (I’m looking at you C) and some leak it…less (i.e. Java).

When you need memory, by default, you can imagine that it all goes in the heap. It’s possible, under any set of circumstances, to use heap memory to solve all problems. Allocations to the heap can be of a size unknown until right when you need it, and can live for an indeterminate amount of time. Allowing those qualities comes at a cost though. Different languages manage it differently, but the point remains that time and effort is spent by the language, in some way, to both allocate, deallocate, and potentially defragment memory in the heap.

Not all memory that’s needed needs that level of flexibility. There are a number of very common contexts in computer programming in which the memory needed is of a size known at compile time and with a scope that contains certain well defined properties. When you call a method you know that the information in memory that represents the parameter list, the return value, and the local variables is of a fixed size, and you know that all new allocations of memory will leave scope before any memory stored at the time it was allocated. This follows the exact implementation of the data structure known as a Stack.

A stack, as a general data structure, is where the last in is the first out. You push items onto it, and then pop items off of item. The item poped is the item most recently pushed on (that’s still in the structure). So we assume that there’s a stack that holds onto memory. When we start execution of a new method we know that the memory we allocate for that method (all methods need memory for their arguments, return value, and local variables). If we push all of that memory onto the stack it will need to be pushed off of the stack before any items “above” it in the stack can be pushed off. This is okay. We know that the memory of the method that called “us” won’t need to be freed until after we finish, and we know that any methods we call will have their memory both allocated and freed before we need to be freed.

Managing this type of memory is much easier than managing heap memory. It’s very quick and easy to add new memory to the stack, and very easy to take it off. The “stack” is really just a long contiguous block of memory with at pointer to the “end” of the stack. Allocating new memory is as simple as increasing the stack pointer and telling someone which addresses they are allowed to access, and deallocating is as simple as decreasing the stack pointer by a fixed value. Adding/subtracting a fixed value to a pointer is very fast and easy for a computer.

So the entire purpose of the stack is not to allow additional functionality; in fact using the stack is more restrictive than using the heap, and most complex programs tend to have at least some situations in which the restrictions of stack memory are prohibitive, so you’ll still need a heap. Stack memory simply allows much quicker allocation and deallocation of a certain uses of memory that meet the restrictions of a stack.

Dynamic pretty much means the number of bytes is not known until runtime:

 void f(int a) {
    int *array=new int[a];
    ...
 }
 int main() {
   f(10);
   f(22);
 }

Having both f(10) and f(22) supported(without separate instances of f) means that the memory block size changes on the runtime.

Filed under: softwareengineering - @ 00:19

Thẻ: heap, stack, theory, variables

Thiết kế website giá rẻ

Danh mục

Stack and heap – dynamic allocation question