Why is the main memory for object allocation called the ‘heap’

heapmemoryprogramming-languagesstack

Has anybody got an idea why the area of main memory where objects are allocated is referred to as the heap. I can understand the rationale for that of the stack LIFO but would like to know what the rationale is for the 'heap' name.

Best Answer

From the information found at StackOverflow - What is the origin of the term “heap” for the free store? and Why are two different concepts both called “heap”?

This information at least dates back to Knuth in 1975 referencing other (unnamed) authors:

Several authors began about 1975 to call the pool of available memory a "heap." But in the present series of books, we will use that word only in its more traditional sense related to priority queues. (The Art of Computer Programming - Fundamental Algorithms, 3rd ed., p. 435)

There is also mention of Wijngaarden discussion on Algol in the early 1970s referring to the available memory pool as a heap (heap is a reserved word in Algol which is defined in places as "allocate variable some free space from the global heap." - Algol68 dates from 1968).

Implementing the ALGOL 68 heap from 1970 may be of use in tracking down some aspects of word origin, though much if it is behind a paywall.

Related Solutions

Stack and Heap Memory Management in Java

The basic difference between stack and heap is the life cycle of the values.

Stack values only exist within the scope of the function they are created in. Once it returns, they are discarded.
Heap values however exist on the heap. They are created at some point in time, and destructed at another (either by GC or manually, depending on the language/runtime).

Now Java only stores primitives on the stack. This keeps the stack small and helps keeping individual stack frames small, thus allowing more nested calls.
Objects are created on the heap, and only references (which in turn are primitives) are passed around on the stack.

So if you create an object, it is put on the heap, with all the variables that belong to it, so that it can persist after the function call returns.

Stack vs Heap – Why Use a Heap if Stack is More Efficient?

The problem with stacks is that you can't "free" memory unless it is on top of the stack. For instance, say you allocated 3 things of varying sizes:

a = allocate(2000000); // 2000000 bytes
b = allocate(1);
c = allocate(5000000);

The stack would have a on the bottom, b in the middle, and c on top. This becomes problematic if we want to free b:

free(b); // b is not on top! We have to wait until c is freed!

The workaround is to move all the data after b and shift if so that it comes after a. This works, but will require 5000000 copies in this case - something that will be much slower than a heap.

This is why we have a heap. While allocation may be slower than a stack (O(log n) vs O(1)), heaps allow freeing memory at an arbitrary location to be fast - O(log n), compared to a stack's O(n)

Best Answer

Related Solutions

Stack and Heap Memory Management in Java

Stack vs Heap – Why Use a Heap if Stack is More Efficient?

Related Topic