Обращение к Javascript-сообществу: перестаньте писать квадраты

Disclaimer: в этой статье будет очень много бредовых примеров и сверх очевидных утверждений. Если для вас предельно очевидно, что ... внутри .reduce даёт вам O(n^2), то можно сразу прыгать к разделу "Критика" или просто проигнорировать статью. Если же нет, милости прошу под cut.

Предисловие

Все мы знаем про стандартную конструкцию for (;;) которая чаще всего, в реальном коде, имеет примерно такой вид:

for (let idx = 0; idx < arr.length; ++ idx) {
  const item = arr[idx];
  // ...
}

Далеко не все из нас любят ей пользоваться (только давайте обойдёмся без холиваров на эту тему, статья не об этом), особенно в простых сценариях, т.к. когнитивная нагрузка довольно высока ― очень много малозначительных или даже ненужных деталей. Например в таком вот сценарии:

const result = [];
for (let idx = 0; idx < arr.length; ++ idx) {
  const item = arr[idx];  
  result.push(something(item));
}
return result;

Большинство из нас предпочтёт более компактную и наглядную версию:

return arr.map(something); 
// или
return arr.map(item => something(item)); 

note: 2-й вариант избавит вас от потенциальных проблем в будущем, когда something может внезапно обзавестись вторым аргументом. Если он будет числовым, то даже Typescript вас не убережёт от такой ошибки.

Но не будем отвлекаться. О чём собственно речь?

Всё чаще и чаще мы видим в живом коде такие методы как:

• .forEach

• .map

• .reduce

• и другие

В общем и в целом они имеют ту же bigO complexity, что и обыкновенные циклы. Т.е. до тех пор, пока речь не заходит об экономии на спичках, программист волен выбирать ту конструкцию, что ему ближе и понятнее.

Однако всё чаще и чаще вы можете видеть в обучающих статьях, в библиотечном коде, в примерах в документации код вида:

return source.reduce(
  (accumulator, item) => accumulator.concat(...something(item)), 
  []
);

или даже:

return Object
  .entries(object) 
  .reduce(
    (accumulator, value, key) => ({
      ...accumulator, 
      [key]: something(value)
    }), 
    {}
  );

Возможно многие из вас зададутся вопросом: а что собственно не так?

Ответ: вычислительная сложность. Вы наблюдаете разницу между O(n) и O(n^2) .

Давайте разбираться. Можно начать с ... -оператора. Как эта штука работает внутри? Ответ: она просто итерирует всю коллекцию (будь то элементы массива или ключи-значения в объекте) с 1-го до последнего элемента. Т.е.:

const bArray = [...aArray, 42]

это примерно тоже самое, что и:

const bArray = [];
for (let idx = 0; idx < aArray.length; ++ idx)
  bArray.push(aArray[idx]);

Как видите, никакой магии. Просто синтаксический сахар. Тоже самое и с объектами. На лицо очевидная сложность O(n).

Но давайте вернёмся к нашему .reduce. Что такое .reduce? Довольно простая штука. Вот упрощённый полифил:

Array.prototype.reduce = function(callback, initialValue) {
  let result = initialValue;
  for (let idx = 0; idx < this.length; ++ idx)
    result = callback(result, this[idx], idx);
  return result;
}

Наблюдаем всё тот же O(n). Уточню почему - мы пробегаем ровно один раз по каждому элементу массива, которых у нас N.

Что же тогда у нас получается вот здесь:

return source.reduce(
  (accumulator, item) => accumulator.concat(...something(item)), 
  []
);

Чтобы это понять надо, ещё посмотреть, а что такое .concat. В документации вы найдёте, что он возвращает новый массив, который состоит из переданных в него массивов. По сути это поэлементное копирование всех элементов. Т.е. снова O(n).

Так чем же плох вышеприведённый код? Тем что на каждой итерации в .reduce происходит копирование всего массива accumulator. Проведём мысленный эксперимент. Заодно упростим пример (но проигнорируем существование .map, так как с ним такой проблемы не будет):

return source.reduce(
  (accumulator, item) => accumulator.concat(something(item)),    
  [] 
);

Допустим наш source.length === 3. Тогда получается, что .reduce сделает 3 итерации.

