InductJS: INcremental DOM Updates in Client-side Templating for JavaScript

2:02 PM Erik Krogen 27 Comments

Overview

Client-side JavaScript templating is widely used in modern web sites. The performance of template instantiation and rendering has a direct impact on the usability of the web site because of JavaScript's single-threaded execution model. In many cases the performance of template instantiation and rendering is dominated not by JavaScript instantiating the template, but by the browser rendering the instantiated HTML string into the DOM. Even though there are numerous libraries that implement client-side JavaScript templating, we believe that there is significant untapped potential to exploit the common use case when a template is re-rendered onto the same place in the web page, with some partial changes to the underlying data to be rendered. This can happen, for example, when the client has received new data from the server and must update part of the web page. Often developers attempt to identify manually the parts of the web page that must be updated, based on keeping track of what has changed in the underlying data and using fine-grained templates that can be rendered independently. We believe that this bookkeeping job can be done better by the templating library.

In this project we are proposing an optimization to client-side JavaScript rendering whereby upon re-rendering the template, the resulting instantiation is compared efficiently with the result of the previous rendering, and only the changed DOM elements are updated. To this end we have developed a very simple compact web templating system, called InductJS, designed to update the DOM incrementally upon re-rendering of templates. In its current form, InductJS certainly works and is definitely fast, but supports only a minimal set of templating features, enough to allow us to evaluate the performance impact of the incrementality optimizations we are proposing in comparison with two other modern templating systems: React and AngularJS. We believe that these results suggest that it may be profitable to implement these optimizations in other fully-featured templating systems.

We describe first the results of the performance comparisons with React and AngularJS, then we describe the usage and implementation details of InductJS.

Results / Comparisons

In order to test the effect of incrementality optimizations, we wrote a template for an HTML table, backed by a 2-dimensional JavaScript array, which in its base form contains 300 rows, each row consisting of an array of 15 strings elements. This benchmark is similar to other performance comparisons we have seen using long lists (Improving AngularJS long list rendering performance using ReactJS, Faster AngularJS Rendering (AngularJS and ReactJS)). We implemented a simple comparison web page (see links in the table below) that renders this template with InductJS, and also with AngularJS 1.4.0-rc.2, and React 0.13.3. We used the production builds of AngularJS and React. The comparison web page allows the user to select which templating system to use, and presents several buttons for re-rendering the template in several scenarios for changes to the underlying data, as discussed below. For every rendering, the page shows the time taken to re-render. This time is measured by taking the difference in system time before and after requesting a re-render through the current framework. Unfortunately, this does not measure the entirety of the update, since the browser will perform some extra style calculation and painting after the rendering call. Initially we attempted to force the browser to finish re-rendering completely by accessing properties (such as width) of a displayed DOM node, but found that the browser was still able to perform steps afterwards. However, we found by viewing the Chrome timeline profiler that the amount of time spent after returning from the JavaScript function was negligible in comparison to the time spent during the JavaScript execution, and was relatively consistent across different frameworks / methods of updating.

We summarize in the table below some of the performance results. Best result for each test is shown in green, and the worst result in red. The leftmost column contains the name and a description of the change-scenario considered. (The name of the scenario is shown in bold, and corresponds to the title of the corresponding control on the comparison web page.) We have found that the performance can depend considerably on whether we update a templating site on the page with text only (no HTML markup, as is the default for expressions in React and AngularJS, and InductJS's "text" templating sites), or if we allow the templating site to change the markup (React's dangerouslySetInnerHTML property, AngularJS's "ng-bind-html" directive, and InductJS's "html" templating sites). The table shows rendering times in milliseconds as measured with Chrome 42.0.2311.39 using Linux Mint 17 on an Intel i7 4750HQ processor at 2 GHz. In order to ensure higher consistency of results across different runs, we used a separate profile in Chrome, we rebooted the computer and ensured that only Chrome is running, and we opened only the browser tab with the performance tests.

A few interesting things to notice:

• We have not found a good way to obtain measurements for AngularJS's initial rendering time so we have left those items blank.
• For large changes (i.e. any of the comparisons that change a percent of the elements) using text-only sites, InductJS is far faster than any of the frameworks. This is especially interesting since in InductJS using a text-only site is an optimization, whereas in React and AngularJS it is the default.
• AngularJS has blazing fast times for re-rendering without changes. InductJS almost manages to keep up, and React lags behind a bit.
• For the operations which do not affect large amounts of the data, the performance is mostly limited by the amount of time it takes to do a full re-check (i.e. a re-render with no changes). For all three frameworks, deleting rows from either end takes a trivial amount of additional time, and InductJS/ReactJS both take a trivial amount of extra time to insert or change a row in the middle.
• Using template sites which are only capable of text vs HTML-capable has very different effects on different frameworks. AngularJS has the smallest difference, with around a 25% speed decrease when forcing it to display arbitrary HTML strings. React takes around twice as long on some large operations, and InductJS has the largest difference, with HTML sites taking nearly 4 times as long in some cases.
• InductJS and React both far outperform AngularJS for large changes, and InductJS's text optimizations are able to give it a significant edge over React on text-only sites, though this gap closes somewhat when both frameworks are asked to display arbitrary HTML strings. This may be somewhat of an unfair comparison, as in React (and AngularJS) displaying an arbitrary HTML string is nonstandard and likely not optimized.

InductJS Usage

