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.