Recursion vs iteration - walk tree

JavaScript performance comparison

Revision 17 of this test case created by Ghulam Mohammed Taher

Preparation code


      
      <script>
Benchmark.prototype.setup = function() {
     var parentElement = document.createElement("div");
     var child, nextChild;
      //create a bunch of nested divs
     for (var i = 0; i < 10; i++) {
       var element = document.createElement("div");
       parentElement.appendChild(element);
       for (var j = 0;
         (j < Math.random() * 10); j++) {
         var nextChild = document.createElement("div");
         if (child && Math.random() > .4) child.appendChild(nextChild);
         else element.appendChild(nextChild);
         child = nextChild;
       }
     }

};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
For Each Strict
//strict mode applies tail recursion optimization in Thunderbird and other ForEach browsers

"use strict";

function iterate(current, depth) {
  var children = current.childNodes;
  if (!children) return;
  children.forEach(c => iterate(c, depth +1 ));
}
iterate(parentElement, 0);
pending…
Iterate through tree (breadth-first)
// simulates operations for walking through tree using iteration
var stack = [{
  depth: 0,
  element: parentElement
}];
var current;

var children, i, len;
var depth;
while (current = stack.pop()) {
  depth = current.depth;
  current = current.element;
  children = current.childNodes;
  for (i = 0, len = children.length; i < len; i++) {
    stack.push({ //pass args via object or array
      element: children[i],
      depth: depth + 1
    });
  }
}
pending…
Iterate Tree (breadth-first)
var stack = [{
  depth: 0,
  element: parentElement
}];
var stackItem = 0;
var current;

var children, i, len;
var depth;
while (current = stack[stackItem++]) {
  depth = current.depth;
  current = current.element;
  children = current.childNodes;
  for (i = 0, len = children.length; i < len; i++) {
    stack.push({ //pass args via object or array
      element: children[i],
      depth: depth + 1
    });
  }
}
pending…
forEach Recursive
//iterate the tree via recursion

function iterate(current, depth) {
  var children = current.childNodes;
  if (!children) return;
children.forEach(c => iterate(c, depth +1 ));
}
iterate(parentElement, 0);
pending…
Recurse through tree (depth first)
//iterate the tree via recurrsion

function iterate(current, depth) {
  var children = current.childNodes;
  if (!children) return;
  var i = children.length
  for (; i--;) iterate(children[i], depth + 1);
}
iterate(parentElement, 0);
pending…
Strict mode recursion
//strict mode applies tail recursion optimization in Thunderbird and other browsers

"use strict";

function iterate(current, depth) {
  var children = current.childNodes;
  if (!children) return;
  var i = children.length
  for (; i--;) iterate(children[i], depth + 1);
}
iterate(parentElement, 0);
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL.

0 Comments