Эта статья была впервые опубликована в паблике WeChat «Интервьюер программиста».
Что такое виртуальный DOM
Виртуальный DOM — это абстракция DOM, по сути объект JavaScript, который представляет собой более легкое описание DOM.
Зачем вам виртуальный DOM
Зачем нам нужен дополнительный уровень абстракции, если у нас уже есть DOM?
Прежде всего, мы все знаем, что один из секретов оптимизации производительности внешнего интерфейса заключается в том, чтобы использовать DOM как можно меньше, не только потому, что DOM относительно медленный, но и потому, что частые изменения в DOM вызовут перекомпоновку браузера. или return, которые являются убийцами производительности.Поэтому нам нужен этот уровень абстракции для максимально возможного обновления различий в DOM во время процесса исправления, чтобы гарантировать, что DOM не пострадает от низкой производительности.
Во-вторых, основное требование современных интерфейсных фреймворков заключается в том, что нет необходимости вручную манипулировать DOM.С одной стороны, ручное манипулирование DOM не может гарантировать производительность программы.Если обзор не является строгим в совместных проектах с несколькими людьми , разработчики могут писать низкопроизводительный код. , и, что более важно, отказ от ручных манипуляций с DOM может значительно повысить эффективность разработки.
Наконец, это также первоначальная цель виртуального DOM, который лучше кросс-платформенный.Например, Node.js не имеет DOM.Если вы хотите достичь SSR (рендеринга на стороне сервера), то один из способов - использовать виртуальный DOM, потому что виртуальный DOM сам по себе является объектом JavaScript.
Ключевые элементы виртуального дома
Создание виртуального DOM
Мы уже знаем, что виртуальный DOM — это абстракция реального DOM, и мы можем создавать разные абстракции в соответствии с разными потребностями, например:snabbdom.jsАбстрактный способ таков.
Конечно, так как snabbdom.js является ориентированной на производство библиотекой, она сделала много абстракции, и поскольку мы понимаем ее только как учебник, мы используем самый простой метод абстракции:
{
type, // String，DOM 节点的类型，如 'div'
data, // Object，包括 props，style等等 DOM 节点的各种属性
children // Array，子节点
}
После указания нашей абстрактной конструкции Virtual DOM нам нужна функция для создания Virtual DOM.
/**
* 生成 vnode
* @param {String} type 类型，如 'div'
* @param {String} key key vnode的唯一id
* @param {Object} data data，包括属性，事件等等
* @param {Array} children 子 vnode
* @param {String} text 文本
* @param {Element} elm 对应的 dom
* @return {Object} vnode
*/
function vnode(type, key, data, children, text, elm) {
const element = {
__type: VNODE_TYPE,
type, key, data, children, text, elm
}
return element
}
Эта функция очень проста, она принимает определенные параметры и возвращает объект на основе этих параметров, этот объект является абстракцией DOM.
Создание виртуального дерева DOM
Выше мы объявили функцию vnode для создания одного виртуального DOM, но все мы знаем, что DOM на самом деле является деревом, следующее, что нам нужно сделать, это объявить функцию для создания абстракции дерева DOM — виртуального дерева DOM. .
function h(type, config, ...children) {
const props = {}
let key = null
// 获取 key，填充 props 对象
if (config != null) {
if (hasValidKey(config)) {
key = '' + config.key
}
for (let propName in config) {
if (hasOwnProperty.call(config, propName) && !RESERVED_PROPS[propName]) {
props[propName] = config[propName]
}
}
}
return vnode(
type,
key,
props,
flattenArray(children).map(c => {
return isPrimitive(c) ? vnode(undefined, undefined, undefined, undefined, c) : c
})
)
}
Обновления виртуального DOM
Виртуальный DOM — это объект JavaScript в конечном счете, мы должны найти способ сопоставить виртуальный DOM с реальным DOM, то есть нам нужно объявить функцию, эта функция может преобразовать vnode в реальный DOM.
function createElm(vnode, insertedVnodeQueue) {
let data = vnode.data
let i
// 省略 hook 调用
let children = vnode.children
let type = vnode.type
/// 根据 type 来分别生成 DOM
// 处理 comment
if (type === 'comment') {
if (vnode.text == null) {
vnode.text = ''
}
vnode.elm = api.createComment(vnode.text)
}
// 处理其它 type
else if (type) {
const elm = vnode.elm = data.ns
? api.createElementNS(data.ns, type)
: api.createElement(type)
// 调用 create hook
for (let i = 0; i < cbs.create.length; ++i) cbs.create[i](emptyNode, vnode)
// 分别处理 children 和 text。
// 这里隐含一个逻辑：vnode 的 children 和 text 不会／应该同时存在。
if (isArray(children)) {
// 递归 children，保证 vnode tree 中每个 vnode 都有自己对应的 dom；
// 即构建 vnode tree 对应的 dom tree。
children.forEach(ch => {
ch && api.appendChild(elm, createElm(ch, insertedVnodeQueue))
})
}
else if (isPrimitive(vnode.text)) {
api.appendChild(elm, api.createTextNode(vnode.text))
}
// 调用 create hook；为 insert hook 填充 insertedVnodeQueue。
i = vnode.data.hook
if (i) {
i.create && i.create(emptyNode, vnode)
i.insert && insertedVnodeQueue.push(vnode)
}
}
// 处理 text（text的 type 是空）
else {
vnode.elm = api.createTextNode(vnode.text)
}
return vnode.elm
}
Вышеуказанные функции на самом деле очень просты, то есть генерируют соответствующий DOM в соответствии с типом и устанавливают различные атрибуты, определенные в данных, в DOM.
Виртуальная DOM разница
Сравнение виртуального DOM — самая сложная и основная часть всего виртуального DOM.Цель сравнения — сравнить старое и новое дерево виртуального DOM, чтобы найти различия и обновить их.
Видимый diff является ключевой частью, которая напрямую влияет на производительность Virtual DOM.
Чтобы сравнить различия виртуального дерева DOM, теоретическая временная сложность достигает O (n ^ 3), что является чрезвычайно высокой временной сложностью.Очевидно, что выбор этого неэффективного алгоритма не может удовлетворить основные требования к производительности нашей программы.
К счастью, в нашей реальной разработке межуровневые изменения DOM происходят редко.Обычно изменения DOM происходят на одном уровне.Поэтому в современных различных библиотеках Virtual DOM сравниваются только различия на одном уровне.В этом случае наша временная сложность равно О (n).
Затем нам нужно реализовать функцию для выполнения определенной операции diff.Основной алгоритм функции updateChildren выглядит следующим образом:
// 遍历 oldCh 和 newCh 来比较和更新
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 1⃣️ 首先检查 4 种情况，保证 oldStart/oldEnd/newStart/newEnd
// 这 4 个 vnode 非空，左侧的 vnode 为空就右移下标，右侧的 vnode 为空就左移 下标。
if (oldStartVnode == null) {
oldStartVnode = oldCh[++oldStartIdx]
} else if (oldEndVnode == null) {
oldEndVnode = oldCh[--oldEndIdx]
} else if (newStartVnode == null) {
newStartVnode = newCh[++newStartIdx]
} else if (newEndVnode == null) {
newEndVnode = newCh[--newEndIdx]
}
/**
* 2⃣️ 然后 oldStartVnode/oldEndVnode/newStartVnode/newEndVnode 两两比较，
* 对有相同 vnode 的 4 种情况执行对应的 patch 逻辑。
* - 如果同 start 或同 end 的两个 vnode 是相同的（情况 1 和 2），
* 说明不用移动实际 dom，直接更新 dom 属性／children 即可；
* - 如果 start 和 end 两个 vnode 相同（情况 3 和 4），
* 那说明发生了 vnode 的移动，同理我们也要移动 dom。
*/
// 1. 如果 oldStartVnode 和 newStartVnode 相同（key相同），执行 patch
else if (isSameVnode(oldStartVnode, newStartVnode)) {
// 不需要移动 dom
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}
// 2. 如果 oldEndVnode 和 newEndVnode 相同，执行 patch
else if (isSameVnode(oldEndVnode, newEndVnode)) {
// 不需要移动 dom
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}
// 3. 如果 oldStartVnode 和 newEndVnode 相同，执行 patch
else if (isSameVnode(oldStartVnode, newEndVnode)) {
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
// 把获得更新后的 (oldStartVnode/newEndVnode) 的 dom 右移，移动到
// oldEndVnode 对应的 dom 的右边。为什么这么右移？
// （1）oldStartVnode 和 newEndVnode 相同，显然是 vnode 右移了。
// （2）若 while 循环刚开始，那移到 oldEndVnode.elm 右边就是最右边，是合理的；
// （3）若循环不是刚开始，因为比较过程是两头向中间，那么两头的 dom 的位置已经是
// 合理的了，移动到 oldEndVnode.elm 右边是正确的位置；
// （4）记住，oldVnode 和 vnode 是相同的才 patch，且 oldVnode 自己对应的 dom
// 总是已经存在的，vnode 的 dom 是不存在的，直接复用 oldVnode 对应的 dom。
api.insertBefore(parentElm, oldStartVnode.elm, api.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
}
// 4. 如果 oldEndVnode 和 newStartVnode 相同，执行 patch
else if (isSameVnode(oldEndVnode, newStartVnode)) {
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
// 这里是左移更新后的 dom，原因参考上面的右移。
api.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}
// 3⃣️ 最后一种情况：4 个 vnode 都不相同，那么我们就要
// 1. 从 oldCh 数组建立 key --> index 的 map。
// 2. 只处理 newStartVnode （简化逻辑，有循环我们最终还是会处理到所有 vnode），
// 以它的 key 从上面的 map 里拿到 index；
// 3. 如果 index 存在，那么说明有对应的 old vnode，patch 就好了；
// 4. 如果 index 不存在，那么说明 newStartVnode 是全新的 vnode，直接
// 创建对应的 dom 并插入。
else {
// 如果 oldKeyToIdx 不存在，创建 old children 中 vnode 的 key 到 index 的
// 映射，方便我们之后通过 key 去拿下标。
if (oldKeyToIdx === undefined) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
}
// 尝试通过 newStartVnode 的 key 去拿下标
idxInOld = oldKeyToIdx[newStartVnode.key]
// 下标不存在，说明 newStartVnode 是全新的 vnode。
if (idxInOld == null) {
// 那么为 newStartVnode 创建 dom 并插入到 oldStartVnode.elm 的前面。
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm)
newStartVnode = newCh[++newStartIdx]
}
// 下标存在，说明 old children 中有相同 key 的 vnode，
else {
elmToMove = oldCh[idxInOld]
// 如果 type 不同，没办法，只能创建新 dom；
if (elmToMove.type !== newStartVnode.type) {
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm)
}
// type 相同（且key相同），那么说明是相同的 vnode，执行 patch。
else {
patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
oldCh[idxInOld] = undefined
api.insertBefore(parentElm, elmToMove.elm, oldStartVnode.elm)
}
newStartVnode = newCh[++newStartIdx]
}
}
}
// 上面的循环结束后（循环条件有两个），处理可能的未处理到的 vnode。
// 如果是 new vnodes 里有未处理的（oldStartIdx > oldEndIdx
// 说明 old vnodes 先处理完毕）
if (oldStartIdx > oldEndIdx) {
before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
}
// 相反，如果 old vnodes 有未处理的，删除 （为处理 vnodes 对应的） 多余的 dom。
else if (newStartIdx > newEndIdx) {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
}
}
Мы можем предположить, что есть два массива, старый массив Vnode и новый массив Vnode, и есть четыре переменные, которые действуют как указатели на начало и конец двух массивов.
Повторяйте следующий процесс сравнения до тех пор, пока указатель начала любого из двух массивов не превысит указатель хвоста, и цикл завершится. :
- Прямое сравнение: сравните заголовки двух массивов, если они найдены, замените новый узел старым узлом и переместите указатель заголовка назад.
- Сравнение хвостов: сравните хвосты двух массивов, если они найдены, вставьте новый узел в старый узел и переместите указатель хвоста вперед.
- Сравнение старого хвоста и новой головы: перекрестное сравнение, старый хвост и новая голова, если они найдены, пришивание нового узла к старому узлу, перемещение старого указателя хвоста вперед и перемещение нового указателя головы назад.
- Сравнение старой головы и новой хвостовой части: перекрестное сравнение, старая голова и новая хвостовая часть, если они найдены, пришивание нового узла к старому узлу, перемещение нового указателя хвостовой части вперед и перемещение указателя старой головки назад
- Использовать сравнение ключей: используйте ключ узла, соответствующего новому указателю, чтобы перейти к старому массиву, чтобы найти соответствующий узел. Здесь есть три случая. Когда нет соответствующего ключа, создайте новый узел. Если ключ есть и это тот же узел, пропатчите новый узел.к старому узлу, если есть ключ, но не тот же узел, создайте новый узел
Предположим, что есть два массива, старый и новый:
- старый массив:
[1, 2, 3, 4, 5] - новый массив:
[1, 4, 6, 1000, 100, 5]
Сначала сравниваем головы к головам, головы нового и старого массивов все1, поэтому указатели головок с обеих сторон перемещаются назад.
Мы продолжаем сравнивать лоб в лоб, но2 !== 4Из-за того, что сравнение не удалось, я ввел сравнение хвост-хвост,5 === 5, то указатель хвоста можно переместить вперед.
Теперь введите новый цикл, прямое сравнение2 !== 4, сравнение хвост-хвост4 !== 100, введите перекрестное сравнение в это время, сначала сравните старый хвост и новую голову, то есть4 === 4, старый хвост перемещается вперед, а новая голова перемещается назад.
Затем введите новый цикл, прямое сравнение2 !== 6, сравнение хвост-хвост3 !== 100, перекрестное сравнение2 != 100 3 != 6, все четыре метода сравнения не совпадают, если вам нужно сравнить по ключу в это время, а затем переместить новый указатель головы назад
Продолжайте повторять приведенный выше цикл сравнения, пока указатель начала любого массива не превысит указатель хвоста, и цикл не завершится.
После завершения вышеуказанного цикла может быть незавершенный обход в двух массивах: После того, как петля закончилась,
-
Сначала сравните указатели головы и хвоста старого массива.Если старый массив был пройден (может быть, новый массив не был пройден, есть проблема с пропущенными добавлениями), добавьте недостающие узлы в новый массив
-
Затем сравните указатели головы и хвоста нового массива.Если новый массив был пройден (возможно, старый массив не был пройден, есть проблема с пропущенным удалением), удалите недостающие узлы в старом массиве
Оптимизация виртуального DOM
В предыдущем разделе наша реализация Virtual DOM относится к реализации snabbdom.js.Конечно, Vue.js также относится к snabbdom.js.Мы опустили много кода, связанного с краевыми состояниями и svg, и реализовали только его основную часть. .
snabbdom.js уже является основной реализацией виртуального DOM в сообществе. Как и snabbdom.js, на этапе vue 2.0 используется «алгоритм двойного сравнения», описанный выше. Есть ли какая-либо схема оптимизации, чтобы сделать его быстрее?
На самом деле, в сообществе есть более быстрые алгоритмы, например, inferno.js известен как самый быстрый фреймворк, похожий на реакцию (хотя причина высокой производительности inferno.js не только в алгоритме, но и в его алгоритме сравнения). самый быстрый на данный момент), а vue 3.0 будет использовать для оптимизации алгоритм inferno.js.
Мы можем подождать, пока выйдет Vue 3.0, чтобы узнать, и сначала можно обратиться к конкретным идеям оптимизации.Обзор принципа алгоритма сравнения, одна из основных идей состоит в том, чтобы использовать идею LIS (самая длинная возрастающая подпоследовательность) для динамического программирования, чтобы найти минимальное количество ходов.
Например, для следующих двух старых и нового массивов алгоритм React переместит a, b, c в соответствующие позиции + 1 за три шага, в то время как inferno.js напрямую переместит d на передний план.
* A: [a b c d]
* B: [d a b c]
Справочная статья: