Diff algorithm comparison

[hkjpotato]

Please discuss a little more details about the diff algorithm in React & Vue & Fre.

[yisar]

Generally speaking, diff algorithm has three levels.

The first level, key map, is to put the key into a map and reuse the key as much as possible.

The second level, preprocessing, directly skips the same head/tail, then key map for the other nodes.

The third level is the longest increasing subsequence, after preprocessing, the remaining part first looks for the longest subsequence, they keep still and move other nodes.

React is the first level, fre is the second, vue3 is the third.

These three different levels of algorithm, editing distance is shorter and shorter, but not necessarily which is faster.

The choice of algorithm is a trade-off, and the performance is determined by many factors, such as the limitation of fiber linked list, which leads to React can only use the simplest key map algorithm. Fre2 has managed to preprocess, but it can't use LIS now.

I have an idea to do LIS on the linked list, but it needs to change the structure of the fiber linked list, which is a challenge, maybe fre3.

[hkjpotato]

Thank you. For quick reference, I will put related materials here for anyone who is interested in this topic:

• React fiber algorithm link: https://github.com/facebook/react/blob/v17.0.2/packages/react-reconciler/src/ReactChildFiber.old.js#L777
• Fre algorithm link: TBA
• Vue3 algorithm link: https://github.com/vuejs/core/blob/v3.2.31/packages/runtime-core/src/renderer.ts
• Vue2 algorithm link: TBA
• Inferno (Vue3 is similar to it): https://github.com/infernojs/inferno/blob/5dedf9d4fc67f7a6d9c3d6cc27e7c21ccc707197/packages/inferno/src/core/implementation.ts#L318 (not sure)

related explanation

• https://www.bebopser.com/2020/12/20/vue3source5/#sketch
• http://hcysun.me/vue-design/zh/renderer-diff.html#%E7%A7%BB%E9%99%A4%E4%B8%8D%E5%AD%98%E5%9C%A8%E7%9A%84%E5%85%83%E7%B4%A0-2

[hkjpotato]

rephrase a bit: due to the hard limit of O(n) by the linked list data structure (no dual end comparison or LIS), React has a known performance issue in dealing with large set of collection.

[yisar]

I implemented the O (ND) algorithm(https://github.com/yisar/fre/blob/master/src/reconcile.ts#L234) in fre. It is much faster than the react algorithm, but it is still limited by the linked list. It is still a little slower than inferno.

[hkjpotato]

thanks for the update, will take a look into it. Btw are you in "贺老Live交流群“?

[yisar]

Btw are you in "贺老Live交流群“?

No, I'm not there. My wechat is shibuyayuri. You can add this.

[hkjpotato]

Sorry I was a bit busy recently, it seems you adopt the binary search approach to find the LIS. I remember Vue3 uses the DP version for LIS.

I haven't got a chance to look deeper in Andrew's comment but I was thinking something similar by introducing reverse pointer, based on his comment it seems the trade off does not worth it haha.

Might not be relevant, but In your binary search implementation I see you are initing a new JS Array. In a previous group chat, the concern of using a JS array in a similar situation (maybe not?) was raised as JS array is not a real continuous memory, but a highly abstract data structure.

FYI, I find this past discussion in the early version of "react-scheduler" quite interesting facebook/react#12746 (comment)

Will add you, thanks!