1 unstable release
0.0.1 | May 19, 2024 |
---|
#14 in #stack-frame
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.run
s, 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