A heap allocated runtime for deeply recursive algorithms.
Turn your cursed recursive algorithm into a blessed heap allocated structure which won't overflow the stack, regardless of depth.
use std::{
mem::MaybeUninit,
time::{Duration, Instant},
};
use reblessive::{Ctx, Stack};
/// Some recursive algorith which can recurse up to some arbitrary depth.
/// Without reblessive this function would quickly overflow the stack.
async fn heavy_fibbo(mut ctx: Ctx<'_>, n: usize) -> usize {
// An extra stack allocation to simulate a more complex function.
let mut ballast: MaybeUninit<[u8; 1024 * 1024]> = std::mem::MaybeUninit::uninit();
// Make sure the ballast isn't compiled out.
std::hint::black_box(&mut ballast);
match n {
0 => 1,
1 => 1,
x => {
/// Move the next recursive calls onto the stack so we don't overflow.
ctx.run(move |ctx| heavy_fibbo(ctx, x - 1)).await
+ ctx.run(move |ctx| heavy_fibbo(ctx, x - 2)).await
}
}
}
fn main() {
// Create a stack to run the function in.
let mut stack = Stack::new();
// run the function to completion on the stack.
let res = stack.run(|ctx| heavy_fibbo(ctx, 20)).finish();
println!("result: {res}");
assert_eq!(res, 10946);
// Reblessive can also make any recursive function interuptable.
let mut runner = stack.run(|ctx| heavy_fibbo(ctx, 60));
let start = Instant::now();
loop {
// run the function forward by a step.
// If this returned Some than the function completed.
if let Some(x) = runner.step() {
println!("finished: {x}")
}
// We didn't complete the computation in time so we can just drop the runner and stop the
// function.
if start.elapsed() > Duration::from_secs(3) {
println!("Timed out!");
break;
}
}
}
40 Jan 4, 2023
29 Feb 6, 2023
105 Apr 8, 2023
3 Feb 21, 2024
14 Nov 20, 2022
136 Dec 11, 2022
18 Dec 28, 2022
294 Dec 23, 2022
4 Oct 2, 2022
19 Dec 13, 2022
88 Dec 31, 2022
2.1k Jan 6, 2023
2.1k Jan 1, 2023
29 Oct 16, 2024
5 Nov 29, 2021
11 Dec 2, 2022
8 May 9, 2022
2 Dec 27, 2021
6 Feb 9, 2022
6 Feb 9, 2022
12 Apr 19, 2023
549 Dec 26, 2022
31 Sep 20, 2022
2 Oct 24, 2021
4 Jun 10, 2023
3 Mar 6, 2022
89 Dec 27, 2022
57 Dec 22, 2022