Logarithmic Scales: For When the Winner is That Big

Up tonight: whatever breaks when I try my all-encompassing, Design Patterns in Dart benchmarking suite on a different pattern. I have been building it out on code for the Visitor Pattern and I think it is finally ready (more or less). So let's see what happens when I pull it back into the code for the Factory Method Pattern.

Note: the code is located at https://github.com/eee-c/design-patterns-in-dart. The current HEAD points to bec37fd41e.

What I found in the Visitor Pattern code was that the benchmark numbers were dependent on the number of times that a particular pattern was run through a loop. This could be specific to patterns that work on node structures like then Visitor Pattern. But for all I know, different approaches like storing a list of Factories in a Map might also be influenced by the number of times through a loop. There is only one way to find out…

I start with a little code re-organization. I think I have settled on storing the preferred solution directly in the lib directory of the particular pattern being explored while alternatives go in lib/alt. After that, I create a separate benchmark script for each approach in the tool directory:

$ tree tool
tool
├── benchmark.sh
├── benchmark.dart
├── benchmark_map_of_factories.dart
├── benchmark_mirrors.dart
└── packages -> ../packages

I also create a mostly-configuration benchmark.sh Bash script file that pulls in common code to run each of those Dart scripts. And it all works pretty brilliantly. Except for the 2 errors per script that cause each benchmark to crash:

Unhandled exception:
FileSystemException: Cannot open file, path = '/home/chris/repos/design-patterns-in-dart/factory_method/tool/packages/args/args.dart' (OS Error: No s)
#0      _rootHandleUncaughtError.<anonymous closure>. (dart:async/zone.dart:713)
...

The solution is fairly simple, though it does expose yet another gap in my thinking—this time regarding Dart Pub packages. Before moving the benchmarking code into a common package location, it was a development dependency for the Visitor Pattern code:

name: visitor_code
dev_dependencies:
  args: any
  benchmark_harness: any

That is no longer needed directly by the pattern code—the common benchmarking code parses command-line arguments now. Only it is clearly not being pulled into this factory method “application.” The factory method application depends on the common dpid_benchmarking package:

name: factory_method_code
dependencies:
  browser: any
dev_dependencies:
  dpid_benchmarking:
    path: ../packages/benchmarking

And dpid_benchmarking does depend on args:

name: dpid_benchmarking
dev_dependencies:
  args: any
  benchmark_harness: any

So why doesn't args get pulled into the application as well?

The answer is simple, really. It is a development dependency of dpid_benchmarking. In other words, it will get installed when used by other applications or packages (like my factory method code). As a development dependency, it is only installed when working directly with the package—when developing it in isolation.

This is not completely obvious. I had not given this much thought, but I realize now that I expected this package's development dependencies to be installed by my application's development dependencies. Somewhere in the back of my mind I was expecting the development dependency on dpid_benchmarking to pull in dpid_benchmarking's development dependencies as well.

Now that I have exposed this flawed thinking, I acknowledge that it was erroneous. Development dependencies are for single package development only. Hopefully I will remember that.

That issue aside, everything else just works. I get nice graphs that seem to prove that the number of times that a Factory Method implementation is used has no impact on its performance:



It may be a little hard to see, but there is a number associated with the “classic” subclass implementation of the Factory Method pattern—it is just really small compared to the other two approaches. For this, I tell gnuplot to plot the y axis logarithmically:

set style data histogram
set style histogram clustered
set style fill solid border
set xtics rotate out
set key tmargin
set xlabel "Loop Size"
set ylabel "µs per run"

set logscale y

plot for [COL=2:4] filename using COL:xticlabels(1) title columnheader

That gives me:



Any way that you look at it, the class subclass approach is the clear performance winner. There may be some maintainability wins for the other approaches, but they would have to be significant to warrant using them over the subclass approach. Even when compiled to JavaScript:



I think that will close out my initial research into object oriented design patterns for the book. I may investigate some concurrency patterns tomorrow. Or it may be time to switch back to Patterns in Polymer.


Day #132

‹prev | My Chain | next›

Internal Dart Packages for Organizing Codebases

This may very well apply only to me…

I would like to re-use some shell and Dart benchmarking code. I will not be duplicating code so I have to find a working solution. The problem with which I am faced is that I am not working on a single Dart package, but dozens—one for each pattern that will be covered in Design Patterns in Dart. Each package has its own internal Dart Pub structure, complete with pubspec.yaml and the usual subdirectories:

$ tree -L 2
.
├── factory_method
│   ├── build
│   ├── lib
│   ├── packages
│   ├── pubspec.lock
│   ├── pubspec.yaml
│   ├── tool
│   └── web
└── visitor
    ├── bin
    ├── lib
    ├── packages
    ├── pubspec.lock
    ├── pubspec.yaml
    └── tool

The code that I would like to share currently exists only in the Visitor Pattern's tool subdirectory. I suppose that I could create another top-level directory like helpers and then import the common code into visitor, factory_method and the still-to-be-written directories. That seems like a recipe for an unmaintainable codebase—I will wind up with crazy depths and amounts of relative imports (e.g. import '../../../../helpers/benchmark.dart') strewn about. And the coding gods help me should I ever want to rename things.

Instead, I think that I will create a top-level packages directory to hold my common benchmarking code, as well as any other common code that I might want to use. As the name suggests, I can create this as an actual Dart Pub package, but instead of publishing it to pub.dartlang.org, I can keep it local:

$ tree -L 2
.
├── factory_method
│   └── ...
├── packages
│   └── benchmarking
└── visitor
    └── ...

I am probably going to regret this, but I named the package's subdirectory as the relatively brief ”benchmarking,” but name the package dpid_benchmarking in pubspec.yaml. The idea here is to save a few keystrokes on the directory name, but ensure that my local package names do not conflict with any that might need to be used as dependencies. So in packages/benchmarking, I create a pubspec.yaml for my local-only package:

name: dpid_benchmarking
dev_dependencies:
  args: any
  benchmark_harness: any

There is nothing fancy there—it reads like any other package specification in Dart, which is nice.

The first bit of common code that I would like to pull in is not Dart. Rather it is the common _benchmark.sh Bash code from last night. There is nothing in Dart's packages that prevent packaging other languages, a fact that I exploit here:

$ git mv visitor/tool/_benchmark.sh packages/benchmarking/lib

I use the lib subdirectory in the package because that is the only location that is readily shared by Dart packages.

To use _benchmark.sh from the vistor code samples, I now need to declare that it depends on my local-only package. This can be done in pubspec.yaml with a dependency. Since this is benchmarking code, it is not a build dependency. Rather it is a development dependency. And, since this is a local-only package, I have to specify a path attribute for my development dependency:

name: visitor_code
dev_dependencies:
  dpid_benchmarking:
    path: ../packages/benchmarking

I suffer a single relative path in my pubspec.yaml because Pub rewards me with a common, non-relative path after pub install. Installing this local-only package creates a symbolic link to packages/dpid_benchmarking/lib in the packages directory:

$ pwd
/home/chris/repos/design-patterns-in-dart/visitor
$ ls -l packages 
lrwxrwxrwx 1 chris chris 31 Jul 22 21:35 dpid_benchmarking -> ../../packages/benchmarking/lib
lrwxrwxrwx 1 chris chris  6 Jul 22 21:35 visitor_code -> ../lib

Especially useful here is that Dart Pub creates this packages directory in all of the standard pub subdirectories like tool:

$ cd tool
$ pwd
/home/chris/repos/design-patterns-in-dart/visitor/tool
$ ls -l packages/
lrwxrwxrwx 1 chris chris 31 Jul 22 21:35 dpid_benchmarking -> ../../packages/benchmarking/lib
lrwxrwxrwx 1 chris chris  6 Jul 22 21:35 visitor_code -> ../lib

This is wonderfully useful in my visitor pattern's benchmark.sh Bash script. Instead of sourcing _benchmark.sh in the current tool directory, I simply change it so that it sources it from the local-only package:

#!/bin/bash

source ./packages/dpid_benchmarking/_benchmark.sh

BENCHMARK_SCRIPTS=(
    tool/benchmark.dart
    tool/benchmark_single_dispatch_iteration.dart
    tool/benchmark_visitor_traverse.dart
)

