Как стать автором
Обновить

Комментарии 28

Я прочитал пост несколько раз пытался понять откуда берётся ускорение.


Допустим у нас 5 раннеров и каждый раннер возвращает нам 10 файлов. В первом варианте каждый раннер будет вызван один раз, функция processFile будет вызвана для каждого файла, т.е. 50 раз.


Да тут есть цикл в цикле но это ничего не меняет. Каждый внутренний проходит только по тем файлам что вернул текущий раннер. Т.е. каждый раннер будет вызван один раз и processFile будет вызвана 50 раз.


function process() {
    const results = [];

    for (const run of runners) {
        const files = run();

        for (const file of files) {
            results.push(processFile(file));
        }

     return results;
}

Т.е. нет никакой разницы с


function process() {
    const results = [];

    for (const run of runners) {
        files.push(...run());
    }

    for (const file of files) {
        results.push(processFile(file));
    }
     return results;
}

Тут также каждый раннер вызывается один раз и потом для каждого файла (а их будет 50 штук) будет вызван processFile.


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


Это можно полечить например с помощью чего-то вроде [].concat(...runners.map(r => r()));, тогда хотя бы не будет добавления элементов по одному.


Но главный вопрос, почему же стало быстрее не давал мне покоя и кажется я нашёл ответ. Проводя контрольный замер автор сравнивает мастер+свой патч с некоторой версией v17.5.0. Рискну предположить что разница из-за какого-то другого изменения. А тактов стало меньше потому что автор разделил функцию на три и они просто между ними размазались.


Может быть я понял что-то не так?

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

Тут также каждый раннер вызывается один раз и потом для каждого файла (а их будет 50 штук) будет вызван processFile.

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


В двух словах идея такая:
имеет горячий код с квадратической сложностью -> делаем замеры -> оптимизируем код до линейной сложности -> делаем замеры -> код стал быстрее и проще в поддержке -> PROFIT


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

Как минимум код стал чище, а еще движку V8 проще оптимизировать маленькие функции, что хорошо отражается на производительности, по этому хуже он не стал точно :).


Это можно полечить например с помощью чего-то вроде [].concat(...runners.map(r => r()));, тогда хотя бы не будет добавления элементов по одному.

Буду благодарен за изминение кода + замеры, а еще мне не до конца понятно использование concat + spread при том, что map возвращает новый массив, и это равнозначно следующему коду:


runners.map((r) => r())

Но главный вопрос, почему же стало быстрее не давал мне покоя и кажется я нашёл ответ. Проводя контрольный замер автор сравнивает мастер+свой патч с некоторой версией v17.5.0. Рискну предположить что разница из-за какого-то другого изменения.

Ну это же легко проверить, вот ченчлог к версии v17.5.1, в этом и идея, что менялся только описанный код.


А тактов стало меньше потому что автор разделил функцию на три и они просто между ними размазались.

Не только тактов стало меньше, но и время выполнения сократилось, что намного важнее и гораздо заметнее для монорепозитория.

В двух словах идея такая:
имеет горячий код с квадратической сложностью -> делаем замеры -> оптимизируем код до линейной сложности -> делаем замеры -> код стал быстрее и проще в поддержке -> PROFIT

Вам несколько человек, включая меня, написали что вы НЕ изменили сложность алгоритма. BigO у вас НЕ изменилось. Отсюда все вопросы к измерениям. Не понятно почему стало лучше. Оба варианта алгоритмически идентичны.


Буду благодарен за изминение кода + замеры, а еще мне не до конца понятно использование concat + spread при том, что map возвращает новый массив, и это равнозначно следующему коду:

  1. Это не идентично. Ваш вариант вернёт массив массивов, а мой плоский массив.
  2. Идея в том, что добавляя элементы по одному вы можете попасть на квадратичную сложность. Операция может иметь линейную сложность и соответственно вы можете на каждом цикле попасть на копирование всего существующего массива. concat принимает сразу массивы и склеивает их, по крайней мере копирование будет одно.

Ну это же легко проверить, вот ченчлог к версии v17.5.1, в этом и идея, что менялся только описанный код.

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


Не только тактов стало меньше, но и время выполнения сократилось, что намного важнее и гораздо заметнее для монорепозитория.

Проблема в том, что не понятно из-за чего произошло изменение, это вызывает все вопросы. Совершенно не понятно при чём тут монорепозиторий.

Вам несколько человек, включая меня, написали что вы НЕ изменили сложность алгоритма. BigO у вас НЕ изменилось. Отсюда все вопросы к измерениям. Не понятно почему стало лучше. Оба варианта алгоритмически идентичны.

Ну как же не изменилось, если квадратическая сложность стала линейной.


Это не идентично. Ваш вариант вернёт массив массивов, а мой плоский массив.

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


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

