Microbenchmark for ADTs in JavaScript

ADTs.js

var $benchmark = require("./benchmark");
var group = $benchmark.group;
var benchmark = $benchmark.benchmark;
var runBenchmarks = $benchmark.runBenchmarks;


function random(i) {
  return Math.floor(Math.random() * i);
}

function check(index, value) {
  if (index === 0) {
    return value === "foo1";

  } else if (index === 1) {
    return value === "bar234";

  } else if (index === 2) {
    return value === "qux56";

  } else {
    return false;
  }
}

function check_toString(index, value) {
  if (index === 0) {
    return value === "Foo(1)";

  } else if (index === 1) {
    return value === "Bar(2, 3, 4)";

  } else if (index === 2) {
    return value === "Qux(5, 6)";

  } else {
    return false;
  }
}


function Classes_Enum() {}

Classes_Enum.prototype.toString = function () {
  switch (this.__tag__ | 0) {
  case 0 | 0:
    return "Foo(" + this.a + ")";
  case 1 | 0:
    return "Bar(" + this.a + ", " + this.b + ", " + this.c + ")";
  default:
    return "Qux(" + this.a + ", " + this.b + ")";
  }
};

Classes_Enum.prototype.metadata = true;

var Enum = new Classes_Enum();


function Foo(a) {
  this.__tag__ = 0 | 0;
  this.a = a;
}

Foo.prototype = new Classes_Enum();
Foo.prototype.constructor = Foo;

Foo.prototype.print = function () {
  return "foo" + this.a;
};

var Foo_prototype = Foo.prototype;


function Bar(a, b, c) {
  this.__tag__ = 1 | 0;
  this.a = a;
  this.b = b;
  this.c = c;
}

Bar.prototype = new Classes_Enum();
Bar.prototype.constructor = Bar;

Bar.prototype.print = function () {
  return "bar" + this.a + this.b + this.c;
};

var Bar_prototype = Bar.prototype;


function Qux(a, b) {
  this.__tag__ = 2 | 0;
  this.a = a;
  this.b = b;
}

Qux.prototype = new Classes_Enum();
Qux.prototype.constructor = Qux;

Qux.prototype.print = function () {
  return "qux" + this.a + this.b;
};

var Qux_prototype = Qux.prototype;


function print_classes_isPrototypeOf(a) {
  if (Foo.prototype.isPrototypeOf(a)) {
    return "foo" + a.a;
  } else if (Bar.prototype.isPrototypeOf(a)) {
    return "bar" + a.a + a.b + a.c;
  } else {
    return "qux" + a.a + a.b;
  }
}

function print_classes_isPrototypeOf_fast(a) {
  if (Foo_prototype.isPrototypeOf(a)) {
    return "foo" + a.a;
  } else if (Bar_prototype.isPrototypeOf(a)) {
    return "bar" + a.a + a.b + a.c;
  } else {
    return "qux" + a.a + a.b;
  }
}

function print_classes_proto(a) {
  switch (a.__proto__) {
  case Foo.prototype:
    return "foo" + a.a;
  case Bar.prototype:
    return "bar" + a.a + a.b + a.c;
  default:
    return "qux" + a.a + a.b;
  }
}

function print_classes_proto_fast(a) {
  switch (a.__proto__) {
  case Foo_prototype:
    return "foo" + a.a;
  case Bar_prototype:
    return "bar" + a.a + a.b + a.c;
  default:
    return "qux" + a.a + a.b;
  }
}

function print_classes_constructor(a) {
  switch (a.constructor) {
  case Foo:
    return "foo" + a.a;
  case Bar:
    return "bar" + a.a + a.b + a.c;
  default:
    return "qux" + a.a + a.b;
  }
}

function print_classes_getPrototypeOf(a) {
  switch (Object.getPrototypeOf(a)) {
  case Foo.prototype:
    return "foo" + a.a;
  case Bar.prototype:
    return "bar" + a.a + a.b + a.c;
  default:
    return "qux" + a.a + a.b;
  }
}

function print_classes_getPrototypeOf_fast(a) {
  switch (Object.getPrototypeOf(a)) {
  case Foo_prototype:
    return "foo" + a.a;
  case Bar_prototype:
    return "bar" + a.a + a.b + a.c;
  default:
    return "qux" + a.a + a.b;
  }
}