_run_benchmarks $1

The symbolic links from Dart Pub takes care of the rest. Nice!

Of course, Pub is the Dart package manager, so it works with Dart code as well. I move some obvious candidates for common benchmarking from visitor/tool/src into the local-only package:

$ git mv visitor/tool/src/config.dart packages/benchmarking/lib/
$ git mv visitor/tool/src/score_emitters.dart packages/benchmarking/lib/

It is then a simple matter of changing the import statements to use the local-only package:

import 'package:dpid_benchmarking/config.dart';
import 'package:dpid_benchmarking/score_emitters.dart';
import 'package:visitor_code/visitor.dart';

main (List args) {
  // ...
}

Dart takes care of the rest!

Best of all, I rinse and repeat in the rest of my design patterns. I add the dpid_benchmarking local-only package as a development dependency, run pub install, then make use of this common code to ensure that I have beautiful data to back up some beautiful design patterns.

That is an all-around win thanks to Dart's Pub package manager. Yay!


Day #130

‹prev | My Chain | next›

Refactoring Bash Scripts

I'll be honest here: I'm a pretty terribly Bash script coder. I find the man page too overwhelming to really get better at it. If I need to do something in Bash—even something simple like conditional statements—I grep through /etc/init.d scripts or fall back to the Google machine.

But tonight, there is no hiding. I have two Bash scripts (actually, just shell scripts at this point) that do nearly the same thing: benchmark.sh and benchmark_js.sh. Both perform a series of benchmarking runs of code for Design Patterns in Dart, the idea being that it might be useful to have actual numbers to back up some of the approaches that I include in the book. But, since this is Dart, it makes sense to benchmark both on the Dart VM and on a JavaScript VM (the latter because most Dart code will be compiled with dart2js). The two benchmark shell scripts are therefore responsible for running and generating summary results for Dart and JavaScript.

The problem with two scripts is twofold. First, I need to keep them in sync—any change made to one needs to go into the other. Second, if I want to generalize this for any design pattern, I have hard-coded way too much in both scripts. To the refactoring machine, Robin!

To get an idea where to start, I diff the two scripts. I have been working fairly hard to keep the two scripts in sync, so there are only two places that differ. The JavaScript version includes a section that compiles the Dart benchmarks in to JavaScript:

$ diff -u1 tool/benchmark.sh tool/benchmark_js.sh 
--- tool/benchmark.sh   2014-07-21 22:32:44.047778498 -0400
+++ tool/benchmark_js.sh        2014-07-21 20:54:20.803634500 -0400
@@ -11,2 +11,16 @@
 
+# Compile
+wrapper='function dartMainRunner(main, args) { main(process.argv.slice(2)); }';
+dart2js -o tool/benchmark.dart.js \
+           tool/benchmark.dart
+echo $wrapper >> tool/benchmark.dart.js
+
+dart2js -o tool/benchmark_single_dispatch_iteration.dart.js \
+           tool/benchmark_single_dispatch_iteration.dart
+echo $wrapper >> tool/benchmark_single_dispatch_iteration.dart.js
+
+dart2js -o tool/benchmark_visitor_traverse.dart.js \
+           tool/benchmark_visitor_traverse.dart
+echo $wrapper >> tool/benchmark_visitor_traverse.dart.js
+
...

The other difference is actually running the benchmarks—the JavaScript version needs to run through node.js:

$ diff -u1 tool/benchmark.sh tool/benchmark_js.sh 
--- tool/benchmark.sh   2014-07-21 22:32:44.047778498 -0400
+++ tool/benchmark_js.sh        2014-07-21 20:54:20.803634500 -0400
...
@@ -15,7 +29,7 @@
 do
-    ./tool/benchmark.dart --loop-size=$X \
+    node ./tool/benchmark.dart.js --loop-size=$X \
         | tee -a $RESULTS_FILE
-    ./tool/benchmark_single_dispatch_iteration.dart --loop-size=$X \
+    node ./tool/benchmark_single_dispatch_iteration.dart.js --loop-size=$X \
         | tee -a $RESULTS_FILE
-    ./tool/benchmark_visitor_traverse.dart --loop-size=$X \
+    node ./tool/benchmark_visitor_traverse.dart.js --loop-size=$X \
         | tee -a $RESULTS_FILE

For refactoring purposes, I start with the latter difference. The former is a specialization that can be performed in a single conditional. The latter involves both uses of the script.

That will suffice for initial strategy, what about tactics? Glancing at the Dart benchmark.sh script, I see that I have a structure that looks like:

#!/bin/bash

RESULTS_FILE=tmp/benchmark_loop_runs.tsv
SUMMARY_FILE=tmp/benchmark_summary.tsv
LOOP_SIZES="10 100 1000 10000 100000"

# Initialize artifact directory
...

# Individual benchmark runs of different implementations
...

# Summarize results
...

# Visualization ready
...

Apparently I have been quite fastidious about commenting the code because those code section comments are actually there. They look like a nice first pass a series of functions. Also of note here is that the script starts by setting some global settings, which seems like a good idea even after refactoring—I can use these and others to specify output filenames, benchmark scripts, and whether or not to use the JavaScript VM.

But first things first, extracting the code in each of those comment sections out into functions. I make a top-level function that will invoke all four functions-from-comment-sections:

_run_benchmarks () {
    initialize
    run_benchmarks
    summarize
    all_done
}

Then I create each function as:

# Initialize artifact directory
initialize () {
  # ...
}

# Individual benchmark runs of different implementations
run_benchmarks () {
  # ...
}

# Summarize results
summarize () {
  # ...
}

# Visualization ready
all_done () {
  # ...
}

Since each of those sections is relying on top-level global variables, this just works™ without any additional work from me.

Now for some actual refactoring. One of the goals here is to be able to use this same script not only for JavaScript and Dart benchmarking of the same pattern, but also for different patterns. To be able to use this for different patterns, I need to stop hard-coding the scripts inside the new run_benchmarks function:

run_benchmarks () {
    echo "Running benchmarks..."
    for X in 10 100 # 1000 10000 100000
    do
      ./tool/benchmark.dart --loop-size=$X \
          | tee -a $RESULTS_FILE
      ./tool/benchmark_single_dispatch_iteration.dart --loop-size=$X \
          | tee -a $RESULTS_FILE
      ./tool/benchmark_visitor_traverse.dart --loop-size=$X \
          | tee -a $RESULTS_FILE
    done
    echo "Done. Results stored in $results_file."
}

The only thing that is different between those three implementation benchmarks is the name of the benchmark file. So a list of files in a global variable that could be looped over is my next step:

BENCHMARK_SCRIPTS=(
    tool/benchmark.dart
    tool/benchmark_single_dispatch_iteration.dart
    tool/benchmark_visitor_traverse.dart
)

Up until this point, I think I could get away with regular Bourne shell scripting, but lists like this are only available in Bash. With that, I can change run_benchmarks to:

run_benchmarks () {
    echo "Running benchmarks..."
    for X in 10 100 1000 10000 100000
    do
        for script in ${BENCHMARK_SCRIPTS[*]}
        do
            ./$script --loop-size=$X | tee -a $results_file
        done
    done
    echo "Done. Results stored in $results_file."
}

At this point, I would like to get a feel for what the common part of the script is and what specialized changes are needed for each new pattern benchmark. So I move all of my new functions out into a _benchmark.sh script that can be ”sourced” by the specialized code:

#!/bin/bash

source ./tool/_benchmark.sh

BENCHMARK_SCRIPTS=(
    tool/benchmark.dart
    tool/benchmark_single_dispatch_iteration.dart
    tool/benchmark_visitor_traverse.dart
)

RESULTS_FILE=benchmark_loop_runs.tsv
SUMMARY_FILE=benchmark_summary.tsv

_run_benchmarks

That is pretty nice. I can easily see how I would use this for other patterns—for each implementation being benchmarked, I would simple add them to the list of BENCHMARK_SCRIPTS.

Now that I see what is left of the code, I realize that the RESULTS_FILE and SUMMARY_FILE variables were only varied to keep from overwriting artifacts of the different VM runs. The basename for each remains the same between the two original scripts—the JavaScript artifacts include an additional _js. That is the kind of thing that can be moved into my new common _benchmark.sh file:

