Why is stack memory "cheaper" than heap memory in C?

Question

Compare the following two:

int arr[10]; // stack memory
int* x = malloc(sizeof(int)*10); // heap memory

Both are essentially allocating 10 integer variables. However, we often say that the first one is much cheaper (faster to alloc and dealloc) b/c it simply moves ahead the stack pointer.

We know that all programs run in virtual memory space, and only the portion that a program actually uses will be allocated (aka mapped to physical memory), and unused ones stay virtual. And that's how the OS shares physical memory between different programs.

So here comes my question. It seems to me that no matter how you allocate the memory (on stack or on heap), one thing in common is that the OS needs to find & reserve a physical memory block, and map the virtual memory address, whether its on stack or on heap, to the physical address. The same for deallocation, when the system needs to remove the mapping & free the physical memory. Then why is stack allocation/deallocation faster? The biggest overhead in memory allocation seems pretty fair between the two.

Answer 1

Calls to malloc and free typically require somewhere between a few 100's and a few 1,000's of instructions on average depending on implementation, current fragmentation of the heap, and other details.

Allocating and deallocating the stack frame for a function requires on the order of 4 instructions.