Hrodvitnir 21 авг 2020 в 08:25

Нативный — не значит быстрый. Обгоняем map, filter и reduce на больших массивах

9 мин

11K

JavaScript*Алгоритмы*Высокая производительность*

Несколько дней назад я выкладывал пост LINQ на JavaScript для самых маленьких. Но моя библиотека сильно уступала по производительности нативным методам и Lodash. В общем-то, сейчас мы будем менять ситуацию.

Скажу сразу: в статье не будет каких-либо откровений, мы не будем строить безумные алгоритмы и т. д. Мы просто сравним производительность разных конструкций языка.

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

Прежде чем мы приступим

Поговорим о статистике

Мы будем проводить замеры следующих методов:

Нативный метод
Аналог написанный с помощью for of
Аналог написанный с помощью for
Аналогичный метод из библиотеки Lodash
Аналогичный метод из моей собственной библиотеки ursus-utilus-collections

Ахтунг!

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

За замер производительности у нас будет отвечать Benchmark.js. Каждый пример проходил замеры 10 раз на массиве размером в 10,000,000 элементов.
Среда выполнения: Node.js.

Так с входными данными разобрались, теперь давайте обсудим то, что будет на выходе.

Я буду приводить пример кода и его наиболее средний бенчмарк.

В конце раздела я приведу таблицу с наиболее полной статистикой: с межквартильным средним и с медианным бенчмарками. И приведу весь бенчмарк-лог.

Приступим

Filter

Для замера производительности мы будем отфильтровывать все нечетные числа:

const filterCondition = (item: number) => !!(item % 2);

Нативная фильтрация

array.filter(filterCondition);

Benchmark
native filter x 3.58 ops/sec ±5.48% (13 runs sampled)

For of

const result = [];

for(let item of array) {
    if(filterCondition(item)) {
        result.push(item)
    }
}

Benchmark
for… of x 3.48 ops/sec ±3.46% (14 runs sampled)

Внимание, for of почти не уступает про производительности нативной фильтрации, но дальше — больше.

For

filterSuite.add('for', () => {
    const result = [];

    for(let i = 0; i < array.length; i++) {
        const item = array[i]
        if(filterCondition(item)) {
            result.push(item)
        }
    }
})

Benchmark
for x 6.92 ops/sec ±5.47% (20 runs sampled)

Обычный for обгоняет filter в 2 раза.

Lodash

Перейдем к игрокам на поле абстракций:

lodash(array).filter(filterCondition).value();

Benchmark
lodash filter x 3.60 ops/sec ±4.13% (13 runs sampled)

Lodash по производительности не уступает filter.

Моя библиотека

ursus(array).where(filterCondition).toArray();

Benchmark
ursus where x 6.87 ops/sec ±4.86% (20 runs sampled)

Моя реализация фильтра ± равна for, но незначительно медленнее.

Итоги

Benchmark log

lodash filter x 3.75 ops/sec ±4.09% (13 runs sampled)
native filter x 3.35 ops/sec ±7.99% (13 runs sampled)
for ... of x 3.38 ops/sec ±3.88% (13 runs sampled)
for x 6.04 ops/sec ±3.54% (20 runs sampled)
optimized for x 5.82 ops/sec ±3.05% (20 runs sampled)
ursus where x 5.83 ops/sec ±4.62% (21 runs sampled)

lodash filter x 3.37 ops/sec ±3.40% (13 runs sampled)
native filter x 3.33 ops/sec ±4.76% (13 runs sampled)
for ... of x 3.86 ops/sec ±9.36% (14 runs sampled)
for x 6.92 ops/sec ±5.47% (20 runs sampled)
optimized for x 6.96 ops/sec ±4.22% (20 runs sampled)
ursus where x 6.71 ops/sec ±4.75% (19 runs sampled)

lodash filter x 3.51 ops/sec ±4.94% (13 runs sampled)
native filter x 3.72 ops/sec ±0.74% (13 runs sampled)
for ... of x 3.54 ops/sec ±2.14% (14 runs sampled)
for x 6.84 ops/sec ±4.60% (20 runs sampled)
optimized for x 6.85 ops/sec ±3.58% (19 runs sampled)
ursus where x 6.46 ops/sec ±11.83% (20 runs sampled)

