fix selectorGetter performance issue #1515

thomaszdxsn · 2021-12-23T02:02:17Z

motivation: the getter is call setDepsInStore every time, harm the performance when multiple call the getter
notes: this pr just a demo, I don't known is this feasible. please give me a confirm, and I will make some further change with testcases

#914 Please refer this issue for detail

facebook-github-bot · 2021-12-23T02:02:21Z

Thank you for your pull request and welcome to our community.

Action Required

In order to merge any pull request (code, docs, etc.), we require contributors to sign our Contributor License Agreement, and we don't seem to have one on file for you.

Process

In order for us to review and merge your suggested changes, please sign at https://code.facebook.com/cla. If you are contributing on behalf of someone else (eg your employer), the individual CLA may not be sufficient and your employer may need to sign the corporate CLA.

Once the CLA is signed, our tooling will perform checks and validations. Afterwards, the pull request will be tagged with CLA signed. The tagging process may take up to 1 hour after signing. Please give it that time before contacting us about it.

If you have received this in error or have any questions, please contact us at cla@fb.com. Thanks!

thomaszdxsn · 2021-12-23T02:05:49Z

By the way, this change is fix my performance issue. But I don't know is it harm other issues?

thomaszdxsn · 2022-01-02T17:51:56Z

@drarmstr give a review, please

drarmstr · 2022-01-03T04:35:52Z

@drarmstr give a review, please

Hi @thomaszdxsn ! Thank you so much for the contribution! I'm still on a bit of a holiday schedule so I'll try to review later this week. We do really appreciate your effort.

drarmstr · 2022-01-03T04:45:35Z

packages/recoil/recoil_values/Recoil_selector.js

