11
$\begingroup$

I'm writing a register- and stack-based virtual machine. My goal is to have something easy to use and general purpose, so I abstain from any form of hardware limitation in its design. Since my VM's stack is implemented with a high-level data structure (the Stack provided by .NET), there is no theoretical limitation on its size. Knowing that I am able to define a stack of indeterminate size (limited only by hardware) my question is whether or not I should limit the stack size for my VM.

I see the following theoretical advantages to an infinite stack size:

  • No overflow can occur ;
  • Deep recursion is possible.

I also see the following disadvantages:

  • An overflow is sometimes a sign that there are things to improve in the underlying code (typically a recursion that should be changed to a loop or with continuations) which the VM will then no longer raise;
  • A VM stack of indeterminate size can massively overflow and slow down the computer (in the extreme case).

For example, Python, C# and Java (to name but a few) are all languages compiled in a stack-based VM where overflow is possible.

So, given that a stack implemented in a virtual machine interpreter is able to have an infinite size, why would we limit its capacity or not?

$\endgroup$
10
  • 1
    $\begingroup$ Welcome to PLDI Stack Exchange! This question is soliciting design tradeoffs but does not define what a good answer is. I advise you to refine it so it describes a specific implementation problem to be solved, as detailed in the help center. $\endgroup$
    – Ginger
    Commented Mar 12 at 18:50
  • 3
    $\begingroup$ I think it should have some minimum below the RAM limit, because otherwise an infinite recursion will slow your system and take longer to overflow, and in practice, operations which use a lot of stack size are usually non-ideal (you shouldn't be doing O(n) stack recursion if your function can be implemented with a tail call). You can make the limit higher than C though, like 512 MB (what Haskell used to use). $\endgroup$
    – tarzh
    Commented Mar 12 at 18:52
  • 1
    $\begingroup$ But it depends on whether the language is suited more or less towards recursion, and maybe there are other factors for smaller stack sizes I'm not aware about. In practice I've rarely seen Stack Overflows which weren't infinite recursion (or overly large so that the algorithm would take too long to compute if it didn't terminate). And when I did, I think it made sense to rewrite the algorithm to use tail recursion or something else anyways. Maybe it's less expensive to write your own "stack" in a function that needs to recurse a lot. $\endgroup$
    – tarzh
    Commented Mar 12 at 18:57
  • 2
    $\begingroup$ Note 'fixed' also means that you want it to be independent of later changes. If you make it, e.g. 8KiB, someone will use 8191B and then get annoyed down the line when a later bugfix makes your implementation use an extra 4B internally. $\endgroup$
    – TLW
    Commented Mar 15 at 12:55
  • 1
    $\begingroup$ Stack sizes stay small (8MB for x86/64) even on high end servers/supercomputers (unless you're talking about ones specialised for a recursive algorithm), its more often a problem the other way round, e.g. porting java to arduino would be difficult/impossible (from cursory googling, it seems to be implemented in hardware extention boards) $\endgroup$ Commented Mar 21 at 12:05

5 Answers 5

17
$\begingroup$

given that a stack implemented in a virtual machine interpreter is able to have an infinite size, why would we limit its capacity or not?

Great question, let me first nitpick and say that "unbounded" is intended for "infinite" here. No stack ever has an infinite size.

For the purposes of this discussion I'd like to distinguish between an infinite recursion, where a bug in a recursive algorithm means that it never reaches its base case, and a finite but unbounded recursion, where the depth of the recursion is equal to the size at runtime of the data passed in; we recurse on every node in a linked list, and so if we want a thousand, a million, a billion calls all we have to do is pass in a list of a thousand, a million, a billion items.

I can maybe give you some insights into how we would consider this question when designing a general-purpose language like C# for a general-purpose runtime like the .NET CLR.

For example, Python, C# and Java (to name but a few) are all languages compiled in a stack-based VM where overflow is possible.

Yes, but let's again be precise about C#, since that's what I know best. "Possible" is correct. The CLR specification does not say what size the "short term memory pool" is, and it does not put any particular limit on the depth of calls. Nor does it guarantee that unbounded calls will blow the stack. The CLR reserves the right to optimize tail calls, and historically has done so with... mixed results at best let's say.

And of course C# has closed-over locals, coroutines, lots of ways that activations don't form stacks, so continuation information can be stored on the long term pool at the discretion of the compiler.

But I'm getting ahead of myself. Let's talk a bit about your typical Windows implementation of the CLR and how both manage the stack. Do forgive occasional simplifications where the messy details are not relevant for your purposes.

The CLR spec does not require any particular implementation strategy as far as stack management is concerned, but the Microsoft implementations typically do the following: IL is JIT-compiled into machine code, and that machine code is what you'd expect. The temporary storage pool is implemented as a bunch of pages called "the stack", one stack per thread. The stack holds activation frames for unlifted locals that were not optimized into registers, and continuations in the form of return addresses. (And continuations for exception control flow and so on.) Frame size is limited in the CLR and I don't recall what the limit is, but it's large enough that you're not going to hit it in reasonable code.

Windows commits 4MB per thread (on 64 bit processes; 1MB for 32 bit processes) to page file and faults them into RAM as they are hit. A special page at the top is set to produce a different fault when it is hit; when that fault happens the CLR issues a stack overflow exception. This exception can be caught, but it cannot be ignored; it is re-thrown automatically. (If the top page is faulted a second time, Windows terminates the process, but in practice the process almost always completes.)

Windows allows for threads to have stacks larger or smaller than the default, but it is rare indeed for line-of-business (LOB) programmers to change that limit from the default of 4MB / 1MB.

Some relevant consequences of this implementation decision are:

FIRST: The JIT compiler can generate optimized code quickly; we have many many decades of experience generating code that reifies activation and continuation onto the stack. Common CPUs instruction sets are highly tuned for this pattern. The performance penalty of managed code vs native code is relatively small.

SECOND: The maximum call depth for "normal" calls -- not tail calls, not coroutines, and so on -- is small. Typically some thousands of calls. Worse, since frame sizes vary depending on the choices of both the C# and JIT compilers, there is no set call depth limit, unlike, say, some implementations of Python. A program with unbounded "normal" recursion will crash when given data of sufficient size. Correct .NET programs that do finite but unbounded recursions are fragile when given deep data structures at runtime.

THIRD: Truly infinite recursions -- the base case never runs -- typically crash your program with an unrecoverable exception. Buggy programs fail fast.

What were the effects of these consequences on the design of C#, a language specifically designed to appeal to professional LOB developers familiar with the C++ family of languages looking for a safer alternative?

Remember, the "design" part of language design is about making reasonable compromises in a world with many incompatible goals.

First consequence: Performance

For better or worse, the original dev teams knew that .NET 1.0 and C# 1.0 were going to be heavily judged by a few speed benchmarks. Keeping the perf penalty of managed code very small was an absolute hard requirement.

You might think, ok, we've got an absolute requirement, so, where's the tradeoff? We've still got to think about the down sides and figure out if they are so down that they're ship-killing, and if not, how to mitigate them.

Second consequence: fragility of "unbounded" recursive programs

This is horrible. C# is general purpose, it runs on clients and servers, there are critical business processes written in it, it's got to be robust.

But due to the first consequence, language designers are in a cleft stick not of our own devising. We've already traded robustness for performance in the design of Windows and the CLR. We need to make language design choices in this environment.

Fortunately, C# programmers were assumed to program like traditional C/C++ programmers, with arrays and loops, not like Schemers with their fancy "lists" and "recursion". (Those Schemers are always up to something suspicious.)

The situation is bad, but the vast majority of OOP LOB programmers aren't ever going to write a program with unbounded recursion on immensely deep data structures. Their programs will work as intended, and run fast, so we can live with this bad situation, and make sure the design of the language appeals to these traditional procedural / OOP programmers.

Third consequence: infinite recursion programs fail fast.

No one cares.

Not one bit.

OK, we cared, but let me explain. How does a bug get to a customer?

  • The developer thinks a bug
  • Then types it into a code editor
  • Then compiles it
  • Then tests it
  • Then reviews and commits it
  • Then nightly tests don't find the bug
  • And so on, and the bug ships to customers.

Each time the bug makes it another step along this path the cost of the fix goes up 10x.

LOB language designers take this seriously! Designing languages, development environments and testing systems that enable developers to identify the bug earlier rather than later is goodness.

What about infinite recursion bugs? Again, not finite but unbounded recursion, where programs are fragile when given large inputs. "You forgot the base case" bugs, where the recursion never bottoms out even on small inputs. Do we care that this fails fast?

No. These kinds of bugs rarely ship to customers because they rarely survive the "test it" phase! An unbounded recursion is just like an infinite loop. Any test case that exercises that code path is going to misbehave badly enough that the test won't pass.

Given the choice between "fail fast and shut down cleanly" and "grind to a halt, chew up memory, never complete" would we prefer "fail fast"? Yes! The fact that we get this is certainly a "nice to have". But "nice" is not anywhere close to a high priority for this language design if we're making real tradeoffs.


I know that was a very long answer but trading off performance vs robustness is a fundamental design problem for a runtime, and loop-centric vs recursion-centric is a fundamental design problem for many languages, so you are very right to think carefully about this question.

If you're building a functional style language for developers expecting to have unbounded but finite deep recursion on very large data structures, then limiting your virtual stack, or reifying an unbounded virtual stack as very-bounded Windows stack are probably bad ideas -- unless you are also going to work hard on tail recursion or continuation passing style or other fun rewrites.

If you have strict high performance requirements (particularly when compared with tightly optimized machine code) then the .NET Stack class is unlikely to butter any parsnips. Thinking about this now is not a premature optimization; it's ensuring that the requirement is more likely to be met. But maybe your requirements aren't that high.

$\endgroup$
7
  • $\begingroup$ Excellent answer, especially in your cleanup of the terminology. But one nit related to that: I think when you say "tail calls," you actually mean "tail call optimisation," right? $\endgroup$
    – cjs
    Commented Mar 15 at 5:59
  • 1
    $\begingroup$ off-topic, but is the Windows default stack size really 1 MB, not 1 MiB? Or is that just an issue of wanting to write in words not numerals, and like any sane person not wanting to write "mebibytes", or something really verbose like one million, forty-eight thousand, five hundred and seventy six? Or is it actually 1MiB including the 4K guard page or something, or even ~48 KiB of guard pages leaving about 1 MB? $\endgroup$ Commented Mar 15 at 18:29
  • $\begingroup$ (Trying to answer that question, I found docs like learn.microsoft.com/en-us/windows/win32/procthread/… which just use MB when perhaps they meant MiB so that's no help. They do talk about 64 KB granularity, with a capital K implying KiB. And some comments on Why is stack size in C# exactly 1 MB? talking about 1572864 = 1.5 MB and 1,048,576 = 1 MB.) $\endgroup$ Commented Mar 15 at 18:46
  • $\begingroup$ @cjs: By a tail call I mean that when the last thing a workflow does is call a method and return its result, then an implementation may choose to re-use the existing stack frame for the new call. Whether a tail call is an optimization or not depends on your cost function! $\endgroup$ Commented Mar 15 at 23:58
  • 1
    $\begingroup$ @cjs: Oh, I understand the distinction you're making now, thanks for clarifying. Yes, I meant specifically optimized tail calls. I'll clarify the text. $\endgroup$ Commented Mar 18 at 17:44
13
$\begingroup$

Consider what will happen when a user's program has a bug causing infinite recursion. If your call stack has a bounded size, then their program will raise a runtime error due to overflowing the call stack. If it does not, then their program will raise a runtime error or worse due to running out of memory.

Either way, there is in practice a limit, but in the second case the limit is less predictable, and in the second case running into the limit causes more problems. This is why implementations like CPython which don't use the "real" stack, still impose an explicit limit on the stack size.

It's worth keeping in mind that out of all programs which overflow the stack, the vast proportion of them do so by recursing infinitely due to the programmer's mistake. So even allowing the stack to use all available memory won't help these programs. If you want to support the few programmers who want to intentionally use deep call stacks, you could allow them to opt in via something like Python's sys.setrecursionlimit.

$\endgroup$
26
  • 2
    $\begingroup$ it seems reasonable to have general mechanisms for space accounting. it seems unreasonable and arbitrary to have a mechanism restricted only to the stack $\endgroup$
    – Moonchild
    Commented Mar 12 at 21:29
  • 4
    $\begingroup$ @Moonchild Why unreasonable? The stack is an area of memory which can be exhausted very quickly if a program exhibits infinite recursion (a common programming mistake), and which otherwise rarely needs to exceed a moderate limit. In most programs, allocating a lot of memory is not clearly a mistake, but an excessive stack depth is. There are also mechanisms to limit heap usage, of course (e.g. Java's -Xmx flag), but a mechanism which only limits the stack is useful because it can be configured more easily according to the number of frames, rather than absolute space. $\endgroup$
    – kaya3
    Commented Mar 12 at 21:49
  • 2
    $\begingroup$ @Moonchild The difference is that a programmer can much more easily know how big of a stack limit should be sufficient for their program, without having to figure out what that translates to in bytes. If your recursive function is going to call itself 10,000 levels deep then a maximum recursion depth of 11,000 is definitely plenty. $\endgroup$
    – kaya3
    Commented Mar 12 at 22:25
  • 4
    $\begingroup$ Would you agree with the similar argument for loops? That is: infinite loops are a common bug, so every time we go through a loop again we should update a counter and if that ever exceeds the "loop size", raise a runtime error rather than allowing the program to potentially do something even worse. If you would not agree with it, what is different in your mind between looping control flows and recursive control flows? $\endgroup$ Commented Mar 12 at 23:22
  • 2
    $\begingroup$ @EricLippert The difference is that in the typical case, infinite recursion of regular functions will necessary consume more and more memory until the program fails, so it is just a question of whether to have it fail with a stack overflow error or less gracefully with an out-of-memory error. This reasoning clearly doesn't apply in several cases ─ notably TCO (in which case recursive calls don't grow the stack), stackless coroutines, or regular infinite loops that don't involve function calls ─ but a stack size limit doesn't affect those cases anyway. $\endgroup$
    – kaya3
    Commented Mar 12 at 23:56
5
$\begingroup$

In the face of language implementations where the stack cannot have unbounded size, algorithms which could otherwise be cleanly expressed become contorted, and must use mechanisms like explicit stacks or continuation-passing style, obscuring the flow of control and computation. This is not very nice.

a stack that may grow to infinity (for example, with a non-optimized recursion that never ends) takes up a lot of memory and might slow down computer operation (if we take an extreme case)

If you need a lot of memory, then you need a lot of memory; the question is simply where and how you allocate it. I could as easily say:

a heap that may grow to infinity takes up a lot of memory and might slow down computer operation (if we take an extreme case)

$\endgroup$
1
  • $\begingroup$ I have little to add to this. Recursive implementations are often the most straightforward. There is no inherent reason these "should" instead be using loops or continuations when they can use a suitable call stack just as well; it's just complicating the implementation. I feel all the people who argue that recursion should be crippled may be leaning too heavily on the imperative side of things. What would they say if I limited their loops to 16k iterations, or their arrays to 16k elements "in case you have an infinite loop or an array that is getting too large"? $\endgroup$
    – Luatic
    Commented Mar 13 at 19:27
5
$\begingroup$

Stack limits permit a virtual machine to handle stack overflows within the language. If you don't provide one, then the consequences of a stack overflow can only be handled by the underlying language. This is analogous to the difference between providing exception handling or merely requiring everyone to call exit() to terminate a program if an exceptional behavior occurs.

If it's at all remotely possible that others might implement their own version of the virtual machine, defining this behavior in the language is likely preferable. Otherwise every implementation may have their own quirky behaviors. "Unspecified behavior" is a powerful tool for language creation, but it's also a crutch that leads to lots of incompatible behaviors.

$\endgroup$
2
  • 4
    $\begingroup$ This is an excellent point but I'll note that a stack limit just makes it easier to handle such user overflows. VM authors can handle user-code-induced stack faults in a variety of ways, none of which are pleasant, even in managed code. I wrote the stack overflow code for JScript in 1994 that had to work on both Windows 3.1 and Windows 95 without ever crashing Internet Explorer, so you kids today with your rock music can get off my lawn. $\endgroup$ Commented Mar 13 at 5:04
  • 1
    $\begingroup$ Correction, 1996, not 1994, I was an intern in 1994! $\endgroup$ Commented Mar 13 at 19:51
0
$\begingroup$

Yes, you should limit the stack size (as well as all other data structures, i.e. heap or whatever you have), unless it is for some reason incredibly hard to do (e.g. huge overhead in processing time).

No, you do not have to make the user (programmer) care too much about it. You can achieve this by setting the default limit to an "unreachable" maximum (i.e., 2^64-1 or whatever is a convenient big number - many programming languages/libraries have a constant like MAX_LONG or something like that).

Yes, you should make this user-configurable. You do not know all use-cases for your application in the future, and an application that uses potentially unlimited memory can be hard to maintain. For example, when deploying a container in Kubernetes, you always declare a maximum RAM limit outside of the executable, in the Kubernetes declaration for your deployment. You also try to get away with as little RAM as possible to allow the orchestrator to distribute the deployments amongst a given amount of nodes efficiently.

When your application exceeds that amount of RAM, it will immediately and unavoidably be force-killed by Kubernetes. If you have a way to set your maximum stack size, the programmer can make an educated guess and set that maximum sufficiently small to avoid his app being killed in this manner. Of course he then can run out of stack space by reaching that limit internally, but your programming language can then spit out a meaningful error message, giving the programmer a working chance to fix the issue.

This is just an example; the same applies of course if your program is simply started on some user's PC. Nobody wants any random program to potentially grab all memory and bring the PC to swap (or kill other random programs just because they unfortunately requested more memory after yours had filled the available RAM fully).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .