🕊 VDom Reconciliation

Reconciliation is a fundamental part of any virtual DOM implementation and as far as I can tell is where most of the complexity and the potential pitfalls and bugs lie. At its most simple, it’s the problem of syncing the real DOM with the virtual DOM, and in particular taking care of updates. Therefore, it’s helpful to look at how it is handled in various projects, as well as to get a handle on the general nature of the problem.

General statement of the problem

Given a tree of virtual DOM nodes it is fairly straightforward to produce a corresponding DOM tree, especially if we’re dealing with the “simple case” of virtual DOM where there are no 🔧 VDom components. We can start with the root node, create a DOM node which corresponds to it, and then recur down the tree through the children, adding new children to the DOM nodes we’ve already created to match our virtual DOM tree structure. This is the easy case and is basically what we do on the first render.

Immediately after that (i.e. at the second render) we’re confronted with a different problem: how do we figure out what we need to update, and how do we keep our updates performant? We’ll be passed a new virtual DOM tree (we don’t worry now about where that comes from or how its calculated) and we need to make changes to the DOM to reflect that new tree so that the user sees the right view.

The simplest possible answer would be to re-render the whole tree, creating an entirely new DOM tree based purely on the new virtual DOM tree which we could then just swap in for the current DOM tree. This would work and possibly be fine for very low interactivity applications with small numbers of DOM nodes, but even though computers are fast this would run into some obvious performance issues very quickly.

So instead what we have to do is figure out a performant way to update the existing DOM tree in-place in order to create a DOM state that matches the new virtual DOM tree.

To put it a bit more formally, let V be the set of all virtual DOM trees (aka the virtual DOM treespace) and let v_{cur}, v_{next} \in V be our old and new virtual DOM trees (current and next). Then let D be the set of all actual (or concrete, I sort of prefer that terminology) DOM trees, and let d_{cur} \in D be the current state of a DOM tree which we assume accurately reflects v_{cur}. There is then some tree d_{next} \in D which is a (currently hypothetical) DOM tree which matches up with v_{next}, or, put another way, if we have some function render: V \to D which maps from the virtual DOM treespace V to the concrete DOM treespace D then we assume render(v_{cur}) = d_{cur} and render(v_{next}) = d_{next}. The problem we’re confronted with then is, more or less, that we assume render to be expensive, and therefore simply swapping out render(v_{next}) for our current tree is impractical.

So then we’ve got to figure out, based on comparing v_{cur} and v_{next}, how to carry out some sequence of transformations S on d_{cur} which will transform it into d_{next}. This is the core of the problem because, to restate, we could always just use render(v_{next}) but we’d like to avoid that because we assume that, in practice, it will get expensive. It turns out that computing the edit script S is something which can be done exhaustively: there are published algorithms which will find a script which minimizes the edit distance between two trees¹. In a perfect world we’d just use one of those and be off to the races! But unfortunately we won’t get away with things that easily. It turns out that until recently the published algorithms for finding the minimal edit script between two trees ran in cubic time (O(n^3))², which means that for a reasonably large but not huge number of nodes in a tree (say 1000) we’d be looking at performing something like a billion comparison operations in order to find the minimal edit script. Not acceptable!

Thus in the real world we need to use some sort of heuristic in order to transform d_{cur} into d_{next}.³ Different virtual DOM implementations use different heuristics for this, I’m going to review them here, describe the current heuristic used in Stencil, and try to produce some useful comparison / summary of tradeoffs between them.

React

The React devs have published a few technical articles details of how React works, including one about reconciliation.

Diffing algorithm

According to their documentation, React’s diffing algorithm works like this, operating on a pair of trees (the old tree of vdom nodes and the new tree):

