DEV Community: thepurplecoder

Why react stopped using stack reconciler? - Blog 2

thepurplecoder — Sat, 19 Jun 2021 15:42:55 +0000

In the previous blog I've written about how React detects a change when an app moves from one state to another. Now let's implement a simple naive recursive algorithm using those concepts and analyse the drawbacks of using recursion for reconciliation.

Structure of Virtual DOM - Naive algorithm

Please note that the following algorithm is just to give you a gist of how React 15 worked before in a simple way.

We all know the real DOM follows a tree data structure and each node has a property called children which contains all of the references of the child elements.

Let's follow the same tree structure for each node of our virtual dom as Virtual dom is just a clone of real dom.

type VirtualElement{
   type: string | object,
   /* 
             If the element is a host component like div type will be a string('div')   
             If the element is a custom react element type is the reference of class/function
  */
   props: any,
   children: Array<element>
}

When an element is created via React.createElement we will attach the element to our virtual dom by attaching the element to its parent node as a child.

Example

ReactDOM.render(<div> <span> Hello Virtual DOM <span/> </div>, rootEle);

The virtual dom of the above code will be

{
  type: 'h1',
  children: [
    {
      type: 'span',
      children: ['Hello Virtual DOM']
    }
  ]
}

Please note that I've omitted most of the keys like ref and key for simplicity.

Steps of the naive algorithm

Now that we've designed our virtual dom structure let's discuss the steps of the naive algorithm using the below code as an example.

The below example will be considered as a reference throughout this article


class App extends Component{
    state = {
        message: 'Hello'
    }
    onChange = (e) => {
        this.setState({message: e.target.value });
    }
    render(){
        const { message } = this.state;
        return(
            <ul>
                <li> 
                       <span>${message}01</span> 
                       <span>${message}02<span> 
                       <span>${message}03<span>  
                </li>
                 <li> 
                       <span>${message}11</span> 
                       <span>${message}12<span> 
                       <span>${message}13<span>  
                </li>
                 <input value={message} onChange={this.onChange}/>
            </ul>
        )
    }
}

ReactDOM.render(<App/> , rootEle);

Structural representation of virtual dom for the above code

Algorithm - Steps

When ReactDOM.render is called for the first time we will create a virtual DOM by iterating the first element i.e App.
While creating virtual dom we will create the corresponding DOM nodes and append the element to its corresponding parent.
Whenever any state changes through setState we will mark it as dirty and pass it to our reconcile function.
Reconcile function accepts currentNode as a param and recursively reconcile every element present in the currentNode tree to find the change and update the corresponding change in DOM too.
If the current node is changed/added/deleted because of an update we will change its attribute or delete or add the node to our virtual dom and real dom. shouldComponentUpdate or React.memo or PureComponent checks will be handled in this step.
Get children of the currentNode by calling it's render method if it is a class component or currentNode(props) if it is a function component with updated props.
Iterate through every child of currentNode and go to step 5 for reconciling every child.

FlowChart

The algorithm for React 15 and its previous versions works almost the same as the above that we've discussed though React15 implements more concepts like Batching etc...
Since it relies on recursion which uses call stack to track the currently processing node, we call this as Stack Reconciler.

Stack calls for the recursive algorithm

Drawbacks of stack reconciler.

Let's imagine that in our App there are 1000 li items and each item takes at least 1000 ms to reconcile(render). Now our main thread will be stuck for 1000 seconds for processing each update. If the user types something, it will process the update only after finishing the current update. The main thread is spending more time on low priority tasks like updating li items rather than a high priority update that users can easily perceive if there is a delay.

We can solve this by synchronously performing high priority task and then incrementally perform low priority task by scheduling them using requestIdleCallback or Task Queue. Before we start processing the next node in a low priority update we will check if we reached the deadline. If there is still time remaining we will process that node and if there is no time remaining we yield our task or empty the call stack so that the main thread can process some other important updates and schedule the next update in the next frame.

Notice that in a low priority update we have to interrupt the stack when the deadline is passed and have to resume the update in the next frame. In our recursive algorithm if we empty the stack in the middle of reconciling we will lose track of our updates and the nodes that are already processed.

We can save our progress in a variable to keep track of it, but whenever we interrupt and process the next update in the next frame we have to rebuild the stack in that little amount of time (16ms)which is not idle for an efficient UI library. That's why react team modified their virtual DOM structure in React 16 so that it doesn't couple to JS stack and also makes it easier to interrupt the reconciliation process.

In the next article, we will learn about Fiber which is used in React 16 which is easily interruptible while reconciling in an optimized manner.

React 16 or higher modifies the virtual DOM structure only so that it is interruptible if we enabled the experimental feature concurrent mode.

The basics of React internals - Blog 1

