Javascript Array.push в 945 раз быстрее, чем Array.concat

От автора: если вы объединяете массивы с тысячами элементов, вы можете сэкономить секунды, используя arr1.push(…arr2) вместо arr1 = arr1.concat(arr2). Если вы действительно хотите работать быстрее, вы можете написать собственную реализацию для объединения массивов. Давайте разберемся, какими преимуществами обладает Javascript Array push.

Подождите минутку … сколько времени нужно, чтобы объединить 15 000 массивов с помощью .concat…

Недавно у нас были жалобы пользователей на значительное замедление выполнения их тестов пользовательского интерфейса. На выполнение каждой команды I.click I.fill I.see, которая обычно занимает ~ 1 секунду (постобработка, например, создание снимков экрана), теперь требовалось более 40 секунд, поэтому тестовые комплекты, которые обычно выполнялись менее чем за 20 минут, вместо этого занимали часы и серьезно ограничивали процесс развертывания.

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

arr1 = arr1.concat(arr2)

Метод массива .concat.

Чтобы иметь возможность писать тесты с использованием простых команд, таких как I.click(«Login») вместо селекторов CSS или XPATH I.click(«#login-btn»), пользовательский интерфейс использует динамический анализ кода для анализа дерева DOM. Это позволяет определить, что и как тестировать на сайте на основе семантики, атрибутов доступности и популярных, но нестандартных шаблонов. Эти операции .concat в настоящее время используются для сглаживания дерева DOM для анализа, но они работали очень плохо, когда дерево DOM было очень большим и глубоким. Что и произошло, когда наш пользователь недавно ввел обновление, вызвавшее значительное раздувание страниц (это еще одна проблема производительности на их стороне, однако это уже другая тема).

Потребовалось 6 секунд, чтобы объединить 15 000 массивов, каждый из которых имел средний размер 5 элементов .concat.

Что? 6 секунд… Для 15 000 массивов со средним размером 5 элементов? Это не много данных. Почему так много? Есть ли более быстрые способы слияния массивов?

Сравнения результатов тестов

.push против .concat для 10000 массивов по 10 элементов в каждом

Поэтому я начала исследование (под этим я имею в виду поиск в Google) тестов .concat по сравнению с другими методами слияния массивов в Javascript.

Оказывается, самый быстрый способ объединения массивов — это использование .push n аргументов:

// Push содержимое arr2 в arr1
arr1.push(arr2[0], arr2[1], arr2[3], ..., arr2[n]) // Так как массивы могут иметь нефиксированный размер, я вместо этого использую `apply`
Array.prototype.push.apply(arr1, arr2)

И это намного быстрее. Насколько конкретно? Я провела несколько тестов производительности, чтобы убедиться в этом. И вот разница в Chrome:

Ссылка на тест на JsPerf

Чтобы объединить массивы размером 10 для 10 000 раз, .concat выполняется со скоростью 0,40 операций / сек, а .push выполняется со скоростью 378 операций / сек. push в 945 раз быстрее concat! Эта разница может быть не линейной, но она значительна уже в этом небольшом масштабе.

А вот результаты в Firefox:

Движок Firefox SpiderMonkey Javascript, как правило, медленнее, чем движок Chrome V8, но .push по-прежнему выходит на первое место, в 2260 раз быстрее.

Это одно изменение в коде решило всю проблему замедления.

.push против .concat для 2 массивов по 50000 элементов в каждом

Но хорошо, что, если вы объединяете не 10 000 массивов размером 10, а 2 гигантских массива по 50000 элементов в каждом?

Вот результаты в Chrome:

Ссылка на тест на JsPerf

.push все равно быстрее .concat, но в 9 раз. Не так драматично, как в 945 раз, но все равно существенно.

Более красивый синтаксис с помощью rest spread

Если вы найдете код подробный Array.prototype.push.apply(arr1, arr2), вы можете использовать простой вариант- синтаксис ES6 rest spread:

arr1.push(...arr2)

Разница в производительности между Array.prototype.push.apply(arr1, arr2) и arr1.push(…arr2) незначительна.

Но почему Array.concat такой медленный?

Это во многом связано с движком Javascript, но я не знаю точного ответа, поэтому я спросила моего приятеля @picocreator, соавтора GPU.js, так как он потратил немало времени на копания исходном коде V8. @picocreator также одолжил мне свой замечательный игровой компьютер, который он использовал для тестирования GPU.js и запуска тестов JsPerf, потому что у моему MacBook не хватало памяти даже для работы .concatс двумя массивами размером 50000.

Очевидно, что ответ во многом связан с тем фактом, что .concat создает новый массив, а .push изменяет первый. Дополнительная работа .concat по добавлению элементов из первого массива в возвращаемый массив является основной причиной замедления.

Я: «Что? Правда? Так сильно? Не может быть!»

@picocreator: «Может, просто попробуй написать несколько простых реализаций .concat и сравни с .push!»

Поэтому я попыталась создать несколько простых реализаций .concat и .push. Некоторые фактически написала, некоторые взял с lodash:

Ссылка на тест на JsPerf

Простая реализация 1

Давайте поговорим о первом наборе простой реализации:

Простая реализация .concat

// Создаем результирующий массив
var arr3 = [] // Добавляем Массив 1
for(var i = 0; i < arr1Length; i++){ arr3[i] = arr1[i]
} // Добавляем Массив 2
for(var i = 0; i < arr2Length; i++){ arr3[arr1Length + i] = arr2[i]
}

Простая реализация .push

for(var i = 0; i < arr2Length; i++){ arr1[arr1Length + i] = arr2[i]
}

Как видите, единственное различие между ними состоит в том, что реализация .push изменяет первый массив напрямую.

Результаты простых методов:

Результаты простой реализации 1

Оказывается, мои DIY реализации concat и push быстрее, чем простые реализации… Но здесь мы видим, что простое создание нового массива результатов и копирование содержимого первого массива значительно замедляет процесс.

Простая реализация 2 (предварительно выделить размер конечного массива)

Мы можем еще больше улучшить простые реализации, предварительно выделив размер массива перед добавлением элементов, и это имеет огромное значение.

Простая реализация .concat с предварительно выделенным размером

// Создаем результирующий массив с предварительно выделенным размером
var arr3 = Array(arr1Length + arr2Length) // Добавляем Массив 1
for(var i = 0; i < arr1Length; i++){ arr3[i] = arr1[i]
} // Добавляем Массив 2
for(var i = 0; i < arr2Length; i++){ arr3[arr1Length + i] = arr2[i]
}

Простая реализация .push с предварительно выделенным размером

// Предварительно выделяем размер
arr1.length = arr1Length + arr2Length // Добавляем элемент arr2 в arr1
for(var i = 0; i < arr2Length; i++){ arr1[arr1Length + i] = arr2[i]
}

Результаты простой реализации 1

Результаты простой реализации 2

Предварительное выделение размера конечного массива повышает производительность в 2-3 раза для каждого метода.

.push массив в сравнении с .push отдельных элементов

Хорошо, что, если мы просто .push элементы по отдельности? Это быстрее чем Array.prototype.push.apply(arr1, arr2)

for(var i = 0; i < arr2Length; i++){ arr1.push(arr2[i])
}

Результаты

Таким образом, выполнение .push отдельных элементов выполняется медленнее, чем выполнение .push всего массива. Имеет смысл.

Вывод: почему .push быстрее.concat

Это правда, что главная причина, почему concat намного медленнее, чем .push, заключается в том, что он создает новый массив и выполняет дополнительную работу по копированию первого массива. Тем не менее, теперь есть еще одна загадка…

Еще одна загадка

Почему vanilla реализации намного медленнее, чем простые реализации? Я снова обратилась за помощью к @picocreator.
Мы взглянули на _.concat реализацию lodash, чтобы попытаться понять, что еще делает vanilla .concat под капотом, поскольку это сопоставимо по производительности (lodash немного быстрее).

Оказывается, что, в соответствии со спецификациями vanilla .concat, метод перегружен и поддерживает две подписи:

Вы даже можете сделать так: [1,2].concat(3,4,[5,6])

Lodash также обрабатывает обе перегруженные подписи, и для этого lodash помещает все аргументы в массив и сглаживает его. Это имеет смысл, если вы передаете в качестве аргументов несколько массивов. Но когда для добавления передается массив, он не просто используется как массив, он копируется в другой массив, а затем сглаживается.

… Хорошо…

Это определенно может быть оптимизировано. И именно поэтому вы можете захотеть создать собственную реализацию слияния массивов.

Кроме того, это только наша с @picocreator теория относительно того, как vanilla .concat работает под капотом, основанная на исходном коде Lodash и его немного устаревшем знании исходного кода V8. Вы можете посмотреть на досуге исходный код lodash здесь.

Дополнительные примечания

В любом случае, почему мы выполняем такие большие операции с массивами во время пользовательских тестов?

Под капотом UI-лицензированный механизм тестирования сканирует дерево DOM целевого приложения, оценивая семантику, доступные атрибуты и другие общие шаблоны, чтобы определить, что является целевым элементом и как его тестировать. Это сделано для того, чтобы тесты могли быть написаны просто, как:

// Переходим к dev.to
I.goTo("https://dev.to") // Заполняем поиск
I.fill("Search", "uilicious")
I.pressEnter() // Я должен увидеть себя или моего соавтора
I.see("Shi Ling")
I.see("Eugene Cheah")

Селекторы CSS или XPATH не используются, чтобы тесты были более читабельными, менее чувствительными к изменениям в пользовательском интерфейсе и проще в обслуживании.

ВНИМАНИЕ: Объявление для всех — Пожалуйста, старайтесь, чтобы размер вашего DOM был как можно меньше!

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

Если вы хотите выяснить, содержит ли ваш сайт слишком много узлов DOM, вы можете запустить аудит Lighthouse.

Согласно Google, оптимальное дерево DOM:

Быстрый аудит Dev.to показывает, что у нас размер дерева DOM довольно хорош:

Неплохо!

Автор: Shi Ling

Источник: https://dev.to

Редакция: Команда webformyself.