Why react stopped using stack reconciler? - Blog 2

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

1. When ReactDOM.render is called for the first time we will create a virtual DOM by iterating the first element i.e App.
2. While creating virtual dom we will create the corresponding DOM nodes and append the element to its corresponding parent.
3. Whenever any state changes through setState we will mark it as dirty and pass it to our reconcile function.
4. 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.
5. 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.
6. 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.
7. 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.