Diffing algorithm & vdom stories

[yoshuawuyts]

Hey @chinedufn :D Here's feedback as requested. It's mostly about what we got wrong in Choo's diffing, and what we would do differently if we had the chance to start from scratch. Hope it comes in useful for Percy's development!

Diffing

An optimization that we were planning for nanomorph, but never realized was to move to a well-known diffing algorithm rather than an ad-hoc hacky one.

After a couple of years of trial-and-error engineering, it became pretty clear to us that there's 2 important features that are hard to get right through trial-and-error:

1. always creating the smallest possible diff, which means the best performance the moment you modify the DOM.
2. being able to move elements around in the DOM. (e.g. changing a sequence of sibling nodes from [1, 2, 3, 4] to [1, 3, 2, 4]).
3. achieving the two features above in at-worst linear time O(n). (we used to do backtracking during diffing, and yep nope never again).

If I had to implement a diffing algorithm today, I'd probably start by looking at the Myers diffing algorithm. It's a pretty straight forward algorithm to achieve small diffs. Once that works, the patience-diff algorithm is an optimization on top of Myers that allows for smaller, cleaner diffs.

note: an incomplete patience-diff implementation in JS can be found here. Rust should be a much better fit for a similar approach because it actually has abstractions for binary opcodes. This is also similar-ish to the way ember does it in Glimmer.

Server Rendering

A cool thing we never implemented was async rendering. Being able to wait for requests to complete while rendering turned out to be a must-have to scale out our server rendering pipeline. We never ended up implementing this in Choo, but that was more due to time constraints rather than anything else.

As a note: I wouldn't go as far as to split all rendering using requestIdleCallback() (RIC) the way for example React does it. I think RIC has a place, but it's a much better choice to manually use it in performance-critical paths, rather than using it by default through a scheduler. The main drawback of always-on RIC is that it creates compatibility problems with third party programs that have their own scheduling loops (e.g. maps, widgets, glsl frames, etc.)

In practice in Rust this would mean every template would return a Future. This is probably not ready for prime-time yet; and most likely not quite needed right now. But I figured I'd share what we ended running into, and the insight we had.

Standardization Efforts

Something to be aware of is that browser vendors are working on standardizing (a part of) DOM diffing (proposal). The webcomponent folks seem to be pushing this effort.

Personally I think this idea is rather promising as it opens up the potential for better interop between (JS) modules. But at least this spec doesn't seem to be exposing anything high-level, so in any case it would require wrappers to at least be useful.

Conclusion

Hope this comes in useful for the future! I'd love to see Percy realize a better diffing engine than we ever could with Choo! :D

Further Reading

• https://blog.jcoglan.com/2017/04/25/myers-diff-in-linear-space-implementation/
• https://blog.jcoglan.com/2017/09/28/implementing-patience-diff/
• https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/

[leeoniya]

fwiw, many of the libs that perform well here [1] use Longest Increasing Subsequence [2] when simple checks fail (common suffix and prefix, etc)

[1] https://github.com/krausest/js-framework-benchmark
[2] https://en.m.wikipedia.org/wiki/Longest_increasing_subsequence

[chinedufn]

@yoshuawuyts @leeoniya WOW these resources are INCREDIBLY helpful.

Thanks for diving into so much detail explaining the approaches, pitfalls and wishlist items with Choo's diffing. Being able to learn from other libraries that have been there done that is SO useful.

While, like you said, not all optimizations will be tackled right away (a lot of documentation, ergonomics and bug fixing will probably happen before "perfect-performance") knowing the direction to going in whenever someone begins tackling optimizing Percy's vdom is an AMAZING start!

I gave some of those links some quick scans, but I'll definitely be diving in to gain a better understand of our options here.

---

In terms of performance approach going forwards, what I have in mind is to have benchmark driven optimizations. So I think that it would be important to have a few benchmarks in place to start (and add more over time of course).

I'm thinking that our benchmarks could look like:

1. Diff benchmarks that diff two different trees. At first whatever worked.. Then over time organized in a way that made it INCREDIBLY easy to add new test cases. Sort of like our diff tests but instead inside of #[bench] tests. This could exist entirely in Rust since no real DOM nodes are needed

2. Patch benchmarks that test how long it takes to apply diffs to real DOM elements. I'm thinking that for lightweight-ness these could be done in Node.js + jsdom similar to our integration tests.. but I'm not sure if we'd be missing out by not testing in real browsers. i.e. is getting faster in jsdom the same as getting faster in chrome/firefox/safari/etc?

I'm almost thinking that getting some basic benchmarks in place (that will probably end up being not-the-best as we learn more but at least it's a starting point to improve on) is step one in our vdom optimization story? Agree? Disagree?

---

Just ideas of course - thanks so much to both of you for all of this detail / insight!!

[yoshuawuyts]

I'm almost thinking that getting some basic benchmarks in place (that will probably end up being not-the-best as we learn more but at least it's a starting point to improve on) is step one in our vdom optimization story? Agree? Disagree?

That sounds like a reasonable approach!

---

For our diffing algorithm we ended up writing about 100 tests by hand, and running another 200 or so each run using a random seed. I feel there's the possibility to do a much better job in Rust for that using proptest or quickcheck!

I don't think you need to test too many different browsers. Most of the DOM modification methods are consistent across browsers. nanomorph/lib/morph.js contains some of the weirdest things we've found; so perhaps that will come in useful.

jsdom will probably not yield the right results for actual testing. I remember we looked into it, but dropped it because certain methods were missing that we ended up using. Using the Electron-based tape-run ended up being much more reliable.

Hope this is useful!

[chinedufn]

WOOHOO again your experience here is so appreciated!

Those tests are 👍🏿👍🏿👍🏿 thank you for linking. Yeah I think some of the crates out there can help give Percy a smooth testing story as things start coming together.

Hope this is useful!

Can’t even overstate it! Your comments have already probably saved dozens of people-hours! Ty ty ty ty!

[chinedufn]

Added some thoughts on how we can get real browser benchmarking in place #22