Performance btw. Stack-Heap Dynamic Arrays

Question

In programming languages concept, Sebesta's book states that (Ninth ed., 284): The disadvantage of fixed heap-dynamic arrays is that they take longer time to allocate array from stack. How can we analyze this statement? What is the difference between fixed heap-dynamic and heap-dynamic arrays. What does that fixed word stand for?

Accepted Answer

Allocating memory off the stack is very simple. You just need to adjust the stack pointer. On x64, it's a single instruction:

```
sub rsp, size
```

Heap allocation requires some memory management mechanism to look for a block large enough to hold the array, choose a block, mark it as allocated somewhere, and possibly asking the OS to allocate more memory pages by growing the address space of your process. It's much more complicated than stack-based allocation.

Re "fixed", since I don't have the book, I don't know the context it's using that word. Probably it means the array will not move in the heap after allocation.

Performance btw. Stack-Heap Dynamic Arrays

Solution

Problem