Регистрация

[Высокая производительность, JavaScript, Алгоритмы] Нативный — не значит быстрый. Обгоняем map, filter и reduce на больших массивах

Ответить на тему
Автор Сообщение
news_bot ®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

Создавать темы news_bot ® написал(а)
21-Авг-2020 10:30
Цитировать


Несколько дней назад я выкладывал пост LINQ на JavaScript для самых маленьких. Но моя библиотека сильно уступала по производительности нативным методам и Lodash. В общем-то, сейчас мы будем менять ситуацию.
Скажу сразу: в статье не будет каких-либо откровений, мы не будем строить безумные алгоритмы и т. д. Мы просто сравним производительность разных конструкций языка.
Когда я впервые выложил свою библиотеку в публичный доступ, у меня стоял вопрос лишь о том, чтобы удешевить итерацию нативного метода. Я старался облегчить callback, потому что у меня даже не возникало мысли, что map, filter или reduce могут быть даже чуточку медленнее, чем скорость света.
Прежде чем мы приступим

Поговорим о статистике
Мы будем проводить замеры следующих методов:
  • Нативный метод
  • Аналог написанный с помощью for of
  • Аналог написанный с помощью for
  • Аналогичный метод из библиотеки Lodash
  • Аналогичный метод из моей собственной библиотеки ursus-utilus-collections
Ахтунг!
Если вы посмотрите исходники, то увидите, что методы из моей библиотеки основаны сугубо на конструкции for.
Но я привожу здесь код с ними сугубо для того, чтобы похвастаться вы могли оценить как влияют на производительность дополнительные слои абстракции.
За замер производительности у нас будет отвечать Benchmark.js. Каждый пример проходил замеры 10 раз на массиве размером в 10,000,000 элементов.
Так с входными данными разобрались, теперь давайте обсудим то, что будет на выходе.
Я буду приводить пример кода и его наиболее средний бенчмарк.
В конце раздела я приведу таблицу с наиболее полной статистикой: с межквартильным средним и с медианным бенчмарками. И приведу весь бенчмарк-лог.
Приступим

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

SPL
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 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

SPL
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

SPL
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.

Несколько дней назад я выкладывал пост LINQ на JavaScript для самых маленьких. Но моя библиотека сильно уступала по производительности нативным методам и Lodash. В общем-то, сейчас мы будем менять ситуацию.
Скажу сразу: в статье не будет каких-либо откровений, мы не будем строить безумные алгоритмы и т. д. Мы просто сравним производительность рызных конструкций языка.
Когда я впервые выложил свою библиотеку в публичный доступ, у меня стоял вопрос лишь о том, чтобы удешевить итерацию нативного метода. Я старался облегчить callback, потому что у меня даже не возникало мысли, что map, filter или reduce могут быть даже чуточку медленнее, чем скорость света.
Прежде чем мы приступим

Поговорим о статистике
Мы будем проводить замеры следующих методов:
  • Нативный метод
  • Аналог написанный с помощью for of
  • Аналог написанный с помощью for
  • Аналогичный метод из библиотеки Lodash
  • Аналогичный метод из моей собственной библиотеки ursus-utilus-collections
Ахтунг!
Если вы посмотрите исходники, то увидите, что методы из моей библиотеки основаны сугубо на конструкции for.
Но я привожу здесь код с ними сугубо для того, чтобы похвастаться вы могли оценить как вляют на производительность дополнительные слои абстракции.
За замер производительности у нас будет отвечать Benchmark.js. Каждый пример проходил замеры 10 раз на массиве размером в 10,000,000 элементов.
Так с входными данными разобрались, теперь давайте обсудим то, что будет на выходе.
Я буду приводить пример кода и его наиболее средний бенчмарк.
В конце раздела я приведу таблицу с наиболее полной статистикой: с межквартильным средним и с медианным бенчмарками. И приведу вель бенчмарк-лог.
Приступим

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

SPL
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 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

SPL
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

SPL
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
===========
Похожие новости: Теги для поиска: #_vysokaja_proizvoditelnost (Высокая производительность), #_javascript, #_algoritmy (Алгоритмы), #_javascript, #_massivy (массивы), #_algoritmy (алгоритмы), #_proizvoditelnost (производительность), #_vysokaja_proizvoditelnost (
Высокая производительность
), #_javascript, #_algoritmy (
Алгоритмы
)
Профиль  ЛС 
Показать сообщения:     
Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 25-Ноя 21:46
Часовой пояс: UTC + 5