function print_classes_switch(a) {
  switch (a.__tag__ | 0) {
  case 0 | 0:
    return "foo" + a.a;
  case 1 | 0:
    return "bar" + a.a + a.b + a.c;
  default:
    return "qux" + a.a + a.b;
  }
}

function print_classes_if(a) {
  var tag = a.__tag__ | 0;
  if (tag === 0 | 0) {
    return "foo" + a.a;
  } else if (tag === 1 | 0) {
    return "bar" + a.a + a.b + a.c;
  } else {
    return "qux" + a.a + a.b;
  }
}

function print_classes_instanceof(a) {
  if (a instanceof Foo) {
    return "foo" + a.a;

  } else if (a instanceof Bar) {
    return "bar" + a.a + a.b + a.c;

  } else {
    return "qux" + a.a + a.b;
  }
}


function toString_tag() {
  switch (this.__tag__ | 0) {
  case 0 | 0:
    return "Foo(" + this.a + ")";
  case 1 | 0:
    return "Bar(" + this.a + ", " + this.b + ", " + this.c + ")";
  default:
    return "Qux(" + this.a + ", " + this.b + ")";
  }
}

function print_tag_switch(a) {
  switch (a.__tag__ | 0) {
  case 0 | 0:
    return "foo" + a.a;
  case 1 | 0:
    return "bar" + a.a + a.b + a.c;
  default:
    return "qux" + a.a + a.b;
  }
}

function print_tag_if(a) {
  var tag = a.__tag__ | 0;
  if (tag === 0 | 0) {
    return "foo" + a.a;
  } else if (tag === 1 | 0) {
    return "bar" + a.a + a.b + a.c;
  } else {
    return "qux" + a.a + a.b;
  }
}

var print_tag_vtables = [
  function (a) {
    return "foo" + a.a;
  },
  function (a) {
    return "bar" + a.a + a.b + a.c;
  },
  function (a) {
    return "qux" + a.a + a.b;
  }
];

function print_tag_vtable(a) {
  return print_tag_vtables[a.__tag__ | 0](a);
}


function toString_array() {
  switch (this[1] | 0) {
  case 0 | 0:
    return "Foo(" + this[2] + ")";
  case 1 | 0:
    return "Bar(" + this[2] + ", " + this[3] + ", " + this[4] + ")";
  default:
    return "Qux(" + this[2] + ", " + this[3] + ")";
  }
}

function print_array_switch(a) {
  switch (a[1] | 0) {
  case 0 | 0:
    return "foo" + a[2];
  case 1 | 0:
    return "bar" + a[2] + a[3] + a[4];
  default:
    return "qux" + a[2] + a[3];
  }
}

function print_array_if(a) {
  var tag = a[1] | 0;
  if (tag === 0 | 0) {
    return "foo" + a[2];
  } else if (tag === 1 | 0) {
    return "bar" + a[2] + a[3] + a[4];
  } else {
    return "qux" + a[2] + a[3];
  }
}

var print_array_vtables = [
  function (a) {
    return "foo" + a[2];
  },
  function (a) {
    return "bar" + a[2] + a[3] + a[4];
  },
  function (a) {
    return "qux" + a[2] + a[3];
  }
];

function print_array_vtable(a) {
  return print_array_vtables[a[1] | 0](a);
}


function toString_object0() {
  return "Foo(" + this.b + ")";
}

function toString_object1() {
  return "Bar(" + this.b + ", " + this.c + ", " + this.d + ")";
}

function toString_object2() {
  return "Qux(" + this.b + ", " + this.c + ")";
}

function print0(a) {
  return "foo" + a.b;
}

function print1(a) {
  return "bar" + a.b + a.c + a.d;
}

function print2(a) {
  return "qux" + a.b + a.c;
}

function print_object(a) {
  return a.a(a);
}


var create_tag = [
  function () {
    return { toString: toString_tag, __enum__: Enum, __tag__: 0 | 0, a: "1" };
  },
  function () {
    return { toString: toString_tag, __enum__: Enum, __tag__: 1 | 0, a: "2", b: "3", c: "4" };
  },
  function () {
    return { toString: toString_tag, __enum__: Enum, __tag__: 2 | 0, a: "5", b: "6" };
  }
];

var create_array = [
  function () {
    var x = [Enum, 0 | 0, "1"];
    x.toString = toString_array;
    return x;
  },
  function () {
    var x = [Enum, 1 | 0, "2", "3", "4"];
    x.toString = toString_array;
    return x;
  },
  function () {
    var x = [Enum, 2 | 0, "5", "6"];
    x.toString = toString_array;
    return x;
  }
];

