查看原文
其他

【第1528期】前端tree组件,10000个树节点,从14.65s到0.49s

杨涛峰 前端早读课 2019-12-16

前言

年后第一个周末,刺激。今日早读文章由360企业安全SOC团队@杨涛峰投稿分享。

正文从这开始~~

全篇主要思想

递归的本质是栈的读取

先看效果对比:

以下都是基于10000条子节点数据作对比,先上最终数据对比:

  • 递归版tree,渲染速度: 14.65s,点击节点处理速度: 9.83s

  • 优化版tree,渲染速度: 0.49s,点击节点处理速度: 0.18s

递归组件实现tree:渲染速度 15.71s -1.06s = 14.65s

1- 递归版 tree 性能图

递归组件版 tree 点击节点性能分析图:点击节点处理速度: 10.19s - 0.357s = 9.833s ≈ 9.83s

2- 递归 tree 点击节点图

最终优化实现 tree: 渲染速度 2.25s - 1.76s = 0.49s

3- 优化 tree 性能图

优化版 tree 点击节点性能分析图:点击节点处理速度 0.623s - 0.3s = 0.3s

4- 优化 tree 点击节点图

最终对比是

  • 递归版tree,渲染速度: 12.19s,点击节点处理速度: 9.52s

  • 优化版tree,渲染速度: 0.49s,点击节点处理速度: 0.18s

分析问题

我们可以借助performance分析一下递归组件的耗时点所在,上递归组件渲染的性能分析:

1、script耗时分析:
5- 递归 tree script 性能分析图

通过图 -1 性能瀑布可以清晰的看到 script 执行占了 8.9s 的时间,通过上图即图 -5 可以看到 script 的的调用栈主要集中在创建 vue 实例时的 createChildren 上面。

2.render 耗时分析
6- 递归 tree render 性能分析图

通过上图即图 -6 可以清晰的看到 render 耗时主要集中在 Recalculate Style、Layout 上面。我们知道 Recalculate Style、Layout 主要是样式计算,因此查看代码:

7- 递归组件部分代码图

发现在递归的 tree-node 组件里面有很多样式的计算,10000 条子节点就需要计算 10000 次。

3.DOM 结构分析

8- 递归组件 DOM 结构图
实现思想

来看我们的开篇思想:递归的本质是栈的读取。

在算法中我们会遇到很多递归实现的案例,所有的递归都可以转换成非递归实现,其中转换的本质是:递归是解析器 (引擎) 来帮我们做了栈的存取,非递归是手动创建栈来模拟栈的存取过程。

万物都是相通的,递归组件也可以转换成扁平数组来实现:

  • 更改 DOM 结构成平级结构,点击节点以及节点的视觉样式通过操作总的 list 数据去实现

  • 然后使用虚拟长列表来控制 vue 子组件实例创建的数量。

优化版实现

主要分为两部分功能:

  1. tree 数据和 DOM 结构的扁平化;

  2. 虚拟长列表控制 DOM 渲染数量。

tree 数据和 DOM 结构的扁平化
9- 优化版 tree 的 DOM 结构图

由上图我们可以看到经过改造之后的 tree 的 DOM 结构,父节点和子节点是平级的,在操作子节点时去操作内存中的 listData 数据来改变相关联节点的状态。

我们再看下 listData 数据的结构:

10- 优化版 tree listData 数据结构图

上图即图 -10 结合图 -9 的 DOM 结构可以对整个功能的实现逻辑一目了然:

listData 中的每一项的 style、checked、path 等信息来描述节点的样式位置和状态,操作一个节点时通过 listData 更改相关节点的状态样式等信息。

因此最终来写我们的代码:

11- 实现.vue 代码图

我们再看下 handleCheckChange 的做了什么:

12-handleCheckChange 处理逻辑图
虚拟长列表控制 DOM 渲染数量

实现思路:

根节点 DOM 分成两个子节点:fui-treephantom 和 fui-treecontent。

两个子节点都是绝对定位,为了在滚动时避免数据的更改回头触发滚动事件。

13- 虚拟列表 DOM 组织结构图

根节点解两个子节点 css:

.fui-tree {
   height
: 400px;
   overflow
: auto;
   position
: relative;
 
}
 
.fui-tree__phantom {
   position
: absolute;
   left
: 0;
   top
: 0;
   right
: 0;
   z
-index: -1;
 
}
 
.fui-tree__content {
   left
: 0;
   right
: 0;
   top
: 0;
   position
: absolute;
 
}

然后我们通过滚动条的位置来计算我们应该要取哪些数据。

主要代码:

14- 计算可视区数据的起止索引 index 图

通过 startIndex、endIndex 可以取出我们需要循环的数据列表 renderNodes:

computed: {
     renderNodes
() {
       
if (!this.treeNode) return []
       
return this.treeNode.listData.slice(this.positionConfig.startIndex, this.positionConfig.endIndex)
     
},
     phantomStyle
() {
       
return {
         height
: this.allListLen * 20 + 'px'
       
}
     
}
   
}

结合图 -11 的 v-for,这样我们在渲染时的 dom 数量是固定的条数,如下图:

15- 优化版 tree DOM 数量是固定的图

虚拟列表的接入可以让即使再多数据量也能渲染固定的 DOM 数量,这样就可以支撑更大数据的渲染和功能。

以上我们实现了业务需求的大数据渲染,目前测试可支撑到 20w 条节点,点击子节点时会有肉眼可见的延迟,主要是图 -12 中 handleCheckChange 的数据查找和处理,这块还有一定的优化空间:使用字典树存储节点相关信息,字典树和扁平数组 listData 的每一个元素指向同一个内存地址,在 handleCheckChange 中通过操作字典树来达到操作 listData 的元素的效果,经典的空间换时间的案例。

参考链接

  • https://zhuanlan.zhihu.com/p/34585166

  • https://juejin.im/post/5c41543a51882525da2656f9

关于本文
作者:@杨涛峰
原文:https://zhuanlan.zhihu.com/p/55528376

最后,为你推荐

【第1426期】代码优化策略 — Idle Until Urgent

【第1411期】Airbnb 爱彼迎房源详情页中的 React 性能优化

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存