Diffing algorithm & vdom stories about percy HOT 5 OPEN

@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!!

from percy.

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

from percy.

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!

from percy.

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!

from percy.

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

from percy.