Inventing a Data Structure for Faster React Lists
Have you ever created a long list in React? Rendering any updates to the list, like adding a single element, will cause the whole page to lock up for a hundred or more milliseconds.
How could a common case like rendering a long list be so unoptimized? Why hasn’t anyone improved on React’s list rendering algorithm?
Virtual lists
One answer is that the React community has found a clever solution around this problem of slow lists: virtual lists. The idea is you only need to render the few elements which users can actually see.
You’ve seen the beautiful demos. A list of 10,000 elements that you can scroll through at 60 fps, while the browser creates and destroys DOM nodes just in time to fill your scroll view.
Virtual lists are amazing tech, but when you try using them, you start to realize how they’ve been oversold. Namely, if your list’s children have more than a few divs each, the DOM cannot be updated fast enough.
Users scrolling your list will start seeing a lot of blank space while the browser struggles to keep up its rendering. Worse, if any one of your children has a couple dozen divs, the whole page will stutter when it is rendered. Yuck!
It’s inescapable that scrolling on a website takes nearly all the 16 ms budget you have per frame, leaving precious little time to render new nodes.
The keep-it-in-memory approach
Our approach is to not do any work while the user is scrolling. Instead, we assemble a long list of DOM nodes for them to scroll through freely, built up over multiple renders. Computers have enough memory; why shouldn’t we use it to make users’ experience better?
But in order for this to work, we need to solve the problem posed at the outset. If we are inserting elements into an already long list, how can we speed up React’s diffing and rendering algorithm? We want to find a solution from within React.
It’s time to buckle up, put on our nerd glasses, and do some computer science!
List diffing
If React takes so long for list changes, does that mean finding the differences between two lists is computationally intensive in general?
To our surprise, the problem is relatively tractable. In particular, jsdiff has a great, fast implementation.
Their algorithm computes the shortest sequence of inserts and deletes to transform one list into another. This takes time in proportion to the size of the two lists, N, times the number of required insert and delete operations, D, or O(ND).
In our experience, you never want to add or remove more than a constant number elements at once or the DOM would lock up for too long. (For example, it’s not a good idea to shuffle 1000 children at once.) For most practical uses then, the algorithm runs in O(N) time, which is great. Experiments verified it is indeed fast.
Our strategy then can be to take control of diffing children. We can tell React which children to render and when. Not only will it be faster than the current diffing, but because jsdiff guarantees the optimal edit sequence, we will create and destroy the fewest possible DOM nodes!
React trees
How do we hack React to render just the changes we want? React handily lets us skip rendering in cases like when the props don’t change for a memo’ed component.
What if we leverage this capability while splitting the list over several components? Then if a particular section of the list didn’t change we could skip rendering it.
Even better, our insight is to build some kind of balanced tree of React fragments, allowing us to skip over whole subtrees that didn’t change, and still render the children identically to a plain list.
This could all be encapsulated in one wrapper component, which takes a list of children and renders them efficiently in a tree of React fragments.
Putting this together, our solution is taking shape nicely:
- A wrapper component receives a new list of children through its props
- We use jsdiff on the new and old children to get a list of insert and delete operations
- We apply these operations to a balanced tree data structure
- Finally, we render a tree of React fragments of children to exactly mirror our tree data structure
Sweet! Now we just have to implement our tree data structure. How hard could it be?
Ordered, balanced, and frozen
There’s a hidden constraint imposed by React that makes this problem much, much harder.
Typical tree data structures like the red-black tree maintain their balance by doing tree rotations. When a section of the tree gets crowded, some elements get shifted to a less-crowded section in a way that preserves ordering.
Alas, we don’t have the luxury of being able to move children between React fragments. Why? The reason is that as soon as we render a child in a different fragment, even if it’s with the same key, it won’t be recognized as the same child by React and will be destroyed and recreated in the DOM.
Thus, we need to invent a tree with a frozen parent hierarchy that maintains balance and ordering.
Arriving at a solution
One promising idea is that when inserting a child we could occasionally spawn a whole new node to grow the tree out. If the tree spawns more nodes in places where lots of elements are being inserted, the tree could grow out balanced branches.
In the diagram above, we could insert ‘3’ in two different places while preserving ordering. (Can you see where?)
About this time, a little voice in my head spoke, and I knew at once it had spoken true. “Randomized algorithms,” it whispered.
And, indeed, it was the perfect opportunity to use a randomized approach. By sprinkling around new nodes, we could get closer to an even distribution! We could even adjust the probabilities. If one node starts to get too many children, perhaps the probability of adding new children to that node could decrease?
The insertion algorithm goes like this. You start at the tree’s root, and check if you can insert your element as a child between any children nodes (based on required ordering). If so, you do a random check:
Math.random() < Math.pow(0.7, node.children.length)If true, you insert that new child. (You also insert it if it’s the only possible spot, i.e. there are no adjacent nodes to insert into.)
What makes the analysis work is that the chance this is true decreases exponentially with the number of children the node currently has. For example, if the node has 0 children, it always inserts the element here. With one child it has a 70% chance, and in the diagram above, it would have a 0.7 ^ 3 = 34.3% chance of inserting 3 as a child of the root node. Crucially, by this scheme, the number of children for a node grows at most in proportion to log(n) after n insertions.
Whenever the algorithm inserts an element, as above, it does another of the same random check. If true, it adds the element directly, and if false, it adds a new node with the element as its first child. This helps grow our tree. When a node has many children already, the algorithm is more likely to create a new node, which could carry even more new children.
Otherwise, if we haven’t inserted the element yet, there is a child node we can insert it in. In the diagram above, if the random check failed, it would move to inserting 3 within the node that has 4 and 5. Finally, the algorithm recurses! Whew!
Removing elements is as simple as finding them in the tree and deleting them. (You can also delete the parent(s) if the deleted element was its last child.)
The result
Great, so we’re done! Will the insert and remove operations be fast? We’ve argued each node has O(log n) children, and I conjecture the tree has depth O(log n). If I am right, both insert and remove are O(log² n) operations because they could iterate through the children at each level of the tree. In other words, it’s sub-linear, which is fast enough!
The pieces I’ve laid out all come together in a very satisfying way. We can write React hooks that encapsulate the diffing and tree operations respectively. And only one component is needed to render the elements of our tree structure recursively inside React fragments.
Take a look at the end result, our optimizing wrapper component called FastChildren, which is magically concise:
First, useChanges runs the jsdiff algorithm to compute the children changes since the last render in the form of inserts and removes. Then useChildrenTree applies those changes to a tree data structure that is ultimately rendered by the ChildrenTree component.
To use it, wrap any group of children like so:
<FastChildren>{manyChildren}</FastChildren>When using FastChildren, keep in mind:
- Each child must specify a ‘key’ prop
- Each child is only rendered once, when inserted (unless you change the key to trigger re-insertion!)
Beyond these gotchas, FastChildren can work nearly anywhere as a general purpose improvement to React’s diffing algorithm.
See for yourself
Try using FastChildren in your own projects! Download our npm package react-fast-children, or check out the source code. I hope you find a use for it or the underlying data structure.
At our startup, we use this to load 500+ chats in a list, while supporting further live insertions. Our vision is building chat that scales to hundreds or thousands of people at a time, with nested replies appearing constantly up and down the whole list. Needless to say, this tech has been crucial! Check out our site: https://throne.live
Thanks for reading! If you want to leave a comment or see this used in a production app, head over to #ReactFastChildren, a chat room I created for us!
