Massive gotcha in deep equality example (and arguably, bug)

[yoni-tock]

There is a really big gotcha in the lodash isEqual example for a custom selector that leads to terrible performance for large data structures.

The root cause is in defaultMemoize, where if the equality check passes, the lastArgs variable isn't updated (code here). The result is that if you have two objects that are deep equal but not shallow equal, lastArgs will never updated but every change will require a deep equality comparison. If the data structure is complex, this is really expensive and actually way worse than just failing the shallow equality check early.

In the pathological case, you could have the dependencies of a selector go something like the following:

null -> a // a is stored
a -> b // a !== b but _.isEqual(a, b) is true, so b is not stored
b -> b // requires deep equality check when shallow would do
b -> b // and again
...

So even if b never changes the entire rest of the time, it will still require deep equality checks every time the store changes.

Is there any reason not to always save the current args to lastArgs? For our case at least, that seems totally reasonable and allows the shallow equality check in _.isEqual to work most of the time.

At the very least, I think this should be noted in the docs. I'm happy to write the copy if that'd be helpful. I'm also happy to open a PR with the change. Here's the custom memoizer we wrote (in ES6), which comes down to defaultMemoize with the aforementioned tiny tweak:

function customMemoize(func, equalityCheck) {
  let lastArgs = null;
  let lastResult = null;
  return function() {
    let _len = arguments.length;
    let args = Array(_len);
    for (let _key = 0; _key < _len; _key++) {
      args[_key] = arguments[_key];
    }

    const hasNotChanged = (lastArgs !== null && lastArgs.length === args.length &&
      args.every((value, index) => {
        return equalityCheck(value, lastArgs[index]);
      })
    );

    if (!hasNotChanged) {
      lastResult = func(...args);
    }
    // Storing this even if hasNotChanged is true is the deviation from `defaultMemoize`
    lastArgs = args;
    return lastResult;
  };
}

[ellbee]

Good catch. It looks like the proposed change should be backwards compatible? If so I can't think of a reason not to accept a PR.

[yoni-tock]

Sounds good, I'll try to get one open this weekend :)

[yoni-tock]

Faster than I thought, lol

[yoni-tock]

Are there tests to run or anything?

[yoni-tock]

Found them and they're passing :)