Why memory allocation on heap is MUCH slower than on stack?

Question

I have been told this many times. But I don't know WHY...What extra cost is involved when allocating memory from heap? Is it hardware related? Is it realted to CPU cycles? So many guesses but no exact answers...Could someone give me some elaboration?

Just as "unwind" said, the Heap data structure is more complicated than Stack. And In my opinion, some memory space is allocated to a thread as its Stack when it starts to run, while the heap is shared by all the threads within a process. This paradigm require some extra mechanism to manage each thread's usage of the shared heap, such as Garbage Collection. Am I right on this?

Thanks in advance.

Answer 1

Because the heap is a far more complicated data structure than the stack.

For many architectures, allocating memory on the stack is just a matter of changing the stack pointer, i.e. it's one instruction. Allocating memory on the heap involves looking for a big enough block, splitting it, and managing the "book-keeping" that allows things like free() in a different order.

Memory allocated on the stack is guaranteed to be deallocated when the scope (typically the function) exits, and it's not possible to deallocate just some of it.

Answer 2

The main difference between a stack and a heap is that items on a stack cannot be removed out of order. If you add items A, B, C to a stack, you can't remove B without removing C first. This means that adding a new item to a stack always means adding it to the end of the stack, which is a very simple operation. You just move the pointer that points to the end of the stack.

On a heap on the other hand, you can remove items out of order. And as long as you don't move the other items around afterwards in memory (as some garbage collected heaps do), your heap then has "hole" in the middle. I.e. if you add A,B,C to a heap and remove B, your heap looks like this in memory: A _ C where _ is a block of unused (free) memory. If you add a new item D now, the allocator has to find a continuous free space big enough to fit D. Depending on how many continuous free spaces there are in your memory, this can be an expensive operation. And it's almost always more expensive than just moving the "last element" pointer of a stack.