Preact: Large child array diff performance

[t-veor]

Hello,
I was looking at performance of updating large arrays of child components which led me to looking at this for loop here: https://github.com/preactjs/preact/blob/master/src/diff/children.js#L83
(summarised with some pseudocode)

oldVNode = oldChildren[i];

if (/* oldVNode matches childVNode */ ) {
    oldChildren[i] = undefined;
} else {
    for (j = 0; j < oldChildrenLength; j++) {
        oldVNode = oldChildren[j];
        if (/* oldVNode matches childVNode */) {
            oldChildren[j] = undefined;
            break;
        }
        oldVNode = null;
    }
}

If I understand this code correctly, when Preact gets an array of children for each one it checks to see if there was a child already there with the same type and key at the same index in the old array, and otherwise it does a linear search to see if any other components match. This means that if every element changes, this code is quadratic in the number of elements.

The problem is that every element or almost every element updating is actually very common (at least, I'm suggesting, having no evidence 😄) in array manipulations. Some examples are:

• Removing an element from the front of an array, like in a scrollback buffer.
• The user reordering a list by moving an element from near the start of a list to near the end.
• Adding new things to the front of an array, like in a news feed.

In these cases most of the elements are unchanged, but a large amount of them will have shifted forward or backwards by 1 in the array, and so the loop above is quadratic.

I think a simple change might be just to change the loop slightly, so there's a much better chance the loop finds the corresponding child earlier:

    for (j = 0; j < oldChildrenLength; j++) {
        const idx = (j + i - 1) % oldChildrenLength;
        oldVNode = oldChildren[idx];
        if (/* oldVNode matches childVNode */) {
            oldChildren[idx] = undefined;
            break;
        }
        oldVNode = null;
    }

This way the loop starts looking at i - 1 first but cycles around to all the elements in the array anyway, so it speeds up those cases since for each it only needs to perform 1-3 comparisons, and falls back to the old quadratic behaviour otherwise. This does make the loop slightly more complicated so might be a pessmisation in real use cases, but again I don't really have any evidence of real usage patterns and any potential performance gains so I'd just like to know if something like this was considered before.

Of course, it's possible to do away with possible quadratic time entirely by pre-computing a look-up table ahead of time on the keys of oldChildren, but I'm more wary of this since it needs to allocate a hashmap and do lookups, so in real use cases it could be much slower.

[localvoid]

const idx = (i + ((j >>> 1) ^ -(j & 1))) % oldChildrenLength;

This one will go in both directions: i, i-1, i+1, i-2, i+2, ...

[marvinhagemeister]

@t-veor Can you file a PR for this? This seems like a worthwhile improvement to follow up on like you laid out :+1:

[developit]

This is a good change. Minimal code impact and likely reduces the hottest loop in the codebase.

For reference, Preact 8 used a precomputed hashmap as you described:
https://github.com/preactjs/preact/blob/8/src/vdom/diff.js#L189-L211

I'd be curious to see how the performance of that approach compares to the current implementation. We know rendering is faster overall, but I can't speak to the efficacy of that map. Most benchmarks are biased to measuring in-place updates and shifts, which the binary search approach handles reasonably with the need for an extra data structure.