Stack and Heap - memory allocation

 

When you declare a new variable the compiler has to generate code that allocates sufficient memory to store the data it is to hold. The whole subject of memory allocation is a complicated and interesting one but every programmer should know about the two very general approaches - the stack and the heap.

Stack based memory is a natural match for the way that variables are allocated and created by a program constructed as a set of nested method calls - which most are.

What happens is that when a method is called all of its local variables are created on the top of the stack - creating its so called stack frame. While the method executes it has access to only its local variables i.e. its entire environment is limited to the data on the stack frame. Exceptions to this local only rule are global variables and objects but these are allocated on the heap.

If the method calls another method then the new method creates its stack frame on the top of the stack. In this way each new method can allocation its own local variables in its own portion of the memory allocated to the stack.

The beauty of stack allocation is that to implement garbage disposal all that has to happen is that when each method terminates its simply clears the stack of its stack frame i.e. it adjusts the stack pointer to point to the end of its stack frame so returning the memory to use. Of course when a method ends control returns to the method that called it and it finds the stack in just the state it needs to access its own local variables.

In this way each method gets access to its local variables while it is running without any need to keep track of where they are. The stack is also use to store parameters and return values passed between methods in a fairly obvious way. If you would like to know more about the theory of how a stack works then see "Stacks" in Babbage's Bag.

stack

The stack in action

The stack works well for storing all manner of data that is created and destroyed following the pattern of method calls - but for global data and for very large or complex data we need something else.

The alternative is the "heap". This is a very descriptive name for an area of memory that is set aside simply for the purpose of storing global data. When a global object is created, by the use of new in c#, an area of the heap is allocated big enough to store it at its initial size and a reference to its location is returned - often to be stored in a local variable on the stack.

However unlike local variables which are created and destroyed along with the method they belong to there is no clear signal that a global object is finished with. It doesn't necessary become redundant when the local variable that it was initially created with goes out of scope because there could be many variables referencing it. So to deal with this problem a system wide garbage collector is provided which keeps track of what is stored on the heap and how many references there are to each. When an object on the heap has no references to it then it is deallocated and the memory recovered.

This the general idea of heap management but in practice there are many subtle problems. For example as the heap is used and released is slowly becomes fragmented into small blocks of used heap separating blocks of free space. The solution is to make the garbage collector consolidate memory every now and again. Notice also that it is generally better to adopt a throw away approach to heap management. For example, if an object, a string say, needs to increase in size then rather than try to open up some space to make the current allocation bigger it is generally better to mark the current allocation as garbage ready for collection and allocation a whole new block of memory even though this involves copying the existing object.

 

 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.