# 减小DOM操作的性能开销

上一章我们讨论了渲染器是如何更新各种类型的 VNode 的，实际上，上一章所讲解的内容归属于完整的 Diff 算法之内，但并不包含核心的 Diff 算法。那什么才是核心的 Diff 算法呢？看下图：

我们曾在上一章中讲解子节点更新的时候见到过这张图，当时我们提到只有当新旧子节点的类型都是多个子节点时，核心 Diff 算法才派得上用场，并且当时我们采用了一种仅能实现目标但并不完美的算法：遍历旧的子节点，将其全部移除；再遍历新的子节点，将其全部添加，如下高亮代码所示：

function patchChildren(
  prevChildFlags,
  nextChildFlags,
  prevChildren,
  nextChildren,
  container
) {
  switch (prevChildFlags) {
    // 省略...

    // 旧的 children 中有多个子节点
    default:
      switch (nextChildFlags) {
        case ChildrenFlags.SINGLE_VNODE:
          // 省略...
        case ChildrenFlags.NO_CHILDREN:
          // 省略...
        default:
          // 新的 children 中有多个子节点
          // 遍历旧的子节点，将其全部移除
          for (let i = 0; i < prevChildren.length; i++) {
            container.removeChild(prevChildren[i].el)
          }
          // 遍历新的子节点，将其全部添加
          for (let i = 0; i < nextChildren.length; i++) {
            mount(nextChildren[i], container)
          }
          break
      }
      break
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

为了便于表述，我们把这个算法称为：简单 Diff 算法。简单 Diff 算法虽然能够达到目的，但并非最佳处理方式。我们经常会遇到可排序的列表，假设我们有一个由 li 标签组成的列表：

<ul>
  <li>1</li>
  <li>2</li>
  <li>3</li>
</ul>

@前端进阶之旅: 代码已经复制到剪贴板

列表中的 li 标签是 ul 标签的子节点，我们可以使用下面的数组来表示 ul 标签的 children：

[
  h('li', null, 1),
  h('li', null, 2),
  h('li', null, 3)
]

@前端进阶之旅: 代码已经复制到剪贴板

接着由于数据变化导致了列表的顺序发生了变化，新的列表顺序如下：

[
  h('li', null, 3),
  h('li', null, 1),
  h('li', null, 2)
]

@前端进阶之旅: 代码已经复制到剪贴板

新的列表和旧的列表构成了新旧 children，当我们使用简单 Diff 算法更新这两个列表时，其操作行为可以用下图表示：

在这张图中我们使用圆形表示真实 DOM 元素，用菱形表示 VNode，旧的 VNode 保存着对真实 DOM 的引用(即 vnode.el 属性)，新的 VNode 是不存在对真实 DOM 的引用的。上图描述了简单 Diff 算法的操作行为，首先遍历旧的 VNode，通过旧 VNode 对真实 DOM 的引用取得真实 DOM，即可将已渲染的 DOM 移除。接着遍历新的 VNode 并将其全部添加到页面中。

在这个过程中我们能够注意到：更新前后的真实 DOM 元素都是 li 标签。那么可不可以复用 li 标签呢？这样就能减少“移除”和“新建” DOM 元素带来的性能开销，实际上是可以的，我们在讲解 pathcElement 函数时了解到，当新旧 VNode 所描述的是相同标签时，那么这两个 VNode 之间的差异就仅存在于 VNodeData 和 children 上，所以我们完全可以通过遍历新旧 VNode，并一一比对它们，这样对于任何一个 DOM 元素来说，由于它们都是相同的标签，所以更新的过程是不会“移除”和“新建”任何 DOM 元素的，而是复用已有 DOM 元素，需要更新的只有 VNodeData 和 children。优化后的更新操作可以用下图表示：

用代码实现起来也非常简单，如下高亮代码所示：

function patchChildren(
  prevChildFlags,
  nextChildFlags,
  prevChildren,
  nextChildren,
  container
) {
  switch (prevChildFlags) {
    // 省略...

    // 旧的 children 中有多个子节点
    default:
      switch (nextChildFlags) {
        case ChildrenFlags.SINGLE_VNODE:
          // 省略...
        case ChildrenFlags.NO_CHILDREN:
          // 省略...
        default:
          for (let i = 0; i < prevChildren.length; i++) {
            patch(prevChildren[i], nextChildren[i], container)
          }
          break
      }
      break
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

通过遍历旧的 children，将新旧 children 中相同位置的节点拿出来作为一对“新旧 VNode”，并调用 patch 函数更新之。由于新旧列表的标签相同，所以这种更新方案较之前相比，省去了“移除”和“新建” DOM 元素的性能开销。而且从实现上看，代码也较之前少了一些，真可谓一举两得。但不要高兴的太早，细心的同学可能已经发现问题所在了，如上代码中我们遍历的是旧的 children，如果新旧 children 的长度相同的话，则这段代码可以正常工作，但是一旦新旧 children 的长度不同，这段代码就不能正常工作了，如下图所示：

当新的 children 比旧的 children 的长度要长时，多出来的子节点是没办法应用 patch 函数的，此时我们应该把多出来的子节点作为新的节点添加上去。类似的，如果新的 children 比旧的 children 的长度要短时，我们应该把旧的 children 中多出来的子节点移除，如下图所示：

通过分析我们得出一个规律，我们不应该总是遍历旧的 children，而是应该遍历新旧 children 中长度较短的那一个，这样我们能够做到尽可能多的应用 patch 函数进行更新，然后再对比新旧 children 的长度，如果新的 children 更长，则说明有新的节点需要添加，否则说明有旧的节点需要移除。最终我们得到如下实现：

function patchChildren(
  prevChildFlags,
  nextChildFlags,
  prevChildren,
  nextChildren,
  container
) {
  switch (prevChildFlags) {
    // 省略...

    // 旧的 children 中有多个子节点
    default:
      switch (nextChildFlags) {
        case ChildrenFlags.SINGLE_VNODE:
          // 省略...
        case ChildrenFlags.NO_CHILDREN:
          // 省略...
        default:
          // 新的 children 中有多个子节点
          // 获取公共长度，取新旧 children 长度较小的那一个
          const prevLen = prevChildren.length
          const nextLen = nextChildren.length
          const commonLength = prevLen > nextLen ? nextLen : prevLen
          for (let i = 0; i < commonLength; i++) {
            patch(prevChildren[i], nextChildren[i], container)
          }
          // 如果 nextLen > prevLen，将多出来的元素添加
          if (nextLen > prevLen) {
            for (let i = commonLength; i < nextLen; i++) {
              mount(nextChildren[i], container)
            }
          } else if (prevLen > nextLen) {
            // 如果 prevLen > nextLen，将多出来的元素移除
            for (let i = commonLength; i < prevLen; i++) {
              container.removeChild(prevChildren[i].el)
            }
          }
          break
      }
      break
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

TIP

完整代码&在线体验地址：https://codesandbox.io/s/qqxxlxzwm6

实际上，这个算法就是在没有 key 时所采用的算法，该算法是存在优化空间的，下面我们将分析如何进一步优化。

# 尽可能的复用 DOM 元素

# key 的作用

在上一小节中，我们通过减少 DOM 操作的次数使得更新的性能得到了提升，但它仍然存在可优化的空间，要明白如何优化，那首先我们需要知道问题出在哪里。还是拿上一节的例子来说，假设旧的 children 如下：

[
  h('li', null, 1),
  h('li', null, 2),
  h('li', null, 3)
]

@前端进阶之旅: 代码已经复制到剪贴板

新的 children 如下：

[
  h('li', null, 3),
  h('li', null, 1),
  h('li', null, 2)
]

@前端进阶之旅: 代码已经复制到剪贴板

我们来看一下，如果使用前面讲解的 Diff 算法来更新这对新旧 children 的话，会进行哪些操作：首先，旧 children 的第一个节点和新 children 的第一个节点进行比对(patch)，即：

h('li', null, 1)
// vs
h('li', null, 3)

@前端进阶之旅: 代码已经复制到剪贴板

patch 函数知道它们是相同的标签，所以只会更新 VNodeData 和子节点，由于这两个标签都没有 VNodeData，所以只需要更新它们的子节点，旧的 li 元素的子节点是文本节点 '1'，而新的 li 标签的子节点是文本节点 '3'，所以最终会调用一次 patchText 函数将 li 标签的文本子节点由 '1' 更新为 '3'。接着，使用旧 children 的第二个节点和新 children 的第二个节点进行比对，结果同样是调用一次 patchText 函数用以更新 li 标签的文本子节点。类似的，对于新旧 children 的第三个节点同样也会调用一次 patchText 函数更新其文本子节点。而这，就是问题所在，实际上我们通过观察新旧 children 可以很容易的发现：新旧 children 中的节点只有顺序是不同的，所以最佳的操作应该是通过移动元素的位置来达到更新的目的。

既然移动元素是最佳期望，那么我们就需要思考一下，能否通过移动元素来完成更新？能够移动元素的关键在于：我们需要在新旧 children 的节点中保存映射关系，以便我们能够在旧 children 的节点中找到可复用的节点。这时候我们就需要给 children 中的节点添加唯一标识，也就是我们常说的 key，在没有 key 的情况下，我们是没办法知道新 children 中的节点是否可以在旧 children 中找到可复用的节点的，如下图所示：

我们可以在使用 h 函数创建 VNode 时，通过 VNodeData 为即将创建的 VNode 设置一个 key：

# 减小DOM操作的性能开销

# 尽可能的复用 DOM 元素

# key 的作用

# 找到需要移动的节点

# 移动节点

# 添加新元素

# 添加新元素

Vue渲染器的核心 Diff 算法|原理篇

Vue渲染器的核心 Diff 算法|原理篇