Nested memoization causes unnecessary computations

[zsparal]

Hello, and thanks for the great library. I'm looking to migrate an existing project with a lot of performance-sensitive selectors to this library. I like the idea and the simplicity and it would greatly improve the readability of the project.

The thing I'm having problems with is the following: coming from reselect, I'm used to composing selectors. As I understood it based on other GitHub issues, just putting memoize on everything is not an ideal way to go, as nested selectors actually have a small performance cost. This requires a bit of a different mindset as with reselect, but it's easy enough to adapt to.

My problem is with selectors that do need to be memoized and their results are used in both React components and other selectors. Here, depending on the order in which the selectors are called, there could be quite a few unnecessary computations:

const base = memoize((state: X) => {
  console.log("B: ", state.key);
  return state.key;
});

const derived1 = memoize((state: X) => {
  console.log("1: ", state.key);
  return base(state) + "1";
});

const derived2 = memoize((state: X) => {
  console.log("2: ", state.key);
  return base(state) + "2";
});

// Slow order
base({ key: "a" });
derived1({ key: "a" });
derived1({ key: "b" });
derived2({ key: "b" });
base({ key: "b" });

My problem is that this produces the following sequence:

B:  a 
1:  a 
1:  b 
B:  b 
2:  b 
B:  b 
B:  b

As you can see, base is calculated 3 times: once for each derived selector and once for the base selector. Moving the base({ key: "b" }) call above the first derived with a key of b solves the problem, but this is not something I can guarantee in the actual application.

[dai-shi]

Hi, good to hear you consider migrating.

just putting memoize on everything is not an ideal way to go

Putting everything is the first option. I know the mental model is different from reselect.

const base = (state: X) => {
  console.log("B: ", state.key);
  return state.key;
};

const derived1 = memoize((state: X) => {
  console.log("1: ", state.key);
  return base(state) + "1";
});

const derived2 = memoize((state: X) => {
  console.log("2: ", state.key);
  return base(state) + "2";
});

Nesting memoized selectors is possible and may perform better in some edge cases, but in general it can be premature optimization.

As you can see, base is calculated 3 times: once for each derived selector and once for the base selector.

If you want nested memoized selectors, it should work well if you keep the state reference.

Please try this:

let state = { key: "a" };
base(state);
derived1(state);
state = { key: "b" };
derived1(state);
derived2(state);
base(state);

[zsparal]

Thank you for the quick answer. I'm guessing that with a Redux use-case, nested memoization would just end up working properly since the state is immutable. Is that correct?

I am definitely planning on following the first approach most of the time: it should lead to less memory usage and better performance if my understanding is correct. But we have a few very expensive selectors that are used in a lot of other selectors: like building a fairly complicated cache based on different graph traversals that is used all over the place. If this cache were to be recomputed in every "derived" selector it would be way too expensive.

[dai-shi]

Yes and yes. You would only need to create a nested memoized selector if computation is really expensive.

[zsparal]

Thank you very much, I'll close the issue but I'll report back with my findings about the performance after the migration (I have no doubts that the readability will be very much improved).