lodash filter x 3.55 ops/sec ±6.26% (13 runs sampled)
native filter x 3.66 ops/sec ±3.06% (13 runs sampled)
for ... of x 3.41 ops/sec ±4.28% (14 runs sampled)
for x 6.95 ops/sec ±3.85% (20 runs sampled)
optimized for x 6.79 ops/sec ±4.33% (20 runs sampled)
ursus where x 7.17 ops/sec ±3.29% (21 runs sampled)

lodash filter x 3.63 ops/sec ±3.38% (13 runs sampled)
native filter x 3.63 ops/sec ±3.35% (13 runs sampled)
for ... of x 3.44 ops/sec ±3.99% (14 runs sampled)
for x 6.89 ops/sec ±4.53% (20 runs sampled)
optimized for x 6.95 ops/sec ±3.17% (20 runs sampled)
ursus where x 6.87 ops/sec ±4.86% (20 runs sampled)

lodash filter x 3.60 ops/sec ±4.13% (13 runs sampled)
native filter x 3.58 ops/sec ±5.48% (13 runs sampled)
for ... of x 3.48 ops/sec ±3.46% (14 runs sampled)
for x 6.95 ops/sec ±3.73% (20 runs sampled)
optimized for x 6.78 ops/sec ±5.62% (20 runs sampled)
ursus where x 7.17 ops/sec ±3.79% (21 runs sampled)

lodash filter x 3.64 ops/sec ±4.11% (13 runs sampled)
native filter x 3.63 ops/sec ±3.35% (13 runs sampled)
for ... of x 3.55 ops/sec ±2.36% (14 runs sampled)
for x 6.91 ops/sec ±4.51% (20 runs sampled)
optimized for x 6.89 ops/sec ±3.76% (20 runs sampled)
ursus where x 7.03 ops/sec ±4.84% (21 runs sampled)

lodash filter x 3.59 ops/sec ±4.17% (13 runs sampled)
native filter x 3.60 ops/sec ±3.14% (13 runs sampled)
for ... of x 3.45 ops/sec ±4.69% (14 runs sampled)
for x 7.09 ops/sec ±2.65% (20 runs sampled)
optimized for x 6.81 ops/sec ±2.90% (20 runs sampled)
ursus where x 7.15 ops/sec ±2.60% (21 runs sampled)

lodash filter x 3.60 ops/sec ±5.57% (13 runs sampled)
native filter x 3.60 ops/sec ±4.55% (13 runs sampled)
for ... of x 3.39 ops/sec ±7.33% (13 runs sampled)
for x 5.71 ops/sec ±2.74% (19 runs sampled)
optimized for x 5.85 ops/sec ±2.70% (20 runs sampled)
ursus where x 6.10 ops/sec ±2.43% (21 runs sampled)

lodash filter x 3.18 ops/sec ±5.88% (13 runs sampled)
native filter x 3.34 ops/sec ±4.43% (13 runs sampled)
for ... of x 3.89 ops/sec ±6.84% (14 runs sampled)
for x 7.09 ops/sec ±2.79% (21 runs sampled)
optimized for x 6.70 ops/sec ±3.32% (20 runs sampled)
ursus where x 7.07 ops/sec ±4.02% (20 runs sampled)

	Межкв. Среднее	Медиана
filter	3,57 ops/sec	3,60 ops/sec
for	3,48 ops/sec	3,47 ops/sec
for of	6,91 ops/sec	6,92 ops/sec
lodash	3,58 ops/sec	3,60 ops/sec
ursus	6,88 ops/sec	6,95 ops/sec

Результаты гонки:

1) For
2) Ursus
3) Lodash
4) Filter
5) For of

Map

Для тестирования мы будем прибавлять ко всем числам +1

const mapCondition = (item: number) => item + 1;

Нативное отображение

array.map(mapCondition);

Benchmark
native map x 0.68 ops/sec ±3.60% (6 runs sampled)

For of