#...
results_basename="benchmark_loop_runs"
summary_basename="benchmark_summary"
results_file=""
summary_file=""
type="js"
# ...
initialize () {
    if [ "$type" = "js" ]; then
        results_file=$tmpdir/${results_basename}_js.tsv
        summary_file=$tmpdir/${summary_basename}_js.tsv
    else
        results_file=$tmpdir/${results_basename}.tsv
        summary_file=$tmpdir/${summary_basename}.tsv
    fi
    # ...
}

If _run_benchmarks is invoked when type is set to "js", then the value of the results_file variable will then include _js in the basename. If "js" is not supplied, then the old basename will be used.

To obtain that information from the command-line, I read the first argument supplied when the script is called ($1) and send it to _run_benchmarks:

_run_benchmarks $1

I can then add a new (very simple) parse_options function to see if this script is running the Dart or JavaScript benchmarks:

_run_benchmarks () {
    parse_options $1
    initialize
    run_benchmarks
    summarize
    all_done
}

parse_options () {
  if [ "$1" = "-js" -o "$1" = "--javascript" ]
  then
      type="js"
  fi
}
# ...

The $1 inside _run_benchmarks is not the same as the $1 from the command-line. Inside a function, $1 refers to the first argument supplied to it.

I can also make use of this to pull in the last piece of refactoring—the compiling that I decided to save until later. Well, now it is later and I can compile as needed when type has been parsed from the command line to be set to "js":

_run_benchmarks () {
    parse_options $1
    initialize
    if [ "$type" = "dart" ]; then
        run_benchmarks
    else
        compile
        run_benchmarks_js
    fi
    summarize
    all_done
}

With that, I have everything I need to keep the specialized versions of the benchmarking script small:

#!/bin/bash

source ./tool/_benchmark.sh

BENCHMARK_SCRIPTS=(
    tool/benchmark.dart
    tool/benchmark_single_dispatch_iteration.dart
    tool/benchmark_visitor_traverse.dart
)

_run_benchmarks $1

No doubt there is much upon which I could improve if I wanted to get really proficient at Bash scripting, but I am reasonably happy with this. It ought to suit me nicely when I switch to other patterns. Which I will try next. Tomorrow.



Day #129

‹prev | My Chain | next›

Reading Files from STDIN in Dart

I need to read from STDIN on the command-line. Not just a single line, which seems to well understood in Dart, but from an entire file redirected into a Dart script.

My benchmarking work has a life of its own now with several (sometimes competing) requirements. One of those requirements is that the code that actually produces the benchmark raw data cannot use dart:io for writing to files (because it also compiled to JavaScript which does not support dart:io). Given that, my benchmark results are sent to STDOUT and redirected to artifact files:

    ./tool/benchmark.dart --loop-size=$X \
        | tee -a $RESULTS_FILE

Or, the JavaScript version:

    node ./tool/benchmark.dart.js --loop-size=$X \
        | tee -a $RESULTS_FILE

That works great, mostly because Dart's print() sends its data to STDOUT regardless of whether or not it is being run the Dart VM or in Node.js after being put through dart2js.

What I need now is a quick way to summarize the raw results that can work with either the Dart or JavaScript results. Up until now, I have hard-coded the current filename inside the summary script which is then run as:

./tool/summarize_results.dart > $SUMMARY_FILE

The problem with that is twofold: I should not hard-code a filename like that and the artifact filenames should all be managed in the same location.

I could send the filename into the ./tool/summarize_results.dart as an argument. That would, in fact, require a minimal amount of change. But I have a slight preference to be consistent with shell file redirection—if STDOUT output is being redirected to a file, then my preference is to (at least support) reading from a file and piping into the script via STDIN.

Fortunately, this is fairly easy with dart:io's stdin top-level getter. It actually turns out to be very similar to the single-line-of-keyboard-input solutions that are already out there:

_readTotals() {
  var lines = [];

  var line;
  while ((line = stdin.readLineSync()) != null) {
    var fields = line.split('\t');
    lines.add({
      'name': fields[0],
      'score': fields[1],
      'loopSize': fields[2],
      'averageScore': fields[3]
    });
  }

  return lines;
}

The only real “trick” here is the null check at the end of the STDIN input stream. Pleasantly, that was easy to figure out since is it similar to many other languages implementation of STDIN processing.



Day #128

‹prev | My Chain | next›

Command Line Arguments with Node.js and Dart2js

How on earth did it come to this?

I need for my compiled Dart to respond to command line arguments when compiled to JavaScript and run under Node.js. I think that sentence reads as proper English.

It all seemed so simple at first. I want to benchmark code for Design Patterns in Dart. I may use benchmarks for every pattern, I may use them for none—either way I would like the ability to quickly get benchmarks so that I can compare different approaches that I might take to patterns. So I would like to benchmark.

So I benchmark my Dart code. I added features to command-line Dart scripts so that they can read command line switches to vary the loop size (which seems to make a difference). Then I try to compile this code to JavaScript to be run under node.js. That actually works. Except for command line options to vary the loop size.

And so here I am. I need to figure out how to get node.js running dart2js code to accept command-line (or environment) options.

Last night I found that the usual main() entry point simply does not see command line arguments when compiled via dart2js and run with node. The print() of the command line args is an empty List even when options are supplied:

main (List<String> args) {
  print(args);
  // ...
}

With the Dart VM, I see command line options:

$ dart ./tool/benchmark.dart --loop-size=666
[--loop-size=666]

And, with the very nice args package, I can even process them to useful things. But when run with node.js, I only get a blank list:

$ node ./tool/benchmark.dart.js --loop-size=666
[]

I had thought to use some of the process environment options, but they are all part of the dart:io package which is unsupported by dart2js. Even initializing a string from the environment does not work:

const String LOOP_SIZE = const String.fromEnvironment("LOOP_SIZE", defaultValue: "10");

No matter how I tried to set that environment variable, my compiled JavaScript would only use the default value.

So am I stuck?

The answer turns out to be embedded in the output of dart2js code. At the very top of the file are a couple of hints including:

// dartMainRunner(main, args):
//    if this function is defined, the Dart [main] method will not be invoked
//    directly. Instead, a closure that will invoke [main], and its arguments
//    [args] is passed to [dartMainRunner].

It turns out that I can use this dartMainRunner() function to grab command line arguments the node.js way so that they can be supplied to the compiled Dart. In fact, I need almost no code to do it:

function dartMainRunner(main, args) {
  main(process.argv.slice(2)); 
}

I slice off the first two command line arguments, supplying the main() callback with the rest. In the case of my node.js code, the first two arguments are the node executable and the script name:

$ node ./tool/benchmark.dart.js --loop-size=666

With those chomped off, I am only supplying the remainder of the command line arguments—the switches that control how my benchmarks will run.

This is a bit of a hassle in my Dart benchmarks since I will need to add that wrapper code to each implementation every time that I make a change. I probably ought to put all of this into a Makefile (or equivalent). For now, however, I simply make it part of my benchmarking shell script:

#...
# Compile
wrapper='function dartMainRunner(main, args) { main(process.argv.slice(2)); }';
dart2js -o tool/benchmark.dart.js \
           tool/benchmark.dart
echo $wrapper >> tool/benchmark.dart.js

# More compiling then actual benchmarks ...

And that works!

Thanks to my already in place gnuplot graphing solution, I can even plot my three implementations of the Visitor Pattern compiled from Dart into JavaScript. The number of microseconds it takes a single run relative to the number of loops winds up looking like this:



That is a little different than last night's Dart numbers, but the bottom line seems to be that it does not matter too much which implementation I choose. At least for this pattern. Regardless, I am grateful to be able to get these numbers quickly now—even from node.js.


Day #127

‹prev | My Chain | next›

Close, But Not Quite Visualizing dart2js Benchmark Comparisons

Thanks to benchmark_harness and gnuplot I can make quick, pretty, and useful visualizations of the performance of different code implementations:



The actual numbers are almost inconsequential at this point. I need to know that I can make and visualize them in order to know that I can choose the right solution for inclusion in Design Patterns in Dart. I can investigate the numbers later—for now I only need know that I can generate them.

