the all-thing | 2010-07-29 19:40:31 -0400 
==========================================

Fibers via Continuations
------------------------
  Date: June  1, 2009  2:47pm
Author: William Morgan
Labels: ruby, ruby1.9, fibers, continuations
   URL: http://all-thing.net/fibers-via-continuations.txt

In the last post I talked about some differences between fibers and
continuations [1]. 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:

table{margin-left: auto; margin-right: auto;}. |         |_. 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)):

table{margin-left: auto; margin-right: auto;}. |         |_. 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)):

table{margin-left: auto; margin-right: auto;}. |         |_. 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).

[1] http://all-thing.net/fibers

This delicious text version served up by Whisper <http://masanjin.net/whisper/>.