var create_classes = [
  function () {
    return new Foo("1");
  },
  function () {
    return new Bar("2", "3", "4");
  },
  function () {
    return new Qux("5", "6");
  }
];

var create_objects = [
  function () {
    return { toString: toString_object0, __enum__: Enum, a: print0, b: "1" };
  },
  function () {
    return { toString: toString_object1, __enum__: Enum, a: print1, b: "2", c: "3", d: "4" };
  },
  function () {
    return { toString: toString_object2, __enum__: Enum, a: print2, b: "5", c: "6" };
  }
];


var tags = [
  create_tag[0](),
  create_tag[1](),
  create_tag[2](),
];

var arrays = [
  create_array[0](),
  create_array[1](),
  create_array[2]()
];

var classes = [
  create_classes[0](),
  create_classes[1](),
  create_classes[2]()
];

var objects = [
  create_objects[0](),
  create_objects[1](),
  create_objects[2]()
];


runBenchmarks([
  group("create", [
    benchmark("tag", function () {
      var index = random(create_tag.length);
      return !!create_tag[index]();
    }),

    benchmark("tag (inline)", function () {
      var index = random(create_tag.length);
      var value;

      if (index === 0) {
        value = { toString: toString_tag, __enum__: Enum, __tag__: 0 | 0, a: "1" };
      } else if (index === 1) {
        value = { toString: toString_tag, __enum__: Enum, __tag__: 1 | 0, a: "2", b: "3", c: "4" };
      } else if (index === 2) {
        value = { toString: toString_tag, __enum__: Enum, __tag__: 2 | 0, a: "5", b: "6" };
      }

      return !!value;
    }),

    benchmark("array", function () {
      var index = random(create_array.length);
      return !!create_array[index]();
    }),

    benchmark("array (inline)", function () {
      var index = random(create_array.length);
      var value;

      if (index === 0) {
        value = [Enum, 0 | 0, "1"];
        value.toString = toString_array;
      } else if (index === 1) {
        value = [Enum, 1 | 0, "2", "3", "4"];
        value.toString = toString_array;
      } else if (index === 2) {
        value = [Enum, 2 | 0, "5", "6"];
        value.toString = toString_array;
      }

      return !!value;
    }),

    benchmark("classes", function () {
      var index = random(create_classes.length);
      return !!create_classes[index]();
    }),

    benchmark("classes (inline)", function () {
      var index = random(create_classes.length);
      var value;

      if (index === 0) {
        value = new Foo("1");
      } else if (index === 1) {
        value = new Bar("2", "3", "4");
      } else if (index === 2) {
        value = new Qux("5", "6");
      }

      return !!value;
    }),

    benchmark("objects", function () {
      var index = random(create_objects.length);
      return !!create_objects[index]();
    }),

    benchmark("objects (inline)", function () {
      var index = random(create_objects.length);
      var value;

      if (index === 0) {
        value = { toString: toString_object0, __enum__: Enum, a: print0, b: "1" };
      } else if (index === 1) {
        value = { toString: toString_object1, __enum__: Enum, a: print1, b: "2", c: "3", d: "4" };
      } else if (index === 2) {
        value = { toString: toString_object2, __enum__: Enum, a: print2, b: "5", c: "6" };
      }

      return !!value;
    }),
  ]),

  group("metadata", [
    benchmark("tag", function () {
      var index = random(tags.length);
      return tags[index].__enum__.metadata === true;
    }),

    benchmark("array", function () {
      var index = random(arrays.length);
      return arrays[index][0].metadata === true;
    }),

    benchmark("classes", function () {
      var index = random(classes.length);
      return classes[index].metadata === true;
    }),

    benchmark("objects", function () {
      var index = random(objects.length);
      return objects[index].__enum__.metadata === true;
    }),
  ]),


  group("access", [
    benchmark("tag (switch)", function () {
      var index = random(tags.length);
      return check(index, print_tag_switch(tags[index]));
    }),

    benchmark("tag (if)", function () {
      var index = random(tags.length);
      return check(index, print_tag_if(tags[index]));
    }),

    benchmark("tag (vtable)", function () {
      var index = random(tags.length);
      return check(index, print_tag_vtable(tags[index]));
    }),

    benchmark("array (switch)", function () {
      var index = random(arrays.length);
      return check(index, print_array_switch(arrays[index]));
    }),

    benchmark("array (if)", function () {
      var index = random(arrays.length);
      return check(index, print_array_if(arrays[index]));
    }),

    benchmark("array (vtable)", function () {
      var index = random(arrays.length);
      return check(index, print_array_vtable(arrays[index]));
    }),

    benchmark("classes (switch)", function () {
      var index = random(classes.length);
      return check(index, print_classes_switch(classes[index]));
    }),

    benchmark("classes (if)", function () {
      var index = random(classes.length);
      return check(index, print_classes_if(classes[index]));
    }),

    benchmark("classes (isPrototypeOf)", function () {
      var index = random(classes.length);
      return check(index, print_classes_isPrototypeOf(classes[index]));
    }),

    benchmark("classes (isPrototypeOf fast)", function () {
      var index = random(classes.length);
      return check(index, print_classes_isPrototypeOf_fast(classes[index]));
    }),

    benchmark("classes (__proto__)", function () {
      var index = random(classes.length);
      return check(index, print_classes_proto(classes[index]));
    }),

    benchmark("classes (__proto__ fast)", function () {
      var index = random(classes.length);
      return check(index, print_classes_proto_fast(classes[index]));
    }),

    benchmark("classes (Object.getPrototypeOf)", function () {
      var index = random(classes.length);
      return check(index, print_classes_getPrototypeOf(classes[index]));
    }),

    benchmark("classes (Object.getPrototypeOf fast)", function () {
      var index = random(classes.length);
      return check(index, print_classes_getPrototypeOf_fast(classes[index]));
    }),

    benchmark("classes (constructor)", function () {
      var index = random(classes.length);
      return check(index, print_classes_constructor(classes[index]));
    }),

    benchmark("classes (method)", function () {
      var index = random(classes.length);
      return check(index, classes[index].print());
    }),

    benchmark("classes (instanceof)", function () {
      var index = random(classes.length);
      return check(index, print_classes_instanceof(classes[index]));
    }),

    benchmark("objects (method)", function () {
      var index = random(objects.length);
      return check(index, print_object(objects[index]));
    }),

    benchmark("objects (method inline)", function () {
      var index = random(objects.length);
      var x = objects[index];
      return check(index, x.a(x));
    }),
  ]),


  group("toString", [
    benchmark("tag", function () {
      var index = random(tags.length);
      return check_toString(index, "" + tags[index]);
    }),

    benchmark("array", function () {
      var index = random(arrays.length);
      return check_toString(index, "" + arrays[index]);
    }),

    benchmark("classes", function () {
      var index = random(classes.length);
      return check_toString(index, "" + classes[index]);
    }),

    benchmark("objects", function () {
      var index = random(objects.length);
      return check_toString(index, "" + objects[index]);
    }),
  ]),
]);

