Why fibers

Sequential CPU-bound code — encoders, compressors, parsers — contains sections that could run in parallel. They are short, though, and they wait for each other in the middle of the work. Whether you can use them depends less on how much parallel work there is than on what each task and each dependency costs.

This page compares that cost for OS threads and for fibers on one worker thread per core. It explains the design decision behind ConcurrentTasks. All values are approximate orders of magnitude; they vary with processor and operating system.

Parallel sections in sequential code

Amdahl's law bounds the speedup of a program with a parallel fraction p on N processors by $$S=\frac{1}{(1-p)+\frac{p}{N}}$$ and p tends to grow with the problem size. Both statements assume that running the parallel part costs nothing. In practice every task and every dependency adds overhead, and splitting more finely exposes more parallelism and pays more overhead at the same time. How much of the parallelism you can use is a property of the code and of the execution mechanism together.

Step-oriented sequential code shows three forms of parallelism:

The size of these sections follows from the throughput of the code. An MP3 frame holds about 26 ms of audio. An encoder running at, say, 50 times real time spends about 0.5 ms per frame. Divided into a handful to a few dozen sections, each section takes tens to hundreds of microseconds. Wavefront dependencies occur once per frame, fork-join points several times. A mechanism whose cost per dependency is a noticeable fraction of 100 µs cannot use this structure.

What a dependency costs with OS threads

Creating threads

Creating a thread allocates kernel objects and a stack; that is far too expensive per task. A thread pool removes the creation cost, but not the cost of waiting inside a task.

Blocking

When a task on a pool thread waits for another task, the thread blocks:

• Waiting takes a system call, a scheduler decision and a context switch.
• Signaling takes another system call to make the waiter ready and, if it continues on another core, a notification to that core.
• Waking an idle core may have to leave a power-saving idle state first, which adds latency.

The direct cost of a context switch is a few microseconds. With its effect on the caches, the total ranges from several to hundreds of microseconds, depending on the working set. The mitigations for speculative-execution vulnerabilities have made every system call and context switch more expensive. Altogether, waiting with kernel threads is about an order of magnitude more expensive than waiting in user mode.

Spinning

Spinning instead of blocking avoids the kernel and the wake-up latency by keeping the core busy during the wait. That works as long as there are at least as many cores as spinning threads. With more threads than cores, a spinning thread uses up the time slice that the thread it waits for would need.

Time slices

A wait costs only microseconds if a core is free when the waiter becomes ready. Otherwise the OS scheduler decides when it runs, and its unit is the time slice (quantum). On Windows, a thread that becomes ready runs at once only if a processor is idle or it has a higher priority than a running thread. Otherwise it waits until a running thread waits, yields or reaches the end of its quantum; a running thread is switched out at the end of its quantum if another thread of at least the same priority is ready. Linux behaves similarly with different parameters.

Windows raises the priority of a thread whose wait has been satisfied, so a woken thread may also preempt a running one. In a parallel computation, the thread it preempts is likely another task of the same computation, possibly one on the critical path. Either way, the intervals are milliseconds, the sections in question microseconds.

Preemption at the wrong moment

• A thread can be preempted while it holds a lock or just before it would signal a dependency. Everyone waiting for it is then delayed by a whole time slice (lock-holder preemption).
• The OS scheduler does not know the application's dependency graph. It cannot tell which ready thread is on the critical path and which one could wait.

Pools with blocking tasks

A pool with one thread per core loses a core whenever one of its threads blocks. A pool that adds threads to compensate has more ready threads than cores, and the time slices above apply again. Neither lets a waiting task hand its core to another task without the kernel.

Not waiting at all: callbacks and coroutines

• Callbacks and continuations. The task registers the rest of its work and returns; the kernel is not involved. The sequential code is split at every wait into separate functions, and its local state moves into explicit objects. Code that should stay comparable to a sequential original changes substantially.
• Stackless coroutines. The compiler does this transformation. A coroutine can only suspend in its own body, so every function on the call path to a wait must become a coroutine itself, and each call of a coroutine allocates its frame on the heap unless the compiler elides it. A wait deep inside an existing call chain means restructuring the chain.

Fibers on one thread per core

