# c-spencer/blog

Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
37 lines (21 sloc) 4.56 KB
layout title category tags
post
quickdiff explained
webdev
 side-project

Quickdiff (implemented for notepag.es) uses an algorithm for doing a fast difference between two DOM trees. Our assumptions for this algorithm, are that the old and new DOM trees are likely to differ only in a small region. For live previews, this is a very good assumption, as between redraws it is unlikely for parts of the document to change that are far from one another. Our goal here is to decouple the cost of a redraw from the size of the document the update is against. This is particularly useful when there is very expensive post processing done after a DOM is generated, such as image bounds checks, or math rendering.

The algorithm uses two scans over the trees, one iterating forwards over children, and the other iterating backwards. In the diagrams below, the result of the forward scan is indicated in blue, and the result of the backward scan in orange. For purposes of demonstration, I will use a simple DOM containing some divs, spans, and text nodes.

A scan constitutes iterating over nodes and their children of the DOM, for two trees, in lock step. So we first compare the node of each given tree. We then recursively compare the children of each tree against each other until a difference is found, which is returned as the path. For identical trees, the lockstep comparison forwards will return no result, which is taken as the identical case.

Considering a single change in the DOM, then the forward and backwards scans will return identical paths:

The left scan will compare: div == div, div == div, span == span, a == a, span == span, b != b*. The path it returns will be the offsets of the children to reach this difference, in this case [0, 1, 0] (first div, second span, first text node). Similarly, the backwards scan will return [0, 1, 0] as it counts down the children. These paths are identical, so we have a single node change. If the change were detected higher, for instance, if the second span were a div, then the path would be returned as [0, 1] and that element would be replaced, rather than the text node inside it.

The next case is for there to be multiple changes in differing children:

The first difference found on the forward scan is identical, [0, 1, 0]. However, the backwards scan now finds a different path, [2, 0, 0]. We can use these two paths to find a segment within which any changes must be in. In this case, it is all of the children of the parent node, or the segment [0, 2] with path []. The operation to patch this difference is then to remove the segment of nodes from the original DOM specified, and replace with the nodes specified in the new DOM.

The final case is on insertion (or deletion):

An extra implementation detail is needed to cope with insertions and deletions: the backwards scan returns two paths, to cope with possibly different indices for the same nodes in each tree. For instance, in this example, the "d" text node has path [2, 0, 0] in the original DOM, but path [3, 0, 0] in the second DOM. With this detail, deletions are a straightforward extension of previous methods, as we are simply replacing a found segment in the original DOM, with a smaller segment from the target DOM. Insertions that are accompanied with changes are also handled easily. The case to consider are insertions with no other changes.

For these pure insertions, the difference between our forwards and backwards scan will be a negative segment length. In this case, we need to instead return the parent node instead of a segment, and an index inside its children of where to insert the new DOMs node(s).

This algorithm can very quickly isolate an area of the DOM which has changed. For a sizable document, the scan takes between 1-2 ms (Chrome) to 15ms (IE8). The cost of the scan is infact dwarfed by re-processing even one equation for MathJax, and generating the new DOM in the first place. However, by only doing this partial redraw, refreshing the live preview on chrome dropped from 600-800ms, to 30-40ms, and from 8-10 seconds on IE8, down to 500-600ms. When math is not required to be redrawn, these figures drop down to 10-20ms on Chrome, and 50-60ms on IE8, which allows a much more responsive live preview.

On another note, Notepag.es has been released on github: notepages repo.