Libfork: Portable Continuation-Stealing With Stackless Coroutines

Fully-strict fork-join parallelism is a powerful model for shared-memory programming due to its optimal time-scaling and strong bounds on memory scaling. The latter is rarely achieved due to the difficulty of implementing continuation-stealing in traditional High Performance Computing (HPC) languages – where it is often impossible without modifying the compiler or resorting to non-portable techniques. We demonstrate how stackless-coroutines (a new feature in C<b>++</b><inline-formula><tex-math notation="LaTeX">$\bm {20}$</tex-math></inline-formula>) can enable fully-portable continuation stealing and present <i>libfork</i> a wait-free fine-grained parallelism library, combining coroutines with user-space, geometric segmented-stacks. We show our approach is able to achieve optimal time/memory scaling, both theoretically and empirically, across a variety of benchmarks. Compared to openMP (libomp), libfork is on average <inline-formula><tex-math notation="LaTeX">$7.2\times$</tex-math></inline-formula> faster and consumes <inline-formula><tex-math notation="LaTeX">$10\times$</tex-math></inline-formula> less memory. Similarly, compared to Intel's TBB, libfork is on average <inline-formula><tex-math notation="LaTeX">$2.7\times$</tex-math></inline-formula> faster and consumes <inline-formula><tex-math notation="LaTeX">$6.2\times$</tex-math></inline-formula> less memory. Additionally, we introduce non-uniform memory access (NUMA) optimizations for schedulers that demonstrate performance matching <i>busy-waiting</i> schedulers.