Joe said:
Can someone explain what a heap and what a stack is? And why I should
care? I used to know, but then I forgot. And I can't seem to find it in
the C++ FAQ.
A stack is a data structure that runs Last In First Out. That's so efficient
and convenient that CPUs generally implement a stack in hardware, so
functions can park their local variables on it. When they call servant
functions, these add their variables to the current head of the stack, then
point the head to the next spot after their variables. So that's how
functions can call functions, each keeping private variables for as long as
each function runs.
A heap is simply the opposite of a stack. You can allocate and de-allocate
arbitrarily sized chunks of heap, in an arbitrary order.
I keep reading how allocating from the heap is slow or something, and I
have no idea why that would be.
A heap must perform much more work at allocation and deallocation time. It
searches for a good unused region, checks this is larger than the requested
size, writes markers around the block to reserve it, fixes up other markers
in the heap to point correctly, and returns a pointer to the block. When it
gets the block back from the program, it erases the markers, and fixes up
the other markers.
A good alternative is a custom heap that returns fixed sized blocks. That's
orders of magnitude faster. If each block is larger than a pointer, then the
heap can store its list of free blocks directly into storage area. Each free
block contains a pointer to the next free block.