A fiber is an execution context in user mode with its own stack, switched cooperatively. The program runs one worker thread per core. Tasks run on fibers, and the workers take ready fibers from shared queues. A task that waits suspends its fiber, and the worker switches to another ready fiber. When the dependency is signaled, the fiber goes back into a queue and is resumed by whichever worker takes it next.

This removes the costs above:

• No system call per dependency. Waiting and resuming happen in user mode.
• No preemption between tasks. A task that holds a lock or is about to signal is never displaced by another task of the same computation.
• The application schedules. Priorities can follow the dependency graph and favor the critical path.
• Never more ready threads than cores. The OS scheduler only ever switches the worker threads themselves, at their time-slice boundaries.

What a switch costs

A fiber switch saves and restores only the callee-saved registers and the stack fields; the calling convention takes care of the rest. That is a few dozen instructions and a few hundred bytes of state.

A dependency adds a queue operation — a few atomic memory operations — and, only if all workers were idle, the wake-up of a parked worker. That wake-up does involve the kernel, but only when the machine is not fully loaded, where it matters least.

Memory

The objection that fibers need as much memory as threads concerns the reserved stack. A reserve is address space; physical memory is committed only for the pages actually used, and a fixed stack well below a megabyte is enough for most tasks. In a CPU-bound task graph, the number of live fibers is bounded by the tasks in flight — hundreds to a few thousand — not by the number of clients of a server.

Rules for task code

• No OS waits. A task must not block its worker thread; every wait goes through the fiber scheduler.
• Stacks do not grow beyond the size chosen in advance.

The smallest task worth splitting off

Split a parallel section into tasks of granularity g — the work between two dependencies — and let each dependency cost c on the executing core. The share of core time spent on useful work is

$$e=\frac{g}{g+c}$$

For at least 90 % efficiency, g ≥ 9c: the overhead per dependency decides the smallest section worth running as a task of its own.

The model is optimistic for threads: it leaves out the indirect cost of a context switch, which can exceed the direct cost by an order of magnitude, and the time-slice delays of several milliseconds whenever more threads are ready than there are cores. Neither exists between fibers.

Only work in sections above the threshold parallelizes efficiently; in terms of Amdahl's law, the rest behaves as if it were sequential. Lowering the threshold by one to two orders of magnitude moves sections between about 1 µs and 50 µs from the sequential to the parallel fraction — in the encoder example above, the finer splits of a frame and the short dependent parts of a wavefront.

When threads are the better choice

• Coarse, independent work. Independent files, or large blocks without dependencies in the middle of the work: the cost per dependency does not matter, and threads or a simple pool are enough.
• Code that blocks the thread. Third-party libraries that wait on OS objects, runtimes with their own assumptions about the stack, and libraries that keep thread-local state across calls do not fit without adaptation.

About the criticism of fibers

The usual criticism judges fibers as a general-purpose replacement for threads: for any code, any library and any number of connections. Measured against that, its objections hold:

• Thread-local storage, OS locks and libraries that block the thread do not know about fibers.
• Every fiber reserves a stack, which adds up with hundreds of thousands of connections.
• Fiber modes in operating systems and databases have not lasted.

Its conclusion is to prefer threads, asynchronous APIs or stackless coroutines. It leaves out the applications in which these objections do not apply. In a CPU-bound task graph — such as the algorithms of an encoder — the task code belongs to the program and keeps no thread-local state across a wait, every wait goes through the fiber scheduler, and the number of fibers is bounded by the tasks in flight.

Similar implementations exist in other languages:

Go preempts goroutines and moves their stacks; Java copies the frames of a waiting virtual thread to the heap. Both rely on a runtime that controls the compiler, which a C++ library does not have.

The obstacle is the same everywhere: whatever is bound to the OS thread. Thread-local storage, OS locks and native code that blocks either pin a fiber to its thread or must be avoided. Java, for example, could release the OS thread inside a synchronized block only after the owner of a monitor had been changed from the OS thread to the virtual thread.

In ConcurrentTasks

The showcase encoders apply this model to a single input file and produce the same bytes as their sequential references; their task graphs are described on the showcase pages, for example ctLame.

See also

• When to use it
• Task graphs
• Performance first