DOM updates not minimal when moving last child to first place

[steadicat]

When a rerender requires the last child to be moved to first place, the update to the DOM is not minimal. Instead of removing the child in question and re-inserting it, all the other children are removed and re-added instead.

This is bad for two reasons:

1. It is unnecessary churn on the DOM, slowing things down. If any of the children is or contains a video element, the video will reset.
2. Using keys to shuffle children around is pretty common when implementing an infinite scroll in React with DOM element reuse. This should work.

Here's a screencast showing how the DOM is changed while I scroll. Notice how when I scroll down the first element is correctly removed from the top and inserted at the bottom. When I scroll back up, instead of moving the last element, React moves the other four.

https://dl.dropboxusercontent.com/u/140702/ReactDomOperations.mov

I'm using React 0.9.0.

[sophiebits]

Yeah, this is unfortunately the case right now. We could look at finding the actual minimal set of mutations for reordering a list; I think it reduces to longest increasing subsequence.

[jordwalke]

For every policy that causes a node to not be removed from the DOM, it is making the decision to actually remove some other node. It's impossible to know which ones the developer intends on being removed from the DOM and it's unfortunate that the DOM's API doesn't provide a better way to perform reordering without side effects. But maybe we can create a way to mark a node as the "pivot" point, where all reorderings occur "around" it.

[plievone]

See also #870 as a way to keep some nodes (iframes etc) attached to dom, while arranging other nodes around them. (Also one could experiment with optimizing most common cases such as common head, common tail).

[steadicat]

I like the idea of special-casing common operations, like moving the first/last element to last/first position. Will probably take care of 95% of the use cases without having to introduce complex algorithms or extra APIs.

[steadicat]

#870 will not solve this problem for me BTW. Special-casing certain tags is not going to take care of the case when these special tags occur inside all (or most) of the children being reordered. For example: <video key="a" /><video key="b" /><video key="c" /> changing to <video key="c" /><video key="a" /><video key="b" /> should move c, and only c, even though c is a video like all the other children.

[syranide]

I'm personally not a fan of "special-casing common operations", because any such operation is going to be more than fast enough in isolation. You'll increase the complexity of React, and you can easily find yourself in situations where the algorithm suddenly performs significantly worse for "no apparent reason" because no "common operation" matched.

Uniformly slow is to be preferred IMHO, that way you actually reason about the performance of your application and can more easily argue for ways to improve performance if it becomes a problem.

I imagine that it would be quite cheap to make the current algorithm at least direction-neutral, which would solve its biggest flaw. IMHO, the most important quality of the algorithm is simplicity (in terms of being able to understand the result).

Also as @plievone mentioned, if we ever want to actually support iframe/video/audo/object, then it also needs to be aware of nodes that mustn't move.

[viniciusdacal]

isn't currently working with proper use of prop key?

[gaearon]

Special-casing specific operations like “last child becomes first” looks great on benchmarks, but as @syranide noted in #1422 (comment), leads to unexpected differences in performance that can make profiling harder.

The issue with moving iframe/video/audio is different, and we don’t have a good solution for it either. I’m not sure solving it would be worth the complexity it introduces.

I will close this issue but if you have more generic ideas on improving diffing algorithm that make it better for the average case without hurting the edge cases (as opposed to adding a special case) let’s discuss them in a new issue.