• На 1-й итерации наш accumulator пуст, поэтому по сути мы просто создаём новый массив из одного элемента. // []

• на 2-й итерации наш accumulator уже содержит один элемент. Мы вынуждены скопировать его в новый массив. // [1]

• на 3-й итерации уже 2 лишних элемента. // [1, 2]

Похоже на то, что мы делаем лишнюю работу. Представьте что length === 1000. Тогда на последней итерации мы будем впустую копировать уже 999 элементов. Напоминает алгоритм маляра Шлемиля, не так ли?

Как нетрудно догадаться, чем больше length , тем больше лишней работы выполняет процессор. А это в свою очередь:

• замедляет программу

• т.к. Javascript однопоточный - препятствует работе пользователя с UI

• тратит батарейку ноутбука или телефона на бесполезную работу

• греет ваше устройство и заставляет работать кулер

В случае объектов ситуация ещё хуже, т.к. там речь идёт не о быстрых массивах, которые имеют многоуровневые оптимизации, а о dictionaries, с которыми, если кратко, всё сложно.

Но что можно с этим поделать? Много чего. Самое главное - переиспользовать тот же самый массивобъект:

// вместо
(accumulator, item) => accumulator.concat(...something(item))
// вот так
(accumulator, item) => {
   accumulator.push(...something(item));
   return accumulator; // это ключевая строка
}

