What is slower about dynamic memory usage? [duplicate]

Question

I know that its faster to allocate memory on the stack than on the heap, but why is heap memory allocation slower? Is it because stack allocation is continuous and therefore the issue arises because of cache locality? Is it not the usage of the memory after it has been allocated, it is the time taken to allocate which is slower?

Answer 1

Caching issues aside, the CPU stack is just that, a stack, a LIFO list/queue. You remove things from it in the exactly opposite order from the one you put them there. You do not create holes in it by removing something in the middle of it. This makes its management extremely trivial:

memory[--stackpointer] = value; // push
value = memory[stackpointer++]; // pop

Or you could allocate a large chunk:

stackpointer -= size; // allocate
memset(&memory[stackpointer], 0, size); // use

and free it likewise:

stackpointer += size; // free

Your heap, OTOH, does not have the LIFO property. And for that reason it must keep track of all allocated blocks individually. Which means, it has to have some kind of list of free blocks and a list of allocated blocks and it needs to look for big enough blocks when allocating and look for the specified block when freeing and then likely do some block splitting and coalescing in the process. The simple stack does not need to do any of this.

This alone is a significant algorithmic difference between two ways of allocation and deallocation.

Caching and explicit calls to map physical memory into the virtual address space add up as well, but if you consider them to be equal in both cases, you still have a few instructions vs a few dozen to a few hundred instructions of difference.