Fibers vs. Threads: A FizzBuzz Throughput Showdown
Lately I've been exploring systems programming by building a fiber runtime library in pursuit of a goroutines-like concurrency model for C.
I already had a threads-based implementation of high-throughput fizzbuzz lying around, and so when I wanted to test my fiber runtime, this was sitting right there, starved for attention.
Hypothesis
Unlike threads, context switching between fibers happens entirely in userspace, therefore bypassing expensive crossings across the user-kernel boundary.
A fibers-based implementation of fizzbuzz should yield a higher throughput.
Method
Fiber runtime: overview
The entire runtime runs on a single thread onto which it multiplexes all fibers.
Scheduler
The scheduler operates on a run queue: a list of fibers ready to be executed concurrently. Looping infinitely, the scheduler, at each iteration, will dequeue the next fiber and run it.
When the scheduler regains control, depending on the state of the fiber it just ran -- either yielded, blocked, or dead -- the scheduler may or may not push the fiber back onto the run queue before moving on to the next iteration.
Channels
Fibers can send and receive data through channels, enabling them to communicate and synchronize with each other. Every receiver gets matched with a sender i.e. they will block on the channel's queue until there is another fiber at the other end.
Netpoller
I/O operations take place in the kernel. When a thread performs I/O, it may block inside the kernel if it cannot resolve immediately.
Given that the entire fiber runtime runs on a single thread, any fiber performing I/O may block the entire thread on which it is running and all other fibers along with it. Instead, we want to block only the calling fiber, allowing the others to make progress in the meantime.
To achieve this, we introduce the netpoller. Any fiber performing I/O first registers its target file with the netpoller. The latter sets the target file to non-blocking mode which prevents the thread from blocking on I/O, forcing an immediate return even if it can't be immediately resolved. In such a case, the calling fiber waits on an I/O queue rather than being pushed back onto the scheduler's run queue. This frees the scheduler up to run other fibers and guarantees that the blocked fiber won't be picked to run until it is unblocked.
The netpoller will also intermittently poll the kernel for any registered target files to know if they are ready for I/O. If a target file is ready, the netpoller unblocks the respective fiber by placing it back onto the scheduler's run queue so it may at some point complete its I/O operation.
Fizzbuzz: threads vs fibers
Subject
The general strategy employed by the solution is to batch the output of fizzbuzz into 1MB-sized buffers and flush them out one batch at a time.
Threads
Two threads, two buffers. One thread fills an empty buffer with the results of running fizzbuzz while the other flushes a full buffer to stdout via a thread-blocking write. Top it off with a mutex and condition variable to coordinate the buffer hand-off from one thread to the other, and voila!
Fibers
The same algorithm as the threads-based solution, but with threads switched out for fibers, a channel instead of a mutex + condition variable, and a fiber-blocking write to replace the thread-blocking one.
Methodology
Run both solutions, one after the other, for 10s each, pinned to core 0, and
pipe the output through to pv to
obtain the average throughput.
taskset -c 0 timeout 10s ./a.out | pv -a > /dev/null
Test #1
| Subject | Median throughput of 5 x 10s runs |
|---|---|
| Threads | 164.32 MiB/s |
| Fibers | 138.17 MiB/s |
Winner: Threads
Perplexed by these results, I set on to investigate what was causing the
discrepancy and discovered a helpful linux utility called
strace that records data about system calls executed
throughout the lifetime of a program.
Findings of strace
strace -f -c taskset -c 0 timeout 10s ./a.out | pv > /dev/null
Threads
| % time | seconds | usecs/call | calls | errors | syscall |
|---|---|---|---|---|---|
| 48.48 | 1.058340 | 529170 | 2 | wait4 | |
| 5.45 | 0.773902 | 267 | 2895 | 200 | futex |
| 5.68 | 0.342301 | 406 | 842 | write |
Fibers
| % time | seconds | usecs/call | calls | errors | syscall |
|---|---|---|---|---|---|
| 60.97 | 0.504908 | 252454 | 2 | wait4 | |
| 31.06 | 0.257175 | 325 | 791 | write | |
| 6.46 | 0.053459 | 33 | 1582 | epoll_wait |
Threads execute more writes than fibers: 842 vs 791, but why?
Notice that fibers make 1582 calls to epoll_wait, the mechanism through which
the netpoller polls the kernel for I/O. That is a lot of system calls -- exactly
double the calls to write!
My best guess was that whatever edge we would have been gained over threads from the cheaper fiber-to-fiber switches was probably being offset by the introduced cost of intermittently polling for I/O.
Adjustment
To demonstrate the true potential of a fibers, we need a test with a higher frequency of thread-to-thread and fiber-to-fiber switches.
Idea: significantly reduce the fizzbuzz output buffer size from 1MB down to 1KB.
A smaller buffer size means it gets filled and flushed out much quicker and more frequently, resulting in more context switches between the filler and flusher.
Test #2: 1KB-sized buffers
| Version | Median throughput of 5 x 10s run |
|---|---|
| Threads | 60.19 MiB/s |
| Fibers | 76.64 MiB/s |
Winner: Fibers
Findings of strace
strace -f -c taskset -c 0 timeout 10s ./a.out | pv > /dev/null
Threads
| % time | seconds | usecs/call | calls | errors | syscall |
|---|---|---|---|---|---|
| 51.74 | 4.093765 | 2046882 | 2 | wait4 | |
| 32.82 | 2.597079 | 16 | 154331 | 55470 | futex |
| 15.40 | 1.218774 | 38 | 31977 | write |
Fibers
| % time | seconds | usecs/call | calls | errors | syscall |
|---|---|---|---|---|---|
| 63.22 | 3.632685 | 1816342 | 2 | wait4 | |
| 23.26 | 1.336554 | 36 | 36517 | write | |
| 13.24 | 0.760869 | 10 | 73035 | epoll_wait |
Observe this time that fibers are making more calls to write: 36517 vs 31977.
epoll_wait is still being called twice as often as write, however the time
saved during fiber-to-fiber switching heavily outweighs the introduced cost of
intermittently polling the kernel for I/O.
Conclusion
As expected, fibers outperform threads for tasks heavy on context switching.