thepurplecoder — Sun, 13 Jun 2021 16:42:49 +0000

React is one of the most popular javascript libraries for building user interfaces. The main advantage of react is when an update happens it only updates the DOM elements that need to be updated. It achieves this by using virtual DOM which is nothing but an internal representation of our UI.

Let’s try to understand how react manages virtual dom and how it evolves the virtual dom structure to support concurrent version.

For those of you who just want to get a gist of react internals I highly recommend to watch Lin Clark 's video of react fiber.

Let's start with the basics.

JSX

React introduces JSX for better developer experience. JSX is a syntactic sugar for React.createElement(type, props,...children) or _jsx/ _jsxs

For example when we define a component like this

the babel compiler transpiles the above code to

And in current versions *_jsx will be there instead of React.createElement. Both performs the same. _jsx was created for improving our React development experience.*

React.createElement returns a JS object describing the node and its properties.
Eg:

const profile = <h1 className='welcome'>Hello World </h1>

would return something like this

{
  type: 'h1',
  props: {
     className: 'welcome',
     children: ['Hello World']
  },
  ref: null,
  key: null,
  $$typeof: Symbol(react.element)
}

The returned element has the following properties.

type
The type of the element
If it is a custom react element the type would be the reference of the function/class of the element.
If it is a host element(like div in DOM) the type would be a string one
props
The props of the element like its children or colour etc.,
$$typeof
This key is just to ensure the component is created from react to prevent XSS. Dan Abramov has explained the importance of key in this article. Do check that out.
key
It is used to uniquely identify the element in case the type of the element is not enough to identify it uniquely.
ref
Reference of the instance if it is a custom react element or the dom node reference if it is a host element

Using this object builds a tree-like data structure i.e virtual DOM and stores it in memory.

Reconciliation

When an update occurs react uses the previously constructed virtual dom and generates a new tree based on the update. React compares these two versions and updates the elements in the DOM efficiently. This process is called Reconciliation

But if react actually compares every node/object in the tree with its previous version, it'd be time-consuming right?. To avoid this react uses a heuristic algorithm that is based on the following rules.

Elements of different types will generate different branches and subtrees

Eg:

<div> Hi I am a div </div>

If the above element changes to the following element,

<span> Hi I am a span </span>

Then react will delete the div and appends span into its parent. Similarly, if

<Hello/>

/* Changes to */

<Bye/>

Then react will unmount Hello element or its instance and mounts Bye

Elements of the same type

If the type of both the elements is the same it will check whether the props changed. If it is changed it will then modify the props of the element. Simple!

Eg:

<Message text='Hi'/> ==> <Message text='Bye'/>

will modify the text property from 'Hi' to 'Bye' in the Message instance.

<div className='active'/> ==> <div className='inactive'/>

will modify the class of the div element

Elements of the same type but with different properties

Let's say we want to list a bunch of fruits like the following

<ul>
  <li>Banana 🍌</li>
  <li>Cherry 🍒</li>
</ul>

And due to an update, we append an entry to the first child of ul element now our component will look like this.

<ul>
  <li>Apple 🍎 </li>
  <li>Banana 🍌</li>
  <li>Cherry 🍒</li>
</ul>

Since react is working on our above-said rules, react will do the following

Checks ul element type first. Since it is the same in both versions it proceeds to check its props. Since children are changed(Reference will be changed) it starts to check every li element
Checks the first element of ul element i.e li in both version since the text content is changed from Banana 🍌 to Apple 🍎, it updates the change to the DOM. Then it proceeds to check the next element
Now it checks the second li element and updates the text change to the DOM from Cherry 🍒 to Banana 🍌
Then it finds out that there is a new element created at the bottom. So it creates a new li element and appends the element to the ul element.

Have you noticed anything unusual in this behaviour? Apple is the one that was appended to the first but react is updating the other two items unnecessarily, right? i.e Instead of performing a single update, react is performing three updates.
To avoid this react has introduced the key to uniquely identify each element.

Elements of the same type but with different keys will be uniquely identified and updated now. So if we introduce key to the above example

<ul>
  <li key={1}>Banana 🍌</li>
  <li key={2}>Cherry 🍒</li>
</ul>

<ul>
  <li key={0}>Apple 🍎 </li>
  <li key={1}>Banana 🍌</li>
  <li key={2}>Cherry 🍒</li>
</ul>

Now react while comparing the first element knows that Apple 🍎 is newly added to the list and performs that single update.

Please do note that using index as key may create some issues especially when each of your components has an internal state and reorders between list is pretty common. Check this codepen for more details.

In the next article, we will try to create a naive react algorithm or the algorithm which relies on recursion by implementing the above concepts.

*P.S: This blog-series is largely inspired from this amazing blog written by Max Koretskyi *