JP Camara, главный инженер Wealthbox, в своём блоге поделился интересным опытом ускорения TanStack Table — новой версии React-библиотеки для создания функциональных таблиц — аж до 10 мс. Делимся с вами переводом его статьи.

JP Camara

Главный инженер Wealthbox — CRM для финансовых консультантов

Несколько месяцев назад я работал над интерфейсом JavaScript для большого набора данных, используя TanStack Table. Ограничения были такие: 

• максимум 50 тыс. строк контента,

• группировка до 3 колонок.

Производительность была хорошей при использовании React и виртуализированного рендеринга для отображения 50 000 строк. Когда же я включил функцию группировки таблиц TanStack, производительность упала уже на нескольких тысячах строк и стала чрезвычайно низкой при 50 000 строк.

Я бы мог и не обратить внимания, если бы всё замедлялось на 100 мс или даже на 500 мс. Но в самых тяжёлых случаях рендеринг строк занимал больше 1 секунды без группировки и до 30–40 секунд с группировкой.

Как я выявил проблему

Сначала я использовал Chrome-профайлер JavaScript, но с ним сложно работать на низкой производительности. Профайлер накладывает на код заметную нагрузку. Исполнение кода уже занимало 30–40 секунд, поэтому профайлер не годился. Оценить производительность при анализе кода React — вообще сложно: некоторые части внутреннего кода используются слишком часто, поэтому результаты трудно расшифровать.

У меня был запасной план, и я обратился к старому доброму console.time. Таймер помогает увидеть, сколько времени занимает выполнение участка кода:

console.time('expensive code');
thisIsExpensive();
console.timeEnd('expensive code');
// console.time
//   expensive code: 1000ms

На будущее учёл, что можно воспользоваться: console.profile. Он подходит для профилирования небольших блоков кода, а не для расшифровки всего стека рендеринга React. Но, в данном случае, учитывая медленную скорость исходного кода, метод бы не помог. Подробнее о нём можно почитать здесь.

Мы, программисты, полны идей о том, ЧТО нужно оптимизировать, и не умеем делать это правильно. Мы обоснованно предполагаем, ЧТО важно оптимизировать и ГДЕ зарыта проблема. Но, пока мы это не ИЗМЕРИМ, наши суждения ошибочны. 

Я начал оборачивать как можно больше кода в тестирование, чтобы убедиться, что верно выбрал части кода для оптимизации. Затем сужал бенчмарк до конкретного куска, который нужно улучшить.

Вот общая того схема, как я нашёл проблему с производительностью:

console.time('everything');
elements.forEach(() => {
  console.time('methodCall');
  methodCall(() => {
    console.time('build');
	build();
	console.timeEnd('build');
  });
  console.timeEnd('methodCall');
});
console.timeEnd('everything');
// build      49ms
// methodCall 50ms
// build      51ms
// methodCall 52ms
// everything 102ms

Все мои предположения о потенциальной проблеме с производительностью ДО проведения измерений оказались ошибочными:

• С моим кодом всё было нормально. Ошибка была в библиотеке, которую я использовал, — для меня это стало неожиданностью. Я проверил каждую строчку кода, и все они работали хорошо. Тормозил всё код библиотеки. Вся логика для таблицы TanStack в React сосредоточена в хуке useReactTable.  Проблема с производительностью возникала именно там:

console.time('everything');
customCode();
console.time('useReactTable');
useReactTable(...);
console.timeEnd('useReactTable');
console.timeEnd('everything');
// useReactTable 31500 ms
// everything    31537 ms

• Когда пишешь на JavaScript, одним из преимуществ работы с пакетами является то, что в любой момент можно открыть папку node_modules и поиграться со сторонним кодом. Я смог изменить исходный код TanStack Table напрямую, добавив информацию о времени загрузки.

• Включение группировки вызывало заметное замедление, поэтому стоило начать с проверки времени загрузки именно этого участка кода.

