Recursion vs iteration - walk tree

JavaScript performance comparison

Revision 28 of this test case created by

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
Iterate through tree (breadth-first)
// simulates operations for walking through tree using iteration
var nodes=[];
var stack = [parentElement];
var current, children;
while (current = stack.pop()) {
  nodes.push(current);
  children = current.childNodes;
  for (var i = 0, len = children.length; i < len; i++) {
    stack.push(children[i]);
  }
}
pending…
treewalker
var nodes=[];
var walker = document.createTreeWalker(
        parentElement,  // root node
        NodeFilter.SHOW_ALL,  // filtering only text nodes
        null,
        false
    );
var node=walker.nextNode();
while (node) {
 nodes.push(node);
 node=walker.nextNode();
}
pending…
NodeIterator
var nodes=[];
var iterator = document.createNodeIterator(parentElement, NodeFilter.SHOW_ALL, null);
var node = iterator.nextNode();
while (node) {
 nodes.push(node);
 node = iterator.nextNode();
}
pending…
forEach Recursive
var nodes=[];
function iterate(current) {
  nodes.push(current);
  var children = current.childNodes;
  if (!children) return;
children.forEach(c => iterate(c));
}
iterate(parentElement);
pending…
walkdom
var nodes=[];
function walkTheDOM(node) {
    nodes.push(node);
    node = node.firstChild;
    while (node) {
        walkTheDOM(node);
        node = node.nextSibling;
    }
}
walkTheDOM(parentElement);
pending…
walkDOM
function walkDOM(main) {
    var arr = [];
    var loop = function(main) {
        do {
            arr.push(main);
            if(main.hasChildNodes())
                loop(main.firstChild);
        }
        while (main = main.nextSibling);
    }
    loop(main);
    return arr;
}
walkDOM(parentElement);
pending…
childs[i]
var nodes=[];
function walker(domObject) {
    if (domObject === null) return; // fail fast
    nodes.push(domObject);
    var childs = domObject.childNodes;
    for (var i = 0; i < childs.length; i++)
        walker(childs[i]);
}
walker(parentElement);
pending…
Iterate recursion
var nodes=[];
function iterate(current) {
  nodes.push(current);
  var children = current.childNodes;
  if (!children) return;
  var i = children.length
  for (; i--;) iterate(children[i]);
}
iterate(parentElement);
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