Reselect: Dependency recalculation with arrays

[avaragado]

I'm hitting an annoyance with memoization of arrays.

I'm keeping normalized data in a redux store as recommended (objects indexed by id, with a separate array of indexes for ordering), and using a selector to denormalize these into an array of objects.

So I'm doing this, effectively:

const selectObjectsById = (state) => state.objectsById;
const selectIds = (state) => state.ids;

const selectDenorm = createSelector(
    selectObjectsById,
    selectIds,
    (objectsById, ids) => ids.map(id => objectsById[id]),
);

When state.objectsById changes, selectDenorm will recalculate. But if state.objectsById changes in a way that doesn't change the result of selectDenorm (for example, if a new object is added to state.objectsById whose id isn't in state.ids) then the new array calculated is memberwise identical to the old one but is not reference-equal.

This means a downstream selector is needlessly recalculated. For example:

const selectMain = createSelector(
    selectDenorm,
    selectFoo,
    selectBar,
    (denorm, foo, bar) => ({ denorm, foo, bar }),
);

I can use createSelectorCreator with a custom equality checker to make a custom selector for selectMain to stop this needless recalculation. But if then selectFoo changes (according to that equality checker), selectMain is recalculated -- using the _new_ selectDenorm result. Which means selectMain(state).denorm is a different reference, even though my custom equality checker insists it's the same.

