Improve selectors performance with a custom isDeepEqual function optimized for immutable data structures

[maxime1992]

Context

Selectors are really powerful and ensure that the performances of the app are as good as possible by applying some memoization.

Let's look at the function:

platform/modules/store/src/selector.ts

Lines 67 to 71 in d5d287c

	export function defaultMemoize(
	projectionFn: AnyFn,
	isArgumentsEqual = isEqualCheck,
	isResultEqual = isEqualCheck
	): MemoizedProjection {

The default way of checking if the arguments of the selectors are the same or not (and same for the result) is done through the isEqualCheck:

platform/modules/store/src/selector.ts

Lines 43 to 45 in d5d287c

	export function isEqualCheck(a: any, b: any): boolean {
	return a === b;
	}

Which is doing a simple comparison by reference.

Main issue

As we're working with immutable data, a comparison by reference may seem to be enough. Unfortunately, I think it isn't. Here are the reasons behind this:

• The store can be completely updated at once. Imagine a full refresh after a polling for example
• A selector could be kicking in without having to. If for example you work on an array, you'll have to return a new reference for this array. Worst case scenario is if for every object in the array you map a computed property or update it in any way. You'll then create a new reference for the object inside the array as well and it'll be double work for all the selectors downstream which will see a new reference and will all run again. But also for the change detection cycles that are a critical part of Angular. If using OnPush and the reference change (while the object is still the same), Angular will run CD on a lot of component for "nothing"

So I got curious and after being bothered by that for quite a long time, I decided to ask on Twitter if anyone had already tried a different strategy (like a deep comparison instead of check by reference for example). Apparently not (?). Anyway, @ZackDeRose said it'd be nice to have a case study and guess what I had this week at work? A hackday 😺. So here we are, with a case study.

The few ideas I had to test

I had a few options in mind and wanted to make a benchmark for all of them:

• Idea 1: A pretty dumb comparison function where I'd just stringify the objects and compare both strings
• Idea 2: Use a deep equal function like isEqual from lodash which would deep into the whole object tree till it finds a difference
• Idea 3: Knowing that we're working with immutable structures, we can probably take advantage of that to skip entire part of the check. Comparing an array for example, with lodash if the 2 arrays have the same reference it'd still make a full comparison of all the values in the array. But as we're using immutable data we know for sure that if the arrays have the same reference then we don't need to check it at all. This we could optimize things by taking a dive into the structure and keep going, until we find a reference that is the same. At which point we know that we don't need to keep going (for that branch of the search at least)

The benchmark

I benchmarked all of the above (+ included the current behavior to compare) by using 2 real apps that I've been working on at work.

Knowing that my custom comparison algorithm would probably perform well with some selectors where only a tiny part of the store had changed (because all the rest would match directly with a reference check), I decided to benchmark what I believe is the worst case scenario: The case where an entire part of the store (if not all of it...) is cloned entirely to have new references everywhere and see how all the selectors would then behave by taking a look into the performance graph in the browser. This case could happen after some polling if we were to replace the whole content of the store (or big chunks of it). In order to have a set of data that could be as relevant as possible I've decided to do the same test 20 times for each case I listed above (actually 19 instead of 20 as I forgot 1 at some point and couldn't bother re-running all the others ha 😅). I then created a pretty dumb action which I just called copyAction and in the reducers added:

  on(copyAction, (state) => JSON.parse(JSON.stringify(state))),

To get a copy of the state with new references everywhere.

I tried it with 2 apps that I've participated to build at work which both have 2 very different ways of holding the data:

• One is doing some classic polling and replacing lots of entire chunks when there's an answer for those. We've got 15 different bits of state that are stored using 15 different reducers. I know that realistically the polling can happen often but not too much either (let say every 5s in average)
• The second one is using websockets to receive some data in real time and as there's a looot of data, we just decided to stream the whole object containing all the data instead of doing some kind of incremental updates for time and complexity constraints (this performs actually quite well!). That streaming of data can happen a lot faster than the polling in the previous app. The app is quite complex and we've got loads of selectors. I've patched ngrx in node_modules directly and hacked into the isEqualCheck to see how many times we were calling selectors and the result is just scary 😅! After like a minute, I have had around 3.4 millions calls made on selectors. Hopefully we've got at least the default reference check and it's running quite nicely.