В мастере многое уже поменялось, разработка не стоит на месте, правильнее наверно сравнивать версии 17.5.1 и 17.5.0.


Проблема в том, что не понятно из-за чего произошло изменение, это вызывает все вопросы.

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


Совершенно не понятно при чём тут монорепозиторий.

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

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


Смотрите пример. Вам надо обойти массив длиной N. Это можно сделать в цикле:


for (let i = 0; i < arr.length; i++) {
something(arr[i]);
}

Кажется мы оба согласны что это алгоритм линейной сложности.


Дальше смотрите я сделаю так:


const half = arr.length / 2;
for (let i = 0; i < 2; i++) {
    for (let j = half * i; j < half * (i+1); j++) {
      something(arr[j]);
    };
}

Является ли второй пример квадратичным? Ведь в нем есть "цикл в цикле"! Нет там все также линейная сложность. Можно переписать это ещё раз и сделать "цикл в цикле в цикле". Кошмар! Должна быть кубическая! Но нет все ещё остаётся линейная.


Но почему? Количество операций которые мы выполняем не изменилось. Мы проходим по каждому элементу один раз. От того что циклов стало два не изменится ничего. Я даже предположу что современные компиляторы выдадут одинаковый результат для обоих кусков кода.


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


Что касается вашего предложения перепроверить ваши замеры, извините но делать этого я не буду. Ваше предложение похоже на чайник Рассела. Вы высказали некоторое утверждение, я указал вам на то что оно кажется неверным и привел некоторое разумное объяснение. Вы предлагаете мне потратить значительно большее количество времени чем то что вы потратили на написание этой статьи. Извините, но даже не понятно что измерять. Вы сначала сравниваете с мастером, теперь с 17.5.0. Что за проект вы анализировали, не указано. Как прогревали кэши и сколько раз проводили измерения — не указано.


Потом вы сами пишете что да, может стало быстрее из-за того что v8 лучше оптимизирует. А может не стало, а может не лучше.


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

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

Я буду благодарен вам, если вы будете указывать ссылки на материал о котором говорите, и будет здорово, если над ним будет проделана такая же работа как над этой статьей, что бы он был таким же простым.


Что касается вашего предложения перепроверить ваши замеры, извините но делать этого я не буду.

Я предложил вам перепроверить ваши замеры, у вас же есть идеи по-поводу того, что concat быстрее push. Это ли не чайник Рассела?


Вы предлагаете мне потратить значительно большее количество времени чем то что вы потратили на написание этой статьи.

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


Извините, но даже не понятно что измерять. Вы сначала сравниваете с мастером, теперь с 17.5.0. Что за проект вы анализировали, не указано.

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

Ну я указал что вам нужно найти. Можете начать с Википедии или курса лекций Яндекса (сложность первые две лекции). То что ваше объяснение проще, ничего не стоит если оно не верное. А оно не верное.

Давайте отбросим рассуждения про push и concat. Разница там будет очень маленькой т.к. v8 оптимизирует push и я не думаю что будет разница заметная на тестах. Я писал про алгоритмическую сложность и сделал пометку про "зависит от реализации". За счёт дополнительной памяти можно сделать push в среднем линейным, если я правильно помню (это разбирается во второй лекции курса ссылку на который я дал).

Давайте вернёмся к главной теме. Ваши алгоритмы до и после оптимизации идентичны. Это изменение не приводит к изменению алгоритмической сложности. Вы можете что-то на это возразить?

Ну я указал что вам нужно найти. Можете начать с Википедии или курса лекций Яндекса (сложность первые две лекции)

Спасибо за ссылку на википедию, я ознакомился и не нашел ничего, что бы подтверждало ваши слова о том, что:


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

Звучит это очень загадочно, как и ваши примеры кода.


Давайте отбросим рассуждения про push и concat. Разница там будет очень маленькой т.к. v8 оптимизирует push и я не думаю что будет разница заметная на тестах. Я писал про алгоритмическую сложность и сделал пометку про "зависит от реализации". За счёт дополнительной памяти можно сделать push в среднем линейным, если я правильно помню (это разбирается во второй лекции курса ссылку на который я дал).

Конечно, давайте отбросим все, что имеет дело к реальному миру и к реальному быстродействию, а так же стимулирует к улучшению програмного продукта.


За счёт дополнительной памяти можно сделать push в среднем линейным, если я правильно помню (это разбирается во второй лекции курса ссылку на который я дал).

Спасибо, мне хватило ссылки на википедию.


Давайте вернёмся к главной теме. Ваши алгоритмы до и после оптимизации идентичны. Это изменение не приводит к изменению алгоритмической сложности. Вы можете что-то на это возразить?

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


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

