4 ms·

You're most likely not getting a minimal diff, but it's highly likely that your diff is good enough for your use-case. React and most other similar VDOM librari

You're most likely not getting a minimal diff, but it's highly likely that your diff is good enough for your use-case. React and most other similar VDOM libraries also fail to achieve minimal diffs, however, that's not necessarily a bad thing. Just because a diff isn't minimal doesn't mean it's wrong. The ideal trade-off (diff-size vs space-time characteristics) depends on the use-case. It might be more important for a VDOM library to obtain a good-enough diff in O(N) time, as opposed to an LCS in O(NM) space and time. Linear diffing for VDOMs works well, especially with heuristics and things like explicit and implicit key matching. Sometimes the asymptotic characteristics of a program are irrelevant if your system is bounded.

victorNicollet 7y ago
React also doesn't need a diff to be of the "longest common subsequence" kind. For instance, the diff between "AB" and "BA" involves no insertion or deletion, just transposition, which React supports but traditional diffs don't.
- anonytrary 7y ago
  What you're talking about is called "implicit key matching" in React-speak. AFAIK it isn't implemented as a transposition, rather an "insert before" because the DOM API supports it directly. I have written a VDOM algorithm that relies only on swaps, deletions and insertions, but it doesn't map well to the DOM API.
devit 7y ago
React doesn't compute diffs, and it would be wrong for it to do so since components are stateful, and so it matters how they are matched (the idea that VDOM diffing is just an optimization is a very common misconception). Instead, you just specify keys for elements (either explicitly or by index in the sequence) and it matches elements with the same key in the old and new trees.
- heavenlyblue 7y ago
  But elements with ids and their attributes can be changed after a re-render and you need to sync those with DOM.
- anonytrary 7y ago
  > React doesn't compute diffs I think this is a bit pedantic. React computes what is essentially an edit path from one tree to another, so yes, it is computing diffs for all intents and purposes. That said, you're right that implicit and explicit key matching are not only for optimizations; they're for persisting state as well.

victorNicollet 7y ago

React also doesn't need a diff to be of the "longest common subsequence" kind. For instance, the diff between "AB" and "BA" involves no insertion or deletion, just transposition, which React supports but traditional diffs don't.

anonytrary 7y ago
What you're talking about is called "implicit key matching" in React-speak. AFAIK it isn't implemented as a transposition, rather an "insert before" because the DOM API supports it directly. I have written a VDOM algorithm that relies only on swaps, deletions and insertions, but it doesn't map well to the DOM API.

devit 7y ago

React doesn't compute diffs, and it would be wrong for it to do so since components are stateful, and so it matters how they are matched (the idea that VDOM diffing is just an optimization is a very common misconception). Instead, you just specify keys for elements (either explicitly or by index in the sequence) and it matches elements with the same key in the old and new trees.

heavenlyblue 7y ago
But elements with ids and their attributes can be changed after a re-render and you need to sync those with DOM.
anonytrary 7y ago
> React doesn't compute diffs I think this is a bit pedantic. React computes what is essentially an edit path from one tree to another, so yes, it is computing diffs for all intents and purposes. That said, you're right that implicit and explicit key matching are not only for optimizations; they're for persisting state as well.