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

user_264052 0
Viewed 16668

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 related 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?

ADD 1 - 10:42 AM 5/13/2022

The management of a stack only involves the instruction and registers (SP, BP), which is naturally/purely hardware in a sense.

While for a heap, it further involves complex software data structures and algorithms, which involves function calling (again stack involved), memory access, etc.

Hardware is fast but not as flexible as software.

Software is flexible but not as fast as hardware.

So heap is not cheap.

stack memory-management c
4 Answers

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.

unwind_281690

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.

user_709150

Creation of data on stack area : Just move the stack pointer Creation of data on head area : Search for area on the pool of memory that satisfies given requirement(You can use first fit,Best fit or worst Fit).After finding the area store the information(Book keeping)

Deletion on stack : Deletion on stack is easy.Just move stack pointer down Deletion on heap area : Find where the element is stored on heap(using book keeping) and merge two adjacent free blocks if necessary;

user_118884000
Related