Asymptotic performance test for d3-hierarchy's binary tree-map

treemapBinary-perf.js

var d3_hierarchy = require("d3-hierarchy");
 
var tile = d3_hierarchy.treemapBinary;

var M = 1000; // number of children
var N = 1000; // number of iterations for perf test

// Util: measure time
function timeit(name, f, N) {
  console.time(name);
  for(var i = 0; i < N; i++) {
    f();
  }
  console.timeEnd(name);
}

// Util: tree constructor
var make_tree = function () {
  return {
    value: 0,
    children: []
  };
}

// Util: add child to tree
var add_child = function(tree, val) {
  tree.value += val;
  tree.children.push({value: val});
}

// Tree 1: Even splits
var tree1 = make_tree();
for (var k = 0; k < M; k++) {
  var val = 1;
  add_child(tree1, val);
}

// Tree2: Unbalanced such that all but one elements always go to the left
var tree2 = make_tree();
for (var k = 0; k < M; k++) {
  var val = Math.pow(2, k);
  add_child(tree2, val);
}

// Tree2: Unbalanced such that all but one elements always go to the right
var tree3 = make_tree();
for (var k = 0; k < M; k++) {
  var val = Math.pow(2, M-1-k);
  add_child(tree3, val);
}
  
// Run benchmarks
timeit("Even splits     ", function(){ tile(tree1, 0, 0, 6, 4) }, N);
timeit("Unbalanced-left ", function(){ tile(tree2, 0, 0, 6, 4) }, N);
timeit("Unbalanced-right", function(){ tile(tree3, 0, 0, 6, 4) }, N);