const result = [];
for(let item of array) {
    result.push(mapCondition(item))
}

Benchmark
for… of x 2.19 ops/sec ±3.47% (10 runs sampled)

В случае отображения for of обгоняет нативный метод в 3 раза.

For

const result = [];
for(let i = 0; i < array.length; i++) {
    result.push(mapCondition(array[i]))
}

Benchmark
for x 3.49 ops/sec ±6.82% (12 runs sampled)

Классический for обгоняет нативный метод в 5 раз.

Lodash

lodash(array).map(mapCondition).value();

Benchmark
lodash map x 5.78 ops/sec ±9.03% (18 runs sampled)

Lodash обходит всех в 9 раз!

Честно, разработчики какие-то волшебники, я не представляю как они такого добились.

Моя библиотека

ursus(array).select(mapCondition).toArray();

Benchmark
ursus select x 3.54 ops/sec ±5.71% (13 runs sampled)

Каким-то образом моя реализация чуточку быстрее чем просто for, на котором она основана. ¯_(ツ)_/¯

Итоги

Benchmark log

lodash map x 6.08 ops/sec ±4.84% (19 runs sampled)
native map x 0.57 ops/sec ±17.60% (6 runs sampled)
for ... of x 1.91 ops/sec ±13.65% (9 runs sampled)
for x 3.51 ops/sec ±5.25% (13 runs sampled)
optimized for x 3.62 ops/sec ±7.49% (13 runs sampled)
ursus select x 3.29 ops/sec ±9.24% (13 runs sampled)

lodash map x 5.59 ops/sec ±10.61% (19 runs sampled)
native map x 0.61 ops/sec ±11.70% (6 runs sampled)
for ... of x 2.30 ops/sec ±2.13% (10 runs sampled)
for x 3.72 ops/sec ±4.39% (13 runs sampled)
optimized for x 3.58 ops/sec ±5.24% (13 runs sampled)
ursus select x 3.58 ops/sec ±5.21% (13 runs sampled)

lodash map x 6.06 ops/sec ±5.23% (19 runs sampled)
native map x 0.68 ops/sec ±3.60% (6 runs sampled)
for ... of x 2.27 ops/sec ±3.49% (10 runs sampled)
for x 3.45 ops/sec ±10.41% (13 runs sampled)
optimized for x 3.59 ops/sec ±4.29% (13 runs sampled)
ursus select x 3.54 ops/sec ±6.08% (12 runs sampled)

lodash map x 5.81 ops/sec ±7.23% (19 runs sampled)
native map x 0.68 ops/sec ±3.63% (6 runs sampled)
for ... of x 2.31 ops/sec ±7.11% (10 runs sampled)
for x 3.62 ops/sec ±4.74% (13 runs sampled)
optimized for x 3.45 ops/sec ±6.67% (13 runs sampled)
ursus select x 3.64 ops/sec ±4.42% (13 runs sampled)

lodash map x 6.03 ops/sec ±5.26% (20 runs sampled)
native map x 0.69 ops/sec ±6.27% (6 runs sampled)
for ... of x 2.12 ops/sec ±8.87% (10 runs sampled)
for x 3.29 ops/sec ±9.33% (13 runs sampled)
optimized for x 3.53 ops/sec ±5.18% (13 runs sampled)
ursus select x 3.66 ops/sec ±4.03% (13 runs sampled)

lodash map x 5.78 ops/sec ±9.03% (18 runs sampled)
native map x 0.65 ops/sec ±6.52% (6 runs sampled)
for ... of x 2.07 ops/sec ±7.41% (10 runs sampled)
for x 3.49 ops/sec ±6.82% (12 runs sampled)
optimized for x 3.50 ops/sec ±5.93% (13 runs sampled)
ursus select x 3.54 ops/sec ±5.71% (13 runs sampled)

lodash map x 5.68 ops/sec ±8.47% (18 runs sampled)
native map x 0.67 ops/sec ±6.40% (6 runs sampled)
for ... of x 2.11 ops/sec ±5.06% (10 runs sampled)
for x 3.52 ops/sec ±5.58% (13 runs sampled)
optimized for x 3.29 ops/sec ±5.51% (13 runs sampled)
ursus select x 3.38 ops/sec ±5.31% (13 runs sampled)

