Why is a recursive deep equality check faster than an iterative version in Javascript?

Question

I noticed that all the deep equality implementations I've found are using recursion and theoretically the iterative form should be faster. However, it's a bit slower for me and I don't understand why.

Assume the data is the result of JSON.parse (i.e. primitives, plain objects, and arrays).

Recursive:

function equals1(x, y) {
  if (x === y) return true;

  if (Array.isArray(x) && Array.isArray(y)) {
    if (x.length !== y.length) return false;

    for (let i = 0; i < x.length; i++) {
      if (!equals1(x[i], y[i])) return false;
    }
    return true;
  }

  if ((typeof x !== 'object') || (typeof y !== 'object')) return false;

  const xKeys = Object.keys(x);
  const yKeys = Object.keys(y);
  if (xKeys.length !== yKeys.length) return false;
  for (const k of xKeys) {
    if (!y.hasOwnProperty(k)) return false;

    if (!equals1(x[k], y[k])) return false;
  }

  return true;
}

Iterative:

function equals2(a, b) {
  const stack = [a, b];
  let idx = 2;
  while (idx > 0) {
    const x = stack[idx - 1];
    const y = stack[idx - 2];
    idx -= 2;

    if (x === y) continue;

    if (Array.isArray(x) && Array.isArray(y)) {
      if (x.length !== y.length) return false;
  
      for (let i = 0; i < x.length; i++) {
        idx += 2;
        if (idx > stack.length) stack.push(x[i], y[i]);
        else {
          stack[idx - 1] = x[i];
          stack[idx - 2] = y[i];
        }
      }
    } else {
      if ((typeof x !== 'object') || (typeof y !== 'object')) return false;

      const xKeys = Object.keys(x);
      const yKeys = Object.keys(y);
      if (xKeys.length !== yKeys.length) return false;
      for (const k of xKeys) {
        if (!y.hasOwnProperty(k)) return false;

        idx += 2;
        if (idx > stack.length) stack.push(x[k], y[k]);
        else {
          stack[idx - 1] = x[k];
          stack[idx - 2] = y[k];
        }
      }
    }
  }

  return true;
}

I'm using the index instead of the traditional stack.pop approach because it's slightly faster.

JSPerf: https://jsperf.com/deep-object-compare-123/1

The data is from Reddit: https://www.reddit.com/r/javascript.json

For me, the iterative version is 20-25% slower on Chrome and Edge, and the same speed on Firefox. I tried pre-allocating the stack array and removing the continue, but it didn't change the results. As far as I know, JS engines can optimize tail-recursive functions, but this isn't tail-recursive.

Any ideas what's going on?

Answer 1

A major difference between the two approaches is that your recursive function is doing a normal depth-first search for the first unequal value while your iterative function is putting all the children of an array/object onto the stack before searching into last child. This causes the stack array to grow much larger than the call stack of the recursive function will ever become, and it does quite some unnecessary copying of the entire data structure into a heterogenous array instead of keeping the values in local variables.

Answer 2

You do a single test on one single data structure, and from that you mean you can conclude that in general, recursive equality checks are faster than iterative ones? Are you serious? From that one single test, you can conclude nothing whatsoever. Neither could I conclude (anything much) of any one test where some iterative algorithm wins. There are sooooooooooooo many recursive and iterative ways to do deep equality testing (and other things), and there are sooooooooo many data structures. I did more than one test, and my results are, very decisively: INCONCLUSIVE, see below.

But first, one thing:

There is a little bug in your code: you don't properly check for the null case. If one argument is null, and the other one is a non-null object, an error will be thrown.

That can be easily fixed by adding the following line:

if ((x===null)||(y===null)) return false;

In equals1, put it right after if (x === y) return true;, and in equals2 put it after the continue. If both arguments were null, then the line before the inserted line does the right thing and makes the code not reach the inserted line, and if only one of the arguments is null, then the inserted line will take care of false being returned, instead of an error being thrown.

I have to admit that I find your iterative version very hard to read. I just can't understand it, but very much would like to. How does it work? Could you enlighten us, please? Does it use LIFO (last in first out) stack, corresponding to depth first search, or is it based on something different? I really would like to know.

I wrote another iterative version, based on your equals1, using a FIFO queue (first in first out, corresponding to breadth first search) - I find that very much easier to read.

And I added 3 test cases to jsperf.com, here they are:

redditData

linkedList1Knodes

linkedList10Knodes

All 3 tests use your equals1 and equals2 you quoted here (with the null bug fixed) and the FIFO version I wrote.

First test uses the original reddit data from your question, second uses a linked list with 1 thousand nodes, and third uses a linked list with 10 thousand nodes.

First test confirms that that your iterative version is about 20% slower than the recursive version, and my FIFO version is in between the two, at about 10% slower than the recursive version.

In the second test, your iterative version is the clear winner, it is much faster than the recursive version, and FIFO comes in last (it's a teeny wee bit slower than the the recursive).

In the third test, the recursive version crashes - stack overflow error, and again your iterative version is the winner (FIFO being about 30% slower)

Sorry I can't explain to you why all that is. A proper explanation probably would have to shed light onto many different aspects, I don't think there is a "singular elephant" explaining it all; maybe it makes sense to add more heterogeneous test cases, instead just one example from reddit (even if that is "real world"...)

And here is the FIFO iterative version

function equals_FIFO(x, y){
    if (x===y) return true;
    if ((x===null)||(y===null)||((typeof x)!=='object')||((typeof y)!=='object')) return false;
    var xStack = [x], yStack = [y];
    var currentIdx = 0;
    var item1, item2, kid1, kid2, keys1, keys2, i, key;
    while (currentIdx<xStack.length){
        item1 = xStack[currentIdx];
        item2 = yStack[currentIdx];
        keys1 = Object.keys(item1);
        keys2 = Object.keys(item2);
        if (keys1.length!==keys2.length) return false;
        for (i=0; i<keys1.length; i++){
            key = keys1[i];
            if (!item2.hasOwnProperty(key)) return false;
            kid1 = item1[key];
            kid2 = item2[key];
            if (kid1!==kid2){
                if ((kid1===null)||(kid2===null)||((typeof kid1)!=='object')||((typeof kid2)!=='object')) return false;
                xStack.push(kid1);
                yStack.push(kid2);
            }
        }
        currentIdx++;
    }
    return true;
}