benchmark.js

var $readline = require("readline");


var groupSeparator = " -> ";

// TODO is this correct ?
function clear() {
  $readline.moveCursor(process.stdout, 0, -1);
  $readline.cursorTo(process.stdout, 0);
  $readline.clearScreenDown(process.stdout);
}


// Returns the difference in milliseconds
function getDiff(a) {
  var x = process.hrtime(a);
  return (x[0] * 1000) + (x[1] / 1000000);
}

function timeIterations(f, iterations) {
  var i = 0;
  var value;
  var diff;

  var start = process.hrtime();

  while (i < iterations) {
    value = f();

    if (!value) {
      throw new Error("Invalid");
    }

    ++i;

    diff = getDiff(start);
  }

  return {
    iterations: iterations,
    duration: diff,
    value: value
  };
}

function timeDuration(f, time) {
  var iterations = 0;
  var value;
  var diff;

  var start = process.hrtime();

  do {
    value = f();

    if (!value) {
      throw new Error("Invalid");
    }

    ++iterations;

    diff = getDiff(start);
  } while (diff < time);

  return {
    iterations: iterations,
    duration: diff,
    value: value
  };
}

function percent(x, top) {
  return ((1 - ((top - x) / top)) * 100).toFixed(5) + "%";
}

// http://stackoverflow.com/a/6274398/449477
function shuffle(array) {
  let counter = array.length;

  // While there are elements in the array
  while (counter > 0) {
    // Pick a random index
    let index = Math.floor(Math.random() * counter);

    // Decrease counter by 1
    counter--;

    // And swap the last element with it
    let temp = array[counter];
    array[counter] = array[index];
    array[index] = temp;
  }

  return array;
}

