Smarter redrawing: diff a tree of values rather than a tree of virtual DOM

[tobyzerner]

Mithril/React's approach of rebuilding and diffing the entire virtual DOM each time something changes is very performant. However, as virtual DOM construction becomes more complicated, and results in larger numbers of virtual DOM elements, performance starts to get pretty bad — especially (but not exclusively) on mobile devices with slower processors.

I've reached a stage in my app where if I have a list of ~400 complicated vDOM constructions (~40,000 elements on the page) then I get a 300ms freeze every time a redraw is triggered. In terms of UX, this kind of delay is acceptable for the initial creation of the tree, but not at all for small interactions (e.g. toggling the visibility of a tiny piece of DOM.)

There are some decent optimizations that can be considered at this stage, namely:

• Subtree directives (retaining a certain part of the tree based on a value dirty-check)
• Partial rerendering (only rerendering part of a tree if you know nothing outside of it will have changed)

However, I think these feel a bit awkward, and aren't solving the root of the problem. The root of the problem is that constructing the whole vDOM tree from scratch every redraw involves performing a lot of work that has already been performed before, just to work out what's changed — even for things that couldn't have changed (e.g. static nodes).

I want to start a discussion about the approach of Ember's new Glimmer rendering engine to see if any of it can be applied in Mithril. Glimmer solves the "unnecessary work" problem by using declarative templates so it knows which parts of the DOM are actually able to change. Then, on a redraw, it only has to compare the tree of values bound to these dynamic nodes, rather than the whole vDOM. The approach is explained in detail in this video: https://youtu.be/msS-3zqKKUI?t=1h14m38s

Obviously, the big problem with bringing something like this to Mithril is that Mithril's templates plain JavaScript code, and they are not declarative. My first thought is to make use of the m.prop getter-setter API, and pass functions into the vDOM, something like:

app.controller = function() {
    this.foo = m.prop();
}
app.view = function(ctrl) {
    return m('div', ctrl.foo);
}

The view function would only be invoked once, and any functions passed as attributes or children (like the ctrl.foo getter-setter) would be retained and diffed on subsequent redraws.

Here's a more complex example: https://gist.github.com/tobscure/7686531d35f10875c2e2

I don't expect this idea to really go too far, because it would be a huge API/conceptual change for a reasonably well-established framework (Ember are lucky that they were already using declarative templates!) But I thought it would be worth bringing up to see if there are any performance-related ideas that can come from it, or if there might be a way to implement some kind of smarter rendering without BC breaks.

[lhorie]

The last time this topic was brought up, the question I was asking was whether the user can actually digest 40,000 DOM elements worth of stuff on screen. For example, people aren't realistically going to grok a 1000 row table. Not saying this is always the case (and it might not be the case for you), but it's something to consider.

In terms of actual performance changes: you're right about the Glimmer/handlebars thing. One of the legacy integration aspects of Ember is that the rest of the system is observer-based, so the mechanism they chose is optimized for that. As with any tech choices, it has pros and cons. One major pro of Mithril's pure js templates is that you get free debugging tools. The pros of the glimmer/handlebars combo is that is handles itself relatively well when the dynamic/static DOM ratio is low (whereas a standard virtual dom implementation has a flatter performance profile). The downside is that glimmer/handlebars suffers a lot when the dynamic/static DOM ratio is high simply because each dynamic spot has more layers of abstraction to go through. When you're at tens of thousands of elements, this starts to matter because the cost of each CPU instruction in the update-value procedure is multiplied by 5 orders of magnitude.

In terms of performance profiling, building a vdom tree (i.e. calling .view) is not the expensive part. Most of the overhead there can be removed w/ the sweet.js macro. Diffing is more expensive.

One optimization that is possible in Mithril, but technically backwards incompatible is to only mark a virtual dom element as dynamic if it has an attributes argument (the 2nd argument), meaning that attributes in the selector string would be considered static. This is backwards incompatible because it's possible to use string interpolation to make the selector dynamic (and especially easy to do it in languages like Coffeescript, which support interpolation syntax)

