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