lodash map x 6.37 ops/sec ±3.10% (19 runs sampled)
native map x 0.67 ops/sec ±2.43% (6 runs sampled)
for ... of x 2.19 ops/sec ±3.47% (10 runs sampled)
for x 3.41 ops/sec ±8.13% (13 runs sampled)
optimized for x 3.54 ops/sec ±5.15% (13 runs sampled)
ursus select x 3.53 ops/sec ±6.28% (13 runs sampled)

lodash map x 5.85 ops/sec ±11.04% (19 runs sampled)
native map x 0.66 ops/sec ±4.30% (6 runs sampled)
for ... of x 2.20 ops/sec ±2.97% (10 runs sampled)
for x 3.45 ops/sec ±8.03% (13 runs sampled)
optimized for x 3.48 ops/sec ±5.13% (13 runs sampled)
ursus select x 3.68 ops/sec ±3.33% (13 runs sampled)

lodash map x 5.31 ops/sec ±12.87% (18 runs sampled)
native map x 0.68 ops/sec ±4.26% (6 runs sampled)
for ... of x 2.11 ops/sec ±6.97% (10 runs sampled)
for x 3.35 ops/sec ±6.12% (13 runs sampled)
optimized for x 3.38 ops/sec ±5.55% (13 runs sampled)
ursus select x 3.54 ops/sec ±6.20% (13 runs sampled)

	Межкв. Среднее	Медиана
map	0.67 ops/sec	0.67 ops/sec
for	2.17 ops/sec	2.16 ops/sec
for of	3.47 ops/sec	3.47 ops/sec
lodash	5.79 ops/sec	5.80 ops/sec
ursus	3.56 ops/sec	3.54 ops/sec

Результаты гонки:

1) Lodash
2) Ursus
3) For
4) For of
5) Map

Reduce

Свертку мы будем тестировать на суммировании элементов

const sumCondition = (item1: number, item2: number) => item1 + item2;

Нативная свертка

array.reduce(sumCondition);

Benchmark
native reduce x 6.09 ops/sec ±9.13% (20 runs sampled)

For of

Пропускает гонку, так как я не придумал как его можно приладить без операций с массивом. А с ними замеры уже будут не такие объективные.

For

let result = array[0];
for(let i = 1; i < array.length; i++) {
    result = sumCondition(result, array[i])
}

Benchmark
for x 57.01 ops/sec ±2.53% (59 runs sampled)

For обходит нативный метод почти в 10 раз!

Lodash

lodash(array).sum();

Benchmark
lodash sum x 8.30 ops/sec ±7.79% (25 runs sampled)

А вот lodash подкачал, он почти такой же, как и reduce.

Моя библиотека

ursus(array).sum(sumCondition);

Benchmark
ursus sum x 56.12 ops/sec ±2.38% (58 runs sampled)

Итоги

Benchmark log

lodash sum x 8.60 ops/sec ±4.35% (25 runs sampled)
native reduce x 6.69 ops/sec ±3.73% (21 runs sampled)
for x 68.67 ops/sec ±3.41% (70 runs sampled)
optimized for x 70.75 ops/sec ±2.63% (72 runs sampled)
ursus sum x 67.78 ops/sec ±3.12% (70 runs sampled)

lodash sum x 9.00 ops/sec ±3.93% (26 runs sampled)
native reduce x 5.47 ops/sec ±21.31% (19 runs sampled)
for x 56.61 ops/sec ±2.70% (59 runs sampled)
optimized for x 56.85 ops/sec ±2.27% (59 runs sampled)
ursus sum x 56.08 ops/sec ±2.40% (59 runs sampled)

lodash sum x 8.69 ops/sec ±3.36% (26 runs sampled)
native reduce x 6.09 ops/sec ±9.13% (20 runs sampled)
for x 57.01 ops/sec ±2.53% (59 runs sampled)
optimized for x 57.38 ops/sec ±2.64% (60 runs sampled)
ursus sum x 56.12 ops/sec ±2.38% (58 runs sampled)

