I put together a few microbenchmarks to try out the performance of Lwt threads versus fibers. The fiber test looks like this:

  module Fiber = struct
    let basic fn yields =
      for i = 1 to 15000 do
        for x = 1 to yields do
          Lwt_fiber.await (fn ())
        done
      done

    let run fn yields =
      Lwt_fiber.start (fun () -> basic fn yields)
  end

We invoke the run function with two arguments: a thread to use for blocking and the number of times we should yield serially (so we can confirm that an increasing number of yields scales linearly). The Lwt version is pretty similar:

  module LWT = struct
    let basic fn yields =
      for_lwt i = 1 to 15000 do
        for_lwt x = 1 to yields do
          fn ()
        done
      done
  
    let run = basic
  end

We do not need to do anything special to launch a thread since we are already in the Lwt main loop, and the syntax extension makes the for loops look like the Fiber example above.

The choice of blocking function is important. The first test runs using a fast Lwt.return () that returns immediately:

The x-axis on the above graph represents the number of yields in each loop. Both Lwt_fiber and pure Lwt optimise the case where a thread returns immediately, and so this graph simply tells us that the fast path is working (which is nice!). The next test replaces the blocking function with two alternatives that force the thread to yield:

There are two blocking functions used in the graph above:

• the "slow" version is Lwt_unix.sleep 0.0 which forces the registration of a timeout.
• the "medium" version is Lwt.pause () which causes the thread to pause and drop into the thread scheduler. In the case of Lwt_fiber, this causes an exception to be raised so we can benchmark the cost of using a delimited continuation.

Interestingly, using a fiber is slower than normal Lwt here, even though our callstack is not very deep. I would have hoped that fibers would be significantly cheaper with a small callstack, as the amount of backtracking should be quite low. Lets confirm that fibers do in fact slow down as the size of the callstack increases via this test:

  module Fiber = struct
    let recurse fn depth =
      let rec sum n = 
        Lwt_fiber.await (fn ());
        match n with
        |0 -> 0
        |n -> n + (sum (n-1)) 
      in
      for i = 1 to 15000 do
        ignore(sum depth)
      done

    let run fn depth = 
      Lwt_fiber.start (fun () -> recurse fn depth)
  end

The recurse function is deliberately not tail-recursive, so that the callstack increases as the depth parameter grows. The Lwt equivalent is slightly more clunky as we have to rewrite the loop to bind and return:

  module LWT = struct
    let recurse fn depth =
      let rec sum n =
        lwt () = fn () in
        match n with
        |0 -> return 0
        |n ->
          lwt n' = sum (n-1) in 
          return (n + n')
      in
      for_lwt i = 1 to 15000 do
        lwt res = sum depth in
        return ()
      done

   let run = recurse
  end

We then run the experiment using the slow Lwt_unix.sleep 0.0 function, and get this graph:

The above graph shows the recursive Lwt_fiber getting slower as the recursion depth increases, with normal Lwt staying linear. The graph also overlays the non-recursing versions as a guideline (*-basic-slow).

This first benchmark was a little surprising for me:

Jake Donham comments:

I speculated in my post that fibers might be faster if the copy/restore were amortized over a large stack. I wonder if you would repeat the experiment with versions where you call fn only in the base case of sum, instead of at every call. I think you're getting N^2 behavior here because you're copying and restoring the stack on each iteration.

When writing the test, I figured that calling the thread waiting function more often wouldn't alter the result (careless). So I modified the test suite to have a recurse test that only waits a single time at the end of a long call stack (see below) as well as the original N^2 version (now called recurse2).

  module Fiber = struct
    let recurse fn depth =
      let rec sum n = 
        match n with
        |0 -> Lwt_fiber.await (fn ()); 0
        |n -> n + (sum (n-1)) 
      in
      for i = 1 to 15000 do
        ignore(sum depth)
      done

    let run fn depth = 
      Lwt_fiber.start (fun () -> recurse fn depth)
  end

The N^2 version below of course looks the same as the previously run tests, with delimcc getting much worse as it yields more often:

However, when we run the recurse test with a single yield at the end of the long callstack, the situation reverses itself and now delimcc is faster. Note that this test ran with more iterations than the recurse2 test to make the results scale, and so the absolute time taken cannot be compared.

The reason for Lwt being slower in this becomes more clear when we examine what the code looks like after it has been passed through the pa_lwt syntax extension. The code before looks like:

  let recurse fn depth =
    let rec sum n =
      match n with
      | 0 -> 
          fn () >> return 0
      | n ->
          lwt n' = sum (n-1) in 
          return (n + n') in

and after pa_lwt macro-expands it:

  let recurse fn depth =
    let rec sum n =
      match n with
      | 0 ->
          Lwt.bind (fn ()) (fun _ -> return 0)
      | n ->
          let __pa_lwt_0 = sum (n - 1)
          in Lwt.bind __pa_lwt_0 (fun n' -> return (n + n')) in

Every iteration of the recursive loop requires the allocation of a closure (the Lwt.bind call). In the delimcc case, the function operates as a normal recursive function that uses the stack, until the very end when it needs to save the stack in one pass.

Overall, I'm convinced now that the performance difference is insignificant for the purposes of choosing one thread system over the other for MirageOS. Instead, the question of code interoperability is more important. Lwt-enabled protocol code will work unmodified in Javascript, and Delimcc code helps migrate existing code over.