#stack #stack-overflow #recursion #overflow #stack-frame

vuot

Run recursive async functions without overflowing the stack

1 unstable release

0.0.1 May 19, 2024

#14 in #stack-frame

MIT license

44KB
674 lines

vuot

lea mu? vuot?

Run recursive functions without overflowing the stack.

Why?

Many algorithms are most naturally defined with recursion. Unfortunately, most programming languages limit you to a small, fixed-size stack, making such implementations unreliable for larger inputs - even if you have plenty of heap memory!

vuot takes advantage of Rust's async machinery to allocate your stack frames on the heap, bypassing this issue. Note that a stack overflow can still occur, but only if you run out of heap memory. That is, vuot unifies stack overflows with any other out-of-memory condition, hopefully making them a little less unpredictable and horrible.

Note that vuot is not all rainbows and sunshine: backtraces are no longer very useful (since it's only ever polling the topmost future on the stack), and there is a fair amount of overhead in it all.

How?

Briefly, use stack.run(future).await instead of Box::pin(future).await. Call vuot::run with either an async fn(Stack<'_>) -> T or something that implements vuot::StacklessFn<'_, T> to get a stack.

There's a type vuot::Stack<'_> that references a "virtual" call stack. Pass it a future in Stack::run to invoke that future without growing the call stack.

use vuot::{call, Stack};

async fn fib(stack: Stack<'_>, n: usize) -> usize {
    if n < 2 {
        n
    } else {
        stack.run(fib(stack, n - 1)).await + stack.run(fib(stack, n - 2)).await
    }
}

If you want to pass data into the future you will run, you have to implement the vuot::StacklessFn trait (at least until async closures stabilize).

use vuot::StacklessFn;

struct Fib<'local>(&'local usize);
impl<'a> StacklessFn<'a, usize> for Fib<'_> {
    async fn call(self, stack: Stack<'_>) -> usize {
        fib(stack, *self.0)
    }
}

Finally, vuot::run takes in a StacklessFn and hands it a stack.

use vuot::run;

async fn main() {
    let n = 40;
    println!("fib(40) = {}", run(Fib(&n)));
}

Optional features

By default, this crate uses Box to allocate individual stack frames. Enable the bumpalo feature to use the bump allocator from the bumpalo crate instead.

vuot = { version = "0.1", features = ["bumpalo"] }

This tends to reduce the overhead of each stack.run invocation, though it does vary how much. If your program is spending a lot of time allocating and freeing memory due to stack.runs, this may be worth a try.

The bumpalo feature uses the unstable allocator_api feature, and therefore requires a nightly compiler.

Safety

Although the entire public API is safe, the crate does internally use a good amount of unsafe blocks and functions. I do actively test with Miri, and am working on reducing and improving this. That said, I am only human and have likely made mistakes. Don't rely on this to be perfect!

Alternatives

  • stacker lets you grow the actual call stack as necessary
  • recursive lets you put a proc-macro on recursive functions, using stacker under the hood
  • reblessive uses the same idea as this crate. In my brief testing, it tends to be a bit faster than vuot, but does not support running arbitrary futures inside its virtual stack.

Dependencies

~60KB