And I think that I finally have that sorted out. I think that I have eliminated inappropriate comparisons, loops, types and just plain silly mistakes. To be sure, the code could (and probably will need to be) better. But, it works. More importantly, it can be run through a single tool/benchmark.sh script:

#!/bin/sh

# Initialize artifact directory
mkdir -p tmp
cat /dev/null > tmp/benchmark_loop_runs.tsv
cat /dev/null > tmp/benchmark_summary.tsv

# Individual benchmark runs of different implementations
echo "Running benchmarks..."
for X in 10 100 1000 10000 100000
do
    ./tool/benchmark.dart --loop-size=$X
    ./tool/benchmark_single_dispatch_iteration.dart --loop-size=$X
    ./tool/benchmark_visitor_traverse.dart --loop-size=$X
done
echo "Done. Results stored in tmp/benchmark_loop_runs.tsv."

# Summarize results
echo "Building summary..."
./tool/summarize_results.dart
echo "Done. Results stored in tmp/benchmark_summary.tsv."

# Visualization ready
echo ""
echo "To view in gnuplot, run tool/visualize.sh."

I am little worried about the need for artifacts, but on some level they are needed—the VM has to be freshly started with each run for accurate numbers. To retain the data between runs—and between the individual runs and the summary—artifacts files will need to store that information. I will worry about that another day.

My concern today is that I am benchmarking everything on the Dart VM. For the foreseeable future, however, the Dart VM will not be the primary runtime environment for Dart code. Instead, most Dart code will be compiled to JavaScript via dart2js. I cannot very well recommend a solution that works great in Dart, but fails miserably in JavaScript.

So how to I get these numbers and visualizations in JavaScript?

Well, I already know how to benchmark dart2js. I just compile to JavaScript and run with Node.js. Easy-peasey, right?

$ dart2js -o tool/benchmark.dart.js \
>            tool/benchmark.dart
tool/src/score_emitters.dart:3:8:
Error: Library not found 'dart:io'.
import 'dart:io';
       ^^^^^^^^^
tool/src/score_emitters.dart:39:18:
Warning: Cannot resolve 'File'.
  var file = new File(LOOP_RESULTS_FILE);
                 ^^^^
tool/src/score_emitters.dart:40:23:
Warning: Cannot resolve 'FileMode'.
  file.openSync(mode: FileMode.APPEND)
                      ^^^^^^^^
Error: Compilation failed.

Arrrgh. All of my careful File code is for naught if I want to try this out in JavaScript. On the bright side, this is why you try a solution in a bunch of different environments before generalizing.

This turns out to have a fairly easy solution thanks to tee. I change the score emitter to simply print to STDOUT in my Dart code:

recordTsvTotal(name, results, loopSize, numberOfRuns) {
  var averageScore = results.fold(0, (prev, element) => prev + element) /
    numberOfRuns;

  var tsv =
    '${name}\t'
    '${averageScore.toStringAsPrecision(4)}\t'
    '${loopSize}\t'
    '${(averageScore/loopSize).toStringAsPrecision(4)}';

  print(tsv);
}

Then I make the benchmark.sh responsible for writing the tab separated data to the appropriate file:

RESULTS_FILE=tmp/benchmark_loop_runs.tsv
# ...
dart2js -o tool/benchmark.dart.js \
           tool/benchmark.dart
# ...
for X in 10 100 1000 10000 100000
do
    ./tool/benchmark.dart --loop-size=$X | tee -a $RESULTS_FILE
    # ...
done

That works great—for the default case:

$ node tool/benchmark.dart.js
Classic Visitor Pattern 6465    10      646.5

Unfortunately, the dart:args package does not work with Node.js. Supplying a different loop size still produces results for a loop size of 10:

$ node tool/benchmark.dart.js --loop-size=100
Classic Visitor Pattern 6543    10      654.3

My initial attempt at solving this is String.fromEnvironment():

const String LOOP_SIZE = const String.fromEnvironment("LOOP_SIZE", defaultValue: "10");

class Config {
  int loopSize, numberOfRuns;
  Config(List<String> args) {
    var conf = _parser.parse(args);
    loopSize = int.parse(LOOP_SIZE);
    // ...
  }
  // ...
}

But that does not work. When I run the script, I still get a loop size of 10:

$ LOOP_SIZE=100 node tool/benchmark.dart.js
Classic Visitor Pattern 6160    10      616.0

Stumped there, I call it a night.

I would have preferred to get all the way to a proper visualization, but the switch to tee for building the tab separated artifact is already a win. The filename is now located in a single script (the overall shell script) instead of two places (the shell script and Dart code). Hopefully I can figure out some way to read Node.js command line arguments from compiled Dart. Tomorrow.


Day #126

‹prev | My Chain | next›

Gnuplot Dart Benchmarks

I am embracing the idea of benchmarking the solutions that I add to Design Patterns in Dart. This early in the research, I am unsure if I will have a strong need for benchmarks. What I do know is that if I cannot make benchmarking easy, then I will almost certainly not use them.

So tonight, I take a quick look at the last piece of my puzzle: visualization. After last night, I have a solution that can store the average run time of a single benchmark run against the number of loops to gather that data. The CSV output looks something like:

Loop_Size, Classic_Visitor_Pattern, Nodes_iterate_w/_single_dispatch, Visitor_Traverses
10, 122.4, 110.6, 117.5, 
100, 118.5, 112.4, 117.6, 
1000, 120.4, 112.4, 116.8, 
10000, 148.6, 148.2, 117.9, 
100000, 148.1, 148.7, 118.5, 

I can paste that data in a spreasheet to produce nice looking graphs like:



But let's face it, if I have to open a spreadsheet every time that I want to look at my data, I am never going to do it. So unless I can find some way to quickly visualize that data, all of this would be for naught. Enter gnuplot.

The preferred data format for gnuplot seems to be tab separated values, so I rework the row output in my Dart benchmark reporter to output tabs instead of commas:

    // ...
    var row = '${loopSize}\t';
    implementations.forEach((implementation){
      var rec = records.firstWhere((r)=> r['name'] == implementation);
      row += '${rec["averageScore"]}\t';
    });
    // ...

The graph type that I want in this case is a clustered histogram culled from data. In gnuplot parlance, that translates as:

set style data histogram
set style histogram clustered

I fiddle a bit with styles (and cull a few from Google / Stack Overflow) to settle on these settings:

set style fill solid border
set xtics rotate out
set key tmargin

The fill style makes the bars a little easier to see and the other two make the data and legends easier to see. Finally, I plot the data as:

plot for [COL=2:4] 'bar.tsv' using COL:xticlabels(1) title columnheader

Which results in:



That is quite nice for just a little bit of work. I do, however, note that this graph suffers from a pretty serious flaw—the same flaw from which my spreadsheet graph suffered unnoticed by me until now. The y-axis does not start at zero, which greatly exaggerates the discrepancies between my three implementations. To start the y-axis at zero, I use:

set yrange [0:]

Now my graph looks like:



Now that I see the “jump” in values at the 10k loop size in that perspective, it does not seem nearly as worrisome.

If I put that all in a gnuplot script file:

# set terminal png size 1024,768
# set output  "bar.png"
set style data histogram
set style histogram clustered
set style fill solid border
set xtics rotate out
set key tmargin
set yrange [0:]
plot for [COL=2:4] 'bar.tsv' using COL:xticlabels(1) title columnheader
pause -1 "Hit any key to continue"

Then I can quickly see my benchmarking results whenever I need to. No excuses.


Day #125

‹prev | My Chain | next›

Fun with Dart Iterable

I am going to take a brief break from my Visitor Pattern benchmarks for Design Patterns in Dart, but not really. Instead of working with the actual numbers, I want to write a simple Dart script that reads a CSV file of runs totals so that they can be grouped and transposed.

In other words, I want to have a little Iterable fun.

After 5 runs of my Visitor Pattern implementation benchmarks, I have 15 rows of results. There are three implementations being benchmarked. For each of the three implementations, I try executing them inside loops of sizes increasing by a power of ten from 10 to 100,000. The results look like:

