## decurse

Macro to make recursive function run on the heap (i.e. no stack overflow).

### 4 releases

 0.0.4 Dec 4, 2021 Nov 25, 2021 Nov 25, 2021 Nov 25, 2021

#487 in Rust patterns

28KB
520 lines

# Decurse

## Example

``````#[decurse::decurse] // 👈 Slap this on your recursive function and stop worrying about stack overflow!
fn factorial(x: u32) -> u32 {
if x == 0 {
1
} else {
x * factorial(x - 1)
}
}

println!("{}", factorial(10));
``````

More examples (fibonacci, DFS, ...) are in the examples directory.

## Functionality

The macros provided by this crate make your recursive functions run on the heap instead. Works on stable Rust (1.56 at the time of writing).

Here's an example to illustrate the mechanism.

``````fn factorial(x: u32) -> u32 {
// 🅐
if x == 0 {
1
} else {

let rec = {
// 🅑
factorial(x - 1)
};

// 🅒
rec * x
}
}
``````

If we call `factorial(1)`, the following would happen:

• We run the code in the function starting at point 🅐.
• When we reach point 🅑, we don't immediately call `factorial(0)`, instead, we save the information that we have to call `factorial(0)`1.
• Once that information is saved, we pause the execution of `factorial(1)`, storing the state on the heap2.
• We then execute `factorial(0)`. During this, the "stack state" of `factorial(1)` is not on the stack. It is stored on the heap.
• Once we got the result of `factorial(0)`, we resume `factorial(1)` giving it the result of `factorial(0)`3.
• The execution continues at point 🅒 and on.

1 To send this information out of the function, we put it in a thread local.

2 This is accomplished by converting your function into an async function, and awaiting to pause it. It is somewhat of a hack using async/await.

3 This again use thread local.

Click to show an example of what the macro expands to
``````fn factorial(arg_0: u32) -> u32 {
async fn factorial(x: u32) -> u32 {
if x == 0 {
1
} else {
x * ({
// Save what we have to do next.
::decurse::for_macro_only::sound::set_next(factorial(x - 1));
// Pause the current function.
::decurse::for_macro_only::sound::PendOnce::new().await;
// Once resumed, get the result.
::decurse::for_macro_only::sound::get_result(factorial)
})
}
}
::decurse::for_macro_only::sound::execute(factorial(arg_0))
}
``````

## Usage

This crate provides two macros: `decurse` and `decurse_unsound`. Simply put them on top of your function.

``````#[decurse::decurse]
fn some_function(...) -> ...
``````
``````#[decurse::decurse_unsound]
fn some_function(...) -> ...
``````

### `decurse`

This is the version you should prefer. This does not use unsafe code and is thus safe.

However, it does not work on functions with lifetimed types (`&T`, `SomeStruct<'a>`, etc.) in the argument or return type.

### `decurse_unsound`

This macro uses unsafe code in very dangerous ways. I am far from confident that it is safe, so I'm calling it unsound. However, I have yet to come up with an example to demonstrate unsoundness, so there is a small chance that this might actually be sound, so for brave souls, try it out!

This version does not suffer from the limitation of the safe version. Arguments and return type can be lifetimed just as in any functions.

## Limitations

• As mentioned, the safe variant only works on functions without lifetimed type arguments or lifetimed return type.

• This is not tail-call optimization. Also you can still blow up your heap (although it is much harder).

• One function only. Alternating recursion (`f` calls `g` then `g` calls `f`) is not supported. Calling the same function but with different generic parameters is not supported.

• Async function are not supported.

• Struct methods are not supported. Freestanding function only.

• The macro only understand recursive calls that are written literally.

`````` // This would work:
recursive(x - 1);

// The macro wouldn't understand this:
let f = recursive;
f(x - 1);
``````
• The function must have no more than 12 arguments.

• `impl Trait` in argument position is not supported.

• You can use normal, named, generics.
• This is still very experimental. The safe variant doesn't contain unsafe code but even then you should still be careful.

## Benchmarks

Benchmarking recursive linear search. See the code.

Vec Size Time (decurse) (s) Time (normal) (s) decurse/normal
20000 0.65 0.19 3.45
40000 1.29 0.43 2.96
60000 2.11 0.78 2.69
80000 2.81 1.24 2.27
100000 3.49 Stack Overflow N/A
120000 4.32 Stack Overflow N/A
140000 5.23 Stack Overflow N/A
160000 5.99 Stack Overflow N/A
180000 6.72 Stack Overflow N/A

`decurse` version runs at about 35% the performance of the normal version.

Same benchmark with the `slow(8723)` call uncommented for both `linear_search` and `stack_linear_search`. `slow()` is an artificial computation to mimick real use cases where the recursive function actually does something.

Vec Size Time (decurse) (s) Time (normal) (s) decurse/normal
20000 2.87 2.56 1.12
40000 5.74 5.18 1.11
60000 8.64 7.80 1.11
80000 11.57 10.49 1.10
100000 14.59 Stack Overflow N/A
120000 17.60 Stack Overflow N/A
140000 20.59 Stack Overflow N/A
160000 23.60 Stack Overflow N/A
180000 26.61 Stack Overflow N/A

`decurse` version runs at about 90% the performance of the normal version.

Anyway, you should do your own benchmarks for your own use cases. The recursive linear search implemented here isn't even something anyone would use!

I would still love to see what the numbers look like for your use cases. Please share!

## Credits

This blog post by hurryabit inspired me to make this. The main idea is basically the same. Mine is more hacky because I want to avoid generators (which require nightly and won't be stabilized anytime soon), so I use async/await instead.

~230–640KB
~15K SLoC