function hasKey(obj, key) {
  return {}.hasOwnProperty.call(obj, key);
}

function orderString(a, b) {
  if (a === b) {
    return 0;

  } else if (a < b) {
    return -1;

  } else {
    return 1;
  }
}

function orderNumber(a, b) {
  return a - b;
}

function orderReverse(a) {
  if (a === 0) {
    return 0;

  } else if (a < 0) {
    return 1;

  } else {
    return -1;
  }
}


exports.group = function group(s, a) {
  return {
    type: "group",
    name: s,
    benchmarks: a
  };
};

exports.benchmark = function benchmark(s, f) {
  return {
    type: "benchmark",
    name: s,
    run: f
  };
};

function processBenchmarks(out, groups, a) {
  if (a.length === 0) {
    throw new Error("Empty benchmarks");
  }

  a.forEach(function (x) {
    if (x.type === "group") {
      processBenchmarks(out, groups.concat([x.name]), x.benchmarks);

    } else if (x.type === "benchmark") {
      if (!x.run()) {
        throw new Error("Invalid");
      }

      out.push({
        groups: groups.join(groupSeparator),
        name: x.name,
        run: x.run
      });

    } else {
      throw new Error("Invalid type: " + x.type);
    }
  });
}

exports.runBenchmarks = function runBenchmarks(a) {
  var runners = [];
  var groups = {};

  processBenchmarks(runners, [], a);

  var progress = 0;
  var progressEnd = runners.length * (100 + 10000);

  function displayProgress() {
    console.log("Progress: " +
      percent(progress, progressEnd) +
      " (about " + ((progressEnd - progress) / 1000).toFixed(2) + " seconds left)");
  }

  displayProgress();

  // Run the benchmarks in a random order, to prevent warmup issues
  shuffle(runners);

  // Run all of the 100ms benchmarks
  runners.forEach(function (x) {
    var x100 = timeDuration(x.run, 100);

    if (!hasKey(groups, x.groups)) {
      groups[x.groups] = {};
    }

    if (!hasKey(groups[x.groups], x.name)) {
      groups[x.groups][x.name] = {
        name: x.name,
        sort: null,
        x100: (x100.iterations / x100.duration).toFixed(5) + "/ms",
        x10000: null
      };

      progress += 100;
      clear();
      displayProgress();

    } else {
      throw new Error("Benchmark defined twice: " + x.name);
    }
  });

  // Run the benchmarks in a random order, to prevent warmup issues
  shuffle(runners);

  // Run all of the 10000ms benchmarks
  runners.forEach(function (x) {
    var x10000 = timeDuration(x.run, 10000);

    var result = groups[x.groups][x.name];

    result.sort = (x10000.iterations / x10000.duration);
    result.x10000 = result.sort.toFixed(5) + "/ms";

    progress += 10000;
    clear();
    displayProgress();
  });

  clear();

  // Display the results
  Object.keys(groups).sort(orderString).forEach(function (key) {
    var obj = groups[key];

    var results = Object.keys(obj).map(function (key) {
      var x = obj[key];

      if (x.sort == null || x.x10000 == null) {
        throw new Error("Bug");
      }

      return x;
    });

    if (results.length === 0) {
      throw new Error("Empty benchmark");
    }

    results.sort(function (a, b) {
      return orderReverse(orderNumber(a.sort, b.sort));
    });

    var maxName = results.reduce(function (a, b) {
      return Math.max(a, b.name.length);
    }, 0);

    var maxIterations100 = results.reduce(function (a, b) {
      return Math.max(a, b.x100.length);
    }, 0);

    var maxIterations10000 = results.reduce(function (a, b) {
      return Math.max(a, b.x10000.length);
    }, 0);

    var first = results[0];

    console.log("");

    console.log(key + ":");

    results.forEach(function (x) {
      console.log("  " + x.name.padEnd(maxName, " ") + "  " +
                  x.x100.padStart(maxIterations100, " ") + "  " +
                  x.x10000.padStart(maxIterations10000, " ") + "  " +
                  // TODO don't hardcode the pad length
                  percent(x.sort, first.sort).padStart(10, " "));
    });
  });
};