js native array.flat медленно для глубины = 1?

Question

Этот gist является небольшим тестом, который я написал, сравнивая производительность для 4 альтернатив для сплющивающих массивов глубина = 1 в JS (код может быть скопирован как есть в консоль гугл). Если я ничего не пропустил, то у штатного Array.prototype.flat наихудшая производительность на сегодняшний день - примерно в 30-50 раз медленнее, чем у любой другой альтернативы. Следует отметить, что 4-я реализация в этом тесте неизменно является наиболее производительной, часто достигая производительности, которая в 70 раз лучше. Код несколько раз тестировался на узле v12 и консоли Chrome.

Этот результат больше всего подчеркивается в большом подмножестве - см. Последние 2 протестированных массива ниже. Этот результат очень удивителен, учитывая spe c и реализацию V8 , которая, кажется, следует за spe c буквой. Мои знания C ++ отсутствуют, так же как и мое знакомство с кроличьей ношей V8, но мне кажется, что с учетом рекурсивного определения, как только мы достигнем окончательного подмассива глубины, для этого вызова подмассива больше не производится никаких рекурсивных вызовов (флаг shouldFlatten имеет значение false, когда уменьшенная глубина достигает 0, т. е. конечного подуровня), и добавление к сглаженному результату включает в себя итеративное зацикливание каждого подэлемента и простой вызов этого метода . Поэтому я не вижу веской причины, по которой a.flat так сильно страдает от производительности.

Я подумал, что, возможно, тот факт, что в исходной квартире размер результата не был предварительно выделен, может объяснить разницу. Вторая реализация в этом тесте, которая не была предварительно выделена, показывает, что это само по себе не может объяснить разницу - она ​​все еще в 5-10 раз более производительна, чем собственная квартира. Что может быть причиной этого?

Протестированные реализации (порядок одинаков в коде, хранящемся в массиве реализаций - два, которые я написал, находятся в конце фрагмента кода):

1. Моя собственная реализация уплощения, которая включает предварительное распределение окончательная сглаженная длина (таким образом избегая размера всех перераспределений). Извините за код императивного стиля, я собирался добиться максимальной производительности.
2. Простейшая наивная реализация, циклически проходящая по каждому подмассиву и вставляющая в финальный массив. (таким образом, рискуя перераспределением многих размеров).
3. Array.prototype.flat (native flat)
4. [] .concat (... arr) (= расширение массива с последующим объединением результатов. Это популярный способ выполнения глубина = 1 выравнивание).

Протестированные массивы (порядок кодов, сохраненный в объекте тестов):

1. 1000 подмассивов по 10 элементов в каждом. (10 тыс. Всего)
2. 10 подмассивов по 1000 элементов в каждом. (10 тыс. Всего)
3. 10000 подмассивов по 1000 элементов в каждом. (Всего 10 мил)
4. 100 подмассивов по 100000 элементов в каждом. (Всего 10 мил)

Answer 1

(здесь разработчик V8.)

Ключевым моментом является то, что обнаруженная вами реализация Array.prototype.flat совсем не оптимизирована. Как вы заметили, он следует буквально за буквой c - так вы получаете правильную, но медленную реализацию. (На самом деле вердикт о производительности не так прост: у этой техники реализации есть преимущества, такие как надежная производительность с первого вызова, независимо от типа обратной связи.)

Оптимизация означает добавление дополнительных быстрых путей, которые используют различные сочетания клавиш при возможный. Эта работа еще не выполнена за .flat(). Это было сделано для .concat(), для которого V8 имеет очень сложную, супероптимизированную реализацию, поэтому этот подход настолько потрясающе быстр.

Два предоставленных вами рукописных метода дают сделать предположения о том, что generi c .flat() должен проверить (они знают, что они перебирают массивы, они знают, что все элементы присутствуют, они знают, что глубина равна 1), поэтому им нужно выполнить значительно меньше проверок. Будучи JavaScript, они также (в конечном итоге) выигрывают от оптимизирующего компилятора V8. (Тот факт, что они оптимизируются через некоторое время, является частью объяснения того, почему их производительность поначалу кажется несколько изменчивой; в более надежном тесте вы могли бы действительно наблюдать этот эффект довольно четко.)

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