Storage Hierarchy

A typical computer has several different levels of storage. Each level of storage has a different speed, cost, and size. The levels form a storage hierarchy, in which the topmost levels (those nearest the processor) are fastest, most expensive and smallest.

Levels typically include processor registers, possibly some levels of cache(1), main memory, and possibly some levels of backing store.

Each level is commonly used as a cache(2) for the next level. For instance, virtual memory systems use main memory as a cache for backing store.

MORE EXPENSIVE / FASTER / SMALLER

| CENTRAL PROCESSING UNIT
| – Functional Units
| | PHYSICAL MEMORY
|Registers
| |Internal Cache
| – External Cache
| – Main Memory
– Backing Store

CHEAP / SLOW / LARGE

Static Allocation

Static allocation means allocation of memory(1) before the program starts and retention until the end.

The locations of objects are basically decided at compile-time, although they might be relocated at load-time. This implies the sizes of the objects must be known then.

Using only static allocation is restrictive, as sizes of data structures can’t be dynamically varied, and procedures cannot be recursive. However, it is also fast and eliminates the possibility of running out of memory. For this reason, this scheme is sometimes used in real-time systems.

Stack Allocation

Stack allocation means run-time allocation and deallocation of memory(1) in last-in/first-out order.

Typically, stack allocation is performed on top of the main stack, but one can have a separate data stack for this purpose as well, as in Forth, or even multiple ones, as in the PostScript language.

Allocation and deallocation are typically fast, since they can be done simply by adding or subtracting the size of the block from the stack pointer.

Using only stack allocation, without heap allocation, is somewhat restrictive, as only objects whose size is known at compile-time can be returned from a procedure.

Some programming languages (such as some versions of Lisp and C) provide program-controlled stack allocation and deallocation of dynamic extent objects for efficiency, despite its being unsafe.

Static Storage Duration

In C and C++, the static keyword applied to a file scope variable or function means it is local to the file; the static keyword applied to a function or a block scope variable means it is allocated and initialized once only.

Objects declared locally in blocks with the static keyword are allocated in static memory(2), and initialized once (usually by the compiler/linker) instead of each time the block is entered.

Static variables within functions retain their value between function invocations, and therefore must form part of the root set of any collector(1).