fortyoneplustwo

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.