1. let newTree be the new vdom tree and oldTree be the old one
2. let newRootVNode be the root node of newTree and let oldRootVNode be the root node of oldTree
3. does newRootVNode.type equal oldRootVNode.type? Type here is basically the element type set in 👩‍🔬 JSX (i.e. the first argument to whatever function processes the JSX) so it could be an HTML tag name like div, span, etc, or it could be a user-defined component like ProfilePicture, Comment, whatever
   1. if they’re not equal, then delete the whole DOM tree rooted at the concrete DOM element corresponding to oldRootVNode and replace it with a new DOM tree created based on newRootVNode
   2. if they’re the same, then
      1. is newRootVNode.type a DOM element or a custom element?
      2. if DOM element:
         1. let rootDOMNode be the DOM node created for oldRootVNode
         2. assign attributes to rootDOMNode for any which are different between newRootVNode and oldRootVNode
         3. assign rootDOMNode as the DOM node for newRootVNode
         4. iterate through the children of newRootVNode and oldRootVNode. let i be the index from 0 to newRootVNode.children.length:
            2. do either of the i-th children have a key prop set on them?
            3. if so, search the other array of children for a VNode with the same key and, if found, recur diffing those two children
            4. else, recur diffing the i-th children
      3. if custom element:
         1. update props of the underlying component instance
         2. let newRenderOutput be the output of the render() function (or just call the function in the case of a function-based component) and let oldRenderOutput be the previous render output. Note that both of these things are trees of VNode objects
         3. recur diffing newRenderOutput and oldRenderOutput

An important point here, and something which was apparent to me in reviewing and documenting our updateChildren method in Stencil, is that any reconciliation algorithm is basically attempting to identifying when and where DOM elements can be preserved across re-renders. As long as the cost of doing these comparisons is less than the cost of just recreating the whole DOM tree it saves computation, but it really is always a “best effort” sort of thing - there are cases where it is ambiguous or too expensive to figure out which elements should be preserved, and in those cases the thing to do really is to just re-render.

For instance, on thing of note is that React makes no attempt to re-use any DOM nodes within a tree if the root node needs to be thrown out. This seems wasteful but is probably fine almost all the time, and I would imagine that if you need children to be preserved the thing to do would be to refactor so that their parents have the same tags.

Just consider how complicated it would get to figure out when nodes buried deep in a tree could get hoisted out and re-used…

Snabbdom

Millions

Preact

Preact’s virtual DOM API is a bit simpler than some others, notably it is quite a bit simpler than React. Instead of having to do a createRoot, call some sort of function to render into that root, and all that, Preact instead just exposes a single render function to the user. This can be called once by the user.

• they store information about the previously rendered tree on the DOM
  • I didn’t really expect that…a bit odd no?

src/render.js:L23-L30

    // To be able to support calling `render()` multiple times on the same
    // DOM node, we need to obtain a reference to the previous tree. We do
    // this by assigning a new `_children` property to DOM nodes which points
    // to the last rendered tree. By default this property is not present, which
    // means that we are mounting a new tree for the first time.
    let oldVNode = isHydrating
        ? null
        : (replaceNode && replaceNode._children) || parentDom._children;

looks like they diff the new vnodes with the old ones and produce a queue of edits that need to be made to the DOM, which are then committed in one step

src/render.js:L39-L65

    diff(
        parentDom,
        // Determine the new vnode tree and store it on the DOM element on
        // our custom `_children` property.
        vnode,
        oldVNode || EMPTY_OBJ,
        EMPTY_OBJ,
        parentDom.ownerSVGElement !== undefined,
        !isHydrating && replaceNode
            ? [replaceNode]
            : oldVNode
            ? null
            : parentDom.firstChild
            ? slice.call(parentDom.childNodes)
            : null,
        commitQueue,
        !isHydrating && replaceNode
            ? replaceNode
            : oldVNode
            ? oldVNode._dom
            : parentDom.firstChild,
        isHydrating
    );

    // Flush all queued effects
    commitRoot(commitQueue, vnode);
}

Somehow though once you call render once if you have a state update or anything like that then Preact seems to auto-update the component, I think basically preact is like a reactive virtual DOM hybrid of sorts.

• is this accurate, that the render function basically sets up listeners which will re-render in the case that a prop changes, that a value changes, etc?