This blog will explain React Fiber Internal Algorithms, we will:
- Revisit how React diff works
- Problems with Tree Traversal
- Morris Traversal
It's recommended to have a basic understanding of React, virtualDOM, and diff before reading this blog.
You can first experience the difference between React Fiber (v17+) and pre-Fiber (v16) by playing with the playground below:
Controls
Preview
You can tell a huge difference between the two versions, the old reconcilor is very slow, but the fiber one is very smooth.
Diff Calculation of React
React's diff calculation is based on the virtualDOM, which is a tree structure that represents the UI. When a state change happens, React will calculate the difference between the old virtualDOM and the new virtualDOM, and then apply the changes to the realDOM.
However, calculating the edit distance of two trees is NP-Complete, and the standard algorithm needs at least a runtime of O(n^3). There are papers that show that the problem is NP-Complete.
Fun Fact: Even calculating the edit distance between two strings is NP-Complete and requires dynamic programming to solve efficiently. Now imagine the complexity of calculating edit distances between entire trees!
There are papers that show that the problem is NP-Complete.
React uses a heuristic approach that compares nodes level-by-level rather than doing an exhaustive node-by-node comparison. While this may sometimes update more nodes than strictly necessary, it ensures no required updates are missed while being much more efficient than a full tree traversal. The algorithm trades perfect accuracy for speed and predictability.
You can see the heuristic approach of diff traversal in the gif below - React compares the tree level by level instead of node by node.
Problem with Recursion
What’s wrong with doing a full tree traversal for diff in the above animation?
Well, there are two problems with traversing the tree using recursion, we all know in computer science:
- For any tree recursion, the call stack is O(n)
- It is impossible to pause the traversal and stop the stack from growing while you are doing recursion.
Here is an interactive slide show of the call stack of the recursion stack:
(You can navigate back and forth using Previous and Next button)
Solution to the problems - Morris Traversal
Morris Traversal is a way to traverse a tree without using recursion. It is a linear time algorithm that uses a single stack to store the nodes.
Here is an interactive slide show of traversing the tree with Morris Traversal:
With Morris Traversal, the call stack is constant O(1) space. Runtime is O(1) for each evaluation. And you can pause the traversal anytime!
This is exactly what React Fiber is doing in their code - adding more path between the nodes to turn a tree into a graph like Morris Traversal.
React Fiber with concurrency
What you can do with fiber once you have O(1) time and space for each evaluation and being able to pause the traversal is concurrent rendering.
This is how React Fiber achieves concurrent rendering, you can see the animation below:
