Benchmarking dart2js Visitor Implementations

I learned a good lesson last night in regards to benchmarking Dart code: keep everything separate. Keep the different benchmark harnesses in separate scripts. I think it also a good idea to keep the implementations being benchmarked in separate libraries. With that in mind, I add a new approach tonight (bringing the number of implementations up to three) and try them out in JavaScript.

I am still benchmarking the Visitor Pattern as background research for the future Design Patterns in Dart. Although I tend to hate the pattern when I come across it in the wild, I rather enjoy it in Dart. For my sample code, I have a settled on a data structure representing work stuff inventory:

  var work_stuff = new InventoryCollection([
    mobile()..apps = [
      app('2048', price: 10.0),
      app('Pixel Dungeon', price: 7.0),
      app('Monument Valley', price: 4.0)
    ],
    tablet()..apps = [
      app('Angry Birds Tablet Platinum Edition', price: 1000.0)
    ],
    laptop()
  ]);

Each node in the work stuff data structure (laptop, mobile, app, etc.) implements the Visitor pattern by defining an accept() method that in turn calls a corresponding method in the Visitor object. The result is that I can throw together a new operation on the data structure without changing the structure or any nodes within it. By way of examples, I have simple total price and categorizing visitors:

  var cost = new PricingVisitor();
  work_stuff.accept(cost);
  print('Cost of work stuff: ${cost.totalPrice}.');

  var counter = new TypeCountVisitor();
  work_stuff.accept(counter);
  print('I have ${counter.apps} apps!');

And it is fairly fast. Even adding 1500 apps to the data structure only requires a little over 100µs to run these. I took up suggestions from the Gang of Four book and tried iterators inside the node structure with double and single dispatch. After realizing the need for keeping these in separate files, I found that the single dispatch approach was slightly faster (as expected).

The other approach suggested by the GoF was to make the visitor itself responsible for traversing the node structure. I am unsure if my current node structure is sufficiently complex to notice a difference, but this is for SCIENCE! Actually, exploring how I approach benchmarking at this point is at least as important as the actual numbers so I forge ahead.

I start by removing forEach() iterations from a copy of my data structure classes. The top-level InventoryCollection no longer iterates over its collection—it just calls the visitInventoryCollection() method in the visitor, expecting the visitor to perform the iterations. The various classes that have apps no longer iterate over each app—the corresponding method in the visitor will do that:

library inventory3; // visitor does the traversing
// ...
class InventoryCollection {
  String name;
  List<Inventory> stuff = [];
  InventoryCollection(this.stuff);
  void accept(visitor) {visitor.visitInventoryCollection(this);}
}
// ...
class Mobile extends EquipmentWithApps {
  Mobile(): super('Mobile Phone');
  double netPrice = 350.00;
  void accept(visitor) {visitor.visitMobile(this);}
}
// ...

Then I implement the iterating Visitor as:

library visitor;

import 'inventory_non_traversing.dart';
export 'inventory_non_traversing.dart';

abstract class InventoryVisitor {
  void visitMobile(Mobile i);
  void visitTablet(Tablet i);
  void visitLaptop(Laptop i);
  void visitApp(App i);
}

class PricingVisitor extends InventoryVisitor {
  double _totalPrice = 0.00;

  double get totalPrice => _totalPrice;

  void visitInventoryCollection(i) {
    _iterate(i.stuff);
  }
  void visitMobile(i) {
    _iterate(i.apps);
    _totalPrice += i.netPrice;
  }
  // ...
  void _iterate(list) {
    list.forEach((i){ i.accept(this); });
  }
}

Thanks to double dispatching, the same _iterate() method can work regardless of the type of collection. Since this is the Visitor Pattern, every node in the structure defines an accept() method (to call the appropriate method back in the same Visitor).

With that, I can throw together the usual benchmark_harness file for this new implementation:

#!/usr/bin/env dart

import 'package:benchmark_harness/benchmark_harness.dart';
import 'package:visitor_code/traversing_visitor.dart';

var visitor, nodes;

_setup(){
  visitor = new PricingVisitor();

  nodes = new InventoryCollection([mobile(), tablet(), laptop()]);
  for (var i=0; i<1000; i++) {
    nodes.stuff[0].apps.add(app('Mobile App $i', price: i));
  }
  for (var i=0; i<100; i++) {
    nodes.stuff[1].apps.add(app('Tablet App $i', price: i));
  }
}

class TraversingVisitorBenchmark extends BenchmarkBase {
  const TraversingVisitorBenchmark() : super("Visitor Traverses");
  static void main() { new TraversingVisitorBenchmark().report(); }

  void run() {
    nodes.accept(visitor);
  }
}

main () {
  _setup();

  TraversingVisitorBenchmark.main();
  TraversingVisitorBenchmark.main();
}

The benchmark code establishes simple node structure with one mobile, tablet, laptop and a bunch of apps. It then visits the node structure in the run() method to get the benchmark numbers.

Comparing this approach with the single and double dispatch versions of the iterators inside the node structure, I find:

$ ./tool/benchmark_for_single_dispatch.dart; \
  ./tool/benchmark_for_double_dispatch.dart; \
  ./tool/benchmark_traversing_visitor.dart 
Nodes iterate w/ single dispatch (RunTime): 116.5093790050099 us.
Nodes iterate w/ single dispatch (RunTime): 113.90818999886092 us.
Nodes iterate w/ double dispatch (RunTime): 128.8078830424422 us.
Nodes iterate w/ double dispatch (RunTime): 125.65971349585323 us.
Visitor Traverses(RunTime): 125.47838634795157 us.
Visitor Traverses(RunTime): 122.737035900583 us.

So the visitor traversing the structure is comparable to the internal double dispatching approach. That is not too unexpected since this approach also uses double dispatching.

What is interesting is what happens when I compile to JavaScript:

$ dart2js -o tool/benchmark_for_single_dispatch.dart.js tool/benchmark_for_single_dispatch.dart
$ dart2js -o tool/benchmark_for_double_dispatch.dart.js tool/benchmark_for_double_dispatch.dart
$ dart2js -o tool/benchmark_traversing_visitor.dart.js tool/benchmark_traversing_visitor.dart  
$ node tool/benchmark_for_single_dispatch.dart.js
Nodes iterate w/ single dispatch (RunTime): 390.70130884938465 us.
Nodes iterate w/ single dispatch (RunTime): 391.00684261974584 us.
$ node tool/benchmark_for_double_dispatch.dart.js
Nodes iterate w/ double dispatch (RunTime): 378.57278061707365 us.
Nodes iterate w/ double dispatch (RunTime): 376.01052829479227 us.
$ node tool/benchmark_traversing_visitor.dart.js
Visitor Traverses(RunTime): 391.6960438699569 us.
Visitor Traverses(RunTime): 391.6960438699569 us.

For some reason the internal double dispatching approach is the winner in this case. It is not a huge win, but it is noticeable. I may take a quick look at these with Chrome tools to see if I can find some explanation for why this would be. Tomorrow.

Day #117

‹prev | My Chain | next›