lodash sum x 8.68 ops/sec ±4.11% (26 runs sampled)
native reduce x 6.06 ops/sec ±9.39% (19 runs sampled)
for x 69.97 ops/sec ±2.82% (71 runs sampled)
optimized for x 66.55 ops/sec ±4.16% (68 runs sampled)
ursus sum x 69.29 ops/sec ±2.73% (71 runs sampled)

lodash sum x 7.86 ops/sec ±8.39% (24 runs sampled)
native reduce x 6.35 ops/sec ±4.79% (20 runs sampled)
for x 55.91 ops/sec ±5.01% (58 runs sampled)
optimized for x 56.41 ops/sec ±2.70% (59 runs sampled)
ursus sum x 57.11 ops/sec ±2.16% (58 runs sampled)

lodash sum x 8.11 ops/sec ±4.72% (24 runs sampled)
native reduce x 5.97 ops/sec ±7.80% (20 runs sampled)
for x 56.43 ops/sec ±3.62% (59 runs sampled)
optimized for x 56.87 ops/sec ±3.75% (59 runs sampled)
ursus sum x 55.37 ops/sec ±3.60% (58 runs sampled)

lodash sum x 8.52 ops/sec ±6.70% (25 runs sampled)
native reduce x 6.12 ops/sec ±7.39% (20 runs sampled)
for x 57.96 ops/sec ±3.50% (58 runs sampled)
optimized for x 55.19 ops/sec ±5.32% (59 runs sampled)
ursus sum x 56.75 ops/sec ±3.33% (58 runs sampled)

lodash sum x 8.00 ops/sec ±8.94% (25 runs sampled)
native reduce x 5.75 ops/sec ±6.95% (19 runs sampled)
for x 56.78 ops/sec ±4.21% (57 runs sampled)
optimized for x 56.89 ops/sec ±2.32% (60 runs sampled)
ursus sum x 54.61 ops/sec ±7.04% (57 runs sampled)

lodash sum x 8.11 ops/sec ±8.83% (24 runs sampled)
native reduce x 5.97 ops/sec ±7.84% (19 runs sampled)
for x 57.32 ops/sec ±4.17% (59 runs sampled)
optimized for x 55.97 ops/sec ±4.18% (59 runs sampled)
ursus sum x 55.76 ops/sec ±3.90% (58 runs sampled)

lodash sum x 8.30 ops/sec ±7.79% (25 runs sampled)
native reduce x 6.31 ops/sec ±5.42% (20 runs sampled)
for x 55.45 ops/sec ±5.56% (58 runs sampled)
optimized for x 57.54 ops/sec ±3.52% (59 runs sampled)
ursus sum x 55.22 ops/sec ±4.34% (57 runs sampled)

	Межкв. Среднее	Медиана
reduce	6.09 ops/sec	6.08 ops/sec
for	57.02 ops/sec	56.90 ops/sec
lodash	8.39 ops/sec	8.41 ops/sec
ursus	56.20 ops/sec	56.10 ops/sec

Результаты гонки:

1) For
2) Ursus
3) Lodash
4) Reduce

Заключение

Как вы могли увидеть, на 10 миллионном массиве нативные реализации работают в разы медленнее, чем for и библиотечные реализации.

В общем-то, нативная реализация начинает обгонять lodash на 50k элементов в массиве и меньше.

А на 25k начинает обгонять даже for.

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

Спасибо за внимание!

Теги:

Хабы:

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку

Нативный — не значит быстрый. Обгоняем map, filter и reduce на больших массивах

Прежде чем мы приступим

Поговорим о статистике

Приступим

Filter

Нативная фильтрация

For of

For

Lodash

Моя библиотека

Итоги

Результаты гонки:

Map

Нативное отображение

For of

For

Lodash

Моя библиотека

Итоги

Результаты гонки:

Reduce

Нативная свертка

For of

For

Lodash

Моя библиотека

Итоги

Результаты гонки:

Заключение

Публикации

Истории

Работа

Ближайшие события