From DesigningPatterns

Contents 1 Overview 2 Heap 3 Stack 4 Data Segment 5 Shared Memory 6 Summary

Overview

In general, there are four parts of a program's address space from which the memory for data could have been allocated: the stack, the heap, the data segment (which is further split into the initialized data segment and the uninitialized data segement, also called the bss), and shared memory. Space in the data segment is allocated at compile time, whereas space in the heap, the stack, and shared memory is allocated at run-time. Although each OS lays out the address space of a process differently, in general the heap and the stack grow towards each other.

Heap

Space from the heap is allocated at run-time. Once allocated, it will not be reclaimed by the heap unless explicitly deallocated. In C and C++, this generally requires explicit calls to free() and delete. Manual deallocation is very error-prone. It is common to fail to free the space when the space is no longer is necessary, in which case the memory cannot be reused until the process has terminated (this is called a memory leak). It also is very possible to free the same space twice, which can lead to heap corruption (because the memory was reallocated to some other part of the process after the first free). There are two common ways to tackle this problem:

• Running a garbage collector in your process. This automatically will deallocate memory when it detects that the memory no longer is being used, so that the programmer is not responsible for this. The benefits of a garbage collector are offset by the slowness that it can introduce into a program, in particular certain periods when it must be very active. A garbage collector also means that the programmer no longer explicitly is controlling the lifetime of objects allocated from the heap, which may not always be optimal.
• Manually deallocating memory, but testing the program against a memory error checker like Purify.

Allocation from the heap lends itself to multi-threaded programming, as each thread will get allocated different memory from the heap (assuming that the allocation scheme is thread-safe). Memory allocated from the heap is visible to all threads, which is good if one wants to share data between multiple threads but bad if one is tracking down memory corruption (since any thread could have corrupted the memory).

Allocation from the heap tends to be slower than allocation from the stack because:

• Heap allocations very often incur synchronization costs in order to provide thread safety.
• Heap allocations may result in a system call, if the program has exhausted its current allocation from the OS.
• Heap allocation algorithms are non-trivial and so some processing time may be incurred.

Allocation from the heap tends to be riskier than allocation from the stack in the absence of garbage collection because, in frequently executed code, a leak quickly can exhaust a process' available address space (causing a crash). This fact and the negative performance implications of heap allocations mean that, whenever possible, allocation from the heap should be avoided in real-time or highly available systems.

More recent languages such as Java and Ruby allocate almost everything from the heap (hiding the details of this from the programmer) and use garbage collectors. The robustness concerns are eliminated by not allowing the programmer to deallocate memory (and relying on a garbage collector), and the performance implications generally are not significant in their problem spaces. It is interesting to note, however, that both Java and Ruby do allocate their most commonly used data types (all primitive data types in Java and Fixnums in Ruby) on the stack for performance reasons (in fairness, this performance boost likely is not only due to storing the values on the stack but also to avoiding object initialization costs).

Stack

The stack is the store from which local variables are allocated in C and C++. The space automatically is deallocated once control returns to the previous stack frame. This means that leaking stack memory is impossible. In addition, because the stack allocation algorithm is trivial, stack allocations are cheap and bounded (in comparison to heap allocations, which may not be cheap and generally are not bounded). Finally, stack allocation lends itself very well to multi-threaded programming since each thread has its own stack. This means, moreover, that no synchronization is necessary for allocation from the stack (whereas it is for allocation from the heap, since all threads share the heap). This also means, however, that memory allocated on the stack by one thread never will be visible to other threads; thus, each thread in a C or C++ program has its own set of local variables.

Each OS provides a differently sized stack to its processes (and, in fact, different processes on the same machine can have different stack sizes). In general, however, one should not make "big" allocations on the stack, as it is very easy to allocate past the stack and trash the process' address space.

Stack allocations usually are sized at compile time (when local variables are declared) but can be sized at run-time (see alloca() on UNIX systems, for instance).

Data Segment

Allocations from the data segment are done at compile-time (in C and C++, global and static variables are allocated from this) and are built into the executable. The space always is allocated for the process lifetime. Any allocations in the data segment are visible to all threads, which generally means that synchronization is required if the data will be accessed by multiple threads.

Large allocations from the data segment could result in bloated executables.

Shared Memory

Shared memory allocation is not as common as the process-specific allocation forms (no language of which I know as language-level support for it). It is allocated via some kind of system call and allows multiple processes to communicate through memory, providing the fastest form of IPC. It has a lifetime independent of the lifetime of any process (including the process that allocated it); deallocation requires all processes to detach from it and for it to be deleted explicitly. This can be a way for applications to persist information past their lifetime (ensuring that state is not lost in a crash, for instance). If multiple threads of control are accessing the memory at the same time, synchronization generally is required.

Summary

Memory Types

Type	Allocation Time	Allocation Sizing	Deallocation Time	Allocation Performance	Threading Issues
Heap	Run-time	Run-time	Run-time	Not as good as that of the stack and not bounded	The memory allocated is visible to all threads, although the allocation itself should be thread-safe.
Stack	Run-time	Most often compile-time, although it can be at run-time	Run-time	Very good, bounded	The memory allocated is not visible to other threads.
Data Segement	Compile-time	Compile-time	Process termination	N/A (since it's not happening at run-time)	The memory allocated is visible to all threads.
Shared Memory	Run-time	Run-time	When explicitly deleted and no processes are attached	Requires a system call to allocate the memory from the OS and, depending on what is done with the memory once allocated, may require further operations	Multiple processes can attach to the memory; the memory will be visible to all threads in an attached process.