Wonky Benchmarks for Single and Double Dispatch in Dart

I think I am nearly done with my exploration of the Visitor Pattern for Design Patterns in Dart (at least the early research). I do not feel as though I have put nearly as much effort into it as I did the Factory Method Pattern though. So, at the risk of dragging this out too much...

There are not many variations of the Visitor. One possible suggestion from the Gang of Four book is to change the iterators used to move through composites in the node structure being processed. While reading this, I realized that my current iterator is using an inefficient double dispatch where a single dispatch is possible. This sounds like a nice chance to introduce benchmarks.

The overall data structure remains an inventory of my work stuff:

  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()
  ]);

Making use of the Visitor Pattern, I can introduce a visitor to this data structure and perform all sorts of useful operations:

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

The unnecessary double dispatch occurs in the concrete nodes like Mobile:

class Mobile extends EquipmentWithApps {
  Mobile(): super('Mobile Phone');
  double netPrice = 350.00;
  void accept(visitor) {
    apps.forEach((app) { app.accept(visitor); });
    visitor.visitMobile(this);
  }
}

Even though I am iterating over a list of apps, I am still invoking the double dispatch accept() method. This is double dispatch because the ultimate definition of the code invoked by this call depends on two objects instead of the usual one. In this case, it depends on the type of the object on which accept is called and the type of visitor. But in this case, I know the type of app at compile-time: it is an App object. Furthermore, I know that the accept() method in App calls visitApp():

class App extends Inventory {
  App(name): super(name);
  void accept(visitor) { visitor.visitApp(this); }
}

Since the apps attribute in Mobile will only be comprised of App instances, I can eliminate the indirection and call visitor.visitApp(app) directly:

class Mobile extends EquipmentWithApps {
  Mobile(): super('Mobile Phone');
  double netPrice = 350.00;
  void accept(visitor) {
    apps.forEach((app) { visitor.visitApp(app); });
    visitor.visitMobile(this);
  }
}

So let's benchmark. I create a single dispatch version of my visitor which is identical to my original except that is uses single dispatch in its iterators:

$ diff -u lib/inventory*
--- lib/inventory.dart  2014-07-08 22:07:45.322210237 -0400
+++ lib/inventory_single_dispatch.dart  2014-07-08 23:44:20.826351606 -0400
@@ -1,4 +1,5 @@
-library inventory2; // iterators double dispatch
+library inventory1; // iterators single dispatch
+
 
 App app(name, {price: 0}) => new App(name)..netPrice = price;
 Mobile mobile([name]) => new Mobile()..name = name;
@@ -44,7 +45,7 @@
   Mobile(): super('Mobile Phone');
   double netPrice = 350.00;
   void accept(visitor) {
-    apps.forEach((app) { app.accept(visitor); });
+    apps.forEach((app) { visitor.visitApp(app); });
     visitor.visitMobile(this);
   }
 }
@@ -53,7 +54,7 @@
   Tablet(): super('Tablet');
   double netPrice = 400.00;
   void accept(visitor) {
-    apps.forEach((app) { app.accept(visitor); });
+    apps.forEach((app) { visitor.visitApp(app); });
     visitor.visitTablet(this);
   }
 }

Then I write my benchmark_harness code such that I import the single dispatch version as i1 and the double dispatch version as i2:

import 'package:benchmark_harness/benchmark_harness.dart';

import 'package:visitor_code/visitor.dart';
import 'package:visitor_code/inventory_single_dispatch.dart' as i1;
import 'package:visitor_code/inventory.dart' as i2;

I do not expect huge differences so I try to push the issue by adding a large number of apps to my test code:

class NodesSingleBenchmark extends BenchmarkBase {
  const NodesSingleBenchmark() : super("Nodes iterate w/ single dispatch ");
  static void main() { new NodesSingleBenchmark().report(); }

  final Map o = {};

  void setup() {
    o['visitor'] = new PricingVisitor();

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

  get visitor => o['visitor'];
  get nodes => o['nodes'];

  void run() {
    nodes.accept(visitor);
    // print('Cost of work stuff: ${visitor.totalPrice}.');
  }
}

My setup adds 1000 apps to the mobile in my inventory collection as well as 100 apps to the tablet. I duplicate this for my double dispatch import as well. With that, I run my benchmarks as:

main () {
  NodesSingleBenchmark.main();
  NodesDoubleBenchmark.main();
  print('--');
  NodesDoubleBenchmark.main();
  NodesSingleBenchmark.main();
}

Running this, I find:

$ ./tool/benchmark.dart
Nodes iterate w/ single dispatch (RunTime): 112.0197154699227 us.
Nodes iterate w/ double dispatch (RunTime): 113.87576154415532 us.
--
Nodes iterate w/ double dispatch (RunTime): 112.19566924716706 us.
Nodes iterate w/ single dispatch (RunTime): 111.11111111111111 us.

Well, I did not expect a huge difference, but I expected some difference.

What is really odd is that, if I switch my single dispatch code back to the original double dispatch implementation then I do see a difference:

$ diff lib/inventory*  
1c1
< library inventory2; // iterators double dispatch
---
> library inventory1; // iterators single dispatch
$ ./tool/benchmark.dart
Nodes iterate w/ single dispatch (RunTime): 121.52883271556176 us.
Nodes iterate w/ double dispatch (RunTime): 112.02599002968688 us.
--
Nodes iterate w/ double dispatch (RunTime): 111.08642523883582 us.
Nodes iterate w/ single dispatch (RunTime): 120.12733497507358 us.

The code should be identical, but is consistently 7% slower than the duplicate. And if I switch the order in which the benchmarks are invoked, then the results change as well. I know that I am doing something wrong, but for the life of me, I cannot figure this one out.

Update: Eventually, I pull the two benchmarks out into separate benchmark scripts. With that, I find the results that I expect. When the iterators in both libraries are identical, I get (nearly) identical results from the benchmarks. When the implementations are different, I do find different numbers:

./tool/benchmark_for_double_dispatch.dart 
Nodes iterate w/ double dispatch (RunTime): 120.14898474107893 us.
Nodes iterate w/ double dispatch (RunTime): 121.0800339024095 us.
$ ./tool/benchmark_for_single_dispatch.dart 
Nodes iterate w/ single dispatch (RunTime): 111.11111111111111 us.
Nodes iterate w/ single dispatch (RunTime): 109.33143825507024 us.

I find this quite interesting—and a little worrisome. It seems safe to say that keeping different Dart benchmark classes in separate code files is more than just a best practice. I wonder how all of this affects dart2js benchmarks. Something to try tomorrow.


Day #116

‹prev | My Chain | next›