Be proactive, not reactive - Faster DOM updates via change propagation

One of the most important features of modern JavaScript frameworks is making minimal DOM changes when transitioning from one application state to another. This is one of the features that makes React so popular.

However, the application state is rarely presented directly by the view layer. More often the view layer presents derived data, a version of the application state that is transformed with .filter(), .map(), etc. When application state changes, both the derived data and DOM need to be updated.

In this article, we’ll explore an algorithmic technique to improve performance for displaying changes in derived data and its DOM representation. Instead of recalculating a new derived data and DOM every time application state changes, our technique will propagate application state changes into derived data changes, and subsequently DOM changes.

This can result in much faster logarithmic updates - O(log(n)) - compared to linear updates - O(n) - in Virtual DOM diffing libraries like React and VirtualDOM.

In this article we will:

Demonstrate that change propagation is faster than Virtual DOM diffing (VDOM diffing).
Explain how change propagation and VDOM diffing work.
Analyze the strengths and weaknesses of a change propagation implementation.

While technologies like VDOM diffing are adequate for most of today's applications, the techniques we'll be describing today might be necessary as more data and computing is shifted to the client.

Performance Demonstration

The following demo uses TodoMVC to compare VDOM diffing with change propagation. TodoMVC requires filtering a list of todos to only completed todos. Each demo is populated with a source list of 10,000 completed todos. Clicking the checkbox next to a todo will update the state of the source list and remove the todo from the visible filtered list.

To observe the performance differences:

Please click “render the list” in each demo.
Then check the box next to any todo. Observe the time until the todo disappears.

Virtual DOM Diffing

JS Bin on jsbin.com

Change Propagation

JS Bin on jsbin.com

You should notice that the time to remove the checked todo is noticeably faster with change propagation.

You may have also noticed that the initial render was slower with change propagation. And you might think that filtering and rendering 10,000 items is beyond the scope of most of today’s applications. We will discuss these points in the analysis section below.

For now, we only want to demonstrate that change propagation can perform array transformations like filter, map, sort, and reduce in human timescales for nearly any conceivable dataset.

In fact, change propagation can update a DOM with 100,000 todos in the same time it takes VDOM with 6 todos.

This type of scalable performance will be important as browsers are tasked with performing ever increasing amounts of data computation.

How Virtual DOM Diffing Works

The following video describes how VDOM Diffing techniques work to update a todo in a list of todos:

tldw; VDOM Diffing performs three loops: re-filtering, rendering the VDOM, and diffing the old and new DOMs. It's a linear time algorithm - O(n).

How Change Propagation Works

The following video describes how change propagation can update the DOM much faster than a linear time algorithm:

tldw; Change propagation uses Red-Black trees to update the derived data and DOM in logarithmic time - O( log(n) * log(n) ).

Analysis

There are many considerations when analyzing Change Propagation techniques, such as:

The technologies used to perform Change Propagation and VDOM diffing.
Comparing DOM update performance or solely data update performance.
The number of items in the source data S.
The number of items in the derived data D.
The number of items updated at one time U.
Initialization time.

We'll go through each of these considerations and conclude with our thoughts on the viability of change propagation in web application develpment.

Technologies Used

The code used for benchmarking can be found here. VirtualDOM is used as the VDOM diffing library because it is easy to measure different parts of the its lifecycle. can-derive is used to perform change propagation on top of can-binarytree's Red-Black tree implementation and CanJS's observables.

Currently, can-derive only supports .filter transformations. However, similar techniques can be used for other common array transformations such as:

.map
.sort
.groupBy
.reduce (reducer and expander functions would need to be passed).

As we will see in future sections, CanJS’s observables are slow compared to plain JavaScript Objects. They support expressiveness that is not used in our simple benchmarks. Our hope is that proxies can help observables close the performance gap.

Comparing Data and DOM updates with solely data updates

As noted in the section previously, sequences of array transformations like .map(fn1).filter(fn2) are common before the final result is inserted into the DOM. It's useful to distinguish the performance of only data updates from data and DOM updates.

Furthermore, while change propagation might be a viable tool for updating the DOM more quickly, it might also be useful for updating derived data from large data sets where there isn't a DOM like NodeJS or a service worker.

Where applicable, we’ll present numbers comparing:

Data only updates with Change Propagation versus native .filter.
DOM updates with Change Propagation versus VDOM diffing.

Scaling with the number of source items

The following subsections analyze how change propagation performs as the number of items in the source list grows.

Data Only updates

The following graph compares the performance of updating a list of items with change propagation versus native .filter. There are n items in the source list and the derived list. It shows the time it takes to change an item in the source list until it is removed from the derived list.

Notes:

At 1 item, change propagation is nearly 100 times slower.
At just over 100 items, change propagation becomes faster.
At 100k items, the performance difference becomes noticeable on human time scales.

Native filtering of plain JavaScript objects is super fast, especially with a simple predicate function. Even with faster observables and better optimized trees, we'd be unlikely to make change propagation faster than native .filter at 40 items.

Data and DOM updates

The following graph compares the performance of updating a list of items with change propagation versus native .filter and VDOM diffing. There are n items in the source list and the derived list. It shows the time it takes to change an item in the source list until it is removed from the derived list and from the DOM.

Notes:

At 10 items, change propagation becomes faster.
At approximately 7k items, the performance difference becomes noticeable on human time scales.

Change Propagation is faster at 10 items here instead of 100 items previously because:

VDOM performs 2 additional loops over the data on top of a .filter.
Creating a new VDOM is expensive compared to filtering and diffing.

Scaling with the derived data size

The following subsections analyze how change propagation performs as the number of items in derived list changes. The number of source items is held constant. For example:

The derived list has 10 completed todos out of 10k source todos and later, an additional todo in the source list is marked as completed.

Compared to:

The derived list has 9,999 completed todos out of 10k source todos and later, an additional todo in the source list is marked as completed.

Data Only

The following graph compares the performance of updating a list of items with change propagation versus native .filter. There are 100k items in the source list, and the derived list is at n items. It shows the time it takes to change an item in the source list until it is removed from the derived list.

Notes:

Change propagation is logarithmic with the size of the derived list. As the derived list grows, inserts into the derived list take O(log n) longer.
Native .filter is linear with the size of the derived list.
- Below 10k items, the time of looping through 100k items and running the predicate function dominates execution time.
- Above 10k items, the time it takes to build the derived list of n items begins to dominate execution time.

Data and DOM updates

The following graph compares the performance of updating a list of items with change propagation versus native .filter and VDOM diffing. There are 10k items in the source list, and n items in the derived list. It shows the time it takes to change an item in the source list until it is removed from the derived list and the DOM.

Notes:

Change propagation is logarithmic with the size of the derived list.
Above 1k items, the performance difference becomes noticeable on human time scales.
Native .filter and VDOM diffing is linear with the size of the derived list.
- Above 10 items, the additional work of creating a new VDOM and diffing it begins to dominate execution time.

Scaling with batched updates

Sometimes multiple updates can happen simultaneously. The following subsections analyze how change propagation performs as the number of simultaneously updated items increases.

Data Only

The following graph compares the performance of updating multiple items in a list of items with change propagation versus native .filter. There are 100k items in the source and derived list. It measures the time it takes to change n items in the source list until it is removed from the derived list.

Notes:

Native .filter is constant O(1) with respect to the number of updates u.
Change propagation is linear, O(u) with the number of updates.

This makes updating u items of a source list of s items into a derived list of d items take:

O(u+s+d) for native .filter
O( u * log(s) * log(d) ) for change propagation.

Initialization Time

The next subsection analyzes change propagation's initialization time - specifically how long it takes to build the first derived list.

Data Only

The following graph compares the performance of initialization of the derived data with change propagation versus native .filter. There are n items in the source and derived list. It measures the time it takes to build the derived list.

Notes:

Native .filter is linear
Change propagation is linear because the tree is built in place.
Native .filter is more than 100 times faster than change propagation.

The performance gap is due to the overhead of reading, binding to, and creating CanJS's observables and creating the predicate and derived tree.

There are many potential improvements that can improve initialization time such as:

Using observables based on proxies.
Deferring binding until the next turn.
Create the predicate tree all at once instead of iteratively.

Conclusion

At as few as 100 items, change propagation can update the DOM more than 10 times faster than VDOM diffing. While this 8ms absolute performance difference is not observable to a user, as techniques like event streams and functional reactive programming establish chains of .map, .filter, and other transforms, the 8ms differences could total to a performance cost that is noticeable on human timescales in medium sized applications.

However, the costly initialization time of the Red-Black trees used by change propagation means that it would not be appropriate for many applications except where initialization time can be sacrificed for faster behavior later.

It's our hope that we can improve initialization time with faster observables and red-black trees, eventually making change propagation techniques beneficial to a wide variety of applications.

Also published on Medium.