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?

Answer 1

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.

Answer 2

If the heap could be grown to accommodate each new allocation then creating an array could be quick. If the heap is "fixed" then we need to find space within the heap and as Mehrdad has explained that requires non-trivial work.

I don't quite parse the end of the sentence though:

The disadvantage of fixed heap-dynamic arrays is that they take longer time to allocate array from stack.

You don't allocate heap memory "from stack" surely.

Answer 3

The terminology comes from three orthogonal concepts:

• Whether the size of the array can change after its initial allocation, or stays the same size forever, "fixed".
• Where the array is located: stack or heap memory.
• If the allocation size is determined at runtime "dynamic", or compile-time.

Answer 4

The answer from ergosys has the terminology exactly right. The question is yet another example of why I hate Sebesta.

In many modern systems, allocating an object from the heap uses exactly the same instructions as allocating from the stack: test and increment the heap pointer. (It it true that it is easier to combine stack allocations than to combine heap allocations, but than can be done too.) Compilers that do this kind of allocation include the Glorious Glasgow Haskell Compiler and Standard ML of New Jersey. SML/NJ has been deployed in this condition for over 20 years, so you think Sebesta might have picked up on it by now.

Summary: Sebesta is overgeneralizing, as usual. There may be reasons to prefer stack allocation, but the story is far more complicated then Sebesta seems to realize, or than Mehrdad describes in his answer. A good place to start with understanding the deeper story is with Andrew Appel's paper about stack allocation.