Rewrite patch algo / improve diffing performance

[jorgebucaran]

I want to rewrite patch to incorporate some prefix/suffix trimming techniques as described in the first link posted below.

Hyperapp unkeyed and keyed fares relatively well according to js-framework-benchmarks (arguably the best benchmark out there and by far), but we could do a bit better and still get away with our 1 KB proposition.

• Appending rows to a large table. #216 (comment)
• https://github.com/yelouafi/petit-dom/blob/master/src/vdom.js

[leeoniya]

there's a non-zero chance that we'll absorb uibench's 4 "worst case" scenarios [1]. prefix/suffix checks will help some of these, but not all.

all of uibench is actually a great testing/perf regression tool.

[1] https://github.com/localvoid/uibench-base/blob/efacae672bbf4133360a928305876ee1de643e64/lib/uibench.ts#L302-L319

--

the public page is here: https://localvoid.github.io/uibench/

what the linked code does should be fairly obvious from the function names.

[jorgebucaran]

@leeoniya Thanks. I've merged your comments into the same post. I don't want to derail this issue and if possible keep the convo on point.

[okwolf]

The core VDOM (Picodom) looks pretty close to vanilla in the latest js-framework-benchmark.

What I find really interesting is where Hyperapp underperforms Picodom:

By a factor of 3x in some cases! 😮

Edit: I mistook pico-dom for picodom, as @jorgebucaran points out below 🙃

[jorgebucaran]

@okwolf That's a different library: https://github.com/hville/pico-dom, the picodom I wrote is not on that list. Not on point though, if you want to contribute to this discussion (I know you want to 😉), check out these links:

• https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/
• https://neil.fraser.name/writing/diff/
• https://www.codeproject.com/Articles/42279/Investigating-Myers-diff-algorithm-Part-of

[okwolf]

@jorgebucaran oh. I guess there can never be too many libraries with similar names 😕

Well, I think comparing the performance of the real Picodom library with Hyperapp might still be a worthwhile experiment.

[okwolf]

@jorgebucaran have you done any more research on this topic yet?

I was browsing through the VDOM for Elm and thinking of you.

[jorgebucaran]

@okwolf A little bit. I have a simplified (still not quite working) version of this. It adds like 300 bytes, but makes Hyperapp as fast as ivi. 🙄

[joshrtay]

solid diff library: https://github.com/ashaffer/dift

[dima-takoy-zz]

Any updates?

[jorgebucaran]

Yes, but nothing concrete yet. I am making progress, just very slowly. I think we'll see a newly improved diff in 2.0 or after, in a few months.

My intention is not to introduce a new faster algorithm at the expense of making the code unreadable and complicated. So, not only I need to understand the problem and the solution perfectly, but I need to document it well so that everyone can understand it too.

[jorgebucaran]

We need to start saving the DOM instance in the vnodes for easier access later, this could even save bytes. This is also what ivi, nerv, (possibly petit-dom too) do if I am not mistaken.

[localvoid]

All fastest vdom implementations are storing reference to a DOM node in a vnode object or create one more tree that contains references to a vnode and DOM node. They don't read anything from DOM nodes, DOM api is used only for mutations.

Storing reference to a DOM node in a vnode object has obvious advantage that you won't need to instantiate many additional objects, but there is also a drawback that you won't be able to reuse vnodes, for example, to hoist static trees. It is possible to detect collisions and clone vnodes, but in my opinion it isn't worth it, because there are too many edge cases.

React is using immutable vnodes and has a plugin[1] that detects static subtrees and hoists them to improve performance.

Vue2 is using mutable vnodes[2], so I guess that it doesn't cause any problems in practice and it is worth it. Developers just should be aware of this limitations[3].

1. https://babeljs.io/docs/plugins/transform-react-constant-elements/
2. https://github.com/vuejs/vue/blob/6bc75cacb72c0cc7f3d1041b5d9ff447ac2f5f69/src/core/vdom/vnode.js#L8
3. https://vuejs.org/v2/guide/render-function.html#Constraints

[jorgebucaran]

@localvoid When you refer to hoisting static trees do you mean something like memoizing a view (that must return the same virtual DOM tree if the state hasn't changed)? In Hyperapp the state is immutable, so it's moderately "easy" to memoize views.

[localvoid]

By hoisting static trees I mean that you can hoist vnodes that doesn't contain any dynamic content from render functions and then reuse it.

For example, here is a component that consists of two spans: one is dynamic and another one is static.

function Component(props) {
  return (
    <div>
      <span>{props.text}</span>
      <span>Static Text</span>
    </div>
  );
}

In React it is possible to hoist span that doesn't change and reuse it each time component is rendered. And transform-react-constant-elements plugin can automatically hoist such static subtrees.

const staticSpan = <span>Static Text</span>;

function Component(props) {
  return (
    <div>
      <span>{props.text}</span>
      {staticSpan}
    </div>
  );
}

In Vue2 it will break because staticSpan will contain reference to a DOM node, and when you create two instances of this component, second one will overwrite reference from the previous one.

In my opinion, it is easy to optimize static subtrees just by wrapping them into components and it is better to improve overall performance by using mutable vnodes, but there are people who disagree.

[okwolf]

Based on this tweet I'm guessing we can close this issue once 2.0 ships?

[jorgebucaran]

@okwolf Not yet, there's still another big optimization left to do.

[jorgebucaran]

V2's new patch algorithm (based on Superfine) is significantly faster than V1. Here are the benchmark results. To maximize performance, the benchmarked example app makes use of memoization to boost the rendering perf of table rows that are not affected by state changes. This technique will eventually make it into core as described in #721.

[poppinlp]

Nice job!! Can't wait~ :)

[jorgebucaran]

Closing as I'm tracking this particular performance optimization as part of the VDOM rewrite that will ship with V2 now.