A template is an HTML string that contains within it templating sites that are replaced with HTML content when the template is rendered. Each templating site contains one JavaScript expression that is evaluated in a context passed to the template rendering function. We implemented four types of template sites: "html", "text", "if", and "for", which are represented and rendered as follows:

"html": {{html-content-expression}}

"text": {{text literal-content-expression}}

"if": {{if boolean-expression}} inner-template {{/if}}

"for": {{for(for-variable) list-expression}} inner-template-to-repeat {{/for}}

In order to support incremental updating of the DOM, each templating site when rendered into the DOM will be wrapped inside host HTML elements, by default with the tag "span". To specify a different tag for the host element, include it between the opening braces. In case of a "for" templating site, each copy of the rendered inner template will be wrapped in a separate element. To access variables contained within the context which is passed in to render, refer to them using context.var_name (the required use of context rather than a bare variable name is a simple limitation due to the way expressions are treated; if a full expression parser was used this would be unnecessary, but that is beyond the scope of the project at this time).

For example, to display a table, we might use a markup string like:

<table> 
  {tr{for(row) context.rows}}
    <td>Row:</td> 
    {td{text context.row.content}} 
    {td{if context.row.footer}} {{'<b>' + context.row.footer + '</b>'}} {{/if}}
  {{/for}} 
</table>

Then to display this table inside of a div with an ID of "insertPoint", we would do:

rend_template = render(template,                              # the template string
                       {rows: myArray},                       # the context    
                       document.getElementById("insertPoint") # the host DOM element
);

where myArray is an array of objects such as {content: "Message", footer: "ending"}.

And, if myArray changed, to update the displayed content (note that the template you pass in must be the template returned from the initial render, not the template string):

rend_template = render(rend_template, {rows: myArray});

InductJS Implementation Details

We discuss the implementation details in the context of the same example we used in the Usage section above.

When a template is rendered for the first time, the following actions are performed:

• the template is compiled and cached: the templating sites are identified, the corresponding expressions are wrapped and cached as JavaScript functions.
• each templating site is instantiated by evaluating the expressions contained in the template, as explained in the Usage section. Each instantiated site is then rendered into the DOM, wrapped into a host element.
• when rendering a template, we construct a snapshot tree data structure with nodes corresponding to the instantiated template sites. For each instantiated template site we record the previous value of the evaluated expression (labeled "prev"), a reference to the DOM host element (labeled "host"), and references to the snapshot sub-trees recording the information for the inner templates (labeled "inner").

  { rows : [
       {content = "Row 1", footer = "Foot 1"}, 
       {content = "Row 2"}
    ] 
  }

the figure below shows the generated HTML at the right, and the snapshot tree data structure at the left:

The inner "html" template within the second iteration of the "for" template is not currently displayed, so it has host and prev values which are null. The "for" template stores a previous value which is equal to the length of the currently displayed array rather than the array itself, since the relevant content is already stored as the previous value within the inner iterations. The list-start and list-end comment nodes are used to keep track of the bounds of the "for" template's iterations; this becomes especially important when the displayed array contains zero elements.

When a template is re-rendered into the same top-level host DOM element, we traverse the snapshot tree data structure, and we reevaluate the expressions in the new context. If the expression evaluates to something different than previously stored in the snapshot, we update the DOM, and adjust the snapshot tree accordingly. However, in the common case when the expression evaluates to the same value as in the snapshot, we do not update the DOM. Even in this case, for "if" and "for" template sites, we continue evaluating the inner template sites (inner and inner_iterations) and compare with the snapshot to find more places that need to be updated.

When an "if" template that was previously false evaluates to true, its inner templates are not currently displayed (as above for the second iteration of the "for" template), so we can't perform an incremental render. In this situation, or for the similar situation where a "for" array grows in size and a new inner iteration must be added, we perform a full HTML string render and place this into the DOM, exactly as we do when we insert a template for the first time. When a "for" array has grown shorter or an "if" template goes from true to false, we simply clear out the matching content. More details about how "for" templates are handled incrementally can be found in the next section.

"For" Template Optimizations

"For" template optimizations are disabled by default, but can be enabled on a per-template basis by using "for*" instead of "for" as the template type (e.g., {{for*(row) context.rows}}). Currently the optimizations employed on "for" templates are somewhat limited, and are optimized for insertion and deletion at either end of the array. We traverse both the new and previous arrays from each end, attempting to find a "match" between the two (defined as 5 or more elements in a row that are equal between the new and previous arrays). If a match is found from both ends, items are then deleted and added outside of the match area as necessary, then the area between the two matches is updated incrementally. This allows us to attempt to leverage as much of the existing content as possible. If no match is found, we still attempt to leverage existing content by performing incremental rerendering on the existing items.

Note that each element of the array used in an optimized "for" template must be unique. You cannot have duplicate strings / numeric values and you cannot use the same object reference twice. This is a limitation due to the way the optimizations are implemented - the current location of an item within the list is tracked using a hash table mapping items to their indices, similar to what is used by React and AngularJS. Allowing a separate array of keys to be used to track elements, similar to what is required by React and available in AngularJS, may be implemented in the future.

Edit (6/26/15): In a previous version of this writeup, we have accidentally shown performance measurements using the development build of React rather than the production build. During the re-testing phase, we discovered some discrepancies in our data, and have regenerated all of the performance data with a higher level of confidence that they are consistent. Switching from the development to production build of React also removed the performance degradation from React version 0.12.2 to 0.13.3, so we have removed the older version of React from our comparisons. The discussion beneath the performance data has been adjusted somewhat to reflect the new data.