Чуть ниже даю сокращённую версию исходного кода сгруппированных строк с первым замером времени загрузки. Я пытался вычислить проблемные части кода, измеряя, сколько времени они выполнялись. Здесь стоит обратить внимание на операторы console.time.

function getGroupedRowModel<TData extends RowData>() {
  console.time('everything');
  //...
	
  console.time('grouping filter')
  const existing = grouping.filter(columnId =>
    table.getColumn(columnId)
  )
  console.timeEnd('grouping filter')
	
  const groupUpRecursively = (
    rows: Row<TData>[],
    depth = 0,
    parentId?: string
  ) => {
    if (depth >= existing.length) {
      return rows.map(row => {
      row.depth = depth
      //...
      if (row.subRows) {
        console.time('subRows')
        row.subRows = groupUpRecursively(
          row.subRows, 
          depth + 1
        )
        console.timeEnd('subRows')
      }
      return row
    });
	
    const columnId: string = existingGrouping[depth]!
    const rowGroupsMap = groupBy(
      rows, 
      columnId
    )
	
    const aggregatedGroupedRows = Array.from(rowGroupsMap.entries()).map(([groupingValue, groupedRows], index) => {
      let id = `${columnId}:${groupingValue}`
      id = parentId ? `${parentId}>${id}` : id
      console.time(
        'aggregatedGroupedRows groupUpRecursively'
      )
      const subRows = groupUpRecursively(
        groupedRows, 
        depth + 1,
        id
      )
      console.timeEnd(
        'aggregatedGroupedRows groupUpRecursively'
      )
      //...
      }
    }
  }
  console.timeEnd('everything');
}

Мне казалось, что виновата функция groupUpRecursively. Логичное предположение, что десятки тысяч рекурсивных вызовов могут снижать производительность (спойлер: как обычно, я ошибся ????).

Первая попытка провалилась. Логгировались тысячи таймеров subRows. Несмотря на то что каждая итерация была быстрой, таймеров было слишком много, поэтому я решил их сократить.

console.time
 subRows: 0 ms
   at map (packages/table-core/src/utils/getGroupedRowModel.ts:48:25)
       at Array.map (<anonymous>)
       at Array.map (<anonymous>)
       at Array.map (<anonymous>)
       at Array.map (<anonymous>)

console.time
 subRows: 0 ms
   at map (packages/table-core/src/utils/getGroupedRowModel.ts:48:25)
       at Array.map (<anonymous>)
       at Array.map (<anonymous>)
       at Array.map (<anonymous>)
       at Array.map (<anonymous>)

Убрав ненужное, я приблизился к своей цели. Я учитывал почти всё время, но было две проблемы: 1) я не учитывал всё время (everything равнялось 33 секундам, а длительность groupUpRecursively была только 23 секунды) и 2) измеряемый отрезок времени был слишком большим, чтобы найти в нём проблемный код:

console.time
  grouping filter: 1 ms
    at fn (packages/table-core/src/utils/getGroupedRowModel.ts:22:17)

console.time
  aggregatedGroupedRows groupUpRecursively: 23248 ms
    at map (packages/table-core/src/utils/getGroupedRowModel.ts:71:23)
        at Array.map (<anonymous>)
        at Array.map (<anonymous>)
        at Array.map (<anonymous>)

console.time
  everything: 33509 ms

Я понял, что пропустил вызов скромной функции groupBy, поэтому добавил к ней блок console.time:

console.time('groupBy')
const rowGroupsMap = groupBy(rows, columnId)
console.timeEnd('groupBy')

Теперь другое дело! Почти всё 31-секундное замедление сосредоточилось на трёх вызовах groupBy.

console.time
  grouping filter: 2 ms
    at fn (packages/table-core/src/utils/getGroupedRowModel.ts:22:17)

console.time
  groupBy: 10279 ms
    at groupUpRecursively (packages/table-core/src/utils/getGroupedRowModel.ts:59:19)

