Million.js - The Future of Virtual DOM

Plug: I work on Million.js: <1kb virtual DOM - it's fast!

TL;DR

Virtual DOM needs to leverage the compiler, so that unnecessary diffing is not incurred.

Introduction

Recently, I published some articles detailing the Virtual DOM paradigm, implementation, and the benefits and flaws using it. These articles received mixed reception, with some developers agreeing with the points in the article, while others disagreed. They argued that compilation based frameworks that do some level of static analysis (notably Svelte) compile to imperative DOM operations and therefore bypass the overhead of a Virtual DOM engine.

You may be wondering: What's the point of using Virtual DOM, if you can just use a compiler-based framework like Svelte? While static analysis and compilation is the future, Virtual DOM should not be completely ruled out as an obselete technology. Svelte only is possible if API conditions are constrained, so that the code is predictive and therefore analyzable. For libraries that need more flexibility, such as React or Vue, conditions cannot be constrained easily and therefore a variant of the Virtual DOM is necessary for those libraries.

This is why Million.js exists—to bring the Virtual DOM into the future by leveraging the compiler for static analysis and optimizations that makes DOM manipulation be performant and flexible.

Virtual DOM Optimizations

Traditionally, Virtual DOM engines do a significant amount of computation during the diffing process. For example, when diffing children, the Virtual DOM engine not only linearly calculates which nodes need to be updated, but also determines the possible swaps/moves that can be done. Although this incurrs the least amount of DOM modifications, the computational cost can be great. Even with extremely efficient list diffing algorithms (like list-diff2), the time complexity is O(n) in the best case (not including the O(n^3 time complexity baseline for diffing). Repeat this for all the children in a vnode tree and you can just imagine how inefficient this can be.

This is why one of the major concepts to create a future oriented Virtual DOM is to be aware and construct the architecture based on the compiler. This not only increases performance by allowing for straight O(1) operations, but also gracefully falls back to normal diffing when necessary. Additionally, bundle sizes decrease significantly, reducing the amount of code that needs to be executed at runtime.

Keys: Specify the identity of a vnode

Keys are useful when you know that a certain vnode's position, data, and children will not change between two states. Keys can be provided by the user manually, or generated by the compiler. This allows for the vnode to be skipped entirely, avoiding unnecessary diffing (O(1))

Flags: Specify the type of content of a vnode's children.

Flags allow for diffing to skip certain computationally expensive condition branches. For example, if the vnode's children only contains text nodes, then just setting the textContent of the element would be significantly faster than constructing and replacing a text node. Million.js currently only supports 3 flags: NO_CHILDREN (O(1)), ONLY_TEXT_CHILDREN (O(n)), and ANY_CHILDREN (O(n^3)).

Deltas: Specify predictive and consistent modifications of a vnode's children.

Deltas can be utilized when simple, imperative micro-actions can be predicted through static analysis. Deltas by default are a series of imperative operations, but leverage the internal diffing algorithm to reduce DOM manipulations. Million.js currently supports 3 fundemental Delta operations: INSERT (O(1)), UPDATE (O(1) to O(n^3)), DELETE (O(1)).

Compiler Optimizations

First off, most—if not all of the implementation complexity will be with the compiler. This is because static analysis is really hard to pull in a way so that it operates as intended. Below is a list of possible optimizations, and is by no means "real static analysis."

Leveraging Million.js features:

The primary way to optimize for Million.js is just leverage the compiler-focused features that it provides. This is the only way to reduce diffing assuming that the patch scope remains constant.

Prerendering + reducing dynamic content

Another way of making performance better is to not even consider static content by reducing the patching scope—especially if your application is only interactive in certain areas. This is even more efficient than generating imperative DOM operations, as DOM manipulation won't even be needed! Additionally, the initial vnode should be prerendered the page, so that the page doesn't need to be fully initialized at runtime.

Bad:
<div></div> inject <button>Click Me!</button>

Good:
<div><button>Click Me!</button></div>

Static vnode + props hoisting:

A standard optimization to hoist vnodes and props that are static, allowing them to be cached and incurr no generation computational cost. This is best illustrated with a code sample:

// Without static VNode hoist
const render = () => patch(el, m('div', undefined, [`My favorite number: ${1 + 2 + 3}`]))
render();
render(); // Static VNode needs to be constructed twice

// With static VNode hoist
const _s = <div>Hello World!</div>
const render = () => patch(el, _s)
render();
render(); // Static VNode is used twice and cached

// Without static props hoist
const render = () => patch(el, m('div', { id: `app${1 + 2 + 3}` }))
render();
render(); // Static props need to be constructed twice

// With static props hoist
const _s = { id: `app${1 + 2 + 3}` };
const render = () => patch(el, m('div', _s))
render();
render(); // Static props are used twice and cached

Note: If you feel that this sort of paradigm has a future and are willing to meet those ends—I highly recommend you check out Million.js and try working on an implementation of a compiler yourself.

Conclusion