Fibers via Continuations
In the last post I talked about some differences between fibers and continuations. What may not have been clear is that continuations are more primitive and flexible than fibers are. In fact, you can implement fibers using continuations.
Here’s how. The basic idea is that we want to maintain two variables with
continuations in them, inside and outside. The first one will transfer
execution into the block of code that forms the fiber. The second will transfer
control back to the outside world.
When the outside world calls #resume, we save our continuation point as
outside, and call the current inside continuation. When, within the block,
#yield is called, we save our current continuation point as inside, and
transfer code back to the current outside.
There are a few more details in terms of passing values from #yield to
#resume, handling the return value of the block, and handling excessive
calls to #resume, but that’s the basic story. Here’s the code:
require 'continuation'
class CFiber
class Error < StandardError; end
def initialize &block
@block = block
callcc do |cc|
@inside = cc
return
end
@var = @block.call self
@inside = nil
@outside.call
end
def resume
raise Error, "dead cfiber called!" unless @inside
callcc do |cc|
@outside = cc
@inside.call
end
@var
end
def yield var
callcc do |cc|
@var = var
@inside = cc
@outside.call
end
end
end
This is also runnable on Ruby 1.8—just remove the require.
So why does Ruby 1.9 bother to implement fibers, when we can just use continuations? I don’t know what the real answer is, but “speed” is at least a good answer. Let’s do some some benchmarking to compare the two:
require 'benchmark'
n = ARGV.shift.to_i
Benchmark.bm do |bm|
bm.report " fibers" do
f = Fiber.new do
x, y = 0, 1
loop do
Fiber.yield y
x, y = y, x + y
end
end
n.times { |i| f.resume }
end
bm.report "cfibers" do
f = CFiber.new do |c|
x, y = 0, 1
loop do
c.yield y
x, y = y, x + y
end
end
n.times { |i| f.resume }
end
end
We’ll start with backporting that code to the Ruby 1.8.7 that Ubuntu provides (ruby 1.8.7 (2008-08-11 patchlevel 72)). For 10000 Fibonacci numbers, we see:
| user | system | total | real | |
|---|---|---|---|---|
| cfibers | 0.810000 | 0.070000 | 0.880000 | 0.879930 |
That’s roughly 11.4kfps (that’s thousand Fibonacci numbers per second) that we can produce using continuation-based fibers.
Let’s try the ancient Ruby 1.9.0 that Ubuntu provides (Ruby 1.9.0 (2008-06-20 revision 17482)):
| user | system | total | real | |
|---|---|---|---|---|
| fibers | 0.040000 | 0.000000 | 0.040000 | 0.037583 |
| cfibers | 18.680000 | 1.770000 | 20.450000 | 20.482006 |
Wow, fibers are fast: 250kfps. But things have gotten significantly worse for cfibers, clocking at a measely 0.489kfps for cfibers.
Finally let’s try the latest and greatest Ruby 1.9.1 (ruby 1.9.1p129 (2009-05-12 revision 23412)):
| user | system | total | real | |
|---|---|---|---|---|
| fibers | 0.040000 | 0.000000 | 0.040000 | 0.035148 |
| cfibers | 0.150000 | 0.000000 | 0.150000 | 0.155890 |
Fibers are just as fast as before, but continuations have improved dramatically—from 11.4kfps to 66.6kfps. Still, native fibers are more than three times faster.
So perhaps Ruby 1.9.1 is the best of both worlds. When you need fast non-preemptive concurrency, you can use native fibers; when you need to implement your own crazy control structures, you can use continuations and be assured that they’re still pretty darn fast (at least, as far as Ruby operations are concerned).
Discussion
To leave a new comment, enter your email address. A copy of the article will be sent to you via email.