Русский
Русский
English
Статистика
Реклама

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


Несколько дней назад я выкладывал пост 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.

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


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

Источник: habr.com
К списку статей
Опубликовано: 21.08.2020 10:13:31
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Высокая производительность

Javascript

Алгоритмы

Массивы

Производительность

Категории

Последние комментарии

  • Имя: Murshin
    13.06.2024 | 14:01
    Нейросеть-это мозг вселенной.Если к ней подключиться,то можно получить все знания,накопленные Вселенной,но этому препятствуют аннуннаки.Аннуннаки нас от неё отгородили,установив в головах барьер. Подр Подробнее..
  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru