How do I minimize reflow in a JavaScript Framework?

Rationale

Unlike JSON, HTML Elements are a bi-directional tree, i.e. each node stores its parent and children.  However, modern JavaScript-based templating demands stringifying HTML to reduce memory footprints and the computation costs of document.appendChild[1].  Generally, a JavaScript framework utilizes a virtual DOM to perform model updates, be it a ShadowDOM, a documentFragment, or a native JavaScript implementation[2].  In a JavaScript framework, the computationally cheapest way to set up a DOM<->Data interface is to utilize stringification methods and not document.appendChild/iterative methods.

Problem

Modern JavaScript has standardized the templating problem with template literals.  Libraries like Angular, React and Mustache encourage curly brace template replacement.  It is quickest to utilize regular expressions to determine the placement of templates such that  data-driven models can replace them.

This problem becomes important  when considering computation cost.

Defining Tree Updates

Only the subset of the tree being updated should cause a browser reflow.  It becomes necessary to define what an update is, and there are two options:

  1. Update the tree when the model tokens are updated.
  2. Update the tree when the template results are updated.

The first option is usually cheaper and requires regex.  The second option has to run the template on each pass, but allows state updates internal to function calls to invalidate the tree.

Allowing function calls in templates complicates the DOM<->Data bridge.  If internal states are changed on each function call, such that a function cannot be called the same way twice given the same inputs, then the program will produce unreliable behavior.  Functions that do not change internal state and are called the same given the same inputs are called idempotent.

Core Assumption: Idempotent Functions

Idempotent functions are a core assumption of JavaScript Frameworks utilizing automated DOM<->Data updates.  Frameworks like Angular and React update their models and render them onto the DOM frequently.  For optimization and usability, only the parts of the page being changed are redrawn with the updated model.  If the entire page were redrawn, it would be slow and complicate user-made updates occurring in drag-and-drop and form input elements.

In order to isolate changes, the data model must be checked for new data and render only what has changed.  Function calls may be removed from this invalidation check and forgo the idempotent requirement.  If, however, function calls are included in the invalidation check, then it is a strongly recommended for functions called in the model to be idempotent since they may be run multiple times prior to rendering their outputs.

You may examine the following function point that compares two models.

 

Possible Solution: Check each value of a model and compare to previous model values.  If a model value is a function, ensure the function is idempotent and repeat comparison function.

Isolating Reflow

Once a template is determined to be invalidated, the DOM tree must be updated.  In Angular, this is known as “dirty type checking“.  In React, this is known as “reconciliation“.  It is non-trivial to know which tree of the DOM must be updated, and two strategies exist:

  1. Stringify the DOM, and rebuild the path via an offset for updated templates
  2. Iterate through the DOM and store a reference to nodes containing templates

Iterative tree-search methods are slower when a) trees are deep b) search subjects are sparse.  Iterative methods must  additionally use string comparisons/regular expressions to determine the existence of templates.  It is undesirable to utilize iterative methods on a raw DOM.

Stringification methods are slower when they repeat computation.  Therefore, it is desirable to perform stringification methods once, and utilize a virtual tree to manage only the nodes containing templates.  Thus, iterative methods may be used more cheaply on the optimized tree.

A hybrid-approach utilizes stringification to pre-compute an optimized DOM tree for performing template updates.  The CSS selector of a template can be programmatically determined from a numerical string offset, given a stringified DOM.  This CSS selector can be used to obtain the DOM node parenting a template.  The template node can then be stored into an optimized “virtual DOM” to quickly manage the DOM<->Data interface.

Consider the following code which generates a selector using the :nth-of-type pseudo-class:

Given a list of invalidated templates for some model, and given an optimized tree associating invalidated templates with DOM nodes, it becomes possible to quickly update only the needed DOM subtrees. Consider the following pseudo-code that will perform a reflow:

Possible Solution: Utilize a stringification strategy to create a virtual DOM that is optimized for quickly updating invalidated templates.

Conclusions

The above described techniques compute trees using intermediate formats and utilize simplified trees.  It’s helpful to consider that these techniques are not new.  3D Game Engines utilize data structures known by gamers as, “maps” to store game world data[3].  A Scene Graph generally mimics a DOM in games and acts like the DOM<->Data bridge described above[4].  Canonically, in games, this problem is known as the “painters algorithm”[5].


1. You can understand the cost of document.appendChild by considering the underlying browser mechanism called reflow.

2. ShadowDOM is a standard mostly pushed by Google.  The documentFragment object has been around since 2013; it is a lightweight DOM that does not render the contents of the tree.  Both React and Angular utilize stringification and native JavaScript methods to pre-construct, pre-render, and sometimes update the DOM given a data model.

3. See https://en.wikipedia.org/wiki/Binary_space_partitioning

4. https://en.wikipedia.org/wiki/Scene_graph

5. https://en.wikipedia.org/wiki/Painter%27s_algorithm

Leave a Reply

Your email address will not be published. Required fields are marked *