I launched the most complex page and the one which probably consumes the more of data coming from the store (through selectors, always) for both apps. And I ran the tests with the different functions (which I'll give some code for after). Here are the results:

Interpretation of the results

• Comparing the result of the string of JSON.stringify doesn't seem to be a good idea 🙅
• On a store with loooads of data, using a "dumb" deep comparison still seems to be a good idea (+16%) ✅
• On a store with loooads of data, using an optimized deep comparison for immutable data structure starts to make a good difference (nearly 40%) ✅
• On a store with many data but not as much as previously, whether we use a deep comparison or an optimized one for immutable data, we get a perf increase around +90% faster 🔥 ✔️

Those tests have been ran by hand and the apps I used to benchmark are not open source. I'm not sure how to test those number in different conditions but I wonder if it may be worth creating a new createSelector function (to avoid a breaking change?) and apply by default the optimized strategy for immutable data structure? I'd be happy to make a PR is people are interested in seeing this directly integrated into ngrx 😺.

Show me some code

For the JSON.stringify comparison I've done:

export const isDeepEqualJson = (resource1, resource2) => JSON.stringify(resource1) === JSON.stringify(resource2)

For my custom comparison optimized for checks against immutable data I've done:

export const isDeepEqualForImmutableObjects = (resource1, resource2) => {
  if (resource1 === resource2) {
    return true;
  }

  const r1IsArray = Array.isArray(resource1);
  const r2IsArray = Array.isArray(resource2);

  const r1IsObject = isObject(resource1);
  const r2IsObject = isObject(resource2);

  if (Array.isArray(resource1) && Array.isArray(resource2)) {
    if (resource1.length !== resource2.length) {
      return false;
    }

    return resource1.every((vr1, i) =>
      isDeepEqualForImmutableObjects(vr1, resource2[i])
    );
  }

  if (r1IsObject && r2IsObject) {
    const keysR1 = Object.keys(r1IsObject);
    const keysR2 = Object.keys(r2IsObject);

    if (keysR1.length !== keysR2.length) {
      return false;
    }

    if (
      keysR1.some((kr1, i) => {
        return kr1 !== keysR2[i];
      })
    ) {
      return false;
    }

    const valuesR1 = Object.values(resource1);
    const valuesR2 = Object.values(resource2);

    return valuesR1.every((vr1, i) =>
      isDeepEqualForImmutableObjects(vr1, valuesR2[i])
    );
  }

  return false;
};

Then I've created some custom memoize functions:

const customMemoizeDeepEqualForImmutableObjects = (projectionFn) =>
  defaultMemoize(projectionFn, isDeepEqualForImmutableObjects, isEqualCheck );

const customMemoizeJson = (projectionFn) =>
  defaultMemoize(projectionFn, isDeepEqualJson, isEqualCheck );

const customMemoizeLodashIsEqual = (projectionFn) =>
  defaultMemoize(projectionFn, _.isEqual, isEqualCheck );

And I simply ran all the different benchmarks by keeping only of those each time:

function createSelector(...input) {
    return createSelectorFactory(defaultMemoize)(...input);
    // return createSelectorFactory(customMemoizeDeepEqualForImmutableObjects)(...input);
    // return createSelectorFactory(customMemoizeJson)(...input);
    // return createSelectorFactory(customMemoizeLodashIsEqual)(...input);
}

Note for the above ☝️:

I believe there's no need to change the comparison function for the output of the selector as it'll trully only ever been triggered if there's an actual change so the output check can remain by reference IMO.

Sorry for the wall of text above, I may be missing some numbers and would be happy to test on more cases if needed as well as raising a MR if the maintainers think it'd be worth it :)

Random words

Thanks for Ngrx, it powers all of our apps at work and is super useful 🙏.

If accepted, I would be willing to submit a PR for this feature

[x] Yes (Assistance is provided if you need help submitting a pull request)
[ ] No

[maxime1992]

I just tried to gather some more info and benchmark purely the selectors (not including the rest of the app, like change detection cycle time for example):

App 2

Replacing all the data in the store to trigger as much as possible the selectors until we reach ~100k calls on selectors:

App	Strategy	Nb of times a selector ran	Nb of cache hits (input)	Nb of cache hits (output)	Cumulated time spend running selectors
App 2	Default	100480	60975	28437	645 ms
App 2	Custom optimized	101091	70040	30645	2498 ms

Launching the app and simply wait till it stabilize (more realistic situation):

App	Strategy	Nb of times a selector ran	Nb of cache hits (input)	Nb of cache hits (output)	Cumulated time spend running selectors
App 2	Default	6690	4417	1855	95 ms
App 2	Custom optimized	6690	4443	1841	77 ms

As we can expect, if we update all the data in the store, the checks will take longer to run when using the custom strategy (total time of 645ms VS 2498ms for 100k calls).

When the app runs in a realistic manner, we can see it's pretty much the same (95ms VS 77ms).

That said, as explained at the top, this benchmark is only including the data for the selectors. If you aggregate those data with the ones in the original post, I assume that the additional time we put in checking the selectors inputs is worth it and probably helps a lot during the change detection cycle. Note: We're using OnPush pretty much everywhere in our app, so maybe that boost wouldn't be as consequent for people not using OnPush but I feel like people using NGRX without using OnPush would be missing a nearly free boost improvement 🙃 🤷.

App 1

Same thing but this time for the app 1. Note: This app has less selectors to run so I stopped after 10k calls but this won't change the ratio:

App	Strategy	Nb of times a selector ran	Nb of cache hits (input)	Nb of cache hits (output)	Cumulated time spend running selectors
App 1	Default	10173	3570	1967	8651 ms
App 1	Custom optimized	10134	6148	3602	7563 ms

Funnily enough in this case, the default strategy is slower for the 10k calls where we replace the whole state. Let see the last case:

App 1 and we just reload the page and wait for the app to be stable:

App	Strategy	Nb of times a selector ran	Nb of cache hits (input)	Nb of cache hits (output)	Cumulated time spend running selectors
App 1	Default	3279	1743	1112	792 ms
App 1	Custom optimized	3270	1780	1106	1220 ms

The custom strategy on this one is technically slower on a selector level but looking at the data in the original message with the overall perf on the app, it's the opposite.

[preda7or]

A selector could be kicking in without having to. If for example you work on an array, you'll have to return a new reference for this array.

I assume this means that a reducer is creating new array reference (or it received an array with new reference but the exact same values). In this case I would say that it is the reducer's responsibility to run a shallow comparison on the arrays and if they match then return the original state. That way even subsequent reducer computations and all store emits can be saved.

[maxime1992]

@preda7or

I assume this means that a reducer is creating new array reference (or it received an array with new reference but the exact same values).

Not necessarily. Imagine that you're not using ngrx entity and that you have to create yourself an equivalent of the getAll selector that ngrx entity gives you for free. It'd look something like this:

export const getAllResources: MemoizedSelector<
  State,
  Resource[]
> = createSelector(getResourcesState, (resourcesState) =>
  !resourcesState
    ? null
    : resourcesState.ids.map((id) => resourcesState.entities[id])
);

Now, imagine that a user click a refresh button, it makes another call to your API and saves the result in the store. Turns out it received exactly the same data (but coming from an HTTP call, all the object references have changed (and that's just one example amongst many many many cases). Well technically you'll get in the end the same array but as the references have changed, this selector and all the ones relying onto it will kick again.

In this case I would say that it is the reducer's responsibility to run a shallow comparison on the arrays and if they match then return the original state. That way even subsequent reducer computations and all store emits can be saved.

In our monorepo we've got around 450 selectors. I don't know about other people but I know for sure that we wouldn't think nor want to manually handle this ourselves in each of them. If it becomes that repetitive, there must be something we can fix upstream to do it for us, right? :)

Can you think of any arguments against the new comparison strategy I'm proposing? If we come up with benchmarks which are not looking good I'd be happy to discard it but so far the solution seems to provide non negligeable perf improvements 😺.

WOUPS I re-read your comment and you said reducer not selector 🤦. My bad. But the same thing applies anyway. And we do have a function (that we've been wishing to open source for a long time now) which does the comparison before applying changes on the reducer to keep existing references as much as possible. But keep in mind that the raw state coming out of the reducer is probably not the one you'll consume straight away (in your components, services, effects, etc). You're probably likely to make those data go through a bunch of selectors which will create new set of data with new references...

I spent some time this week end to try to get some automation for the benchmark so I could produce some numbers faster instead of trying to read a flame graph and eyeball the change detection I'm looking for 😄. I can now come up with benchmarks providing data for 100 or 1000 passes to get a good average.

I ran the benchmark on my app 1 with the copyAction (which updates the whole state by making a deep copy of it). So this is probably the worst case scenario for the new strategy I'm offering in this issue:

Default strategy:

Optimized strategy for deep comparison on immutable structures:

So in the worst case scenario (for this app), it's a 38.8% performance improvement.

Now if I update the test to dispatch an action which will "only" deep copy 1 part (out of the 15 ones) of the state:

Default strategy:

Optimized strategy for deep comparison on immutable structures:

Now that's a 92.4% performance boost 🔥.

So overall the automated benchmarks ran on a bigger scale seem to confirm the first numbers I came up with manually 😊. I'd be happy to test that on any app, if you've got open source apps send them my way please so we can gather more data 👍. But I'm wondering if there's any reason not to make this a default (or at least have a new createSelector function exported by ngrx directly so that everyone could beneficiate from this without having to add any code (just refactor a few imports and change a function name by another).

[preda7or]

I see. 👍
I am just a random guy here, looking for performance improvement tips, so I would like to understand some details. I cannot argue with your benchmark results, but I would like to test some worst case scenarios, e.g. a deeply nested objects that differ only at the deepest, last value.

Do you have a repo maybe that I can play with?

You replaced the isArgumentsEqual in your custom memoize functions, not the isResultEqual.
I still think that state equalities should be handled by reducers: in your example, the http request returns the same array or object with different reference of course, but these values are added to the state via reducers, the reducers can run an equality check and decide not to modify the substate at the end.
(There is an interesting approach to simplify reducers and reuse states: ngrx-etc / immer)
(note: your selector takes resourcesState directly, I would add another layer of selectors for ids and entries to leverage memoization)

I would agree with your approach if the state changes but the selector results in the same deeply equal object/array. And that is why I would use your immutable object comparer as isResultEqual function.

I let the NGRX team form their opinion too ;)

[preda7or]

Another note: comparing objects by Object.values is not reliable: {a:1,b:2} and {b:1,a:2} both returns [1,2].
I would rather iterate the keys.

[daniel-sc]

I have another scenario in which the proposed solution would solve some of my headaches:

A simplified example state type:

export interface OrderState {
  orders: {comment: string, executed: boolean}[];
}

with the following selectors:

const selectExecuted = createSelector(rootState, state => state.orders.map(o => o.executed));
const selectAtLeastOneExecuted = createSelector(selectExecuted , executedList => executedList.some(e => e === true));

Now, when some other attribute changes - say comment of course selectExecuted runs, but with an optimized compare strategy all further downstream selectors - such as selectAtLeastOneExecuted could be skipped.

(I know this example seems trivial, but imagine you select auto complete hints from larger lists of entities, then this becomes actually very relevant!)

[maxime1992]

@brandonroberts you've closed this issue without explaining why. I know it's been a while but I recently came back to it and was wondering if there was a specific reason?