Re: Stack vs. heap?

["mdj" <mdj.mdj@gmail.com>]

Martin Doherty wrote:
> I believe I thoroughly understand the operation of a stack, but the term
> "heap" is a mystery.  I know it's used in UCSD/Apple Pascal for memory
> management functions of some kind; can anyone explain to me what a heap
> is in general concept, and what it's used for in Pascal?

In general, the 'heap' is the block of space, either starting where
your program code ends building up, or starting where memory ends
building down, which is used for dynamic memory allocation.

The Apple's 6502 has a fixed hardware stack, which resides at memory
locations $100-1FF. Most systems even slightly more modern than 6502
allow the stack to be placed anywhere in memory, so it usually ends up
at one end of program space or the other, depending on the way the CPU
works.

In Apple Pascal, while it's called a 'heap' the actual data structure
employed is a stack. You have a pair of operations - mark, which
records the current top of heap, and release, which sets the current
top of heap pointer. Each time you call new in pascal to allocate a new
object, the top of heap pointer is decremented by the number of bytes
it takes to store an object of that type.

So that's Apple Pascal, who's heap is actually a stack. Most
implementations of Pascal include an operator called dispose, which
teamed up with new, does automatic heap management. Unfortunately you
don't have this functionality in Apple Pascal. In C, the equivalent
standard library functions are malloc(), and free() (althought C also
has a realloc function for convenient resizing of arrays, etc)

You'll actually find that most systems use a fairly simple allocation
scheme for heaps, like a linked list.

Now if that's not confusing enough, this heap is not to be confused the
data structure called a heap, which is (generally) speaking a
specialised form of tree structure, such that a parent node is always
greater than, or equal to it's children. This is commonly used to
implement priority queues, or sometimes for sorting.

You'll find that in general when people refer to the heap, they're
talking about the block of memory used for storage allocation, not the
data structure.

You'll also find in general, that computer programs are comprised of
heaps of stacks, but not stacks of heaps (sorry, couldn't resist the
joke) ...

Hope this explains it - I'm sure others will jump in and clarify.

Matt