preface
In today’s increasingly complex front-end engineering, performance optimization has become an essential environment. The front end needs to be optimized from every detail. So how to be better, of course, depends on how his implementation. For example, why can’t key use index? Why not use random numbers? The answer, of course, is performance, so why? I believe you will understand a little bit after reading the diff algorithm in this article.
Synchronize the progress of the author’s blog source code series:
| | | blog theme sequence number link | | — – | — – | — — — — — — — — — — — – | | | 1 handwritten vue_mini source code parsing | juejin. Cn/post / 684790… | | 2 | handwritten react_mini source code parsing | juejin. Cn/post / 685457… | | 3 | handwritten webpack_mini source code parsing | juejin. Cn/post / 685457… | | | 4 handwritten jquery_mini source code parsing | juejin. Cn/post / 685457… | | | 5 handwritten vuex_mini source code parsing (that is, in this article) | juejin. Cn/post / 685529… | | | 6 handwritten vue_route source code parsing | juejin. Cn/post / 685956… 7 | | | handwritten diff algorithm source code parsing | juejin. Cn/post / 686881… | | | 8 written promise source code parsing | juejin. Cn/post / 686920… | | | 9 handwritten native js source code parsing (manual to realize common API) | is expected in September | | | handwritten react_redux, 10 fiberd source code parsing etc. | | September is expected to 11 | | handwritten koa2_mini | is expected in September, the front-end | priority
Diff algorithm concept
Diff algorithm, a concept generated by Virtual DOM, is used to calculate the changed part of Virtual DOM, and then perform native DOM operations according to the results of DOM calculated by the algorithm, without re-rendering the whole page, thus improving page rendering efficiency. Has become an integral part of today’s framework (VUE, React).
Handwritten diff algorithm process
Background: DOM has a high consumption of performance, so predecessors proposed to use JS objects to simulate DOM operations and calculate the last part that needs to be updated. The time complexity of dom itself is O(n ^ 3). The React team came up with the Diff algorithm! (This case provides the core code, as well as the full case) a simple understanding of the core of the version of the idea can be divided into three steps:
1. Simulate “DOM tree” and convert DOM to JS array.
Defines js constructors that synchronize DOM objects. An object can be composed of: tag('string'): the name of the tag props('object'): properties and values of properties {class: 'a', type: 'hidden'} children('array'): child key('string'): unique identifier for element 'nowKeys'Copy the code2. Obtain the difference between two DOM numbers (DIff algorithm)
Compare two DOM entities and get their differences according to the sequential array. The current demo handles the following methods:
Change: 'Change',// indicates that the element has changed Move: 'Move',// indicates that the element has changed position Add: 'Add',// indicates that the element is newly added Del: 'Del',// indicates that the element has been removed DiffPropsList: 'DiffPropsList',// indicates that the attribute list of the element is changed DelProps: 'DelProps',// indicates that the attribute is deleted ChangeProps: 'ChangeProps',// indicates that the attribute is changed AddProps: 'AddProps',// indicates that the property is newCopy the code3. “Render” the “difference”
According to Step 2), handle the differences accordingly
The example method is as follows:
Var a1 =new WzElement('div', {class: 'a1Element'}, ['a1'], "a1"); var a2 =new WzElement('div', { class: 'a2Class' }, ['a2'], "a2") let root = a1.render(); Step 2) let pathchs = diff(a1, a2); Step 3) reloadDom(root, pathchs); // Re-render according to the differencesCopy the codeCore code (Step 1) :
_createDom( tag, props, children, key ){
let dom = document.createElement( tag );
for( let propKey in props ){
dom.setAttribute( propKey, props[propKey] );
}
if( !key ){
dom.setAttribute( "key", key );
}
children.forEach( item => {
if( item instanceof WzElement ){//
var root = this._createDom(
item.tag,
item.props,
item.children,
item.key
)
dom.appendChild( root );
}else{
var childNode = document.createTextNode( item );
dom.appendChild( childNode );
}
});
return dom;
}
Copy the codeCore code (Step 2) :
Function DFS (oldElement, newElement, index, patches) {function DFS (oldElement, newElement, index, patches) {// If the new object is empty, there is no need for a comparison. Var curPatches = []; if (! newElement) { } else if (oldElement.key ! = newElement.key || oldElement.tag ! = newElement.tag) { curPatches.push({ type: stateType.Change, node: newElement }); } else { var propsDiff = diffProps(oldElement.props, newElement.props); if (propsDiff.length > 0) { curPatches.push({ type: stateType.DiffPropsList, node: newElement }); } diffChildren(oldElement.children, newElement.children,index, patches); } if (curPatches. Length > 0) {if (! patches[index]) { patches[index] = [] } patches[index] = patches[index].concat(curPatches); } return patches; } function diffChildren(oldChild, newChild, index, patches) {let {changeList, resultList } = listDiff(oldChild, newChild, index, patches); if (changeList.length > 0) { if (! patches[index]) { patches[index] = [] } patches[index] = patches[index].concat(changeList); } let last = null; oldChild && oldChild.forEach((item, i) => { let child = item && item.children; if (child) { if ( last && last.children ! = null) {// Index = index + last.children. Length + 1; } else { index += 1; } let keyIndex = resultList.indexOf( item.key ) ; Let node = newChild[keyIndex] // let node = newChild[keyIndex] If (node) {DFS (item, node, index, patches)}} else {index += 1; if (node) {DFS (item, node, index, patches)}} else {index += 1; } last = item }); }Copy the codeCore code (Step 3) :
var num = 0; Function reloadDom(node, patchs){var changes = patchs[num]; let childNodes = node && node.childNodes; if (! childNodes) num += 1 if( changes ! = null ){ changeDom( node, changes ); } var last = null childNodes &&childnodes. ForEach ((item, i ) => { if( childNodes ){ if ( last && last.children ! Num = num + last.children. Length + 1; } else { num += 1; } } reloadDom( item, patchs ); last = item; Function changeDom(node, changes){changes && changes.forEach(change => {let {type} = change; switch( type ){ case stateType.Change: node.parentNode && node.parentNode.replaceChild( change.node.create() , node ); break; case stateType.Move: let fromNode = node.childNodes[change.from]; let toNode = node.childNodes[change.to]; let formClone = fromNode.cloneNode(true); let toClone = toNode.cloneNode(true); node.replaceChild( fromNode, toClone ) ; node.replaceChild( toNode, formClone ) ; break; case stateType.Add: node.insertBefore( change.node.create(), node.childNodes[ change.index ] ) break; case stateType.Del: node.childNodes[change.index ].remove(); break; case stateType.DiffPropsList: let {props} = change.node; for( let key in props ){ if( key == stateType.DelProps ){ node.removeAttribute( ); } else { node.setAttribute( key, props[key] ); } } break; default: break; }}); }Copy the codeThe project address
Github.com/zhuangweizh…