И где-то это даже может быть очень важно, но цель статьи, в том что бы показать, что оптимизация важна и она может улучшать качество кода.

Звучит это очень загадочно, как и ваши примеры кода.

Извините, но это буквально уже невежливо.


Ваша статья строится на том, что вы изменили сложность алгоритма с квадратичной на линейную. Это основное утверждение которое вы сформулировали в своей статье. Я утверждаю что у вас НЕ изменилась сложность алгоритма т.к. он как был линейным так и остался (если считать за N число файлов).


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


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


Вот в википедии написано:


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

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


Дальше вы начинаете писать что то про стоимость поддержки и что оптимизация важна. Я просто не понимаю вы мешаете стоимость поддержки с алгоритмической сложностью.


Если бы вы написали "я сделал код более читаемым и поддерживаемым, и при этом он ещё почему-то начал быстрее работать, возможно v8 лучше оптимизирует" у меня не было бы ни одного вопроса. Но вы пишете что вы уменьшили вычислительную сложность и улучшили скорость выполнения. То есть вы буквально вводите читателя в заблуждение и говорите что делаете это потому что "для базового понимания материала мой подход гораздо удобнее".


Касательно замены push на concat я совершил ошибку что об этом написал. Не потому что то что я сказал неправильно просто теперь вы всё время пытаетесь увести разговор на это, вместо то чтобы обсуждать что в статье допущена ошибка. Если мы придём к согласию относительно статьи я могу разобрать с вами смысл замены push на concat и объяснить почему это может или не может приводить к изменению скорости исполнения (с учётом реализации в v8), но сейчас давайте оставим этот вопрос за скобками, т.к. в реальных условиях вклад этого изменения врятли будет заметен измерением. Либо вы можете разобраться в этом сами если посмотрите первые две лекции курса ссылку на который я отправил выше. При том что ваше изменение вклада не имеет вообще потому что это буквально тот же код.


Кроме того я провёл измерение следующим способом:


git pull https://github.com/coderaiser/putout.git

# коммит с оптимизацией
git checkout 07ced670d1ff03c768844b114f63e70117b15be3
npm i

# Первый прогон отбрасываем чтобы прогрелись все кэши
time npm run lint:fresh

# Делаем три прогона и усредняем
time npm run lint:fresh
time npm run lint:fresh
time npm run lint:fresh

# откатываем коммит с оптимизацией
git revert 07ced670d1ff03c768844b114f63e70117b15be3
npm i

# Первый прогон отбрасываем чтобы прогрелись все кэши
time npm run lint:fresh

# Делаем три прогона и усредняем
time npm run lint:fresh
time npm run lint:fresh
time npm run lint:fresh

Я получил такие результаты.


С оптимизацей
Executed in 36.76 secs
Executed in 37.00 secs
Executed in 36.51 secs
Среднее 36.76


Без оптимизации
Executed in 36.93 secs
Executed in 36.88 secs
Executed in 36.79 secs
Среднее 36.87


Разница 0.11s или 0.3%. При том что разброс между отдельными измерениями вполне доходит до 0.5s я думаю что это можно списать на погрешность. Ни о каких 13% ускорения речи не идёт.

Внес правки в соответствии с вашими предложениями, благодарю за проделанную работу! У меня числа получились другими, возможно дело было в конкретной версии node.js. Рад, что вы не поленились клонировать репозиторий, кстати, недавно вышел Putout v18, в котором я немного переосмыслил API процессоров, сделав его более наглядным.


Буду рад любым пулл риквестам от вас, которые могут улучшить быстродействие :)!

Не понял ничего. Изначальный и конечный код у вас асимптотически идентичен. BigO тот же самый. Было O(N + M), где N это число run, а M это количество файлов из этих run() (из всех сразу). И на выходе всё тоже самое. То, что вы убрали цикл из цикла на асимптотику не повлияло, т.к. количество операций то же самое (N-раз для run, M-раз для files). Сам M зависит от N, но не только от N, а ещё от… надо смотреть что внутри run.


Количество вложенности в циклах не влияет на асимптотику так, как вы вероятно думаете. Положим есть у вас квадратный массив 10 на 10 array: number[][]. Вы можете его обойти за счёт двух for-of, а можете работать с плоским массивом на 100 элементов (array: number[]). В одном случае у вас два цикла, один вложен в другой и bigO(N*M) (где N = 10, M = 10), а во втором случае bigO(Z), где Z = 100. Но асимптотика получается та же самая.


О чём статья? Почему такие странные выводы? Вы точно сравнивали сопоставимые вещи? :)


Положим (для удобства) что все run() дают ровно Z файлов. Тогда в первом случае у вас O(n * z), а во втором O(n) + O(n * z) = O(n * z). Т.е. одно и то же.

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

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