// вместо
(accumulator, value, key) => ({
  ...accumulator, 
  [key]: something(value)
}, 

// вот так
(accumulator, value, key) => {
  accumulator[key] = something(value);
  return accumulator;
}

Стало чуть менее нагляднее (возможно), но разительно быстрее. Или нет? Давайте разбираться.

Как я уже сказал выше, всё зависит от размера коллекции. Чем больше итераций, тем больше разница. Я провёл пару простых тестов в Chrome и Firefox:

Firefox

Chrome

При length=30 разница не очень убедительная (13 vs 3). При length=1000 уже становится особенно больно (2600 vs 30).

Критика

Я понимаю, что к этому моменту будет уже много недовольных моими обобщениями. Простите, я попытался написать максимально просто. Но давайте пройдёмся по наиболее популярным аргументам против:

1. При малых N вы не заметите разницу

Что же, это valid point. Если N=3, то разница столь невелика, что едва ли вы хоть когда-нибудь столкнётесь с её последствиями. Правда ваши друзья из мира C++ перестанут с вами здороваться. Особенно в мире Javascript, который как известно скриптовый язык с динамической типизацией, и, поэтому, не предназначен для решения задач, которые требуют настоящей производительности. Что впрочем не мешает ему проникать даже в эти отрасли, вызывая потоки гнева

А что если у нас не 3 элемента, а скажем 30. На моих синтетических "наколеночных" тестах получилась разница в 4 раза. Если этот участок кода выполняется единожды, а не, скажем, в цикле, то вы, скорее всего, точно также не сможете ничего заметить. Ещё бы, ведь речь идёт о долях миллисекунды.

Есть ли тут подводные камни? На самом деле да. Я бы сказал, что тут возможны (как минимум) две проблемы.

• Первая проблема: сегодня ваш код исполняется единожды. Завтра вы запускаете его для какого-нибудь большого списка. Скорее всего даже не заглянув внутрь (в больших проектах это может быть очень непросто). В итоге та изначально небольшая разница, может начать играть весомую роль. И моя практика показывает, что хочешь рассмешить бога, расскажи ему о своих планах мы слишком часто ошибаемся в своих суждениях относительно того, как наш код будет использоваться в будущем.

• Вторая проблема: у вас ваш код запускается для 30 элементов. Okay. Но среди ваших пользователей есть 5% таких, у которых немного нестандартные потребности. И у них уже почему-то не 30, а 300. Кстати, возможно эти 5% пользователей делают 30% вашей выручки.

Приведу пример. На немецком сайте Ikea (надеюсь они это уже исправили) была проблема: при попытке купить больше 10-12 товаров корзина заказа начинала настолько люто тормозить, что почти любая операция с ней сводилась к 40 секундным задержкам. Т.е. до глупого забавная ситуация: человек хочет купить больше, т.е. отдать компании больше денег, но т.к. где-то внутри сокрыты алгоритмы маляра Шлемиля, он не может этого сделать. Полагаю разработчики ничего об этом не знали. И QA отдел тоже (если он у них есть). Не переоценивайте ваших посетителей, далеко не каждый будет готов ждать по 40 секунд на действие. Признаю, что пример экстремальный. Зато показательный.

Итого: в принципе всё верно. Для большинства ситуаций вы и правда не заметите разницы. Но стоит ли это того, чтобы экономить одну единственную строку? Ведь для того, чтобы избежать этой проблемы, не требуется менять алгоритм, не требуется превращать код в нечитаемый ад. Достаточно просто мутировать итерируемую коллекцию, а не создавать новую.

По сути всё сводится к: каковы мои трудозатраты и каков мой результат. Трудозатраты - одна строка. Результат - гарантия того, что у вас не возникнут "тормоза" на абсолютно ровном месте.

2. Чистые функции в каждый дом

Кто-то может возразить, что пока мы возвращаем в каждой итерации новый массив наша функция чиста, а как только мы начинаем в ней что-нибудь мутировать, мы теряем драгоценную purity. Ребята, любящие FP, у меня для вас замечательная новость: вы можете сколько угодно мутировать в своих чистых функциях state. Они от этого не перестают быть чистыми. И тут в меня полетели камни.

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

• быть детерминированной

• не вызывать side effect-ов

И да, мутация это effect. Но обратите внимание на слово "side". В нём вся соль. Если вы мутируете то, что было целиком и полностью создано внутри вашей функции, то вы не превращаете её в грязную. Условно:

const fn = () => {
  let val = 1;
  val = 2;
  val = 2;
  return val;
}

Это всё ещё чистая функция. Т.к. val существует только в пределах конкретного вызова метода и он для неё локален. А вот так уже нет:

let val = 1;
const fn = () => {
  val = 2;
  return val;
}

Т.е. не нужно идти ни на какие сделки с совестью (а лучше вообще избегать всякого догматизма), даже если чистота ваших функций вам важнее чистоты вашего тела.

3. Умный компилятор всё оптимизирует

Тут я буду краток: нет, не оптимизирует. Попробуйте написать свой, и довольно быстро поймёте, что нет никакой магии. Да внутри v8 есть разные оптимизации, вроде этой (Fast_ArrayConcat). И да, они не бесполезны. Но не рассчитывайте на магию. Увы, но мы не в Хогвартсе. Математические законы превыше наших фантазий.

По сути для того чтобы избежать O(n^2) в такой ситуации, компилятору необходимо догадаться, что сия коллекция точно никому не нужна и не будет нужна в текущем виде. Как это гарантировать в языке, в котором почти ничего нельзя гарантировать (из-за гибкости и обилия абстракций)?

Причина

Зачем эта статья? От безысходности и отчаяния. Мне кажется основной причиной этой широко распространённой проблемы является React и Redux, с их любовью к иммутабельности. Причём не сами эти библиотеки, а различные материалы к ним (коих тысячи), где встречается этот "паттерн". Если по началу это можно было объяснить тем, что хочется приводить максимально простые примеры, то сейчас это стало mainstream-ом.

Вот например:

PS: coming-out - часто делаю concat внутри reduce 🙂 в 99% задач вроде не сильно афектит

Или вот:

getDependencies(nodes) {
  this.processQueue();
  return nodes.reduce(
    (acc, node) => acc.concat(Array.from(this.dependencies.get(node) || [])),
    []
  );
}

I'm pretty surprised that this has any impact, I don't have a good rationale for why but it appears to be dramatically faster to update the array in place.

Складывается ощущение, что этот "паттерн" применяется почти в каждой второй статье про Javascript. Я думаю настало время что-то с этим делать. Люди на собеседованиях не видят никакой проблемы в вызове .includes внутри .filter и подобных штуках. ...-оператор по их мнению работает за O(1). А v8 переполнен магией. Люди с 7-ю+ годами боевого опыта делают удивлённые глаза и не понимают, что может пойти не так. Впрочем это уже другая история.

P.S. по вопросам опечаток и стилистических ошибок просьба обращаться в личку.