walker-benchmarking.coffee

#!/usr/bin/env coffee

coffeeWalk = (category, id) ->
  category.selected = category.id is id
  for subcategory in category.subcategories
    coffeeWalk subcategory, id
    category.selected or= subcategory.selected

# var coffeeWalk = function(category, id) {
#   var i = 0, subcategories = category.subcategories, len = subcategories.length, subcategory;
#   for (; i < len; i++) {
#     subcategory = subcategories[i];
#     coffeeWalk(subcategory, id);
#     category.selected || (category.selected = subcategory.selected);
#   }
#   return category.selected || (category.selected = category.id === id);
# };

`
function slowestWalk(category, id) {
  var subcategories = category.subcategories, i = subcategories.length;
  category.selected = category.id === id;
  subcategories.forEach(function (subcategory) {
    slowestWalk(subcategory, id);
    subcategory.selected || (category.selected = true);
  });
};
`

`
function nestedMembersWalk(category, id) {
  var i = 0, len = category.subcategories.length;
  category.selected = category.id === id;
  for (; i < len; i++) {
    nestedMembersWalk(category.subcategories[i], id);
    category.subcategories[i].selected || (category.selected = true);
  }
};
`

`
function fastWalk(category, id) {
  var i = 0, subcategories = category.subcategories, len = subcategories.length;
  category.selected = category.id === id;
  for (; i < len; i++) {
    fastWalk(subcategories[i], id);
    subcategories[i].selected || (category.selected = true);
  }
};
`

`
function fastestWalk(category, id) {
  var subcategories = category.subcategories, i;
  category.selected = category.id === id;
  for (i = subcategories.length; i--;) {
    fastestWalk(subcategories[i], id);
    subcategories[i].selected || (category.selected = true);
  }
};
`

`
function whileWalk(category, id) {
  var subcategories = category.subcategories, i = subcategories.length;
  category.selected = category.id === id;
  while (i--) {
    whileWalk(subcategories[i], id);
    subcategories[i].selected || (category.selected = true);
  }
};
`

#
# Testing
#
assert = require 'assert'
data   = require './walker-test-data'
tree   = subcategories: data.rest.categories
whileWalk tree, 5
assert.deepEqual tree.subcategories, data.expected


##
# Benchmarking
##
repetitions = 1e7
measure = (fn) ->
  time = process.hrtime()
  i = repetitions
  fn() while (i--)
  diff = process.hrtime(time)
  ms = (diff[0] * 1e9 + diff[1]) / 1e6
  console.log "%d ms", ms

##
# Benchmarking on a small dataset
##
# measure -> slowestWalk     tree, 5
measure -> nestedMembersWalk tree, 5
measure -> coffeeWalk        tree, 5
measure -> whileWalk         tree, 5
measure -> fastestWalk       tree, 5

#
# Benchmarking on a big dataset
#
request = require 'request-json'
client = request.createClient 'http://www.dummy.com'
client.get '/itxrest/1/catalog/store/10701/category', (err, res, body) ->
  tree = subcategories: body.categories

  coffeeWalk tree, 358015

  # measure -> slowestWalk      tree, 358015 #=> takes forever
  measure -> nestedMembersWalk tree, 358015
  measure -> coffeeWalk        tree, 358015
  measure -> whileWalk         tree, 358015
  measure -> fastestWalk       tree, 358015

#######################################################
#     v0.11.16    #      v0.12      #      v1.4.3     #
#######################################################
#   815.321438 ms #   926.212391 ms #   813.600139 ms #
#   996.250807 ms #  1179.699770 ms #   899.439075 ms #
#  1179.038399 ms #  1357.995683 ms #  1193.502141 ms #
#   844.751042 ms #  1011.134039 ms #   858.574465 ms #
# 83868.850255 ms # 98363.935533 ms # 72076.221498 ms #
# 89970.252629 ms # 95892.070397 ms # 75472.053187 ms #
# 93260.007715 ms # 90943.750059 ms # 86544.491715 ms #
# 77620.460786 ms # 88838.661629 ms # 65074.596061 ms #
#######################################################

walker-test-data.coffee

module.exports = exports =
  rest: {
    categories: [
      {
        id: 1
        subcategories: [
          {
            id: 2
            subcategories: [ ]
          }
          ,
          {
            id: 3
            subcategories: [
              {
                id: 4
                subcategories: [ ]
              }
              ,
              {
                id: 5
                subcategories: [ ]
              }
              ,
              {
                id: 6
                subcategories: [ ]
              }
            ]
          }
        ]
      }
      ,
      {
        id: 7
        subcategories: [ ]
      }
    ]
  }
  expected: [
    {
      id: 1
      subcategories: [
        {
          id: 2
          subcategories: [ ],
          selected: false
        }
        ,
        {
          id: 3
          subcategories: [
            {
              id: 4
              subcategories: [ ],
              selected: false
            }
            ,
            {
              id: 5
              subcategories: [ ],
              selected: true
            }
            ,
            {
              id: 6
              subcategories: [ ],
              selected: false
            }
          ],
          selected: true
        }
      ],
      selected: true
    }
    ,
    {
      id: 7
      subcategories: [ ],
      selected: false
    }
  ]