Welcome to libfork 🍴

A bleeding edge, lock-free, wait-free, continuation-stealing coroutine-tasking library.

** Now supplying 🌵! **

Libfork is primarily an abstraction for fully-portable, strict, [fork-join parallelism](https://en.wikipedia.org/wiki/Fork%E2%80%93join_model). This is made possible without the use of any macros/inline assembly using C++20's coroutines. Ultra-fine grained parallelism (the ability to spawn tasks with very low overhead) is enabled by an innovative implementation of an (almost) non-allocating [cactus-stack](https://en.wikipedia.org/wiki/Parent_pointer_tree) utilizing _segmented stacks_. Libfork presents a cross-platform API that decouples scheduling tasks (a customization point) from writing tasks. Additionally, libfork provides performant NUMA-aware work-stealing schedulers for general use. If you'd like to learn more check out [the tour of libfork](#a-tour-of-libfork) then try it on [compiler explorer](https://godbolt.org/z/MTdMorjav) or, just grok the __TLDR__:

#include "libfork/core.hpp"

inline constexpr auto fib = [](auto fib, int n) -> lf::task<int> { 

  if (n < 2) {
    co_return n;
  }

  int a, b;

  co_await lf::fork[&a, fib](n - 1);    // Spawn a child task.
  co_await lf::call[&b, fib](n - 2);    // Execute a child inline.

  co_await lf::join;                    // Wait for children.

  co_return a + b;                      // Safe to read after a join.
};

## Performance Libfork is engineered for performance and has a comprehensive [benchmark suit](bench). For a detailed review of libfork on 1-112 cores see the [paper](https://arxiv.org/abs/2402.18480), the headline results are __linear time/memory scaling__, this translates to: - Up to 7.5× faster and 19× less memory consumption than OneTBB. - Up to 24× faster and 24× less memory consumption than openMP (libomp). - Up to 100× faster and >100× less memory consumption than taskflow. ### Scheduler overhead For a quick comparison with other libraries, the average time to spawn/run a task during the recursive Fibonacci benchmark gives a good approximation to the tasking overhead and peak throughput: ### Memory consumption Libfork is competitive with other libraries in terms of memory consumption; below is the peak (physical) memory allocation during the T3L [unbalanced tree search](https://doi.org/10.1007/978-3-540-72521-3_18) benchmark: View graph ## Using libfork Libfork is a header-only library with full CMake support and zero required-dependencies. Refer to the [BUILDING](BUILDING.md) document for full details on compiling the tests/benchmarks/docs, installation, optional dependencies and, tools for developers. See below for the easiest ways to consume libfork in your CMake projects. ### Package managers We recommend consuming libfork via a package manager, this streamlines the management of optional dependencies. #### vcpkg Libfork is available via vcpkg. Add the following to your `vcpkg.json`:

"dependencies": [
    "libfork"
]

You may then use the library in your project's cmake:

find_package(libfork CONFIG REQUIRED)  

target_link_libraries(
    project_target PRIVATE libfork::libfork
)

__NOTE:__ The libfork port in vcpkg is kept up to date by Microsoft team members and community contributors. If the version is out of date, please [create an issue or pull request](https://github.com/Microsoft/vcpkg) on the vcpkg repository. #### Conan2 Libfork has best effort support for Conan2 and supplies a `conanfile.py`. Libfork is not yet available via conan-center, After building the package locally add the following line to your `conanfile.txt`

[requires]
libfork/3.7.2

and install it to conan2 cache:

conan install .. --build missing

(Please make sure that you use a c++20 ready conan profile!) You may then use the library in your project's cmake:

find_package(libfork CONFIG REQUIRED)  

target_link_libraries(
    project_target PRIVATE libfork::libfork
)

### With CMake If you have installed libfork from source, following the [BUILDING](BUILDING.md) document, then you can use the following CMake code to consume libfork in your project:

find_package(libfork CONFIG REQUIRED)

target_link_libraries(
    project_target PRIVATE libfork::libfork
)

#### Using CMake's ``FetchContent`` If you have not installed libfork you may use CMake's `FetchContent` to download and build libfork as part of your project:

include(FetchContent)

FetchContent_Declare(
    libfork
    GIT_REPOSITORY https://github.com/conorwilliams/libfork.git
    GIT_TAG v3.7.2
    GIT_SHALLOW TRUE
)

FetchContent_MakeAvailable(libfork)

target_link_libraries(
    project_target PRIVATE libfork::libfork
)

### Using git submodules You can incorporate libfork into your project as a git submodule. In this case, assuming you cloned libfork as a submodule into "external/libfork":

add_subdirectory(external/libfork)

target_link_libraries(
    project_target PRIVATE libfork::libfork
)

### Single header Although this is __not recommend__ and primarily exist for easy integration with [godbolt](https://godbolt.org/z/MTdMorjav); libfork supplies a [single header](single_header/libfork.hpp) that you can copy-and-paste into your project. See the [BUILDING](BUILDING.md) document's note about hwloc integration and compiler flags. ## API reference See the generated [docs](https://conorwilliams.github.io/libfork/). ## Contributing 1. Read the [CODE_OF_CONDUCT](CODE_OF_CONDUCT.md) document. 2. Read the [BUILDING](BUILDING.md) document. 3. Have a snoop around the `impl` namespace. 4. Ask as many questions as you can think of! ## Changelog See the [ChangeLog](ChangeLog.md) document. ## A tour of libfork This section provides some background and highlights of the `core` API, for details on implementing your own schedulers on-top of libfork see the [extension documentation](https://conorwilliams.github.io/libfork/). Don't forget you can play around with libfork on [godbolt](https://godbolt.org/z/MTdMorjav). ### Contents - [Fork-join](#fork-join) - [The cactus stack](#the-cactus-stack) - [Restrictions on references](#restrictions-on-references) - [Delaying construction with `lf::eventually`](#delaying-construction) - [Exception in libfork](#exceptions) - [Immediate invocation](#immediate-invocation) - [Explicit scheduling](#explicit-scheduling) - [Contexts and schedulers](#contexts-and-schedulers) ### Fork-join Definitions: - __Task:__ A unit of work that can be executed concurrently with other tasks. - __Parent:__ A task that spawns other tasks. - __Child:__ A task that is spawned by another task. The tasking/fork-join interface is designed to mirror [Cilk](https://en.wikipedia.org/wiki/Cilk) and other fork-join frameworks. The best way to learn is by example, lets start with the canonical introduction to fork-join, the recursive Fibonacci function, in regular C++ it looks like this:

auto fib(int n) -> int {

  if (n < 2) {
    return n;
  }

  int a = fib(n - 1);
  int b = fib(n - 2);

  return a + b;
}

We've already seen how to implement this with libfork in the TLDR but, here it is again with line numbers:

 1| #include "libfork/core.hpp"
 2|
 3| inline constexpr fib = [](auto fib, int n) -> lf::task<int> { 
 4|  
 5|   if (n < 2) {
 6|     co_return n;
 7|   }
 8|
 9|   int a, b;
10|
11|   co_await lf::fork[&a, fib](n - 1);    
12|   co_await lf::call[&b, fib](n - 2);  
13|
14|   co_await lf::join;                  
15|
16|   co_return a + b;                    
17| };

__NOTE:__ If your compiler does not support the `lf::fork[&a, fib]` syntax then you can use `lf::fork(&a, fib)` and similarly for `lf::call`. This looks almost like the regular recursive Fibonacci function. However, there are some important differences which we'll explain in a moment. First, the above fibonacci function can be launched on a scheduler, like ``lazy_pool``, as follows:

#include "libfork/schedule.hpp"

int main() {

  lf::lazy_pool pool(4); // 4 worker threads

  int fib_10 = lf::sync_wait(pool, fib, 10);
}

The call to `sync_wait` will block the _main_ thread (i.e. the thread that calls `main()`) until the pool has completed execution of the task. Let's break down what happens after that line by line: - __Line 3:__ First we define an _async function_. An async function is a function-object with a templated first argument that returns an `lf::task`. The first argument is used by the library to pass static and dynamic context from parent to child. Additionally, it acts as a [y-combinator](https://en.wikipedia.org/wiki/Fixed-point_combinator) - allowing the lambda to be recursive - and provides a few methods which we will discuss later. - __Line 9:__ Next we construct the variables that will be bound to the return values of following forks/calls. - __Line 11:__ This is the first call to `lf::fork` which marks the beginning of an _async scope_. `lf::fork[&a, fib]` binds the return address of the function `fib` to the integer `a`. Internally the child coroutine will have to store a pointer to the return variable so we make this explicit at the call site. The bound function is then invoked with the argument `n - 1`. The semantics of all of this is: the execution of the forked function (in this case `fib`) can continue concurrently with the execution of the next line of code i.e. the _continuation_. As libfork is a continuation stealing library the worker/thread that performed the fork will immediately begin executing the forked function while another thread may _steal_ the continuation. - __Line 12:__ An `lf::call` binds arguments and return address in the same way as `lf::fork` however, it has the semantics of a serial function call. This is done instead of an `lf::fork` as there is no further work to do in the current task so stealing it would be a waste of resources. - __Line 13:__ Execution cannot continue past a join-point until all child tasks have completed. After this point it is safe to access the results (`a` and `b`) of the child task. Only a single worker will continue execution after the join. This marks the end of the async scope that began at the `fork`. - __Line 16:__ Finally we return the result of the to a parent task, this has similar semantics to a regular return however, behind the scenes an assignment of the return value to the parent's return address is performed. This is the end of the async function. The worker will attempt to resume the parent task (if it has not already been stolen) just as a regular function would resume execution of the caller. __NOTE:__ At every ``co_await`` the OS-thread executing the task may change! __NOTE:__ Libfork implements _strict_ fork-join which means all children __must__ be joined __before__ a task returns. This restriction give some nice mathematical properties to the underlying directed acyclic graph (DAG) of tasks that enables many optimizations. #### Ignoring a result If you wanted to ignore the result of a fork/call (i.e. if you wanted the side effect only) you can simply omit return address from lines 11 and 12 e.g.:

co_await lf::fork[fib](n - 1);    
co_await lf::call[fib](n - 2); 

### The cactus-stack Normally each call to a coroutine would allocate on the heap. However, libfork implements a cactus-stack - supported by segmented-stacks - which allows each coroutine to be allocated on a fragment of linear stack, this has almost the same overhead as allocating on the real stack. This means the overhead of a fork/call in libfork is very low compared to most traditional library-based implementations (about 10x the overhead of a bare function call). The internal cactus-stack is exposed to the user via the `co_new` function:

inline constexpr auto co_new_demo = [](auto co_new_demo, std::span<int> inputs) -> lf::task<int> {

  // Allocate space for results, outputs is a std::span<int>
  auto [outputs] = co_await lf::co_new<int>(inputs.size());

  // Launch a task for each input.
  for(std::size_t i = 0; i < inputs.size(); ++i) {
    co_await lf::fork[&outputs[i], some_function](inputs[i]);
  }

  co_await lf::join; // Wait for all tasks to complete.

  co_return std::accumulate(outputs.begin(), outputs.end(), 0);
};

Here the `co_await` on the result of `lf::co_new` returns an immovable RAII class which will manage the lifetime of the allocation. ### Restrictions on references References as inputs to coroutines can be error prone, for example:

co_await lf::fork[process_string](std::string("32")); 

Th