Monday, January 9, 2012

Dart Isolates for Speed

‹prev | My Chain | next›

Try as I might, I cannot avoid the dreaded fibonacci sequence example when working with Dart Isolates. I need a function that is going to take a little while so that I can compare the timing of a long running series of calculations with and without isolates.

So fibonacci, it is. In Dart, this looks like:
fib(i) {
  if (i < 2) return i;
  return fib(i-2) + fib(i-1);
}
That quite similar to just about every other fibonacci implemented in any other language. Now to make use of it. I take a series of six numbers, calculate the fibonnaci for each and print out the timing results:
#import('pretty_stopwatch.dart');

main() {
  var list = [5, 40, 39, 32, 6, 41];

  var timer = new PrettyStopwatch.start();
  var answers = {};
  list.forEach((i) {
    answers[i] = fib(i);
    print("fib(" + i + ") = " + answers[i]);
  });
  timer.stop();
}

fib(i) {
  if (i < 2) return i;
  return fib(i-2) + fib(i-1);
}
(try.dartlang.org) The result is:
➜  command_line git:(master) ✗ dart timer06.dart
fib(5) = 5
fib(40) = 102334155
fib(39) = 63245986
fib(32) = 2178309
fib(6) = 8
fib(41) = 165580141
Elapsed time: 11337ms
11.3 seconds. Pity my poor MacBook Air for not being faster. But even my early model Air has two cores, which means that, if I split the work across two isolates, I ought to halve the time it takes to calculate all six. I am using some non-DRY code, but it should serve its purpose to generate some numbers:
#import('pretty_stopwatch.dart');

main() {
  final fib_solver = new FibSolver();

  var list = [5, 40, 39, 32, 6, 41];

  // Spawn isolate #1 for the first 3 elements
  var timer1 = new PrettyStopwatch.start();
  fib_solver.spawn().then((port) {
    port.call(list.getRange(0,3)).receive((message, replyTo) {
      message.forEach((i, answer) {
        print("fib(" + i + ") = " + answer);
      });
      timer1.stop();
    });
  });

  // Spawn isolate #2 for the last 3 elements
  var timer2 = new PrettyStopwatch.start();
  fib_solver.spawn().then((port) {
    port.call(list.getRange(3,3)).receive((message, replyTo) {
      message.forEach((i, answer) {
        print("fib(" + i + ") = " + answer);
      });
      timer2.stop();
    });
  });
}

// Isolate class for solving lists of fibonacci numbers
class FibSolver extends Isolate {
  main() {
    var answers = {};

    port.receive((message, replyTo) {
      message.forEach((i) {
        answers[i] = fib(i);
        // print("fib(" + i + ") = " + answers[i]);
      });

      replyTo.send(answers);
    });
  }
}

fib(i) {
  if (i < 2) return i;
  return fib(i-2) + fib(i-1);
}
This results in:
➜  command_line git:(master) ✗ dart timer07.dart
fib(32) = 2178309
fib(6) = 8
fib(41) = 165580141
Elapsed time: 6554ms
fib(5) = 5
fib(40) = 102334155
fib(39) = 63245986
Elapsed time: 6856ms
It looks like both complete in around 6.8 seconds. Rather than run the time for each isolate individually, I would like to know when both have completed. Since I am not DRYing my code well here, I need two booleans—one to track each of the two isolates. When both have completed, I mark a timer Completer as complete, triggering the timer to stop and print out the results:
main() {
  final fib_solver = new FibSolver();

  var list = [5, 40, 39, 32, 6, 41];

  var timer = new PrettyStopwatch.start()
    , completer = new Completer();

  completer.future.then((args) {
    timer.stop();
  });

  var done1 = false
    , done2 = false;

  fib_solver.spawn().then((port) {
    port.call(list.getRange(0,3)).receive((message, replyTo) {
      message.forEach((i, answer) {
        print("fib(" + i + ") = " + answer);
      });
      done1 = true;
      if (done2) completer.complete(true);
    });
  });


  fib_solver.spawn().then((port) {
    port.call(list.getRange(3,3)).receive((message, replyTo) {
      message.forEach((i, answer) {
        print("fib(" + i + ") = " + answer);
      });
      done2 = true;
      if (done1) completer.complete(true);
    });
  });
}
(try.dartlang.org) I won't win any style points for that, but it does the trick, I now have accurate timing information for splitting the sequence of calculations across two isolates (each of which gets a core on my Air). The results:
➜  command_line git:(master) ✗ dart timer08.dart
fib(32) = 2178309
fib(6) = 8
fib(41) = 165580141
fib(5) = 5
fib(40) = 102334155
fib(39) = 63245986
Elapsed time: 6375ms
6.4 seconds. Not quite half, but that is to be expected since it was not an exact divide of calculations and there is some overhead involved in building isolates. If nothing else, I finally have a decent measure of how useful Isolates can be. Day #260

9 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. @Peter: The pure Dart version won't work unless you download and compile "Dartium": http://japhr.blogspot.com/2012/01/dartium.html

    But, just like with coffeescript, you can compile this into Javascript, which will run in any browser. The resultant Javascript is still on the large side, but that'll change at the tool evolves.

    Here's an example of converting Dart to JS: http://japhr.blogspot.com/2012/01/converting-complex-dart-apps-to.html

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
  3. i tried to get this working via a normal application project with the dart editor (i.e. html file, 2 dart files) which is converted to js anyway (at least the dart files)...doesn't work right now and my main problem is: how can the compiler convert multi-threading to js because js is always single-threaded?

    ReplyDelete
    Replies
    1. Actually, this should be single threaded as well. Dart Isolates come in two varieties: regular and heavy. The default, which I am using here, are single threaded just like JS. Under the covers they rely on evented callbacks to swap execution.

      The heavy version of Isolates start in different threads. When compiled into Javascript, these would then have to fall back to the regular, single-threaded version.

      I'll investigate this a bit more in a follow-up post. I am curious how the heavy Isolates affect the timing.

      Delete
    2. OK. I looked into it and was surprised at the results. Heavy vs. light Isolates made no difference in Dart. But it *did* make a difference when compiled to Javascript.

      The gory details: http://japhr.blogspot.com/2012/01/heavy-vs-light-dart-isolates.html

      (includes links to working dart and JS pages)

      Delete
  4. Hi Chris,
    I'm making a thesis on Dart and the actor model for my graduation in computer science engineering. I've tried your Fibonacci code with light and heavy isolate on a DartBoard and it gave me different results: heavy about 8sec; light about 16sec. Have you already seen this results?
    Thanks for your work, it helped my a lot.
    Ciao from Italy

    ReplyDelete
    Replies
    1. Yup, I found similar results the following night when I compiled this into Javascript: http://japhr.blogspot.com/2012/01/heavy-vs-light-dart-isolates.html (Dartboard is also compiled to Javascript).

      Glad to hear my stuff has been of use -- good luck with the thesis!

      Delete