console.time
  groupBy: 10868 ms
    at groupUpRecursively (packages/table-core/src/utils/getGroupedRowModel.ts:59:19)
        at Array.map (<anonymous>)

console.time
  groupBy: 10244 ms
    at groupUpRecursively (packages/table-core/src/utils/getGroupedRowModel.ts:59:19)
        at Array.map (<anonymous>)
        at Array.map (<anonymous>)

console.time
  aggregatedGroupedRows groupUpRecursively: 21159 ms
    at map (packages/table-core/src/utils/getGroupedRowModel.ts:71:23)
        at Array.map (<anonymous>)
        at Array.map (<anonymous>)

console.time
  everything: 31537 ms

Каждый сгруппированный столбец вызывал groupBy, и каждый вызов занимал около 10 секунд. 

Так что же, чёрт возьми, происходило с функцией groupBy, которая вызывала такое сильное замедление? Можете ткнуть пальцем?

function groupBy<TData extends RowData>(rows: Row<TData>[], columnId: string) {
  const groupMap = new Map<any, Row<TData>[]>()
	
  return rows.reduce((map, row) => {
    const resKey = `${row.getValue(columnId)}`
	const previous = map.get(resKey)
	if (!previous) {
	  map.set(resKey, [row])
	} else {
	  map.set(resKey, [...previous, row])
	}
	return map
  }, groupMap)
}

Я начал делить функцию на части. Сперва я переключил Map на литерал объекта, чтобы устранить возможную нагрузку на память. Затем попробовал переключиться на цикл for вместо reduce и проверить, вызывают ли проблему количество итераций с завершениями. По своему опыту скажу, что современные движки JavaScript хорошо оптимизированы и могут обрабатывать функции forEach, map и reduce точно так же, как и цикл for, написанный вручную. Эти функции почти никогда не являются причиной проблем с производительностью в JavaScript, даже при работе с большим количеством итераций, поскольку движок может эффективно их оптимизировать.

Описанные выше действия не дали никакого эффекта. Тогда я начал комментировать строки функции, чтобы изолировать проблему. Когда я закомментил вот эту строку ↓, мгновенно ушла проблема с производительностью:

// map.set(resKey, [...previous, row])

Какова была цель этой строки и почему она была такой медленной

const resKey = `${row.getValue(columnId)}`
const previous = map.get(resKey)
if (!previous) {
  map.set(resKey, [row])
} else {
  map.set(resKey, [...previous, row])
}

При каждой итерации функции reduce код совершал следующее:

• Использовал значение этой ячейки столбца в качестве ключа карты. Допустим, значением является строка «Нью-Йорк».

• Если не было значения, связанного с «Нью-Йорком», устанавливалось значение текущей row, заключённой в массив.

• Если значение присутствовало, код использовал spread оператор для объединения текущего row с концом предыдущего значения массива.

• Поэтому на каждой итерации reduce оператор spread создавал новый, постепенно увеличивающийся массив, замедляясь с каждой новой итерацией.

// 1st iteration
[...previous, row] => [1,2]
// 2nd iteration
[...previous, row] => [1,2,3]
// 3rd iteration
[...previous, row] => [1,2,3,4]
// ...
// 50,000th iteration
[...previous, row] => [1,...49998,49999]

Стоит отметить, что самая низкая производительность наблюдалась при плохом распределении групп. Если бы у вас был столбец только с одним уникальным значением, все 50 000 строк были бы сгруппированы под одним ключом. Однако, если бы в столбце было много уникальных значений, группы были бы меньше и обрабатывались бы быстрее. 

Что делает spread оператор

В моём случае spread оператор перебирает итерируемый объект, чтобы создать новый массив. Возможно, всё гораздо сложнее, но в моём варианте оператор spread  — это O(n). Чем больше размер массива, тем больше времени требуется для раскладывания значений в новый массив.

Я уверен, что внутренние компоненты языка обеспечивают дополнительную эффективность, но следующий код практически такой же:

