Lightweight fibres for TruffleRuby.

These are currently called java.lang.Fiber in the project loom prototype, and they provide a nice simple model. Fibres are started with a scheduler, and whenever the has nothing to do it parks itself. When the scheduler decided that that fibre has more work it can do then it will schedule it next. The scheduler isn't special, it's a standard java.util.concurrent.Executor and it can use whatever scheduling strategy it likes, across as many threads as it likes. If your fibres are mostly doing IO, or waiting for locks then you probably won't even have to park them explicitly as the Java class library will do that for you.

Continuations are a lower level concept upon which those lightweight threads are built. A continuation can be run, and can yield control back to the function which ran it. If it is run again then it will continue from the point at which it yielded with the same call stack, local variables, and so forth.

A normal java.lang.Thread in Hotspot is a normal operating system thread, it has a stack, and will be scheduled by the operating system, and in the JVM it will include data structures for things like thread local variables. Scheduling threads is heavyweight because it has to happen via kernel space and because the kernel only has a very limited idea of which thread it would be sensible to schedule next. Lightweight user mode threads and continuations can involve much less data since we only need to preserve the part of the stack between the call to run the continuation and the point at which it yielded, and can often be very effectively scheduled since the application may often know precisely what to run next.

Ruby has the Fiber class. You create a Fiber with a block like this

f = Fiber.new do |x|
  puts "Fiber called with #{x}"
end

and call it like this

f.resume(1)

which should produce Fiber called with 1 as output. Fibres can explicitly transfer control to another fibre, or yield to the fibre which transferred control to them.

Continuations in Ruby are created using the Kernel#callcc method. This takes a block which will be executed immediately, and create a continuation object which when called will resume execution from the end of the block. They are quite hard to get your head round, so an example is probably helpful. I've adapted this one from the Ruby documentation on continuations.

require "continuation"
def f
  arr = [ "Freddie", "Herbie", "Ron", "Max", "Ringo" ]
  cont = nil
  callcc do |cc| 
    puts 'Creating continuation'
    cont = cc
  end
  puts(message = arr.shift)
  cont.call unless message =~ /Max/
end

If you run this Ruby method it will output the following

Creating continuation
Freddie
Herbie
Ron
Max

What's going on here? Well the method creates an array arr, and a variable cont. It then calls callcc which executes the block, passing in the continuation object as an argument. The block prints out that we're creating a continuation, and assigns it to cont so we can use it later. We then remove the first element of arr and assign it to message and output it. Finally we call the continuation again unless message matches "Max", and this causes the latter half of the method to be run again.

There's quite a lot of debate over whether continuations like this are a good idea, and they certainly aren't widely used in production code, but they are still part of the standard Ruby implementation and we do support them in TruffleRuby.

Most of the code in TruffleRuby concerned with fibres is in a small set of classes, mainly FiberManager which handles the creation of fibres and how control is passed between them. This makes it quite easy for us to prototype new implementations.

callcc is harder to map to Loom's fibres or continuations, at least at the moment. If the continuations can be cloned however then it could be done roughly as follows. Each heavyweight thread would need to be run almost entirely inside a java.lang.Continuation, and the control flow would go like this:

1. Creating the continuation.
   1. Create a Ruby Continuation object.
   2. Execute the block passed to callcc passing the Ruby continuation in.
   3. Place the Ruby continuation somewhere the thread can access it.
   4. Yield control to the thread.
   5. The thread clones the main java.lang.Continuation and sets it on the Ruby continuation object.
   6. The thread returns control to the original java.lang.Continuation.
2. Calling the continuation.
   1. Place the Ruby continuation somewhere the thread can access it.
   2. Yield control to the thread.
   3. The thread clones the java.lang.Continuation on the Ruby continuation.
   4. The thread returns control to this new cloned continuation.

It's very easy to support a large number of fibres if they are simply initialised but never used, so we want a test that will create a large set of fibres which are active. Something like this should do.

def test_fiber_1(t)
  Fiber.new do |x|
    if x > t
      Fiber.yield x
    else
      f = test_fiber_1(t)
      f.transfer( x + 1 )
    end
  end
end

Using this code I ran some tests to see how many fibres could be supported by different implementations. This was done by making an initial guess and then performing a binary search to find the approximate number of fibres that could be supported without raising an error, or causing the VM to crash completely. MRI 2.5 has made changes to its fibre code and can now support a larger number of fibres. I'll update these results with figures for MRI 2.5 soon.

These results are very encouraging. The only real limit to the number of fibres we can support appears to be memory.

Testing the performance of this is not easy with JRuby or TruffleRuby using threads as neither can clean up threads fast enough to run the test multiple times with large numbers of threads. We can however compare TruffleRuby with continuations to MRI 2.4. The test was run with 10000 fibres 20 times fibres to allow for warm up, and then another 20 times to collect timings.

Another thing to test is how fast it is to transfer control from one fibre to another. We'll use a very small test which will be completely dominated by the transfer time. Here is the source for this test.

def create_fibers(t)
  fibers = []
  0...t.times do
    fibers << Fiber.new do |x|
      while (true)
        f = fibers[rand(t)]
        Fiber.yield(f)
      end
    end
  end
  fibers
end

def schedule_fibers(t, n)
  fibers = create_fibers(t)
  next_fiber = fibers.first
  0...(n * t).times do
    next_fiber = next_fiber.resume
  end
end

This will create t fibres and transfer control among them t * n times. I had hoped to test this with large numbers of fibres, but again encountered issues with running the test using JRuby or TruffleRuby with threads, so tested with t = 100 and n = 1000

As you can see, MRI beats all the other implementations easily, and Loom's continuations still have a lot of work to be done on them performance wise. Some experiments with varying the values of t and n suggests that MRI's time is mostly spent creating the fibres, and it's very quick to transfer control between them. All other implementations are dominated by the time to transfer control between fibres and have run times mostly unaffected by the total number of fibres created (at least within the range I could test).