Recursion vs iteration - walk tree - dont copy

JavaScript performance comparison

Revision 5 of this test case created by Aaron

Preparation code

<script>
   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
parentElement.depth = 0;
parentElement.next = null;

var children, i, len;
var depth;
current = parentElement;
while (current) {
  depth = current.depth;
  children = current.childNodes;
  //removes this item from the linked list
  current = current.next;
  for (i = 0, len = children.length; i < len; i++) {
    child = children[i];
    child.depth = depth+1;
    //place new item at the head of the list
    child.next = current;
    current = child;
  }
}
pending…
Recurse through tree (depth first)
//iterate the tree via recurrsion

function iterate(children, depth) {
  for (var i = 0, len = children.length; i < len; i++) {
    var grandChildren = children[i].childNodes;
    if (!grandChildren) continue; //handle text nodes
    iterate(grandChildren, depth + 1);
  }
}
iterate(parentElement.childNodes, 0);
pending…
Iterate Tree (breadth-first)
// simulates operations for walking through tree using iteration
parentElement.depth = 0;
parentElement.next = null;

var children, i, len;
var depth;
var current,last;
current = parentElement;
last = current;

while (current) {
  children = current.childNodes;
    for (i = 0, len = children.length; i < len; i++) {
      child = children[i];
      child.depth = current.depth+1;
      child.next = null;
      //place new item at the tail of the list
      last.next = child;
      last = child;
    }
  //removes this item from the linked list
  current = current.next;
}
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; //handle text nodes
  for (var i = 0, len = children.length; i < len; 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