Version 3.6.0

[ConorWilliams]

Major overhaul - see the ChangeLog.

---

This discussion was created from the release Version 3.6.0.

[MartyMcFlyInTheSky]

I'm excited to try this new version and read the paper when I get to it! I'm not quite comfortable with the cactus stack, it's a shame you had to reintroduce it for performance reasons. I hope we can remove it again once the coroutine optimizations become more... advanced? In the optimal case we should not get any new calls eventually I hope.

[ConorWilliams]

I believe sufficiently-smart compilers could remove all allocations for all non-recursive functions. Unfortunately, recursion (which is very helpful in fork-join) will always require some kind of allocation and a cactus stack is the best-known solution to that problem. Maybe if we can figure out how to remove recursion from fork-join algorithms we can remove the cactus stack.

[MartyMcFlyInTheSky]

Recursive coroutines... now that is something I haven't really thought about. How does this work? You use the coroutine handle to call the same coroutine from within the coroutine body?

[ConorWilliams]

I tried to reply to this but accidentally posted a new comment

[ConorWilliams]

Recursive coroutines... now that is something I haven't really thought about. How does this work? You use the coroutine handle to call the same coroutine from within the coroutine body?

For a coroutine a bit like this:

auto do_the_thing(int arg_a, int arg_b) -> task<int> {
    int a = regular_function(arg_a);
    int b = regular_function(arg_b);
    co_return a + b;
}

If this was called from another coroutine then the compiler can calculate the size of the do_the_thing coroutine frame at compile time, then (if the compiler is sufficiently smart) it can embed this coroutine frame in the parents frame (HALO) hence, zero allocation.

However consider this coroutine:

auto do_the_thing(int arg) -> task<int> {
    if (arg <= 1) {
        co_return 0;
    }
    int a = do_the_thing(arg - 1);
    int b = do_the_thing(arg - 2);
    return a + b;
}

How big is the coroutine frame? Well, its big enough to fit two integers but, if the compiler wants to (HALO) optimize the recursive calls to do_the_thing it is kind of equivalent to asking how big this struct is:

struct frame {
    int a, b;
    frame r1, r2;
};

Which is infinite as it's a recursive type. Hence, any coroutine that is recursive or mutually recursive needs some indirection, which manifests as an allocation.

[MartyMcFlyInTheSky]

That's true at compile time we never know how big the coroutine gets, but couldn't the allocation of the coroutine frame still be done on the caller stack, even recursivley (basically with the same risk of stack overflow as any recursive function)? I'm sure I'm missing something since it's quite a while that I have read this excellent article.

[ConorWilliams]

As the caller doesn't know which part of the child task will be stolen I think it would be required to allocate enough space for all child tasks to co-exist at once, which would blow up to exponential space. That is a good read :)