скоростные циклы в js

Работаю над улучшениями плагина Master, узнаю много всего нового про API Figma, JavaScript и программирование в целом. Сначала я столкнулся с довольно странной проблемой медленного доступа к невидимым элементам — про неё писал в твиттере. А последнюю неделю боролся с прогресс баром для поиска всех компонентов по файлу: это довольно медленный процесс даже на файлах средней величины. При наличии 50 тысяч элементов на странице, на моём компьютере поиск занимал около 30 секунд. Поэтому я для начала попробовал написать примерный подсчёт количества элементов на странице.

Несколько дней назад, тестируя алгоритм на разных файлах, я заметил, что в одном документе, где содержится всего 17 тысяч элементов, поиск занимает более 50 секунд! Попытки выявить причину долгое время ни к чему не приводили и я обратился к друзьям за помощью. Мне рассказали, что рекурсия в принципе довольно дорогая, а ещё посоветовали оптимизировать мои циклы (я обычно использую стандартный for цикл). После того как я много раз переписал свои бедные 20 строчек кода, я обнаружил странный момент: если я копирую массив слоёв принадлежащих контейнеру в переменную — всё работает быстрее, хотя операция копирования массива должна быть довольно дорогой.

Оказалось, что дело в том, как JS работает с объектами. Если объекты занимают много памяти (а слои в Figma абсолютно точно это делают), то доступ к их полям может быть довольно дорогой операцией. В моём случае, я считывал элемент массива “детей” объекта в каждой итерации цикла. Но я не думал о том, что я также считываю и сам массив. А сохранив его в отдельную переменную (даже после цикла копирования), я неосознанно сделал его всегда доступным циклу, и не оставил необходимости считывать его в каждой итерации. В итоге оказалось, что копировать массив не нужно — достаточно просто сохранить его в переменную. И все необходимые действия уже делать с этой переменной.

Теперь немного кода для понимания. Так выглядел мой цикл до оптимизации. Как ты можешь видеть, в каждой итерации я получаю доступ к потомкам элемента через свойство children объекта node. Более того, в каждой итерации происходит то же самое и для вычисления длины массива:

for (var i = 0; i < node.children.length; i++) {
	recursive(node.children[i]);
}

Мне удалось ускорить программу в 25 раз, просто переписав эти строчки! В двадцать пять раз! С 50 до 2 секунд! Мне до сих пор не верится. В улучшенной версии я считываю массив children всего один раз. Я не сразу додумался считывать длину из переменной, поэтому некоторое время моё улучшение работало только в пару раз быстрее, вместо двадцати пяти. Вот как выглядит “правильный” цикл:

let children = node.children;
let length = children.length;
for (var i = 0; i < children.length; i++) {
  recursive(children[i]);
}

Полный код и больше методов обхода дерева слоёв: https://gitlab.com/-/snippets/2074293

Мой пост на форуме Figma на эту тему: https://forum.figma.com/t/estimating-the-size-of-the-search-tree/551/4

Оригинал поста в моём Telegram: https://t.me/gleb_sexy/72