Own cactus stack and/or ability to pass custom allocators?

[solbjorn]

I know that using a 3rd-party allocator (I use mimalloc3) mitigates most of heap allocation penalty, but it still is some cost.
Do you have any plans to implement a custom allocator like in libfork or at least give ability to pass custom allocators when creating coroutines?

[tzcnt]

I tried to do this a few different ways. However, there are some constraints:

• The only way to communicate information about a coroutine to its operator new class method is via the constructor parameters. However, these parameters have to be part of the coroutine function signature, or they have to be injected by an intermediate call (this is why libfork has the funky syntax for its call and join functions)
• The above conflicts with my desire to make TMC as clean and easy to use as possible. Almost every other coroutine library for C++ requires you to pollute your function signatures with these extra parameters, and I personally dislike it. It also complicates the process of making existing code async, since you need to may need to rewrite the entire function signature, rather than just change the return type to task<>
• The simplest way to improve allocation performance is to allocate an arena, bump-allocate each task within it, then free the entire block at once. However, this only works if we can be sure that all of the tasks will complete together as part of the same group - and we have to be able to statically determine this before the allocation block is created. This works for libfork because of the difference between the lf::fork and lf::detach calls which are invoked statically before the task is created. Libfork also knows whether tasks are "root tasks" or "child tasks" by its lambda parameter dispatch tagging - for recursive functions it actually creates 2 different versions of the function for this purpose. This also conflicts with TMC's model, where tasks are created first, and then customized afterward. In fact, in TMC, tasks can be created by external functions and then added to an execution group later.
• The only way that an arena/bump group allocator can work right now with TMC is in tmc::spawn_many with an iterator parameter, if that iterator creates tasks on-demand when operator* is called. If the iterator is actually backed by an array of tasks that were already created, then it would have no positive impact. I was able to implement a prototype of such behavior, and I did get a small performance win for the lazy iterator group; however, other use cases showed a small performance loss due to the dynamic checking necessary to implement this - several additional if statements needed to be added to hot code paths which caused degradation for light tasks such as calling a single coroutine. This compounds if that coroutine calls another coroutine, and so on.

A second possible design would be to allow users to customize the allocator by an optional template parameter to tmc::task<>. However, this would require rework of multiple library facilities to handle tasks of different types. This seems like a possible route to explore but I haven't put the time into it yet. If this were to be implemented, it would be very important to me that users who don't care to pass a custom allocator would be able to completely ignore this functionality, with no additional syntactical or mental overhead.

Currently, my plan is explore Clang's annotations that allow allocations to be elided entirely (see #61) as this would result in the best performance and least impact on the code, being handled almost entirely by the compiler.

[solbjorn]

Yeah, something like

// use custom_alloc
tmc::task<int, custom_alloc> function()

// use default alloc
tmc::task<int> function2()

would be nice to see.

I asked only theoretically to be honest as I assumed this 1:1.21 difference in the benchmarks (in comparison to libfork) is only due to his cactus stack. On my setup and workloads, TMC actually performs better lol; moreover, libfork doesn't seem to fit my needs (only lf::join with no control when and where to await for a single coroutine, no async control primitives like mutexes or braids etc.).
I'm aware that the cactus stack works like that because libfork has strong restrictions on tasks' scope. I just thought that maybe having something like a big arena per each executor could work out, OTOH TMC tasks can be told to move to another executor anytime, so this is questionable as well.

Yeah, Clang's annotations could make a difference.
Feel free to reach out to me if/when you want some tests -- I compile my engine with LLVM (21-rc1 currently) under MSVC, but with both LLVM's libc++ and llvm-libc linked in statically (FatLTO) -- weird stuff that may give some diversification to tests :D

Last question: did I read it correctly that you do align tmc::task<non-void> allocations to a cacheline, but don't align tmc::task<void>, IOW coroutines not returning any value are not aligned?

[tzcnt]

I think that allocation performance is a big portion of the diff between TMC and LF. IIRC it can be 15% of the workload in synthetic benchmarks for me (even using tcmallloc). However these are benches that are pushing up to 1 billion tasks per second. In my real world use cases, the total library+allocation overhead is <1%.

That's correct, I do align non-void tasks but not void tasks. This decision was made due to the way tasks collect results from children in an array, if that task is also part of another group then I don't want its children colliding with other groups children. However it's possible that this scenario would also occur with a non-void task so I could be convinced to apply the padding there as well.

If you want to test some allocators, you have found where they are implemented in the allocator new. For me to implement a template based version will have to wait until after the first major release - currently focused on bug fixing and improving the code structure and docs.

BTW since you have an unusual setup, please let me know if you ever get a crash dump that seems like it's coming from the library. I'm currently working on fixing some race conditions that occur only when shutting down an executor, which are annoyingly difficult to reproduce. So more data is always good. Thanks!

[tzcnt]

