1
$\begingroup$

In stack-based memory allocation: is memory allocated at compile time? If so, then how can we allocate space for, say, n number of recursive calls made during the execution of the program?

$\endgroup$
1
$\begingroup$

The amount of stack space allocated to a process (or a thread, if you are talking about multithreading) is decided at run time, when it starts - usually by the system, which just allocates a fixed amount without regard to what the program might actually need: "allocate a megabyte and keep your fingers crossed". Alternatively, when creating a thread within a program, it is sometimes (depending on the system) possible for the programmer to specify the size of the stack required by the thread - but this, too, is done before knowing what the thread's real requirements might be.

With virtual memory, of course, what is really allocated is address space rather than actual memory, so in principle one could just increase the address space allocated to each thread and cross one's fingers a little less. But the same point remains: a fixed limit is being imposed, in advance, without knowing what is actually going to be needed.

Ultimately no reliable computer system can have both unlimited recursion and stack-based storage. Mainframes such as the IBM 360 did not use stacks for return addresses or for local storage. There are "stackless" implementations of various programming languages - any programming language could be implemented stacklessly if people really wanted to do it.

This Stack Exchange answer goes into much greater detail, more rigorously.

$\endgroup$
  • $\begingroup$ 1. Withmodern 64-bit computers we have a plenty of address space, so we can allocate more address space than entire ram+hdd of particular computer; 2. there is chunked stacks, even for C++ (f.e. implemented by GCC) and probably may more languages $\endgroup$ – Bulat Jul 16 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.