libfork

Libfork is primarily an abstraction for fully-portable, strict, fork-join parallelism. 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 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 then try it on compiler explorer 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. For a detailed review of libfork on 1-112 cores see the paper, 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 benchmark:

Using libfork

Libfork is a header-only library with full CMake support and zero required-dependencies. Refer to the BUILDING 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 on the vcpkg repository.

Conan2

Libfork is available in Conan Center Index, to install the latest version run (Please make sure that you use a c++20 ready conan profile!):

conan install --requires="libfork/[*]" --build=missing

Or add libfork/[*] to your conanfile recipe requirements.

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 recipe in Conan is kept up to date by Conan team members and community contributors. If the version is out of date, please create an issue or pull request on the Conan repository.

With CMake

If you have installed libfork from source, following the BUILDING 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; libfork supplies a single header that you can copy-and-paste into your project. See the BUILDING document's note about hwloc integration and compiler flags.

API reference

See the generated docs.

Contributing

1. Read the CODE_OF_CONDUCT document.
2. Read the BUILDING document.
3. Have a snoop around the impl namespace.
4. Ask as many questions as you can think of!

Changelog

See the ChangeLog 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. Don't forget you can play around with libfork on godbolt.

Contents

• Fork-join
• The cactus stack
• Restrictions on references
• Delaying construction with lf::eventually<T>
• Exception in libfork
• Immediate invocation
• Explicit scheduling
• 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 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<T>. 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 - 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