Как быстро происходит сравнение DOM деревьев?

Как быстро происходит сравнение DOM деревьев?

Этот вопрос про Reconciliation (сравнение) и Diffing алгоритмы, которые используются в React и других фреймворках. Сравнение DOM деревьев нужно для определения, какие части нужно обновить.

Теоретическая сложность

Полное сравнение двух деревьев: O(n^3) операций, где n - количество элементов

Дерево с 1000 элементов:
- Полный алгоритм: 1,000,000,000 операций
- Это слишком медленно для real-time приложений!

Поэтому фреймворки используют эвристические алгоритмы с O(n) сложностью.

Алгоритм сравнения в React (Reconciliation)

1. Два основных допущения

// React предполагает:
// 1. Если элементы разных типов -> полная перестройка
// 2. Разработчик может помочь через keys

// Пример 1: Разные типы - полная перестройка
<div>Hello</div>  // Было
<span>Hello</span>  // Стало -> полная перестройка!

// Пример 2: Одинаковые типы - сравнить props
<div className="old">Hello</div>  // Было
<div className="new">Hello</div>  // Стало -> обновить className

2. Алгоритм сравнения

React сравнивает элементы поуровнево (breadth-first):

Старое дерево:         Новое дерево:
    <div>                  <div>
    /   \\                 /   \\
  <p>   <span>         <p>   <span>
  /      /   \\        /      /   \\
<a>    <b>  <i>    <a>    <b>  <em>

1. Сравнить корни <div> - OK, одинаковые
2. Сравнить детей <p> и <span> - OK
3. Сравнить внутри <p>: <a> - OK
4. Сравнить внутри <span>: <b>, <i> vs <b>, <em> - ИЗМЕНЕНИЕ!

Оптимизация через Keys

Без keys - O(n) сравнений

// Было
<ul>
  <li>Item 1</li>
  <li>Item 2</li>
  <li>Item 3</li>
</ul>

// Стало (добавили в начало)
<ul>
  <li>Item 0</li>  <- Новый элемент
  <li>Item 1</li>
  <li>Item 2</li>
  <li>Item 3</li>
</ul>

// React без keys: сравнит по позициям
// Item 1 -> Item 0 (обновить текст)
// Item 2 -> Item 1 (обновить текст)
// Item 3 -> Item 2 (обновить текст)
// null -> Item 3 (добавить)
// Результат: 4 обновления + создание!

С keys - оптимальное сравнение

// Было
<ul>
  <li key="1">Item 1</li>
  <li key="2">Item 2</li>
  <li key="3">Item 3</li>
</ul>

// Стало
<ul>
  <li key="0">Item 0</li>  <- Новый
  <li key="1">Item 1</li>
  <li key="2">Item 2</li>
  <li key="3">Item 3</li>
</ul>

// React с keys: сравнит по ID
// key="0" -> новый (создать)
// key="1" -> существует (оставить)
// key="2" -> существует (оставить)
// key="3" -> существует (оставить)
// Результат: только 1 добавление! O(n) операций

Практические временные затраты

1. Малые изменения в маленьком дереве

// 100 элементов, изменился 1
// Время: ~1-5 мс

const [count, setCount] = useState(0);

return (
  <div>
    <h1>{count}</h1>  <- Только это изменилось
    {/* 99 других элементов */}
  </div>
);

2. Полная перестройка большого дерева

// 10000 элементов, сложная структура
// Время: ~50-200 мс (зависит от браузера и ПК)

// Это может вызвать рассинхронизацию (jank) с 60 FPS!
// 16мс на кадр -> 200мс = потеря ~12 кадров

Оптимизация производительности

1. React.memo для мемоизации компонентов

const ExpensiveComponent = React.memo(({ data }) => {
  // Этот компонент пересчитывается только если data изменился
  return <div>{data.map(item => <Item key={item.id} />)}</div>;
});

function App() {
  const [count, setCount] = useState(0);
  const data = [{ id: 1 }, { id: 2 }];  // Создаётся заново каждый раз!

  return (
    <div>
      <button onClick={() => setCount(count + 1)}>Count: {count}</button>
      <ExpensiveComponent data={data} />  // Пересчитывается каждый раз!
    </div>
  );
}

2. useMemo для мемоизации значений

function App() {
  const [count, setCount] = useState(0);
  
  // Создавать data только когда нужно
  const data = useMemo(
    () => [{ id: 1 }, { id: 2 }],
    []  // Зависимости - если пусто, создаётся один раз
  );

  return (
    <div>
      <button onClick={() => setCount(count + 1)}>Count: {count}</button>
      <ExpensiveComponent data={data} />  // Не пересчитывается!
    </div>
  );
}

3. useCallback для мемоизации функций

function Parent() {
  const [count, setCount] = useState(0);

  // Функция пересоздаётся каждый раз
  const handleClick = () => console.log(count);

  return <Child onClick={handleClick} />;
}

// Оптимизированно:
function Parent() {
  const [count, setCount] = useState(0);

  const handleClick = useCallback(
    () => console.log(count),
    [count]  // Пересоздаётся только при изменении count
  );

  return <Child onClick={handleClick} />;
}

Инструменты для анализа производительности

1. React DevTools Profiler

// Measure сколько времени тратит каждый компонент
const start = performance.now();
// ... код ...
const end = performance.now();
console.log(`Render time: ${end - start}ms`);

2. Chrome DevTools Performance tab

performance.mark('render-start');
// ... render code ...
performance.mark('render-end');
performance.measure('render', 'render-start', 'render-end');

Реальные примеры производительности

// ПЛОХО - O(n^2) из-за неправильных keys
function List({ items }) {
  return (
    <ul>
      {items.map((item, index) => (
        <li key={index}>{item}</li>  // Index как key - худший вариант!
      ))}
    </ul>
  );
}

// ХОРОШО - O(n)
function List({ items }) {
  return (
    <ul>
      {items.map((item) => (
        <li key={item.id}>{item.name}</li>  // Уникальный ID
      ))}
    </ul>
  );
}

Выводы

Сравнение DOM деревьев происходит быстро благодаря эвристикам:

• Теория: O(n^3), но это неприменимо
• Практика: O(n) благодаря допущениям React
  • Разные типы элементов -> новое дерево
  • Одинаковые типы -> сравнить props
  • Keys помогают идентифицировать элементы
• Типичные затраты:
  • Малые деревья (100 элементов): < 5мс
  • Большие деревья (10000 элементов): 50-200мс
• Оптимизация: React.memo, useMemo, useCallback, правильные keys

Для обычных приложений это достаточно быстро, но нужно помнить про оптимизацию при работе с большими списками и сложными компонентами.