8 ms·

React’s diff algorithm (2013)

64 points by tilt 12y ago

amelius 12y ago
Nice explanation. I'm still wondering about something. Assume that I have one big data model (the main state). I build my virtual DOM from the main state. The states from all the sub-components are derived from this main state. Now, something in the main-state is changed, but the change should affect only a single sub-component in the tree. How does React know that only that sub-component needs to be re-rendered? I guess that it is still necessary to call setState on the sub-component, but I suspect that the logic to figure out which component needs to be re-rendered can become quite ugly, and prone to errors. Are they not addressing this issue, or am I overlooking something?
- pests 12y ago
  Basically, boolean shouldComponentUpdate(object nextProps, object nextState) Here is a good talk from ReactConf which goes over improving performance, largely including this method, here: http://youtu.be/KYzlpRvWZ6c http://youtu.be/KYzlpRvWZ6c
- masterj 12y ago
  > How does React know that only that sub-component needs to be re-rendered? It doesn't. By default it will render the whole tree again. This happens in javascript and is probably much faster than you think. However, when an app grows large enough, this can be a source of performance issues, which is why React provides ways you can inform it about work it shouldn't have to do, namely shouldComponentUpdate. If you can compare the data and determine that a particular sub-tree doesn't need to be updated you can implement a shouldComponentUpdate callback that does this. Immutable data that can be cheaply compared by checking reference equality is the preferred way of doing this. More info on this was recently added to the docs: http://facebook.github.io/react/docs/advanced-performance.html http://facebook.github.io/react/docs/advanced-performance.ht...
  - amelius 12y ago
    Yes, I'm aware that it is possible to go around this limitation. The problem I have with this is that it kind of defeats the purpose of the library: keeping the view logic in one place.
    - pests 12y ago
      Have you looked at immutable.js[0] and the benefits PureRenderMixin[1] give you? [0] https://github.com/facebook/immutable-js https://github.com/facebook/immutable-js [1] http://facebook.github.io/react/docs/pure-render-mixin.html http://facebook.github.io/react/docs/pure-render-mixin.html
    - mikewhy 12y ago
      > keeping the view logic in one place Each component has its own logic. If you are rendering your main app state in child components you will be passing the state via props. var UserInfo = React.createClass({ shouldComponentUpdate: function (nextProps, nextState) { if (nextProps.id !== this.props.id) { return true; } return false; } }) which makes perfect sense
      - amelius 12y ago
        Imagine I have a control with a large number (say N) of sub-components. Now something changes in the state of the control, which corresponds only to one of the sub-components. This change has to propagate to the right component. However, the shouldComponentUpdate() function is invoked on each of the components. This is O(N) work. This seems unreasonable. To work around this, I could determine which component needs to change in the parent control. But this would mean a separation of logic.
        TheCoelacanth 12y ago
        But are you really going to have a single list of 1 million components or are you going to have 1000 components that each contain 1000 components? The second case is much more common and is handled just fine. If you really do need a 1 million top-level sub-components, then you need to look at different data structures other than just a flat list
amelius 12y ago
Is it possible to automatically (without any additional code) animate the differences between two versions of the DOM? This would make it possible to, e.g., animate the creation of some space between two DIVs before inserting a new DIV in between, and animate the removal of space when a DIV disappears. This is something that is not easy in CSS alone, and could reduce much of the flickering in web-pages which potentially makes users lose their orientation (if the DIVs are large).
- pests 12y ago
  There was a recent ReactConf talk that included something like this. Check out the examples referencing 'magic move'. There is a YT video of the talk where this is shown but you can install the examples locally to see them yourself. https://github.com/ryanflorence/reactconf-2015-HYPE https://github.com/ryanflorence/reactconf-2015-HYPE I think does what you describe. If you want to see something cool check out the '06-itunes-style-interface' example. Implements the drop down that iTunes uses for albums or how Google Image Search has an inline drop down when you click a result. The item being left closes gracefully when you switch to another item at the same time the new item is opening.
- lobster_johnson 12y ago
  That's what transition groups do. When you wrap something I a transition group, it will generate events when a child is removed or added, allowing you to add required transition effects. The CSS transition group is pretty useful: When a child is removed, it is kept in the DOM, with a CSS "exit" class added (here you could have a CSS transition for opacity, for example), and then finally removed when React determines that the animation is done. Conversely, added nodes get an "enter" class. Transition groups are explicit -- you have to wrap your components in them -- and that's a good thing, as it allows you to control what kinds of transitions are used in different contexts.