Classic Visitor Pattern, 1224, 10, 122.4
Nodes iterate w/ single dispatch, 1106, 10, 110.6
Visitor Traverses, 1175, 10, 117.5
Classic Visitor Pattern, 1.185e+4, 100, 118.5
Nodes iterate w/ single dispatch, 1.124e+4, 100, 112.4
Visitor Traverses, 1.176e+4, 100, 117.6
Classic Visitor Pattern, 1.204e+5, 1000, 120.4
Nodes iterate w/ single dispatch, 1.124e+5, 1000, 112.4
Visitor Traverses, 1.168e+5, 1000, 116.8
Classic Visitor Pattern, 1.486e+6, 10000, 148.6
Nodes iterate w/ single dispatch, 1.482e+6, 10000, 148.2
Visitor Traverses, 1.179e+6, 10000, 117.9
Classic Visitor Pattern, 1.481e+7, 100000, 148.1
Nodes iterate w/ single dispatch, 1.487e+7, 100000, 148.7
Visitor Traverses, 1.185e+7, 100000, 118.5

To make pretty graphs from those numbers, I would like to group the results by loop size (the 3rd column in the CSV) and include the results of each implementation (Classic, Single Dispatch, Visitor Traverses). So it ought to look like:

10,     122.4, 110.6, 117.5
100,    118.5, 112.4, 117.6
1000,   120.4, 112.4, 116.8
10000,  148.6, 148.2, 117.9
100000, 148.1, 148.7, 118.5

I create the script and make it executable:

$ touch tool/group_totals.dart 
$ chmod 755 tool/group_totals.dart

I read the totals with a little synchronous help (I just prefer synchronous reads for small stuff) from dart:io:

_readTotals() {
  var file = new File('totals.csv');
  var lines = file.readAsLinesSync();

  return lines.map((line){
    var fields = line.split(', ');
    return {
      'name': fields[0],
      'score': fields[1],
      'loopSize': fields[2],
      'averageScore': fields[3]
    };
  }).toList();
}

I have to toList() on the result of the map()—otherwise I would return an Iterable.

The problem at this point is that Dart lacks a groupBy() method on Lists and Iterables. There seems to be a groupBy package available, but I am curious how I might implement this on my own. And the best that I can come up with is to find all values for loopSize and convert them to a Set (to eliminate duplicates):