O(1) — константная сложность, идеальный вариант, сколько данных — столько и операций.
Неправильно описано. O(1) — нет зависимости от количества данных. Классический пример O(1) — поиск элемента в массиве. Вы просто вычисляете смещение элемента и возвращаете его. Вам не важно* 10 у вас элементов в массиве, 1000 или миллиард.

* Аппаратная реализация с кэшами может вносить коррективы, но с точки зрения алгоритма — разницы нет.

Речь идет о том, что количество входных данных не влияет на количество операций выполняемых функцией, поэтому да: не важно 10 элементов в массиве или миллиард.

Но в тексте написано прямо противоположное. "сколько данных — столько и операций" это линейная сложность.


Простейший пример линейной сложности — поиск в односвязном списке. Чтобы получить элемент с номером N вам надо пройти по N ссылкам. В худшем случае, при получении последнего элемента по всему списку. Т.е. "сколько элементов в массиве, столько и операций". Размер списка имеет значение.


Пример константной сложности — поиск в массиве. Чтобы получить элемент с номером N надо просто взять смещение по размеру элемента и обратиться к нужному месту в памяти. Поэтому размер массива не имеет значения.


О(1) это константная сложность.

Да, вы правы, переформулировал. Спасибо большое!

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

Очень хорошая идея, я делал такие изменения с замерами и они ни на что не влияли в плане скорости, а код был менее поддерживаемым. Буду благодарен если поменяете код и произведете замеры:


В теории нет разницы между теорией и практикой. А на практике есть.
Количество runners — N
Максимальное количество файлов, возвращаемое runner — M
Было:
function process() {
    const results = [];
    
    for (const run of runners) { // N итераций, по одной для каждого элемента runners
        const files = run();
  
        for (const file of files) { // M итераций, по одной  для каждого элемента files
            results.push(processFile(file));
        }
     
     return results;
}

O(N * M)

Стало:
function process() {
    const results = [];
  
    for (const run of runners) { // N итераций, по одной для каждого элемента runners
        files.push(...run());  // M итераций, по одной  для каждого элемента, возвращаемого run(). Spread оператор не за константу ведь работает?
    }
    
    for (const file of files) { // N*M итераций, по одной  для каждого элемента files (для каждого из N runners мы добавили в files M элементов).
        results.push(processFile(file));
    }
     return results;
}

O(N*M) + O(N*M) = O(N*M)

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

Внёс уточнения в статью, спасибо большое за детальный разбор!

Но почему-то оставили в основной части статьи, что у вас «оптимизация» превращает сложность из квадратической в линейную. Наверно потому что иначе неоткуда взяться 13%? Вам уже несколько раз доходчиво объяснили почему сложность не изменилась. Еще большие вопросы к вашей методике измерения, по статье выглядит так, будто вы сделали по одному прогону, в таком случае совсем неудивительно получить неправильные результаты. Причем тут уже доказали ошибочность измерений

Вы мне предлагаете переписать статью? Присылайте правки, я посмотрю что можно улучшить :).

То есть исправлять явные ошибки, лежащие в основе статьи, которые к тому же вводят читателя в заблуждение, за вас должны другие? Да, предлагаю переписать, на вашем месте я бы сделал именно так

Лучше просто удалить.

В результате оптимизации код стал не только быстрее отрабатывать, но и быть проще для восприятия, а значит более поддерживаемым и расширяемым

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

Очень хороший аргумент! Рассмотрим такой вариант.
Открываем processor.js:


function process(runners) {
    const files = getFiles(runners);
    const results = lintFiles(files);

    return results;
}

Видим, что у нас две операции, которые происходят последовательно. Вначале getFiles, а потом lintFiles, при этом getFiles зависит только от значения runners, переданных из вне. Тут происходит разделение сущностей на уровне выполняемого действия согласно Философии UNIX:


Пишите программы, которые делают что-то одно и делают это хорошо

Далее, в случае необходимости, разобраться почему файлы не все пришли, либо, почему не сработало конкретное правило, а другие правила на файле сработали — будет совсем просто. Таким образом, имея на выходе данные, мы можем получить достаточно информации, что бы заглянуть в getFiles:


function getFiles(runners) {
    const files = [];

    for (const run of runners) {
        files.push(...run());
    }

    return files;
}

Либо lintFiles:


function lintFiles(files) {
    const results = [];

    for (const file of files) {
        results.push(processFile(file));
    }

    return results;
}

Для того, что бы разобраться в конкретных деталях.


Так же, если нужно будет поменять способ получения списка файлов, либо добавить еще несколько видов обработок файлов — достаточно будет добавить рядом функцию и ее вызов.


Теперь для понимания связи между двумя циклами я должен просмотреть отдельно функции и при внесении изменений редактировать их отдельно друг от друга.

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

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.