chenglou 12y ago
Just a reminder: the best part of React isn't about its diffing algorithm or the virtual DOM. Plenty of articles have been written on this (e.g. https://medium.com/@dan_abramov/youre-missing-the-point-of-react-a20e34a51e1a https://medium.com/@dan_abramov/youre-missing-the-point-of-r...). The diffing algorithm is a smart way of circumventing the fact that the DOM is so slow; there's nothing to be proud of working with such thing. Ideally your platform isn't so. Web devs will keep reimplementing parts of React elsewhere; but at least, be inspired by some other parts of React please.
- moonchrome 12y ago
  >we can focus on examining React’s true strengths: composition, unidirectional data flow, freedom from DSLs, explicit mutation and static mental model. So wannabe functional programming in JS ? I always wondered why Facebook didn't just go all-in on clojurescript when they did React, they have the resources to deal with any compiler/technical issues, heck they could reimplement the compiler themselves they already maintain a bunch of PHP VM/language stuff. It does everything react tries to do but better and by default.
  - nilliams 12y ago
    There are a huge number of people who don't enjoy programming in lisps and don't buy the tradeoff that homoiconicity is somehow worth sacrificing all syntax for. You can take 'good parts' from functional programming without going 'all in'. Many of us don't agree that the 'all in' is actually better. (See Gary Bernhardt's 'Boundaries' talk [0] for an amazing explanation of what I mean by taking the good parts of FP). React isn't really about functional programming, it's very object-oriented. And where the parent comment refers to 'composition', they mean composition of components/view code, not pure functions as you may have interpreted it as. Personally my dive into the Clojure community has been very frustrating, I find very few answers on how to actually compose large apps, and the answers I do find basically point back to OOP (but implemented in a syntax-less, ad-hoc manner [1]). If I've got this wrong, please tell me, I'm dying for better answers. [0] https://www.destroyallsoftware.com/talks/boundaries https://www.destroyallsoftware.com/talks/boundaries [1] Stuart Sierra - Components Just Enough Structure - https://www.youtube.com/watch?v=13cmHf_kt-Q https://www.youtube.com/watch?v=13cmHf_kt-Q

64 points by tilt 12y ago

Nice explanation. I'm still wondering about something. Assume that I have one big data model (the main state). I build my virtual DOM from the main state. The states from all the sub-components are derived from this main state. Now, something in the main-state is changed, but the change should affect only a single sub-component in the tree. How does React know that only that sub-component needs to be re-rendered? I guess that it is still necessary to call setState on the sub-component, but I suspect that the logic to figure out which component needs to be re-rendered can become quite ugly, and prone to errors. Are they not addressing this issue, or am I overlooking something?

pests 12y ago
Basically, boolean shouldComponentUpdate(object nextProps, object nextState) Here is a good talk from ReactConf which goes over improving performance, largely including this method, here: http://youtu.be/KYzlpRvWZ6c http://youtu.be/KYzlpRvWZ6c
masterj 12y ago
> How does React know that only that sub-component needs to be re-rendered? It doesn't. By default it will render the whole tree again. This happens in javascript and is probably much faster than you think. However, when an app grows large enough, this can be a source of performance issues, which is why React provides ways you can inform it about work it shouldn't have to do, namely shouldComponentUpdate. If you can compare the data and determine that a particular sub-tree doesn't need to be updated you can implement a shouldComponentUpdate callback that does this. Immutable data that can be cheaply compared by checking reference equality is the preferred way of doing this. More info on this was recently added to the docs: http://facebook.github.io/react/docs/advanced-performance.html http://facebook.github.io/react/docs/advanced-performance.ht...
- amelius 12y ago
  Yes, I'm aware that it is possible to go around this limitation. The problem I have with this is that it kind of defeats the purpose of the library: keeping the view logic in one place.
  - pests 12y ago
    Have you looked at immutable.js[0] and the benefits PureRenderMixin[1] give you? [0] https://github.com/facebook/immutable-js https://github.com/facebook/immutable-js [1] http://facebook.github.io/react/docs/pure-render-mixin.html http://facebook.github.io/react/docs/pure-render-mixin.html
  - mikewhy 12y ago
    > keeping the view logic in one place Each component has its own logic. If you are rendering your main app state in child components you will be passing the state via props. var UserInfo = React.createClass({ shouldComponentUpdate: function (nextProps, nextState) { if (nextProps.id !== this.props.id) { return true; } return false; } }) which makes perfect sense
    - amelius 12y ago
      Imagine I have a control with a large number (say N) of sub-components. Now something changes in the state of the control, which corresponds only to one of the sub-components. This change has to propagate to the right component. However, the shouldComponentUpdate() function is invoked on each of the components. This is O(N) work. This seems unreasonable. To work around this, I could determine which component needs to change in the parent control. But this would mean a separation of logic.
      - TheCoelacanth 12y ago
        But are you really going to have a single list of 1 million components or are you going to have 1000 components that each contain 1000 components? The second case is much more common and is handled just fine. If you really do need a 1 million top-level sub-components, then you need to look at different data structures other than just a flat list

amelius 12y ago

Is it possible to automatically (without any additional code) animate the differences between two versions of the DOM? This would make it possible to, e.g., animate the creation of some space between two DIVs before inserting a new DIV in between, and animate the removal of space when a DIV disappears. This is something that is not easy in CSS alone, and could reduce much of the flickering in web-pages which potentially makes users lose their orientation (if the DIVs are large).

pests 12y ago
There was a recent ReactConf talk that included something like this. Check out the examples referencing 'magic move'. There is a YT video of the talk where this is shown but you can install the examples locally to see them yourself. https://github.com/ryanflorence/reactconf-2015-HYPE https://github.com/ryanflorence/reactconf-2015-HYPE I think does what you describe. If you want to see something cool check out the '06-itunes-style-interface' example. Implements the drop down that iTunes uses for albums or how Google Image Search has an inline drop down when you click a result. The item being left closes gracefully when you switch to another item at the same time the new item is opening.
lobster_johnson 12y ago
That's what transition groups do. When you wrap something I a transition group, it will generate events when a child is removed or added, allowing you to add required transition effects. The CSS transition group is pretty useful: When a child is removed, it is kept in the DOM, with a CSS "exit" class added (here you could have a CSS transition for opacity, for example), and then finally removed when React determines that the animation is done. Conversely, added nodes get an "enter" class. Transition groups are explicit -- you have to wrap your components in them -- and that's a good thing, as it allows you to control what kinds of transitions are used in different contexts.

chenglou 12y ago

Just a reminder: the best part of React isn't about its diffing algorithm or the virtual DOM. Plenty of articles have been written on this (e.g. https://medium.com/@dan_abramov/youre-missing-the-point-of-react-a20e34a51e1a https://medium.com/@dan_abramov/youre-missing-the-point-of-r...). The diffing algorithm is a smart way of circumventing the fact that the DOM is so slow; there's nothing to be proud of working with such thing. Ideally your platform isn't so. Web devs will keep reimplementing parts of React elsewhere; but at least, be inspired by some other parts of React please.

moonchrome 12y ago
>we can focus on examining React’s true strengths: composition, unidirectional data flow, freedom from DSLs, explicit mutation and static mental model. So wannabe functional programming in JS ? I always wondered why Facebook didn't just go all-in on clojurescript when they did React, they have the resources to deal with any compiler/technical issues, heck they could reimplement the compiler themselves they already maintain a bunch of PHP VM/language stuff. It does everything react tries to do but better and by default.
- nilliams 12y ago
  There are a huge number of people who don't enjoy programming in lisps and don't buy the tradeoff that homoiconicity is somehow worth sacrificing all syntax for. You can take 'good parts' from functional programming without going 'all in'. Many of us don't agree that the 'all in' is actually better. (See Gary Bernhardt's 'Boundaries' talk [0] for an amazing explanation of what I mean by taking the good parts of FP). React isn't really about functional programming, it's very object-oriented. And where the parent comment refers to 'composition', they mean composition of components/view code, not pure functions as you may have interpreted it as. Personally my dive into the Clojure community has been very frustrating, I find very few answers on how to actually compose large apps, and the answers I do find basically point back to OOP (but implemented in a syntax-less, ad-hoc manner [1]). If I've got this wrong, please tell me, I'm dying for better answers. [0] https://www.destroyallsoftware.com/talks/boundaries https://www.destroyallsoftware.com/talks/boundaries [1] Stuart Sierra - Components Just Enough Structure - https://www.youtube.com/watch?v=13cmHf_kt-Q https://www.youtube.com/watch?v=13cmHf_kt-Q