main() {
  List<Map> totals = _readTotals();
  var loopSizes = totals.map((r)=> r['loopSize']).toSet();

  loopSizes.forEach((loopSize) {
    // Print results for each loop size
  }
}

That is already kind of ugly, but lacking better ideas, I forge ahead. I find all records where the loop size is the same as the current value:

  loopSizes.forEach((loopSize) {
    var records = totals.where((r)=> r['loopSize'] == loopSize);
    // ...
  }

From that list of records, I then extract the individual records that I seek (Classic Visitor Pattern, Single Dispatch Optimized, and Visitor Traverses the Node Structure):

  loopSizes.forEach((loopSize) {
    var records = totals.where((r)=> r['loopSize'] == loopSize);

    var classic = records.firstWhere((r)=> r['name'].contains('Classic'));
    var single = records.firstWhere((r)=> r['name'].contains('single'));
    var vTraverses = records.firstWhere((r)=> r['name'].contains('Traverses'));

    print(
      '${loopSize}, '
      '${classic["averageScore"]}, '
      '${single["averageScore"]}, '
      '${vTraverses["averageScore"]}'
    );
  });

And then I print the results (adjacent strings in Dart are concatenated). The prettiness of the code has not improved much, but it works:

$ ./tool/group_totals.dart
10, 122.4, 110.6, 117.5
100, 118.5, 112.4, 117.6
1000, 120.4, 112.4, 116.8
10000, 148.6, 148.2, 117.9
100000, 148.1, 148.7, 118.5

And, pasted into a spreadsheet, it is easy to obtain pretty graphs:



Still, iterables in Dart would be a lot more fun with a group-by method.

The code is located in the book's public code repository. Tonight's script was group_totals.dart (81d0ed10ff).


Day #124

‹prev | My Chain | next›

Constant Constructors and Benchmark Scoring

I really appreciated the graph from last night's benchmarking post:



It makes it much more obvious where things change than just looking at a table of numbers:

Loop Size	Classic	Nodes Traverse (single dispatch)	Visitor Traverses
10	131.6	122.7	121.4
100	125.9	113.6	120.15
1000	123.8	122.8	120.65
10000	157.0	153.25	120.45
100000	158.05	154.65	121.05

Building the actual graph was a pain. If there is pain involved, it is quite likely that I am not going to make use of what I just described as very useful. So, before moving on to other learning territory, let's see if I ease the pain.

The pain involved manually copying CSV benchmarks of three different implementations of the Visitor Pattern in Dart. The benchmarking code is available in the tool subdirectory of the publicly available visitor book code for the forthcoming Design Patterns in Dart (last night's SHA1 was 14dea8561a).

To make the graph, I pasted the CSV into Google Docs spreadsheets, which is where the work (and pain) really started. The pain involved:

1. adding a column dividing the time by the number of loops
2. adding another sheet that averaged the numbers in different runs to create the table above
3. generating the graph with the correct labels and headers

Step #1 should be easy—I probably should have done that myself in the Dart benchmarking code. That I did not are the hazards of plowing ahead in a solution without thinking.

Step #2 was particularly hard because I had to manually edit the range of cells to be averaged and the cell that identified the number of loops. Copying and pasting always got the wrong column and or row. In a 5×3 table, that is 15 edits of 3 values. There is no way I am doing that again by hand.

Step #3 may very well need to remain in Google spreadsheets. I know of no Dart packages that can manipulate Google Sheets (really?) nor are there any Dart packages that I can find that can manually build pretty graphs in PNG form. I am more than happy to be corrected on either point!

Anyhow, let's see what I can do about steps #1 and #2. Ugh... strike that. Let's see what I can do about the “easy” #1. In theory, #1 ought to be easy—all I need to do is get the loopSize from my benchmark's main() entry point down to the benchmark class:

main (List args) {
  // Determine loopSize from command-line args...

  _setup();
  for (var i=0; i<<numberOfRuns; i++) {
    VisitorBenchmark.main();
  }
}

If VisitorBenchmark knows the loopSize it can emit a score that includes the actual run time of the benchmark divided by loopSize:

class LoopScorer implements ScoreEmitter {
  const LoopScorer(this.numLoops);

  void emit(String testName, double value) {
    print(
      '$testName (RunTime in µs), '
      '${value.toStringAsPrecision(4)}, '
      '${numLoops}, '
      '${(value/numLoops).toStringAsPrecision(4)}'
    );
  }
}

Ah, my old friend constant constructors. Wait, not “friend” in this case—the loopSize is coming in from the command-line so there is no way that it will ever be a compile time constant. So there is no way to create a constant scorer.

So I do something bad instead: storing the score in a global and make the loop responsible for printing the results:

double lastScore;
class GloballyPersistingScoreEmitter implements ScoreEmitter {
  const GloballyPersistingScoreEmitter();
  void emit(String testName, double value) {
    lastScore = value;
  }
}

The benchmark then needs to use this scorer:

class VisitorBenchmark extends BenchmarkBase {
  const VisitorBenchmark() :
    super(NAME, emitter: const GloballyPersistingScoreEmitter());
  // ...
}

And finally, my loop reports the results:

main (List args) {
  // ...
  for (var i=0; i<numberOfRuns; i++) {
    VisitorBenchmark.main();
    print(
      '${NAME} (RunTime in µs), '
      '${lastScore.toStringAsPrecision(4)}, '
      '${loopSize}, '
      '${(lastScore/loopSize).toStringAsPrecision(4)}'
    );
  }
}

The results are a nice set of CSV values for inclusion in a spreadsheet:

$ ./tool/benchmark.dart
Classic Visitor Pattern (RunTime in µs), 1205, 10, 120.5
Classic Visitor Pattern (RunTime in µs), 1213, 10, 121.3
Classic Visitor Pattern (RunTime in µs), 1192, 10, 119.2

I can understand why benchmarks rely on compile-time constants like the benchmarker and scorer. No matter how many times I create a new instance, no new memory is consumed. In other words, the benchmark harness will not be responsible for triggering garbage collection. At the same time, it sure makes reporting anything more than the simplest information a pain.

Update: I do not need the scoring emitter after all. I can get away with returning the results of measure() directly from main() in my benchmark class:

class VisitorBenchmark extends BenchmarkBase {
  const VisitorBenchmark(): super(NAME);
  static double main()=> new VisitorBenchmark().measure();
  // ...
}

Since I am no longer calling the benchmarker's report() method, the score emitter is not invoked. The script's main entry point can then report to its heart's content using this return value:

  // ...
  for (var i=0; i<numberOfRuns; i++) {
    double score = VisitorBenchmark.main();
    print(
      '${NAME} (RunTime in µs), '
      '${score.toStringAsPrecision(4)}, '
      '${loopSize}, '
      '${(score/loopSize).toStringAsPrecision(4)}'
    );
  }
  // ...

And no global values.


Day #123

‹prev | My Chain | next›

Benchmarking at Different Run Length

It seems that my benchmarks may be hitting a garbage collection limit somewhere along the way. Or something.

I continue to benchmark three (slightly) different implementations of the Visitor Pattern in Dart. The actual goal is reasonable assurance that I am suggesting the most performant version of each pattern in the forthcoming Design Patterns in Dart. Toward that end, I am seeking out as many considerations involved in benchmarking patterns as possible (and I have found a number). At this point, the actual numbers are not as important as the process. Still, the numbers do suggest considerations of which I need to be aware.

The source code for this is located in the public facing code repository for the book.

I have noted that the time-per-run seems dependent on the number of loops used in the benchmark. Normally, the benchmark_harness package will run as many loops as necessary to fill a 2 second run. In order to get the numbers to be relatively stable between runs, I have been experimenting with increasing the number of loops in the benchmark. The results seem relatively consistent for limited numbers of loops in my benchmark code:

class VisitorBenchmark extends BenchmarkBase {
  // ...
  void run() {
    for (var i=0; i<10; i++) {
      visitor.totalPrice = 0.0;
      nodes.accept(visitor);
    }
  }
}

But, if I change the comparison from 10 to 1,000 to 100,000, then strange things happen to my numbers.

To test this out in detail, I add command line options to my benchmarks (using the nice args Dart package), write a shell script to exercise them:

#!/bin/sh

for X in 10 100 1000 10000 100000
do
    echo ''
    echo '=='
    echo "Loop size: $X"
    ./tool/benchmark.dart --loop-size=$X
    echo '--'
    ./tool/benchmark_single_dispatch_iteration.dart --loop-size=$X
    echo '--'
    ./tool/benchmark_visitor_traverse.dart --loop-size=$X
done

What I find is (numbers are microseconds for a single run):

Loop Size	Classic	Nodes Traverse (single dispatch)	Visitor Traverses
10	131.6	122.7	121.4
100	125.9	113.6	120.15
1000	123.8	122.8	120.65
10000	157.0	153.25	120.45
100000	158.05	154.65	121.05

Or, in graphical form:



I am unsure if that is really garbage collection, but something reliably affects the two implementations in which the node structure is responsible for traversing itself. And somehow making the visitor responsible for traversing the node structure (even with double dispatching) is not affected.

It is worth noting that the last two loop sizes push the benchmark run to and past the 2 second built-in lower limit of benchmark_harness. This may be a coincidence, especially since this does not seem to affect all three implementations.


Day #122

‹prev | My Chain | next›

Long vs Short Benchmarks (also, I'm a true idiot)

For the second day in a row, I have to come clean on a dumb mistake. Benchmarks have a particular knack for doing me in, it would seem. And, as hard as I might try to rationalize the numbers that do not fit my world view, eventually the numbers get me. Which is why I like them so darn much.

This time around, it was Lasse Reichstein Holst Nielsen who pointed out a flaw in my numbers. Specifically, my exponentiation. While mucking with the number of times that my benchmarks get run, I tried one million times, or 1e+6. Only that is not what I put in my code:

class VisitorBenchmark extends BenchmarkBase {
  // ...
  void run() {
    for (var i=0; i<10^6; i++) {
      visitor.totalPrice = 0.0;
      nodes.accept(visitor);
    }
  }
}

As Lasse was kind enough to point out, the hat operator in Dart is “bitwise or.” So I was combining the bits in 1010 and 0110, giving me 1110… or 12. That's just slightly less than the ONE MILLION I was going for... Speaking of which, I was wondering why increasing that number to 10^20 didn't bring things to a grinding halt. Generally, running a loop 30 times does not do that. Sigh.

I should have noticed that the numbers did not line up, but in my defense, benchmark_harness ensures that the code being executed runs for at least 2 seconds. It will run the code a thousand or a billion times if needed to ensure that the code is executed for that 2 seconds. So I assumed that the lack of significant increase was due to fewer iterations needed.

Yup… I assumed.

Anyhow, I think this is the last of my blinders involved in this bit of benchmarking, which tries different implementations of the Visitor Pattern for eventual use in Design Patterns in Dart. Since I had already gotten useful data from the 12 iteration approach to benchmarking, I had even planned on moving on to other territory tonight.

And then I thought, “what happens if I do run the code ONE MILLION times?” Well, the answer is that it takes too long for me to wait. So instead, I try ten thousand for each of my three implementation benchmarks. The “classic” implementation that I will likely use in the book gets a benchmark like:

class VisitorBenchmark extends BenchmarkBase {
  const VisitorBenchmark() :
    super(
      "Classic Visitor Pattern",
      emitter: const ProperPrecisionScoreEmitter()
    );

  static void main() { new VisitorBenchmark().report(); }

  void run() {
    for (var i=0; i<1e+5; i++) {
      visitor.totalPrice = 0.0;
      nodes.accept(visitor);
    }
  }
}

This results in:

$ ./tool/benchmark.dart; \
    echo '--'; \
    ./tool/benchmark_single_dispatch_iteration.dart; \
    echo '--'; \
    ./tool/benchmark_visitor_traverse.dart
Classic Visitor Pattern (RunTime): 1.444e+7 µs.
Classic Visitor Pattern (RunTime): 1.447e+7 µs.
Classic Visitor Pattern (RunTime): 1.449e+7 µs.
--
Nodes iterate w/ single dispatch (RunTime): 1.509e+7 µs.
Nodes iterate w/ single dispatch (RunTime): 1.507e+7 µs.
Nodes iterate w/ single dispatch (RunTime): 1.509e+7 µs.
--
Visitor Traverses (RunTime): 1.121e+7 µs.
Visitor Traverses (RunTime): 1.113e+7 µs.
Visitor Traverses (RunTime): 1.121e+7 µs.

What is interesting about these numbers is that they are almost the complete opposite of what I found last night. In this case, making the Visitor object responsible for traversing the data structure is the clear winner. Also as interesting is that hand-optimizing the code with a single-dispatch call is the loser. Last night, with only 12 stinking runs, I found:

/tool/benchmark.dart; \
    echo '--'; \
    ./tool/benchmark_single_dispatch_iteration.dart; \
    echo '--'; \
    ./tool/benchmark_visitor_traverse.dart
Classic Visitor Pattern (RunTime): 1176 µs.
Classic Visitor Pattern (RunTime): 1167 µs.
Classic Visitor Pattern (RunTime): 1136 µs.
--
Nodes iterate w/ single dispatch (RunTime): 1097 µs.
Nodes iterate w/ single dispatch (RunTime): 1074 µs.
Nodes iterate w/ single dispatch (RunTime): 1078 µs.
--
Visitor Traverses (RunTime): 1179 µs.
Visitor Traverses (RunTime): 1142 µs.
Visitor Traverses (RunTime): 1118 µs.

Obviously the numbers are much smaller, but the winner for smaller sample sizes is the single dispatch approach. These were not just 12 runs and that is it. The default benchmark_harness implementation runs the benchmark code 10 times and will do so for at least 2 seconds. There are even a few warm-up runs for good measure. In other words, those numbers are legitimate benchmarks.

In terms of what to use in the book, I am not quite sure what to make of this. Clearly, the longer that code is executed (10+ seconds vs 2 seconds) gives the Dart VM more time to optimize calls. I do not have a good explanation for why making the visitor responsible for traversing the node structure wins—and maybe I do not need one.

My takeaway is that it would behoove me to investigate alternate approaches for each pattern and to include discussions for limited use (~1000 calls) vs heavy usage (10k+ calls).


Day #121

‹prev | My Chain | next›

Blurry Benchmarks

tl;dr You may regret reading this post. I am grateful that I wrote it because I wound up correctly a major problem in my thinking because of a dumb mistake, but it was a really dumb mistake....

At the risk of overdoing my benchmark exploration for Design Patterns in Dart, there is one other facet of them that I would like to make sure I understand.

After a bit of code reorganization last night, I found that my three approaches to the Visitor Pattern broken down like:

Classic Visitor Pattern (RunTime): 1374 µs.
--
Nodes iterate w/ single dispatch (RunTime): 1290 µs.
--
Visitor Traverses (RunTime): 1362 µs.

This more or less breaks down like I expected from the outset. There is a slight win for the second approach, which exploits some knowledge of the structure being visited in order to invoke a collection with single dispatch.

What strikes me as odd is that, prior to reorganizing the file locations, I was seeing numbers like:

Classic Visitor Pattern (RunTime): 1345 us.
--
Nodes iterate w/ single dispatch (RunTime): 1344 us.
--
Visitor Traverses(RunTime): 1411 us.

Only the location of the code changed. Not of the actual code changed—well except for one thing...

I have settled on laying out the code for the public facing book repository like this:

lib
├── inventory.dart
├── visitor.dart
└── alt
    ├── single_dispatch_iteration
    │   ├── inventory.dart
    │   └── visitor.dart
    └── visitor_traverse
        ├── inventory.dart
        └── visitor.dart

The preferred solution (either because of suitability or performance) will reside at the top the package's lib directory. Alternate approaches will reside in lib/alt. Before this file reorganization, all implementations resided in the top level of the lib directory. And some shared code.

I am fairly sure that the sharing of the code inadvertently caused the slowness in the pre-file-reorg benchmarks. I would actually be somewhat surprised if that is the case because it would be an issue caused by types which I thought Dart ignored. Anyway, enough speculation.

Previously, the “classic” visitor pattern implementation (e.g. with double dispatch) and the single-dispatch code shared visitor.dart. Once I re-organized files, they are still identical copies:

$ diff -s lib/visitor.dart lib/alt/single_dispatch_iteration/visitor.dart
Files lib/visitor.dart and lib/alt/single_dispatch_iteration/visitor.dart are identical

But previously they were the same file and both benchmarks loaded the same file. To reproduce the prior situation, I change the top-level benchmark to use the single-dispatch's visitor:

#!/usr/bin/env dart

import 'package:benchmark_harness/benchmark_harness.dart';

import 'package:visitor_code/alt/single_dispatch_iteration/visitor.dart';
import 'package:visitor_code/inventory.dart';

main () {
  _setup();

  VisitorBenchmark.main();
  VisitorBenchmark.main();
  VisitorBenchmark.main();
}
//  ...

When I run the benchmarks, however, I find no change. The single dispatch approach still runs the quickest and the double dispatch implementation still runs slightly slower. So it seems like my supposition about types was wrong after all. I had begun to suspect that importing the single dispatch's visitor was in turn pulling in the single dispatch node structure (where the single dispatch actually resides). But that is not the case.

So why did I get nearly identical single and double benchmark numbers? Well, it turns out that the explanation is much simpler. I luckily saved my work in git, so I can git checkout the benchmarks in question:

$ git checkout HEAD~1

The previous double dispatch benchmark looked like:

#!/usr/bin/env dart

import 'package:benchmark_harness/benchmark_harness.dart';

import 'package:visitor_code/visitor.dart';

main () {
  _setup();

  NodesDoubleBenchmark.main();
  NodesDoubleBenchmark.main();
  NodesDoubleBenchmark.main();
}
// ...

So I was relying on visitor.dart to export the relevant inventory. For double dispatch, this should have been the double-dispatching inventory library, but... it was the single dispatching code:

library visitor;

import 'inventory_single_dispatch.dart';
export 'inventory_single_dispatch.dart';
// ...

So of course the two benchmarks were identical—they were explicitly running the same damn code!

Ugh.

I am so ashamed. It turns out that select is not broken. I had readily built up a ridiculous explanation in my head for why two different approaches resulted in the same results. It turns out that the results were the same because I used the same approach both times.

I can take some measure of solace in the fact that I took the time to correct myself. I almost did not investigate the discrepancy in numbers tonight (I was seriously that certain that my rationalization was valid). Luckily I did investigate. And even though I once again proved that I am an idiot, hopefully I am a slightly more knowledgeable idiot.

More importantly, I am far more convinced that I need to organize my implementations in the lib/alt scheme. Before tonight, I thought keeping everything in the top-level was a little messy, but hardly cause for worry. Had I not attempted to shove everything into the top-level as I had, I never would have gotten myself into this situation.

Now if you'll excuse me, I need to go flog myself.



Day #120

‹prev | My Chain | next›

Crazy Warm Dart Benchmarks

After last night, I am happy to have a new benchmark reporter that does not report 16 digits of precision when times vary after 3 digits:

$ ./tool/benchmark.dart; \
      echo '--'; \
        ./tool/benchmark_single_dispatch_iteration.dart; \
      echo '--'; \
        ./tool/benchmark_visitor_traverse.dart
Classic Visitor Pattern (RunTime): 1409 µs.
Classic Visitor Pattern (RunTime): 1375 µs.
Classic Visitor Pattern (RunTime): 1374 µs.
--
Nodes iterate w/ single dispatch (RunTime): 1311 µs.
Nodes iterate w/ single dispatch (RunTime): 1276 µs.
Nodes iterate w/ single dispatch (RunTime): 1290 µs.
--
Visitor Traverses (RunTime): 1388 µs.
Visitor Traverses (RunTime): 1350 µs.
Visitor Traverses (RunTime): 1362 µs.

But I am still not satisfied that I have a solid handle on benchmarking different approaches to patterns for Design Patterns in Dart.

I can live with small deviations in reported times, but the numbers that I get now indicate that the “warm-up” time for my benchmarks is woefully insufficient. I currently have three variations of the Visitor Pattern that I am benchmarking. For each of the three, I run my benchmarks three times. And, for every group, the first run takes the longest while the second two runs are very close to each other.

The idea of a warm-up run is not some brilliant insight on my part. It is baked right into Dart's benchmark_harness package:

part of benchmark_harness;

class BenchmarkBase {
  // ...
  // Runs a short version of the benchmark. By default invokes [run] once.
  void warmup() {
    run();
  }
  // ...
}

One might be tempted to think the problem obvious: only running the benchmark run() method once is woefully inadequate. Except that the run() method in each of my three benchmark variations runs the actual code ONE MILLION times:

class VisitorBenchmark extends BenchmarkBase {
  const VisitorBenchmark() :
    super(
      "Classic Visitor Pattern",
      emitter: const ProperPrecisionScoreEmitter()
    );

  static void main() { new VisitorBenchmark().report(); }

  void run() {
    for (var i=0; i<10^6; i++) {
      visitor.totalPrice = 0.0;
      nodes.accept(visitor);
    }
  }
}

OK. OK. It's more fun to say ONE MILLION than it is effective. But what might be effective?

The warmup() method of BenchmarkBase seems like it might be fit my needs:

class VisitorBenchmark extends BenchmarkBase {
  const VisitorBenchmark() :
    super(
      "Classic Visitor Pattern",
      emitter: const ProperPrecisionScoreEmitter()
    );
  static void main() { new VisitorBenchmark().report(); }

  void warmup() {
    for (var i=0; i<10^20; i++) {
     visitor.totalPrice = 0.0;
      nodes.accept(visitor);
    }
  }

  void run() { /* ... */  }
}

But even at 10^20 iterations, this has little effect (the stinking Visitor Pattern is just too darn efficient).

I need the warmup to run for even longer. For that, I think I'll override BenchmarkBase's measure() method:

class VisitorBenchmark extends BenchmarkBase {
  const VisitorBenchmark() :
    super(
      "Classic Visitor Pattern",
      emitter: const ProperPrecisionScoreEmitter()
    );
  // ...
  double measure() {
    setup();
    // Warmup for at least 100ms. Discard result.
    measureFor(() { this.warmup(); }, 100);
    // Run the benchmark for at least 2000ms.
    double result = measureFor(() { this.exercise(); }, 2*1000);
    teardown();
    return result;
  }
}

That will not work as-is because the measureFor() method invoked by measure() is a static method of BenchmarkBase:

$ ./tool/benchmark.dart
Unhandled exception:
Class 'VisitorBenchmark' has no instance method 'measureFor'.

NoSuchMethodError: method not found: 'measureFor'
Receiver: Instance of 'VisitorBenchmark'
Arguments: [Closure: () => dynamic, 10000]
#0      Object.noSuchMethod (dart:core-patch/object_patch.dart:45)
#1      VisitorBenchmark.measure (file:///home/chris/repos/design-patterns-in-dart/visitor/tool/benchmark.dart:44:15)
#2      BenchmarkBase.report (package:benchmark_harness/src/benchmark_base.dart:65:31)
#3      VisitorBenchmark.main (file:///home/chris/repos/design-patterns-in-dart/visitor/tool/benchmark.dart:35:53)
#4      main (file:///home/chris/repos/design-patterns-in-dart/visitor/tool/benchmark.dart:10:24)

So I have to manually resolve it:

class VisitorBenchmark extends BenchmarkBase {
  const VisitorBenchmark() :
    super(
      "Classic Visitor Pattern",
      emitter: const ProperPrecisionScoreEmitter()
    );
  // ...
  double measure() {
    setup();
    BenchmarkBase.measureFor(() { this.warmup(); }, 10*1000);
    // Run the benchmark for at least 2000ms.
    double result = BenchmarkBase.measureFor(() { this.exercise(); }, 2*1000);
    teardown();
    return result;
  }
}

While I am at it, I call BenchmarkBase.measureFor() for 10 seconds worth of warm-up instead of the base 100ms. With that, I get more consistent number for each of my benchmark runs:

$ ./tool/benchmark.dart
Classic Visitor Pattern (RunTime): 204.5 µs.
Classic Visitor Pattern (RunTime): 203.7 µs.
Classic Visitor Pattern (RunTime): 203.7 µs.
$ ./tool/benchmark.dart
Classic Visitor Pattern (RunTime): 201.8 µs.
Classic Visitor Pattern (RunTime): 203.2 µs.
Classic Visitor Pattern (RunTime): 201.4 µs.

That is all well and good, but it may be overkill. Even with the original numbers, the comparison between the different approaches would still be valid for the first run. Even though the numbers are elevated in the first run, they are consistently elevated. All that I need to determine which, if any, approaches should be discounted for performance reasons is a consistent comparison. And, for the different approaches to Visitor, the difference is so small that any would work just as well as the others.

Still, it was good to dig into Dart's benchmark harness some more. I have a better handle on how it works—and how I might tailor it should I need to.


Day #119

‹prev | My Chain | next›

Precision vs Accuracy in Benchmarking

I continue to explore benchmarking design patterns for Design Patterns in Dart. I am still in the preliminary stages of research for the book so the actual benchmarks are not as important as how I want to benchmark. The simple answer is to use benchmark_harness—the official benchmark harness for Dart. As I have found over the past couple of days, there is more involved than simply using it.

I have already determined that it is best to run implementation comparisons in separate files. Further investigation by Vyacheslav Egorov (aka @mraleph) suggests that I need to run the benchmark code longer than I currently am:

@eee_c I looked a bit at it today, but there are some seriously confusing performance flakes there. I recommend making run() longer running

— Vyacheslav Egorov (@mraleph) July 10, 2014

@eee_c e.g. by adding a loop in run() --- I can't explain flakes though they come and go when I try to catch them

— Vyacheslav Egorov (@mraleph) July 10, 2014

@eee_c everything stabilizes with longer running run()

— Vyacheslav Egorov (@mraleph) July 10, 2014

Taking Vyacheslav up on his advice, I work through each of my three Visitor Pattern implementations (in the visitor/tool directory of the Design Patterns public repository). To each, I add a loop to the run() method of the harness:

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

  void run() {
    for (var i=0; i<10^6; i++) {
      visitor.totalPrice = 0.0;
      nodes.accept(visitor);
    }
}

In each of the three benchmarks, I loop over the visit a million times. For good measure, I run each benchmark report 3 times.

When I run the code, I find:

$ ./tool/benchmark_for_single_dispatch.dart; \
  echo "--"; \
  ./tool/benchmark_for_double_dispatch.dart; \
  echo "--"; \
  ./tool/benchmark_traversing_visitor.dart 
Nodes iterate w/ single dispatch (RunTime): 1373.6263736263736 us.
Nodes iterate w/ single dispatch (RunTime): 1331.5579227696405 us.
Nodes iterate w/ single dispatch (RunTime): 1344.0860215053763 us.
--
Nodes iterate w/ double dispatch (RunTime): 1381.9060773480662 us.
Nodes iterate w/ double dispatch (RunTime): 1322.7513227513227 us.
Nodes iterate w/ double dispatch (RunTime): 1345.8950201884254 us.
--
Visitor Traverses(RunTime): 1452.4328249818445 us.
Visitor Traverses(RunTime): 1417.4344436569809 us.
Visitor Traverses(RunTime): 1411.4326040931546 us

I notice two things here. First, the difference between single and double dispatching is negligible. Also, the default reporter has a precision vs. accuracy.

When the objects structure is responsible for traversing itself, double dispatching surprisingly has no effect. I can only speculate that the VM recognizes the double dispatch target method and is able to optimize calls to it. Oddly (and unlike last night's non-looping benchmark), making the visitor responsible for traversing object structure is the loser.

Since this is an exercise more focused on how to benchmark than the actual results, I will let those slide for now. Besides, I am far more bothered by benchmark_harness' incredible precision (13 decimal places!) when the runs vary by 40µs. The reported precision implies an accuracy that is simply not possible.

If the numbers are varying at the third significant digit, it makes no sense to report more than 4 significant digits. This means that I need a new benchmark reporter. The benchmark_harness package defines a simple interface for its “emitters”:

abstract class ScoreEmitter {
  void emit(String testName, double value);
}

I implement this locally as ProperPrecisionScoreEmitter:

class ProperPrecisionScoreEmitter implements ScoreEmitter {
  const ProperPrecisionScoreEmitter();

  void emit(String testName, double value) {
    print("$testName (RunTime): ${value.toStringAsPrecision(4)} µs.");
  }
}

The key difference between the default implementation and mine is that I explicitly request a sane precision with double's toStringAsPrecision() method.

To use this sane precision emitter, I update my redirecting constructor in the benchmark class. The constructor in the BenchmarkBase accepts an optional named emitter:

class NodesDoubleBenchmark extends BenchmarkBase {
  const NodesDoubleBenchmark() :
    super(
      "Nodes iterate w/ double dispatch",
      emitter: const ProperPrecisionScoreEmitter()
    );
  static void main() { new NodesDoubleBenchmark().report(); }

  void run() {
    // run the benchmarked code here ...
  }
}

After doing that for each of my implementation benchmarks, I have:

$ ./tool/benchmark_for_single_dispatch.dart; \
  echo "--"; \
  ./tool/benchmark_for_double_dispatch.dart; \
  echo "--"; \
  ./tool/benchmark_traversing_visitor.dart 
Nodes iterate w/ single dispatch (RunTime): 1371 µs.
Nodes iterate w/ single dispatch (RunTime): 1322 µs.
Nodes iterate w/ single dispatch (RunTime): 1328 µs.
--
Nodes iterate w/ double dispatch (RunTime): 1377 µs.
Nodes iterate w/ double dispatch (RunTime): 1324 µs.
Nodes iterate w/ double dispatch (RunTime): 1316 µs.
--
Visitor Traverses (RunTime): 1476 µs.
Visitor Traverses (RunTime): 1417 µs.
Visitor Traverses (RunTime): 1445 µs.

Ahhh. Much better.

The deviation between runs remains an open question. Certainly other activity on my machine plays some part in it, but it would be nice if the numbers could have a little more precision. I will investigate the actual benchmark code tomorrow to see if this is possible.


Day #118

‹prev | My Chain | next›

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›