libfork also benefits from being statically linked to the application, whereas tcmalloc is typically linked dynamically. I was able to shave 2-5% off the benchmarks runtime by statically linking tcmalloc.

[tzcnt]

I ran into an issue in my testing which could also occur with a hypothetical template-allocator task. Consider the following pseudocode example:

template <typename Allocator>
tmc::task<int, Allocator> child_task(Allocator& a) {
  //operator new of this type delegates to the Allocator parameter
  return 42;
}

tmc::task<void> parent_task() {
  std::array<std::byte, 4096> buffer;
  std::pmr::monotonic_buffer_resource mbr{buffer.data(), buffer.size()};
  std::pmr::polymorphic_allocator<std::byte> pa{&mbr};

  // allocate the children in this task's static array buffer
  auto results = co_await spawn_tuple(child_task(pa), child_task(pa));
}

The following sequence of events can happen:

1. child_task 1 reaches the final_suspend point and decrements the shared done_count tracker variable. Then its thread is pre-empted by the OS.
2. child_task 2 reaches the final_suspend point and decrements the shared done_count tracker variable. Seeing that both tasks in its group are completed, it resumes the awaiting parent task by symmetric transfer.
3. The parent task completes and runs its destructor and deallocates its memory, including the contained buffer which has the allocations for the child tasks.
4. child_task 1 resumes once its thread is rescheduled and attempts to access any member variable / run destroy() on itself, but the memory that was containing it has already been freed.

The seemingly obvious solution is to not decrement the shared done_count until inside the child task destructor, but this doesn't work since we need to be able to decide based on the result of the fetch_sub whether or not we should symmetric transfer - which cannot be done from inside of a destructor. Or... what if we just didn't symmetric transfer when resuming child -> parent? Just post the parent back to the local task queue and pick it up afterward... I will investigate.

A working solution which I tried is to move the memory out into a shared_ptr allocation which is refcounted among all children, since this refcount is not decremented until the destructor is run. This works and prevents the deallocation of the shared buffer until all children are finished, but it affected the performance heavily due to the large number of atomic synchronization accesses (2x extra per task) - much slower than just using tcmalloc.

So I'm considering now that the lifetime of the allocator needs to always outlive the lifetime of any child task. Given that a thread running a task could theoretically be pre-empted for an effectively infinite amount of time, this means that the lifetime of the allocator needs to be effectively infinite. This means that taking an allocator as a task template parameter is probably non-viable, as it would be too easy for users to fall into this kind of issue.

I'm experimenting with a thread-local bump allocator which can create new blocks as needed but there are a lot of logistics to consider with how to make this work properly - specifically when it comes to deallocation. Allocation is easy and can be non-atomic, but deallocation may occur on a different thread than when the allocation happened, so there needs to be an atomic synchronization at some point. This is getting quite close to just reimplementing a general-purpose multithreaded allocator, so I'm a bit leery of it.

I should look at how libfork solves this problem...

[tzcnt]

The way most libraries handle this is by injecting a parameter into the coroutine argument list (which is visible to task::operator new). I've so far been against this, in the interest of keeping syntax equivalent to non-coroutine functions.

However, this parameter could serve another purpose - as a generic Context object (inspired by Go's context.Context), it could be used to hold multiple things:

• coroutine group allocator
• cancellation token
• user data such as tracing info, or a logger

As a whole, this makes more sense. The last thing is for me to investigate whether the existing task type can optionally make use of this context without breaking any existing code, or if a new context_task type would need to be created.

[solbjorn]

I personally don't have any good candidate for a custom coro allocator (modern allocators like mimalloc/tcmalloc/etc have own pools for small objects), so the scope of this issue is limited to the "bump allocator" that you mentioned several times (if I got the idea correctly, that under certain conditions we could allocate coro frames for spawn_many() in one go instead of one-by-one?).

[tzcnt]

A scoped bump allocator tied to a single spawn_many() group would be useful.

An even more powerful option would be a full "stackful" allocator. For example, the fib(40) benchmark only has a maximum of 80 active coroutine frames if executing on a single thread. If executing in a purely fork-join context, it should be possible to "pop" completed tasks off the end of the allocator and then reuse that space again for the next fork. However, as soon as there is a task that outlives its parent task (isn't purely fork-join), things get messy as there is a space in the allocator that can't be freed. There are two supported ways to cause this problem now: detach(), and a fork_group() which is passed in by reference from a parent.

I've thought for a long time about how to solve the "stackful" allocator problem when a user may detach a task at any time, and I don't think that it's possible to do with the current design of the library, without introducing a new template parameter to tmc::task. That's where the context comes in - if the user wants to pass a StackfulContext then they would be responsible for ensuring that tasks are strictly fork-join.

[tzcnt]

RE: my earlier comment about the parent task owning an allocation that's destroyed before the child task does, it turns out that HALO behaves exactly the same way, so I had to solve this problem already in #201. Now that this blocker is removed, I'll test again with a std::pmr based solution.