The virtual dom diff would still be O(n=vdomSize), but each check can be a bit faster if there's a flag that short circuits the rest of the conditional when the element is deemed static. I should stress that while this is possible, it isn't very exciting because it's still O(n).

I'm not aware of any other optimization possibilities that don't involve skipping diffs in certain areas (aka subtree directives and partial rerendering)

With all that said, skipping diffs only improves performance of static areas of a template. If you have tens of thousands dynamic nodes and no workflow mechanisms to push back on feature requests that further increase DOM size, no amount of performance optimization is gonna save you on the worst case scenarios.

[tobyzerner]

Thanks for the response @lhorie, very helpful.

In my case, the interface is an "infinite scroll" list of posts in a discussion. So initially there are only 20 items displaying and things are speedy, but if the user keeps scrolling down, they can load as many as they want and things get progressively slower. It's not like they're actually digesting all of that information at once, it just builds up over time. (I guess one thing I could do is make items further up unload as you scroll down, but that is something I would like to consider as a last resort.)

I ran some tests and it turns out I massively overestimated the number of DOM elements I'm constructing: it's only about 10,000, not 40,000. As you pointed out, the diff (build) is the most expensive part. And I measured the dynamic/static DOM ratio (according to the presence of the attributes argument), and it's quite low (1:3).

So that optimization you mentioned is very enticing to me. I tried to work out how to implement it to see if it would make a difference, but I'm not having much luck... I did the following, but I'm sure I must be missing something important because it's not saving any time (and the JS profile shows that setAttributes only accounts for a very small proportion of CPU time).

1. In m(), change line 39 to var cell = {tag: "div", attrs: {}, dynamic: hasAttrs};
2. In build(), change line 309 to if (hasKeys && data.dynamic) setAttributes(node, data.tag, data.attrs, cached.attrs, namespace);

Can you offer any advice here?

As for the diff-skipping optimizations, I think these would be plenty sufficient for my case if I can work out a nicer API to implement them with. I can be reasonably certain that a post template will only change if the post's data changes (subtree directives). Likewise, I can be reasonably certain that toggling the visibility of an element inside of a post will only change the template of that particular post (partial rerendering).

For subtree directives, I've been playing around with something like this:

function retainUnlessChanged() {
  var old = [];
  var callbacks = [].slice.call(arguments);
  return function(build) {
    var needsRebuild = false;
    callbacks.forEach(function(callback, i) {
      var result = callback();
      if (result !== old[i]) {
        old[i] = result;
        needsRebuild = true;
      }
    });
    return needsRebuild ? build() : {subtree: 'retain'};
  }
}

// controller
this.post = m.prop(post);
this.retain = retainUnlessChanged(this.post);

// view
return m('article', dynamicAttributes, ctrl.retain(() => m('div', [
  // children that won't change unless the post data has changed
]);

I'm quite happy with that, except for the extra 'div' surrounding the children... if I get rid of that, things bug out, because the {subtree: 'retain'} is being exchanged with an array of children. Would that be easy to fix?

For partial rerendering, I've posted a thought about an API in https://github.com/lhorie/mithril.js/pull/291#issuecomment-91714281

[barneycarroll]

@tobscure Leo's thoughts here echo an article he wrote WRT performance concerns as a result of design, rather than a micro-tuning exercise. At one point he talks about the challenge to 'mitigate the cognitive load of a huge grid' – pagination is mentioned, but he could just as well be referring to application design patterns like occlusion culling, where only the visible elements of a grid are shown.

This gist won't plug-and-play, but it might give you some insights into how to apply similar principle to your grid…

[lhorie]

if I get rid of that, things bug out, because the {subtree: 'retain'} is being exchanged with an array of children. Would that be easy to fix?

@tobscure unfortunately I don't think so. The challenge with allowing replacement of arrays is that I would then need to support node lists with a mix of dynamic and static ranges (e.g. [m(...), {subtree: "retain"}, m(...)], which would complicate the engine significantly

[tobyzerner]

@barneycarroll Thanks for the links, interesting!

@lhorie OK. Out of interest, is that the same reason why you can't return an array from a component's view?