(At least, this is my understanding of what's going on, which might be wrong.)

If reselect, when it recalculates a selector, uses the _previous_ value of each argument that passed the equality check, then this would improve things. Or perhaps it could run the equality check on the result of the recalculation against the previous result, and return the previous one if they're the same. Or do both?

Or should I be doing things differently?

Thanks for a great library!

[ellbee]

selectDenorm will only return a referentially different value if its arguments have changed (i.e. selectObjectById or selectIds). Looks to me that you should be using a custom equality check for selectDenorm?

[avaragado]

I don't think a custom equality checker on selectDenorm would help.

As I understand it, a custom equality checker for selectDenorm would apply to selectObjectsById and selectIds, and not to the result of the function.

Imagine this initial state:

{
  objectsById: { 1: { id: 1 }, 2: { id: 2 } },
  ids: [1, 2],
}

then selectDenorm(state) is [ { id: 1 }, { id: 2 } ], and the two refs objectsById and ids are memoized.

Now someone updates the state, leaving ids alone and replacing objectsById with a new object (different reference):

{
  objectsById: { 1: { id: 1 }, 2: { id: 2 } , 3: { id: 3 } },
  ids: [1, 2],
}

The next call to selectDenorm(state) will see that the ids ref is the same, but the objectsById ref has changed, so it calls the function. The result is [ { id: 1 }, { id: 2 } ].

Compare this to the result of the first call to selectDenorm(state). It's not the same reference, but it is effectively the same array as all its members have identical references. So any other selectors that use it as a dependency will update unnecessarily.

A custom equality checker on selectDenorm surely wouldn't help here.

A custom equality checker on selectMain would spot that the result of selectDenormis effectively the same if not referentially identical, and might help. But as I said above, if another of the dependencies of selectMain updates, then the new, referentially different result of selectDenorm is fed into the selectMain function. So the fact that a custom equality checker has deemed it "the same" has been lost.

[ellbee]

Can provide me with some code that I can run which demonstrates the problem? I'm super busy right now, and I think that will be the quickest way for me to understand the problem.

[avaragado]

I've added a gist that runs under node, requiring reselect.

https://gist.github.com/avaragado/60550167ea230016a5e4

As you can see, adding a custom equality checker to selectDenorm doesn't help. This is because custom equality checkers only apply to the arguments to the calculation function (calcDenorm in the gist) and not to its result.

The effect: there's no way within a single selector to say: "this result is the same as the previous result, even though it's not the same reference, so return the old reference".

It's possible to work around using a wrapping identity selector:

// createEqualishSelector compares arrays memberwise. See the gist.
// The selectDenorm selector could use the default equality checker.

var selectDenormWrap = createEqualishSelector(
    selectDenorm,
    function (v) { return v; }
);

// Any succeeding selectors must depend on the wrapper not the original.

This feels clunky, though.

[ellbee]

Right, I get it now. In my initial reply I was missing the new object that is added. (Your clarifying comment was actually very thorough and clear now I have taken the time to actually read through it properly, so thanks for humouring me and creating the example code anyway. It seems when I'm busy my reading comprehension is significantly reduced!)

The idea of using the previous result is interesting. I haven't thought about it much, but I don't see a reason why it wouldn't work. Let me have a play around with it.

[avaragado]

Thank you!

[ellbee]

I think my preference for now is to leave the default behaviour the same, and instead I'll suggest creating a selector creator with a custom memoize function:

function resultCheckMemoize(
  func,
  resultCheck = defaultEqualityCheck,
  argsCheck = defaultEqualityCheck
) {
  let lastArgs = null
  let lastResult = null
  return (...args) => {
    if (lastArgs !== null &&
        args.every((value, index) => argsCheck(value, lastArgs[index]))) {
      return lastResult
    }
    lastArgs = args
    let result = func(...args)
    return resultCheck(lastResult, result) ? lastResult : result
  }
}

We can always officially support this in Reselect a little later on, as we all know its easier to add things than take them out! What do you think?

[avaragado]

I think that's a good idea. I'll try out that custom memoize function and let you know if I experience any problems. Thanks for helping out!

[landabaso]

@ellbee, @avaragado thanks for this discussion!

I also encountered exactly the same problem. I'm surprised there isn't more people getting into this kind of issue. Maybe this should go to the docs somehow?

Once you adhere to redux recommendations (normalization + reselect) you'll end up having object updates to add a few items and thus reselect will always return new return values even if the list of Ids keeps being the same.

I followed the discussion but I'm not sure how/where set resultCheckMemoize, where is defaultEqualityCheck and so on. It's the first time I use reselect. Could you guys elaborate a bit more?

This is what I tried so far but returned values are not correct (the returned array is equal to null):

import { createSelectorCreator } from 'reselect';

function defaultEqualityCheck(currentVal, previousVal) {
  return currentVal === previousVal
}

function resultCheckMemoize(
  func,
  resultCheck = defaultEqualityCheck,
    argsCheck = defaultEqualityCheck
) {
  let lastArgs = null
  let lastResult = null
  return (...args) => {
    if (lastArgs !== null &&
        args.every((value, index) => argsCheck(value, lastArgs[index]))) {
          return lastResult
        }   
        lastArgs = args
        let result = func(...args)
        return resultCheck(lastResult, result) ? lastResult : result
  }
}
const customCreateSelector = createSelectorCreator(resultCheckMemoize);

//Then I use customCreateSelector instead of createSelector

Thanks!

[landabaso]

In fact it was easier than expected. This is all you need to do (following the example by @avaragado above):

//fbjs will already be installed if using react npm module
import shallowEqual from 'fbjs/lib/shallowEqual';
import { defaultMemoize, createSelector, createSelectorCreator } from 'reselect';

//Do this part as usual
const selectObjectsById = (state) => state.objectsById;
const selectIds = (state) => state.ids;

const intermediateSelectDenorm = createSelector(
    selectObjectsById,
    selectIds,
    (objectsById, ids) => ids.map(id => objectsById[id]),
);

//Add this:
const customCreateSelector = createSelectorCreator(defaultMemoize, shallowEqual);

export const selectDenorm = customCreateSelector (
  intermediateSelectDenorm,
  (objects) => objects );

[avaragado]

Glad you got it working!

[rickharrison]

I've just started running into this issue since I started normalizing my data more in redux. Essentially, I need a selector that is only re-computed when state.ids changes but not state.objectsById. Changing the equality comparison to deepEqual seems like throwing away a lot of what redux gets you.

Is it possible to define a selector that only re-computes based on one of its dependencies? I.E. in:

createSelector(
  selectListIds,
  selectObjectsBYId,
  (listIds, objectByIds) => listIds.map(id => objectsById[id])
);

In this example, I only want the selector to re-compute when selectListIds changes. @avaragado Are you still using that same approach or have you found a better solution?

[avaragado]

I'm using a memoizer that performs a ref-equal comparison for dependencies, and a loose-equal comparison for the result. This means if the dependencies change the selector recalculates, as standard, but if the result is deep equal to the cached result then the cached result is returned. This stops a cascading recalculation of dependent selectors.

[dictcp]

the corrected version of resultCheckMemoize (need to memoize lastResult)

function resultCheckMemoize (func,
                            resultCheck = defaultEqualityCheck,
                            argsCheck = defaultEqualityCheck) {
  let lastArgs = null
  let lastResult = null
  return (...args) => {
    if (lastArgs !== null &&
      lastArgs.length === args.length &&
      args.every((value, index) => argsCheck(value, lastArgs[index]))) {
      return lastResult
    }
    lastArgs = args
    let result = func(...args)
    return resultCheck(lastResult, result) ? lastResult : (lastResult = result)
  }
}

[OliverJAsh]

I'm using a memoizer that performs a ref-equal comparison for dependencies, and a loose-equal comparison for the result. This means if the dependencies change the selector recalculates, as standard, but if the result is deep equal to the cached result then the cached result is returned. This stops a cascading recalculation of dependent selectors.

This issue is missing an example of how to use resultCheckMemoize. Here is how I got it working:

const assert = require('assert');
const { createSelectorCreator } = require('reselect');
const shallowEqual = require('shallowequal');

function defaultEqualityCheck(currentVal, previousVal) {
  return currentVal === previousVal;
}

function resultCheckMemoize(
  func,
  resultCheck = defaultEqualityCheck,
  argsCheck = defaultEqualityCheck,
) {
  let lastArgs = null;
  let lastResult = null;
  return (...args) => {
    if (
      lastArgs !== null &&
      lastArgs.length === args.length &&
      args.every((value, index) => argsCheck(value, lastArgs[index]))
    ) {
      return lastResult;
    }
    lastArgs = args;
    const result = func(...args);
    return resultCheck(lastResult, result) ? lastResult : (lastResult = result);
  };
}

// Start example

const selectObjectsById = state => state.objectsById;
const selectIds = state => state.ids;

const createArraySelector = createSelectorCreator(resultCheckMemoize, shallowEqual);

const selectDenorm = createArraySelector(selectObjectsById, selectIds, (objectsById, ids) =>
  ids.map(id => objectsById[id]),
);

const state = {
  objectsById: { 1: { id: 1 }, 2: { id: 2 } },
  ids: [1, 2],
};

const newState = {
  ...state,
  objectsById: { ...state.objectsById, 3: { id: 3 } },
};

assert(selectDenorm(state) === selectDenorm(newState));

[OliverJAsh]

/cc @ellbee

I have an example just like this but I need to map over each value in the array to create an object, e.g.

const getDenorm = obj => ({ ...obj, foo: 'bar' })

const selectDenormAll = createSelector(
    selectObjectsById,
    selectIds,
    (objectsById, ids) => ids.map(id => getDenorm(objectsById[id])),
);

In order to utilise the resultCheckMemoize mentioned above, I think I need to memoize the result of getDenorm. However, I'm not sure how to handle the cache for getDenorm, as it will be receiving lots of different inputs.

[timmfin]

However, I'm not sure how to handle the cache for getDenorm, as it will be receiving lots of different inputs.

I realize this is an old and closed issue, but I've been messing with this sort of problem and I was exploring it in this runkit notebook so I figured I'd share:

const createState = () => ({
  items: ['5','3'],
  itemInfo: { 3: { name: 'Three' }, /* ... */ }
});

const getItemIds = state => state.items;
const getItemInfo = state => state.itemInfo;

// Selector factory for a selector that memoizes only the data access for each item
const makeGetBaseItemById = itemId =>
  createSelector(
    getItemInfo,
    itemInfo => {
      console.log(`getBaseItemById ${itemId}`);
      return itemInfo[itemId];
    }
  );

// Selector factory for a selector that memoizes some (potentially expensive?) processing on each item
const makeGetItemById = (itemId, getBaseItemById) =>
  createSelector(
    makeGetBaseItemById(itemId),
    baseItem => {
      console.log(`getItemById ${JSON.stringify(baseItem)}`);
      return {
        ...baseItem,
        other: `Thing for: ${baseItem.name}`
      };
    }
  );

// The standard, non-memoized get array of items selector
const getItems = createSelector(
  getItemIds,
  getItemInfo,
  (items, itemInfo) => {
    console.log("Calculating getItems");
    return items.map(itemId => itemInfo[itemId]);
  }
);

// A custom selector factory that memoizes the items array at several levels
const makeCachedGetItems = () => {
  const cachedItemSelectorsById = {};
  let lastResult;

  return createSelector(
    getItemIds,
    getItemInfo,
    (items, itemInfo) => {
      console.log("Calculating getItems");

      const newResult = items.map(itemId => {
        if (!cachedItemSelectorsById[itemId]) {
          cachedItemSelectorsById[itemId] = makeGetItemById(itemId);
        }
        return cachedItemSelectorsById[itemId](state, itemInfo);
      });

      if (shallowEqual(lastResult, newResult)) {
        console.log("Reusing last array");
        return lastResult;
      }
      lastResult = newResult;
      return newResult;
    }
  );
};

const getItems2 = makeCachedGetItems();

That is likely overkill for most scenarios, but it does give you memoization at several levels and ensures that the final resulting array reference only changes if some item actually changed.

[OliverJAsh]

PR to add something like resultCheckMemoize to the library: https://github.com/reduxjs/reselect/pull/456