3

The following paragraph is from The Racket Guide (2.3.4):

At the same time, recursion does not lead to particularly bad performance in Racket, and there is no such thing as stack overflow; you can run out of memory if a computation involves too much context, but exhausting memory typically requires orders of magnitude deeper recursion than would trigger a stack overflow in other languages.

I'm curious about how Racket was designed to avoid stack overflow? What's more, why other languages like C cannot avoid such a problem?

0

2 Answers 2

3

First, some terminology: making a non-tail call requires a context frame to store local variables, parent return address, etc. So the question is how to represent an arbitrarily large context. "The stack" (or call stack) is just one (admittedly common) implementation strategy for the context.

Here are a few implementation strategies for deep recursion (ie, large contexts):

  • Allocate context frames on the heap and let the GC be responsible for cleaning them up. (This is nice and simple but probably relatively slow, although people would argue that point.)
  • Allocate context frames on the stack. When the stack is full, copy the frames currently on the stack into the heap, clear the stack, and reset the stack pointer to the bottom. When returning, if the stack is empty, copy frames from the heap back to the stack. (This means you can't have pointers to stack-allocated objects, though, since the objects get moved around.)
  • Allocate context frames on the stack. When the stack is full, allocate a new big chunk of memory, call that the new stack (ie set the stack pointer), and keep going. (This might require mprotect or other operations to convince the OS that the new block of memory is okay to treat as a call stack.)
  • Allocate context frames on the stack. When the stack is full, make a new thread to continue the computation, and wait for the thread to finish and arrange to grab a return value from it to return to the old thread's stack. (This strategy can be useful on platforms like the JVM that don't let you directly control the stack, stack pointer, etc. On the other hand, it complicates features like thread-local storage, etc.)
  • ... and more variations on the strategies above.

Support for deep recursion often coincides with support for first-class continuations. In general, implementing first-class continuations means you almost automatically get support for deep recursion. There's a nice paper called Implementation Strategies for First-class Continuations by Will Clinger et al. with more detail and comparisons between different strategies.

2

There are two pieces to this answer.

First, in Racket and other functional languages, tail calls do not create additional stack frames. That is, a loop such as

(define (f x) (f x))

... can run forever without using any stack space at all. Many non-functional languages don't prioritize function calling in the same way as functional languages, and therefore aren't properly tail-calling.

HOWEVER, the comment that you're referring to isn't just limited to tail-calling; Racket allows very deeply nested stack frames.

Your question is a good one: why don't other languages allow deeply nested stack frames? I wrote a short test, and it looks like C unceremoniously dumps core at a depth of between 262,000 and 263,000. I wrote a simple racket test that does the same thing (being careful to ensure the recursive call was not in tail position), and I interrupted it at a depth of 48,000,000 without any apparent ill effects (except, presumably, a fairly large runtime stack).

To answer your question directly, there's no reason that I'm aware of that C couldn't allow much much more deeply nested stacks, but I think that for most C programmers, a recursion depth of 262K is plenty.

Not for us, though!

Here's my C code:

#include <stdio.h>

int f(int depth){
  if ((depth % 1000) == 0) {
    printf("%d\n",depth);
  }
  return f(depth+1);
}

int main() {
  return f(0);
}

... and my racket code:

#lang racket

(define (f depth)
  (when (= (modulo depth 1000) 0)
    (printf "~v\n" depth))
  (f (add1 depth))
  (printf "this will never print..."))


(f 0)

EDIT: here's the version that uses randomness on the way out to stymie possible optimizations:

#lang racket

(define (f depth)
  (when (= (modulo depth 1000000) 0)
    (printf "~v\n" depth))
  (when (< depth 50000000)
    (f (add1 depth)))
  (when (< (random) (/ 1.0 100000))
    (printf "X")))

(f 0)

Also, my observations of the process size are consistent with a stack frame of about 16 bytes, plus or minus; 50M * 16 bytes = 800 Megabytes, and the observed size of the stack is about 1.2 Gigabytes.

5
  • 1
    interesting, a "smart" compiler could realize that the last printf call is unreachable, remove it altogether, and be left with ... a tail-recursive function! can we be sure this didn't happen here?
    – Will Ness
    Apr 19, 2018 at 18:29
  • The size of the C stack is basically up to the compiler/OS. It can't be counted on, unless it is specified during compilation (assuming that's available on the platform which it definitely needn't be). Apr 20, 2018 at 0:27
  • @WillNess Well... I updated the code so that at a depth of 50M, it stops recurring and exits out, printing output on every 100K calls on the way back out, and this worked fine. OTOH, perhaps the clever compiler is optimizing away all of the calls that don't generate output... I could use dissasembly to be sure. Apr 22, 2018 at 19:09
  • @WillNess one other experiment; I changed the code to randomly generate an X on the output on the way back out with probability 1/100K. Again, it appears to work fine, suggesting that racket has no problem with a stack depth of 50M. Apr 22, 2018 at 19:11
  • oh! this seems definitive, especially with the randomness, surely no compiler would throw that away. I had no doubt BTW; Racket is said to just keep its stack on the heap, and I have no reason to not believe this. ... maybe update the answer with this? the old simple code just looks so suspicious/susceptible. :)
    – Will Ness
    Apr 22, 2018 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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