vuot

lea mu? vuot?

运行不导致栈溢出的递归函数。

为什么？

许多算法最自然地使用递归定义。不幸的是，大多数编程语言限制您使用一个小的、固定大小的栈，这使得对于较大的输入的实现不可靠——即使您有大量的堆内存！

vuot利用Rust的async机制在堆上分配您的栈帧，绕过这个问题。请注意，栈溢出仍然可能发生，但只有当您耗尽堆内存时。也就是说，vuot将栈溢出与其他任何内存不足条件统一起来，希望使它们更加不可预测和可怕。

请注意，vuot并非全是彩虹和阳光：回溯不再非常有用（因为它只是始终检查栈顶的future），而且其中有很多开销。

如何？

简要来说，使用stack.run(future).await而不是Box::pin(future).await。使用vuot::run调用一个async fn(Stack<'_>) -> T或实现了vuot::StacklessFn<'_, T>的类型来获取一个栈。

存在一个类型vuot::Stack<'_>，它引用一个“虚拟”调用栈。在Stack::run中传递一个future来调用该future，而不会增长调用栈。

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
    }
}

如果您想在要运行的future中传递数据，您必须实现vuot::StacklessFn特质（至少直到异步闭包稳定）。

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)
    }
}

最后，vuot::run接受一个StacklessFn并将其传递给一个栈。

use vuot::run;

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

可选功能

默认情况下，此crate使用Box来分配单个栈帧。启用bumpalo功能可使用来自bumpalo crate的bump分配器。

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

这通常会减少每次stack.run调用的开销，尽管减少的量可能会有所不同。如果你的程序因为stack.run而花费大量时间进行内存分配和释放，这可能值得一试。

bumpalo功能使用不稳定的功能allocator_api，因此需要一个nightly编译器。

安全性

尽管整个公共API是安全的，但crate内部确实使用了大量的unsafe块和函数。我确实用Miri进行了积极测试，并致力于减少和改进这一点。话虽如此，我只是凡人，很可能犯过错误。不要完全依赖它是完美的！

替代方案

• stacker允许您根据需要扩展实际的调用栈
• recursive允许您在递归函数上使用proc-macro，底层使用stacker
• reblessive使用了与这个crate相同的思想。在我的简短测试中，它比vuot快一点，但不支持在其虚拟栈内运行任意future。