@@ -700,7 +700,7 @@ function selector<T>(
  ): void {
    deps.add(newDepKey);

-    setDepsInStore(store, state, deps, executionId);
+    // setDepsInStore(store, state, deps, executionId);


With this simplification we can just get rid of setNewDepInStore() and call deps.add() directly in getRecoilValue().

drarmstr · 2022-01-03T04:48:38Z

packages/recoil/recoil_values/Recoil_selector.js

@@ -782,6 +782,7 @@ function selector<T>(

    try {
      result = get({get: getRecoilValue, getCallback});
+      setDepsInStore(store, state, deps, executionId)


Best if this is done outside of this try/catch block. We could just call it before the return, which references depValues, so it might be a nice logical place for it.

drarmstr · 2022-01-03T05:05:22Z

Ok, I took a look; thanks again @thomaszdxsn ! I've actually thought an optimization like this makes sense, but we need to be careful with asynchronous cases. If a selector has pending dependencies, or is async itself, then it needs to update it's dependencies before relinquishing control; from a glance this may be done as there are calls to setDepsInStore() in the various promise wrapping logic. The thing would be to have tests that confirm that a selector will properly be triggered to re-evaluate due to a dependency change if it is in the pending state either due to a pending dependency or due to itself still pending resolving its promise. So, I think this is safe, but let's test it!

@csantos42 do you have thoughts?

thomaszdxsn · 2022-01-05T04:45:49Z

Ok, I will dive into internals

drarmstr · 2022-01-20T22:25:47Z

Hi @thomaszdxsn, have you had a chance to dive in further?

thomaszdxsn · 2022-01-21T01:17:17Z

Sorry, I am busy until 2022-01-26. after 01-25 I will give some further progress

drarmstr · 2022-01-25T08:32:56Z

@thomaszdxsn - In the meantime, #1568 and #1566 do some unrelated cleanup of the selector implementation. Hopefully it should help make it a bit more readable.

thomaszdxsn · 2022-01-26T02:01:42Z

@thomaszdxsn - In the meantime, #1568 and #1566 do some unrelated cleanup of the selector implementation. Hopefully it should help make it a bit more readable.

got it, thanks

facebook-github-bot · 2022-01-26T06:29:56Z

Thank you for signing our Contributor License Agreement. We can now accept your code for this (and any) Meta Open Source project. Thanks!

thomaszdxsn · 2022-01-26T18:42:50Z

Sorry, make a mess so pr is closed.

The codebase is overwhelming for me. please give some mentor

from a glance this may be done as there are calls to setDepsInStore() in the various promise wrapping logic. The thing would be to have tests that confirm that a selector will properly be triggered to re-evaluate due to a dependency change if it is in the pending state either due to a pending dependency or due to itself still pending resolving its promise. So, I think this is safe, but let's test it!

Do I need add code for "various promise wrapping log"?
Do I need add more testcase? I do test already, and modify some resolvingSel with refresher, it make selector re-evaluate.
Or I need add a new testcase, let the selector's deps change to variadic in runtime? like [a, b] -> [a, c, d]

drarmstr · 2022-01-26T20:03:05Z

Sorry, make a mess so pr is closed.

The codebase is overwhelming for me. please give some mentor

from a glance this may be done as there are calls to setDepsInStore() in the various promise wrapping logic. The thing would be to have tests that confirm that a selector will properly be triggered to re-evaluate due to a dependency change if it is in the pending state either due to a pending dependency or due to itself still pending resolving its promise. So, I think this is safe, but let's test it!

Do I need add code for "various promise wrapping log"?

Do I need add more testcase? I do test already, and modify some resolvingSel with refresher, it make selector re-evaluate.

Or I need add a new testcase, let the selector's deps change to variadic in runtime? like [a, b] -> [a, c, d]

Yeah, I'm hoping that no other promise wrapping logic changes are needed here. But we should add more unit testcases in Recoil_selector-test.js or Recoil_selectorHooks-test.js. At least something like:

Selector await's on some Promise, which resolves, then get()'s a new dependency of some atom, then waits again on either another async dependency or Promise (test both). Either way, the selector should still be in a pending state. Then, we change the value of the atom and confirm the selector re-evaluates with the new value of the atom. Based on the new value of the atom the selector can then just resolve and provide a value. The key is that the dynamic dependency discovered after the await was recorded and changes to it cause the selector to re-evaluate.

Also, we started stubbing some performance tests in Recoil_perf-test.js.

thomaszdxsn · 2022-01-27T17:58:35Z

Sorry I discover the new merged code now, Let me merge it

facebook-github-bot · 2022-01-27T20:02:20Z

@drarmstr has imported this pull request. If you are a Meta employee, you can view this diff on Phabricator.

drarmstr · 2022-02-07T09:30:05Z

@thomaszdxsn - Thanks for the updates so far. I worked closer with your test case and updated it to cover some more cases.

  testRecoil('Dynamic deps will refresh', async () => {
    const myAtom = atom({
      key: 'selector dynamic deps atom',
      default: 'DEFAULT',
    });
    const myAtomA = atom({
      key: 'selector dynamic deps atom A',
      default: new Promise(() => {}),
    });
    const myAtomB = atom({
      key: 'selector dynamic deps atom B',
      default: 'B',
    });
    const myAtomC = atom({
      key: 'selector dynamic deps atom C',
      default: new Promise(() => {}),
    });

    let selectorEvaluations = 0;
    const mySelector = selector({
      key: 'selector dynamic deps selector',
      get: async ({get}) => {
        selectorEvaluations++;
        await Promise.resolve();
        const sw = get(myAtom);
        if (sw === 'A') {
          return 'RESOLVED_' + get(myAtomA);
        }
        if (sw === 'B') {
          return 'RESOLVED_' + get(myAtomB);
        }
        if (sw === 'C') {
          return 'RESOLVED_' + get(myAtomC);
        }
        await new Promise(() => {});
      },
    });

    const wrapperSelector = selector({
      key: 'selector dynamic deps wrapper',
      get: ({get}) => {
        const loadable = get(noWait(mySelector));
        return loadable.state === 'loading' ? 'loading' : loadable.contents;
      },
    });

    let setAtom, setAtomA, setAtomB;
    function ComponentSetter() {
      setAtom = useSetRecoilState(myAtom);
      setAtomA = useSetRecoilState(myAtomA);
      setAtomB = useSetRecoilState(myAtomB);
    }
    const c = renderElements(
      <>
        <ComponentSetter />
        <ReadsAtom atom={wrapperSelector} />
      </>,
    );
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"loading"');
    expect(selectorEvaluations).toBe(1);

    // Cause re-evaluation to pending state
    act(() => setAtom('TMP'));
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"loading"');
    expect(selectorEvaluations).toBe(2);

    // Add atomA dependency, which is pending
    act(() => setAtom('A'));
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"loading"');
    expect(selectorEvaluations).toBe(3);

    // change to atomB dependency
    act(() => setAtom('B'));
    await flushPromisesAndTimers();
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"RESOLVED_B"');
    expect(selectorEvaluations).toBe(4);

    // Set atomB
    act(() => setAtomB('SETB-0'));
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"RESOLVED_SETB-0"');
    expect(selectorEvaluations).toBe(5);

    // Change back to atomA dependency
    act(() => setAtom('A'));
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"loading"');
    expect(selectorEvaluations).toBe(6);

    // Setting B is currently ignored
    act(() => setAtomB('SETB-IGNORE'));
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"loading"');
    expect(selectorEvaluations).toBe(6);

    // Set atomA
    act(() => setAtomA('SETA'));
    await flushPromisesAndTimers();
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"RESOLVED_SETA"');
    expect(selectorEvaluations).toBe(7);

    // Setting atomB is ignored
    act(() => setAtomB('SETB-LATER'));
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"RESOLVED_SETA"');
    expect(selectorEvaluations).toBe(7);

    // Change to atomC, which is pending
    act(() => setAtom('C'));
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"loading"');
    expect(selectorEvaluations).toBe(8);

    // Setting atomA is ignored
    act(() => setAtomA('SETA-LATER'));
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"loading"');
    expect(selectorEvaluations).toBe(8);

    // change back to atomA for new value
    act(() => setAtom('A'));
    await flushPromisesAndTimers();
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"RESOLVED_SETA-LATER"');
    expect(selectorEvaluations).toBe(9);

    // Change back to atomB
    act(() => setAtom('B'));
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"RESOLVED_SETB-LATER"');
    expect(selectorEvaluations).toBe(10);

    // Set atomB
    act(() => setAtomB('SETB-1'));
    await flushPromisesAndTimers();
    expect(c.textContent).toBe('"RESOLVED_SETB-1"');
    expect(selectorEvaluations).toBe(11);
  });

You'll notice this also adds a wrapper selector using noWait(). It turns out that using a snapshot or just the selector directly causes the component using it to suspend and thus re-evaluate on wake even if the dependencies aren't sufficient. Thee wrapper helps avoid this and reveals this approach isn't working. Restarting the evaluation is reseting the deps list and the partial evaluation promises are never resolving so they don't have a chance to set them either. So, I don't think we can avoid updating deps when calling getRecoilValue()...

But, I still think there is hope here if we can just optimize saveDependencyMapToStore(). For example, maybe updating mergeDependencyMapIntoGraph() to only go through the expensive update if thee graph's dependencies don't already match what it is trying to set it to. So, perhaps it could first check if the work is already done and then abort. What do you think?

thomaszdxsn · 2022-02-07T18:07:18Z

Involve async things make it very complicate. actually I don't use any async in recoil(I have a little async logic, but write as redux-thunk style. etc async then update atom).So I don't have use many API in Recoil like noWait.

I known what you meaning but don't know how to optimize saveDependencyMapToStore

thomaszdxsn · 2022-02-07T18:16:43Z

My scenario is:

A atomFamily representation a linked list nodes
UI as a Tree
Every atom has a collapse/expand field
A Selector calculate display nodes based on collapse and children
Each time user click the collapse button, the selector is reevaluate.

When display nodes show more than 900+, the response time is 500ms+. Because every get trigger mergeDependencyMapIntoGraph() is very expensive

thomaszdxsn · 2022-02-07T18:22:13Z

For example, maybe updating mergeDependencyMapIntoGraph() to only go through the expensive update if thee graph's dependencies don't already match what it is trying to set it to. So, perhaps it could first check if the work is already done and then abort...

@drarmstr What you mean if thee graph's dependencies don't already match what it is trying to set it to? does this API can call only once?

drarmstr · 2022-02-08T03:10:51Z

Yeah, even though many have simple use cases we still need to be careful to make sure all the corner cases work for everyone.

The possible optimization is perhaps just checking if the graph needs to be updated before updating it. Thinking is that the updating process, with taking multiple set differences, is more expensive than just first checking if they are already equivalent up-front..

thomaszdxsn · 2022-02-08T03:58:31Z

@drarmstr Sorry but what is timing for dependencies don't already match? for my view the deps don't match after every get() called

drarmstr · 2022-02-10T07:00:57Z

@drarmstr Sorry but what is timing for dependencies don't already match? for my view the deps don't match after every get() called

Ah, I see, you're trying to cover the case of looping over new dependencies, not just existing dependencies. Yeah, then that idea won't be sufficient either.

Hmm, I guess it's worth diving into the actual graph update algorithm in Recoil_Graph.js, then, as that could likely be heavily optimized...

drarmstr · 2022-02-10T07:05:29Z

Add better unit test for dynamic dependencies in #1598

drarmstr · 2022-03-04T06:19:23Z

@thomaszdxsn - An idea to optimize the common case, while still supporting all cases, might be to lazily update all of the dependencies that are synchronously requested by the selector from the initial execution of the get() callback, then handle the remaining async dependencies on-demand as now. Hopefully that should help cover your situation and many others while still protecting correctness.

thomaszdxsn · 2022-03-04T06:22:47Z

An idea to optimize the common case, while still supporting all cases, might be to lazily update all of the dependencies that are synchronously requested by the selector from the initial execution of the get() callback, then handle the remaining async dependencies on-demand as now. Hopefully that should help cover your situation and many others while still protecting correctness.

Can you give some pseudo code?

drarmstr · 2022-03-04T22:42:59Z

An idea to optimize the common case, while still supporting all cases, might be to lazily update all of the dependencies that are synchronously requested by the selector from the initial execution of the get() callback, then handle the remaining async dependencies on-demand as now. Hopefully that should help cover your situation and many others while still protecting correctness.

Can you give some pseudo code?

It might be as easy:

Set a boolean as true at the top of evaluateSelectorGetter()
Call setDepsInStore() at the end of evaluateSelectorGetter(), as you added and set that boolean as false
Then, change getRecoilValue() to conditionally call setDepsInStore() based on the boolean being false.

drarmstr · 2022-03-08T02:55:42Z

@thomaszdxsn - Ok, I've got it implemented and it seems to work really well. You don't have to worry about updating the PR, I can take care of merging it. Thanks for all of your help here, this will be a great improvement!

(Also note #1651)

Summary: The current algorithm for updating selector dependencies in the data flow graph is expensive. Currently we update the graph every time a new dependency is added, which scales very poorly. This optimization only updates the graph with all sycnhronous dependencies after the synchronous selector evaluation completes. We still have to update the graph after every asynchronous dependency is added since we need to know if we have to re-evaluate the selector if one of them is updated before the selector completely resolves. This optimization significantly helps the common case for synchronous dependencies: ``` Improvement Number of synchronous dependencies 2x 100 4x 1,000 40x 10,000 ``` facebookexperimental#914 Please refer this issue for detail Pull Request resolved: facebookexperimental#1515 Test Plan: Unit tests from D34100807 check for proper re-evaluation of updated async dependencies before async selectors resolve. Differential Revision: https://www.internalfb.com/diff/D33825247?entry_point=27 Pulled By: drarmstr fbshipit-source-id: 6df53e7bca2a2284c350149c662d7a7e7e31ca52

thomaszdxsn · 2022-03-08T04:01:19Z

@thomaszdxsn - Ok, I've got it implemented and it seems to work really well. You don't have to worry about updating the PR, I can take care of merging it. Thanks for all of your help here, this will be a great improvement!

(Also note #1651)

You are very gorgeous man, thank you very much, I learn a lot of things from this issue

Summary: The current algorithm for updating selector dependencies in the data flow graph is expensive. Currently we update the graph every time a new dependency is added, which scales very poorly. This optimization only updates the graph with all sycnhronous dependencies after the synchronous selector evaluation completes. We still have to update the graph after every asynchronous dependency is added since we need to know if we have to re-evaluate the selector if one of them is updated before the selector completely resolves. This optimization significantly helps the common case for synchronous dependencies: ``` Improvement Number of synchronous dependencies 2x 100 4x 1,000 40x 10,000 ``` (Note: to scale to 10,000+ also requires D34633750) facebookexperimental/Recoil#914 Please refer this issue for detail Pull Request resolved: facebookexperimental/Recoil#1515 Test Plan: Unit tests from D34100807 check for proper re-evaluation of updated async dependencies before async selectors resolve. Test performance of scalability with `Recoil_Perf-test.js` Reviewed By: mondaychen Differential Revision: D33825247 Pulled By: drarmstr fbshipit-source-id: 943b64ef371833c1f77c0185c3c13d239526ad39

drarmstr reviewed Jan 3, 2022

View reviewed changes

drarmstr linked an issue Jan 3, 2022 that may be closed by this pull request

using selectorFamily in a loop is slow #914

Closed

drarmstr added the performance label Jan 8, 2022

facebook-github-bot added the CLA Signed This label is managed by the Facebook bot. Authors need to sign the CLA before a PR can be reviewed. label Jan 26, 2022

thomaszdxsn closed this Jan 26, 2022

thomaszdxsn force-pushed the main branch from dbcb277 to f75d4b8 Compare January 26, 2022 18:33

🎨 simplify setDepsInStore in evaluateSelectorGetter

ac48bc5

thomaszdxsn reopened this Jan 26, 2022

thomaszdxsn added 4 commits January 28, 2022 01:37

add testcase for 'selector dep changed on async flying'

5cbda1e

🔥 remove duplicate testcase

2c050e0

resolve conflict

81c1455

Merge branch 'facebookexperimental-main'

fd91da2

add testcase

bf280f3

thomaszdxsn closed this Feb 8, 2022

thomaszdxsn reopened this Feb 8, 2022

drarmstr self-assigned this Mar 8, 2022

facebook-github-bot closed this in 0f89f5c Mar 9, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

fix selectorGetter performance issue #1515

fix selectorGetter performance issue #1515

thomaszdxsn commented Dec 23, 2021

facebook-github-bot commented Dec 23, 2021

thomaszdxsn commented Dec 23, 2021

thomaszdxsn commented Jan 2, 2022

drarmstr commented Jan 3, 2022

drarmstr Jan 3, 2022

drarmstr Jan 3, 2022

drarmstr commented Jan 3, 2022

thomaszdxsn commented Jan 5, 2022

drarmstr commented Jan 20, 2022

thomaszdxsn commented Jan 21, 2022

drarmstr commented Jan 25, 2022

thomaszdxsn commented Jan 26, 2022

facebook-github-bot commented Jan 26, 2022

thomaszdxsn commented Jan 26, 2022 •

edited

drarmstr commented Jan 26, 2022 •

edited

thomaszdxsn commented Jan 27, 2022

facebook-github-bot commented Jan 27, 2022

drarmstr commented Feb 7, 2022

thomaszdxsn commented Feb 7, 2022

thomaszdxsn commented Feb 7, 2022

thomaszdxsn commented Feb 7, 2022 •

edited

drarmstr commented Feb 8, 2022

thomaszdxsn commented Feb 8, 2022 •

edited

drarmstr commented Feb 10, 2022

drarmstr commented Feb 10, 2022

drarmstr commented Mar 4, 2022

thomaszdxsn commented Mar 4, 2022

drarmstr commented Mar 4, 2022

drarmstr commented Mar 8, 2022 •

edited

thomaszdxsn commented Mar 8, 2022

fix selectorGetter performance issue #1515

fix selectorGetter performance issue #1515

Conversation

thomaszdxsn commented Dec 23, 2021

facebook-github-bot commented Dec 23, 2021

Action Required

Process

thomaszdxsn commented Dec 23, 2021

thomaszdxsn commented Jan 2, 2022

drarmstr commented Jan 3, 2022

drarmstr Jan 3, 2022

Choose a reason for hiding this comment

drarmstr Jan 3, 2022

Choose a reason for hiding this comment

drarmstr commented Jan 3, 2022

thomaszdxsn commented Jan 5, 2022

drarmstr commented Jan 20, 2022

thomaszdxsn commented Jan 21, 2022

drarmstr commented Jan 25, 2022

thomaszdxsn commented Jan 26, 2022

facebook-github-bot commented Jan 26, 2022

thomaszdxsn commented Jan 26, 2022 • edited

drarmstr commented Jan 26, 2022 • edited

thomaszdxsn commented Jan 27, 2022

facebook-github-bot commented Jan 27, 2022

drarmstr commented Feb 7, 2022

thomaszdxsn commented Feb 7, 2022

thomaszdxsn commented Feb 7, 2022

thomaszdxsn commented Feb 7, 2022 • edited

drarmstr commented Feb 8, 2022

thomaszdxsn commented Feb 8, 2022 • edited

drarmstr commented Feb 10, 2022

drarmstr commented Feb 10, 2022

drarmstr commented Mar 4, 2022

thomaszdxsn commented Mar 4, 2022

drarmstr commented Mar 4, 2022

drarmstr commented Mar 8, 2022 • edited

thomaszdxsn commented Mar 8, 2022

thomaszdxsn commented Jan 26, 2022 •

edited

drarmstr commented Jan 26, 2022 •

edited

thomaszdxsn commented Feb 7, 2022 •

edited

thomaszdxsn commented Feb 8, 2022 •

edited

drarmstr commented Mar 8, 2022 •

edited