dfs implicit vs explicit

Benchmark created on

Setup

const Node = (name)=>({name, children:[], push(...args){this.children.push(...args)}});
const root = Node("root");
const a = Node("a");
const b = Node("b");
const c = Node("c");
const d = Node("d");
const e = Node("e");
const f = Node("f");
const g = Node("g");
const h = Node("h");
root.push(a);
root.push(b);
a.push(c);
a.push(d);
d.push(e);
d.push(f);
e.push(g);
b.push(h);

function dfsExplicit(node, func) {
  const stack = [[0,[node]]];
  const NEXT_INDEX = 0;
  const CHILDREN = 1;
  while (stack.length > 0) {
      const lastDepth = stack[stack.length-1];
      const nextIndex = lastDepth[NEXT_INDEX];
      const children = lastDepth[CHILDREN];
      if (nextIndex === children.length) {
          stack.pop();
          continue;
      }
      const currentNode = children[nextIndex];
      func(currentNode);
      if (currentNode.children.length > 0) {
          stack.push([0, currentNode.children]);
      }
      lastDepth[NEXT_INDEX] += 1;
  }
}

function dfsImplicit(node, func) {
    func(node);
    for (let i = 0; i < node.children.length; i++) {
        dfsImplicit(node.children[i], func); 
    }
}

Test runner

Ready to run.

Testing in
TestOps/sec
dfsExplicit
dfsExplicit(root,()=>{});
ready
dfsImplicit
dfsImplicit(root,()=>{});
ready

Revisions

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