What is diff algorithm?

As evident from its name, the main work of a diff algorithm is to find a heuristic to change anything from a state to another. Let’s say  there is a text A and with the minimal number of steps, it has to be changed to text B. The basic idea is to find a ‘modification script’ that will turn Text A into Text B. The scripts includes insertion and deletion. Usually, the minimal number of changes is required, but some application might also have to weigh the operations depending on how much text each one affects, or other factors.

 

Why is it needed in React?

The first time we render a react component, a tree of all the elements is made(point A). On the next update of any state or prop element,  the render() function is called again to update a different set of react elements(point B), what react needs is to identify the fatest/ minimal utilisation of resources to react from point A to point B. The general solution to this problem has  a complexity in the order of O(n3), where n is the number of elements in the tree.

 

How React approached this problem?

If we used the above approach in React, displaying 1000 elements would require in the order of one billion comparisons. This is far too exhausting and time taking. Instead, React implements a heuristic O(n) algorithm based on two assumptions:

  1. Two elements of different types will produce different trees.
  2. The developer can hint at which child elements may be stable across different renders with a key prop.

 

  1. Different root element

If the root element is different , it completely tears down the old tree and begins from the root of the new tree

Example:

 

Point A Point B
<p><MyComponent></p><span><MyComponent></span>

 

In the above case it will unmount(componentWillUnmount) point A and mount (componentWillMount followed by componentDidMount) point B.

 

  1. Same root element

If the root element is same, then the algorithm compares each and every difference in attributes, keeps the same valued attributes and changes only the new/differed attributes.

 

Point A Point B
<div className=”component-1” style=”color:red;background-color:black;font-weight:bold;”>test</div><div className=”component-2”  style=”color:black;background-color:blue;font-weight:bold;”>test</div>

 

  1. By comparing these two elements, React knows to only modify the className on Point 2.
  2. When updating style, React also knows to update only the properties that changed.

 

  1. All the Elements are Of The Same Type

When a component updates, the instance stays the same, so that state is maintained across renders. React updates the props of the underlying component instance to match the new element, and calls componentWillReceiveProps() and componentWillUpdate() on the underlying instance.

Next, the render() method is called and the diff algorithm recurses on the previous result and the new result.

  1. Recursion on Child elements

React generates a mutation comparing each and every element of the previous and the new list.

 

Point A Point B
<ul>
 <li>a</li>
 <li>b</li>
</ul>
<ul>
 <li>a</li>
 <li>b</li>
 <li>c</li>
</ul>


React will match the two <li>a</li> trees, match the two <li>b</li>trees, and then insert the <li>c</li> tree.On the other hand, inserting an element at the top performs badly. For example, converting between these two trees works badly:

 

Point A Point B
<ul>
 <li>a</li>
 <li>b</li>
</ul>
<ul>
 <li>c</li>
 <li>a</li>
 <li>b</li>
</ul>

React will mutate every child instead of realizing it can keep the Point A subtrees intact. This inefficiency can be a problem.

  1. Use of key:

To solve the above problem, React came out with the ‘key’ attribute.

 

Point A Point B
<ul>
 <li key=’1’>b</li>
 <li key=’2’>c</li>
</ul>
<ul>
 <li key=’3’>c</li>
 <li key=’1’>a</li>
 <li key=’2’>b</li>
</ul>

In the above scenario React compare the two list and does not change the attributes having the same key value.(The key needs to be unique)

Looking for ReactJS Development Company, Hire our dedicated developers!

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

This site uses Akismet to reduce spam. Learn how your comment data is processed.