const a = [1, 2, 3, 4, 5, 6, 7];
	
// spread
const b = [...a, 8];
	
// manual loop
let c = [];
	
for (let i = 0; i < a.length; i++) {
  c.push(a[i]);
}
c.push(8);

Неудивительно, что внутренняя работа v8 довольно сложная. Поскольку оператор spread — фундаментальная функция, его логика присутствует во многих частях движка, что затрудняет поиск конкретной реализации.

Значит, исходная версия кода groupBy была такой:

// original code
map.set(resKey, [...previous, row]
	
// manual spread
for (let i = 0; i < rows.length; i++) {
  const tempPrevious = [];
  for (let j = 0; j < previous.length; j++) {
    tempPrevious.push(previous[j]);
  }
  tempPrevious.push(rows[i]);
  previous = tempPrevious;
  map.set(resKey, tempPrevious);
}

Здесь сразу бросается в глаза вложенный цикл. Под вложенным циклом подразумевают одну из самых медленных форм алгоритмической сложности — квадратичную сложность O(n^2). Она не подходит для масштабирования: при увеличении объёма входных данных время работы растёт экспоненциально. В моём случае для размера массива в 50 000 требуемое количество итераций составило 50 000^2, то есть 2,5 миллиарда итераций ????

Если вы не слышали о сложности Big O («О» большое), с этим способом измерения эффективности алгоритмов стоит ознакомиться. Сложность помогает определить, сколько по времени будет выполняться алгоритм и насколько хорошо он масштабируется относительно размера набора данных. Если хотите разобраться, вот отличный бесплатный ресурс.

В моём конкретном случае массив вырос с пустого до размера 50 000, так что всё было не так уж и плохо. Технически это была квадратичная сложность O(n^2), но на практике выходило O(n^2/2). 

С точки зрения алгоритмической сложности O(n^2) и O(n^2/2) эквивалентны, так как обычно константу опускают (в данном случае 1/2). Но с практической точки зрения, разве вы бы предпочли, чтобы и так медленный алгоритм был ещё медленнее? Конечно, нет ????

В моём случае выходило так:

• 1 249 975 000 или 1 миллиард 249 миллионов итераций;

• 49 999 отброшенных массива для 1 249 925 001 записи;

• Умножаем вызов функции groupBy на три — получается 3 749 925 000 итераций, 149 997 отброшенных массива и 3 749 775 003 записи.

Стоит отдать должное сборщику мусора и среде выполнения JavaScript ????????‍♂️☠️????????‍♂️ Честно говоря, учитывая, сколько итераций и сколько мусора накопилось, код работал вполне прилично ????

Но можно ли его оптимизировать — вот в чём вопрос.

Spread — это иммутабельная (неизменяемая) структура данных. Стоит ли мутировать данные?

Spread оператор не только быстро даёт доступ к «материалу», из которого состоят итерируемые объекты, но и сохраняет код иммутабельным (неизменяемым). Это особенно важно, когда один объект используется в разных частях кода. В таком случае изменение объекта в одном месте может привести к ошибкам в другом. Неизменяемые структуры данных позволяют предотвратить мутации объектов.

Если код был написан как иммутабельный, то доступны альтернативные варианты для улучшения производительности, которые ведут себя аналогично оператору spread:

// Array.from()
//   ~10 seconds, just as slow ????
const arr = Array.from(previous)
arr.push(row)
map.set(resKey, arr)
	
// slice()
//   ~10 seconds, just as slow ????
const arr = previous.slice()
arr.push(row)
map.set(resKey, arr)
	
// concat(row)
//   ~10 seconds, just as slow ????
map.set(resKey, previous.concat(row))
	
// hand written for loop
//   ~14 seconds, slower than spread! ???? 
let arr = []
for (let i = 0; i < previous.length; i++) {
  arr.push(previous[i])
}
arr.push(row)
map.set(resKey, arr)
	
// concat([row])
//   ~4 seconds ????‍♂️ 
map.set(resKey, previous.concat([row]))
	
// using the `immer` node package
//   ~100ms ???? 
return produce(groupMap, (draft) => {
  return rows.reduce((map, row) => {
    const resKey = `fixedKey`
    let previous = map.get(resKey)
    if (!previous) {
      map.set(resKey, [row])
    } else {
      previous.push(row)
    }
    return map
  }, draft)
})

Array.from, slice и concat имеют ту же производительность, что и оператор spread. Однако вылезли другие сюрпризы:

• Ручной цикл for был самым медленным. Его выполнение длилось около 14 секунд. Нативные версии кода гораздо более оптимизированы, чем самостоятельно написанный ручной цикл.

• concat, при передаче массива в качестве аргумента вместо простого объекта, был быстрее, чем оператор spread на любой платформе v8 (node/chrome). Это заняло половину времени! Либо в моём коде было трудно найти ошибку, либо среда выполнения имела специальную оптимизацию для этого кейса. Но всё ещё слишком медленно.

• Функция immer выполнялась существенно быстрее остальных. immer предоставляет обычные интерфейсы JavaScript для неизменяемых данных, используя прокси-серверы и совместное использование структур, чтобы вносить эффективные изменения в структуры данных без изменения оригинала. В данном случае основное преимущество подхода immer заключается в том, что я не копировал никакие массивы, а просто pushил прямо в них, потому что они созданы встроенными в мою функцию.

Нужна ли иммутабельность? Достаточно ли хорош  immer подход? А можно ещё быстрее?

Использование метода push

Для производительности нет ничего лучше мутаций кода.

Мутации изменяют данные на месте, без копирования и создания дубликатов данных. Если посмотреть на функцию groupBy, то там нет никакой необходимости в иммутабельных операциях. Всё было уже создано в функции, поэтому я мог без проблем изменить её, прежде чем вернуть результат. Я не думаю, что исходный код был написан с учётом иммутабельности — просто использовать синтаксис оператора spread было удобным.

При реализации метода push время работы алгоритма будет O(1), то есть алгоритм будет выполняться за константное время. По мере роста массива длительность вставки новых элементов не увеличивается. Это постоянное время: что для одного, что и для 50 000 элементов.

Вот окончательная версия кода, теперь в 1 000 раз быстрее:

function groupBy<TData extends RowData>(rows: Row<TData>[], columnId: string) {
  const groupMap = new Map<any, Row<TData>[]>()
	
  return rows.reduce((map, row) => {
    const resKey = `${row.getValue(columnId)}`
    const previous = map.get(resKey)
    if (!previous) {
      map.set(resKey, [row])
    } else {
      previous.push(row)
    }
    return map
  }, groupMap)
}

Видите разницу? Она — в одном изменении строки:

previous.push(row)

previous.push(row) изменяет существующий массив и сокращает время исполнения с 10 секунд на groupBy примерно до 10 мс, что в 1 000 раз быстрее, чем в исходном коде ????

Несмотря на то что оператор spread — полезная и мощная функция в программировании, в его основе лежит тип цикла for. Если вы столкнулись с тем, что оператор spread используется в цикле и есть вероятность, что он будет работать со многими значениями, вам стоит подумать о его перезаписи.

Исходный код

Вы можете увидеть полный пул-реквест здесь. 

Поскольку решение было простым, большинство изменений в пул-реквесте — это спецификация для предотвращения возможных проблем с производительностью в будущем. 

А вот исходный код для каждой попытки на Replit. Тайминг будет медленнее на процессоре с меньшей мощностью, чем у моего компьютера, но результат будет соотноситься с тем, что описано в посте.

Получите новую специальность или повышение с этими курсами Нетологии:

• 1C-программист: с нуля до middle

• Разработчик игр на Unity

• PHP-разработчик с нуля

Для самых внимательных — скидка 10% по промокоду codehabr10.