React React's diff algorithm


Generating the minimum number of operations to transform one tree into another have a complexity in the order of O(n^3) where n is the number of nodes in the tree. React relies on two assumptions to solve this problem in a linear time - O(n)

  1. Two components of the same class will generate similar trees and tw components of different classes will generate different trees.

  2. It is possible to provide a unique key for elements that is stable across different renders.

In order to decide if two nodes are different, React differentiates 3 cases

  1. Two nodes are different, if they have different types.
  • for example, <div>...</div> is different from <span>...</span>
  1. Whenever two nodes have different keys
  • for example, <div key="1">...</div> is different from <div key="2">...</div>

Moreover, what follows is crucial and extremely important to understand if you want to optimise performance

If they [two nodes] are not of the same type, React is not going to even try at matching what they render. It is just going to remove the first one from the DOM and insert the second one.

Here's why

It is very unlikely that a element is going to generate a DOM that is going to look like what a would generate. Instead of spending time trying to match those two structures, React just re-builds the tree from scratch.