Replacing large array very slow (possibly due to reconciliation)

[yossivainshtein]

Bug report
I have a simple model containing an array of ~10K randomly generated points (points are a very simple model with an identifier and a string field).
I'm replacing the array with another similar-sized array of randomly-generated points. (In the real app this would be data coming from the server)

The replace itself takes a very, very long time - about 16 seconds on my machine.

I tried to understand why, I think this is due to the attempts of entity reconciliation in the array. It has 2 nested for loops, resulting in O(n^2) iterations.
I'm not sure why this is needed though, as the entities contain IDs and can be looked up quickly - Is there a reason for this? Am I doing something wrong?

const Point = types.model("Point").props({
  uuid: types.identifier,
  name: types.string,
});

const PointsStore = types
  .model({
    points: types.array(Point),
  })
  .actions((self) => ({
    setPoints(points: Instance<typeof Point>[]): void {
      self.points.replace(points);
    },
  }));
const store = PointsStore.create({
  points: generateRandomPoints(10000),
});
const newPoints = generateRandomPoints(10000).map((e) => Point.create(e));

const before = new Date();
// store.setPoints([]); // If I include this, replacing is fast
store.setPoints(newPoints); // <-- This is very slow!

if I insert the line
store.setPoints([]);
before assigning the new array, there's no performance issue. This is a workaround though, I don't want to always be conscious of this issue when replacing arrays.

• I've checked documentation and searched for existing issues and discussions
• I've made sure my project is based on the latest MST version
• Fork this code sandbox or another minimal reproduction.

Sandbox link or minimal reproduction code
https://codesandbox.io/p/sandbox/check-mst-repalce-performance-forked-2jvqwj?workspaceId=ws_UCwiGtoQYRJP5RUk9PpyQL

** What should happen? **
setPoints should take a reasonable amount of time
** What happens instead? **
setPoints is agonizingly slow, takes 16sec on my machine

[coolsoftwaretyler]

Hey @yossivainshtein - thanks for the bug report!

I agree that's pretty bad.

You wrote this:

It has 2 nested for loops, resulting in O(n^2) iterations.

What code are you referring to specifically? I can take a look and see if there's a chance to clean things up.

I will mark this as a bug and hopefully get around to it in the coming months! Happy to review any PRs that you or other observers write.

[yossivainshtein]

Hi @coolsoftwaretyler , Thanks for the quick response!

I was referring to the function reconcileArrayChildren in ArrayType.
It's general structure, is

function reconcileArrayChildren<TT>(
    parent: AnyObjectNode,
    childType: IType<any, any, TT>,
    oldNodes: AnyNode[],
    newValues: TT[],
    newPaths: (string | number)[]
)
  for (let i = 0; ; i++) {
        const hasNewNode = i <= newValues.length - 1
        const oldNode = oldNodes[i]
        let newValue = hasNewNode ? newValues[i] : undefined

        if (!oldNode && !hasNewNode) {
            // both are empty, end
            break
        } else if (!hasNewNode) {
            // new one does not exists
            ...
        } else if (!oldNode) {
            // there is no old node, create it
            ...
        } else if (areSame(oldNode, newValue)) {
            // both are the same, reconcile
            ...
        } else {
            // nothing to do, try to reorder
            let oldMatch = undefined
            // find a possible candidate to reuse  <------- * This iterates over entire `oldNodes` array instead of just looking up by key *
            for (let j = i; j < oldNodes.length; j++) {
                if (areSame(oldNodes[j], newValue)) {
                    oldMatch = oldNodes.splice(j, 1)[0]
                    break
                }
            }
         ...
        }

So the reconciliation process makes 2 nested loops, taking a long time.

I'd love to write a PR for this but i'm not familiar with the project, I can try. Would appreciate any pointers on contributing if you can.
Thanks a lot

[coolsoftwaretyler]

Thanks for the specifics, @yossivainshtein.

We have a contributing guide in https://github.com/mobxjs/mobx-state-tree/blob/master/CONTRIBUTING.md that will help you get started.

Happy to answer any specific questions you have.

I'm going to assign this issue to you for now. Feel free to drop any dev questions you have in this thread, or send me an email. If you decide not to work on it, please let me know and I'll remove your assignment and we'll add it to the backlog.

[k-ode]

Note that if you change the array to types.map the replace call will be very fast, as expected.