Недавняя статья о важности использования линейных алгоритмов вдохновила меня на оптимизацию «горячей» квадратической функции, о том как я это сделал, и к каким результатам это привело — я сегодня расскажу. Завари в чашке Пу Эр, откинься на спинку кресла:
▍Всё — JavaScript
…в сущности, никакого счастья нет, есть только сознание счастья. Или, другими словами, есть только сознание.В начале этого
© Виктор Пелевин «Желтая стрела»
js(x)
, ts(x)
и flow
файлы, но и markdown
, yaml
, ignore
, json
, и любые другие, реализующие интерфейс движка.Процессор достает
JavaScript
-код из файлов, и склеивает все обратно, например в процессоре Markdown.Либо конвертирует
json
, yaml
и ignore
в JavaScript
для поиска и исправления ошибок плагинами.Интерфейс процессора выглядит так:
process(rawSource, {fix}) -> [processedSource, processedPlaces]
— возвращает обработанный исходный код либо найденные ошибки в соответствии с флагомfix
;preProcess(processedSource) -> preProcessedList
— изымаетJavaScript
изprocessedSource
для проверки и исправления;postProcess(processedSource, preProcessedList) -> processedSource
— склеивает исправленныйJavaScript
;
Сердце Putout состоит из 4-х частей(движков):
- Парсер переводит строку в
AST
иAST
обратно в строку; - Загрузчик находит и загружает плагины (в том числе для
Babel
), и кодмодыjscodeshift
- Исполнитель распознает и обрабатывает все виды плагинов (сейчас их 4);
- Процессор управляет работой предыдущей троицы;
Схема работы может выглядеть так:
▍Ищем «горячие» функции
Всё дело в том, что мы постоянно отправляемся в путешествие, которое закончилось за секунду до того, как мы успели выехать.В соответствии с законом Парето: 20% верно направленных усилий дадут нам 80% результата, поэтому первым делом всегда имеет смысл найти самые «горячие» функции, и с ними работать.
© Виктор Пелевин «Желтая стрела»
Для начала получим
isolate
-файл в node v14
с помощью ключа --prof, запустим из корня репозитория:node --prof packages/putout/bin/putout.mjs --fresh .
После чего обработаем его с помощью ключа
--prof-process
: node --prof-process isolate-0x1049e5000-86428-v8.log > processed.txt
Просматривая информацию, которая относится к
engine-processor
в processed.txt
замечаем строку:334 93.6% LazyCompile: *module.exports.runProcessors /Users/coderaiser/putout/packages/engine-processor/lib/processor.js:26:32
Ага, движок Процессоров отрабатывает 334 такта и 93,6% вызовов, при вызове родительской функции.
▍Немного про Big O
Прошлое — это локомотив, который тянет за собой будущее. Бывает, что это прошлое, вдобавок чужое. Ты едешь спиной вперёд и видишь только то, что уже исчезло. А чтобы сойти с поезда, нужен билет. Ты держишь его в руках, но кому ты его предъявишь?Для функции
© Виктор Пелевин «Желтая стрела»
fn
, которая принимает на вход data
, и возвращает result
:const result = fn(data);
Big O дает информацию о самом пессимистичном варианте развития событий.
Время выполнения
fn
можно получить с помощью функции complexity
, она принимает на вход operationsCount
:const time = complexity(operationsCount);
Время выражается буквой
n
, это удобнее чем пользоваться числами, поскольку их много, но их значение не особо важно (отсекаем Бритвой Оккама): техника — меняется, на смену слабым компьютерам — приходят новые, более производительные. Что действительно имеет значение, так это: возможность сравнения алгоритмов. И она существует! Это Big O, и вот его простейшие примеры:- O(1) — константная сложность, идеальный вариант, количество данных не влияет на количество операций. Конкретное количество операций не особо важно, важно, что бы разница между количество входных данных и операций была не большой:
time = complexity(2 + n); O(1); const fn = (name) => { const str = `hello ${name}`; return str; }
- O(n) — линейная сложность, оптимальный вариант в плане возможности и сложности реализации, может встречаться в обходе списка файлов в директории для обработки. Для 10 файлов, выполнится 100 операций:
time = complexity(n * 10); O(n); const fn = (files) => { const results = []; for (const file of files) { results.push(processFile(file)); } return results; }
- O(n^2) — квадратичная сложность, не очень хороший вариант, поскольку количество операций гораздо быстрее растет чем количество входных данных. Разница в количестве итераций каждого из циклов не особенно важна, поэтому мы всегда можем округлить все до
n
. Еслиrunners
содержит 5 элементов, аrun
каждый раз возвращает по 10 элементов, получим:
time = complexity(5 * 10); O(n * n); function process(runners) { const processed = []; for (const run of runners) { const files = run(); for (const file of files) { processed.push(processFile(file)); } return processed; }
▍Оптимизируем
— Запомни, когда человек перестает слышать стук колес и согласен ехать дальше, он становится пассажиром.Упрощенный вариант запуска Движка Процессоров содержит цикл в цикле, то есть имеет
— Нас никто не спрашивает, согласны мы или нет. Мы даже не помним, как мы сюда попали. Мы просто едем, и все. Ничего не остается.
— Остается самое сложное в жизни. Ехать в поезде и не быть его пассажиром.
© Виктор Пелевин «Желтая стрела»
квадратическую сложность
, выглядит так:function process(runners) {
const processed = [];
for (const run of runners) {
const processed = run();
for (const file of files) {
processed.push(processFile(file));
}
return processed;
}
Упрощенный исправленный вариант содержит два последовательных цикла, и имеет
линейную сложность
, выглядит так:function process(runners) {
const processed = [];
for (const run of runners) {
files.push(...run());
}
for (const file of files) {
processed.push(processFile(file));
}
return processed;
}
А в идеальном варианте, функции с циклами вынесены, и вызываются из главной функции:
function process(runners) {
const files = getFiles(runners);
const linted = lintFiles(files);
return linted;
}
function getFiles(runners) {
const files = [];
for (const run of runners) {
files.push(...run());
}
return files;
}
function lintFiles(files) {
const linted = [];
for (const file of files) {
linted.push(processFile(file));
}
return linted;
}
▍Снимаем замеры
Весь этот мир — попавшая в тебя жёлтая стрела, поезд, на котором ты едешь к разрушенному мосту.Для снятия замеров я использовал
© Виктор Пелевин «Желтая стрела»
time
. Это не самый точный способ, поскольку на разных компьютерах время выполнения может сильно отличатся, однако в рамках одной системы, время +- одинаковое и разница между большинством запусков не особо значительна. К примеру на маке время выполнения меньше в два раза чем на удаленном линуксе, в соответствии с характеристиками, у тебя время может отличатся.Когда я пишу
putout
часто запускаю проверки (уже более чем) 1800 файлов, и полторы минуты, может показаться не много, но если сравнить со временем выполнения 3000 тестов за 15 секунд, становится ясно: есть куда расти! Таким образом выберем тег v17.5.0
и запустим свежий линт с помощью redrun:git checkout v17.5.0 && time redrun fresh:lint
> putout . --fresh
real 1m32.712s
user 1m25.502s
sys 0m6.542s
git checkout master && time redrun fresh:lint
> putout . --fresh
real 1m20.898s
user 1m13.502s
sys 0m6.542s
Нас интересуют первые строки: минута 33 секунды, и минута 20 секунд — стало быстрее на 13 секунд, это около 12% к ним добавим замер после оптимизации до идеального варианта и получим все 13%.
Повторив поиск «горячих» функций, получаем такие числа:
73 54.9% LazyCompile: *module.exports.runProcessors /Users/coderaiser/putout/packages/engine-processor/lib/processor.js:26:32
Отработанных тактов в 4 раза меньше, и проценты уменьшились с 93% до 54%, что само по себе очень не плохо. Буду благодарен, если кто-то в комментариях расширит информацию о данных, которые сохраняет в файл профайлер.
▍Далеко идущие выводы
Закрыв за собой дверь, Андрей включил воду, поглядел на свое лицо в зеркале и подумал, что за последние лет пять оно не то что повзрослело или постарело, а скорее потеряло актуальность, как потеряли ее расклешенные штаны, трансцендентальная медитация и группа “Fleetwood Mac”. Последнее время в ходу были совсем другие лица, в духе предвоенных тридцатых, из чего напрашивалось множество далеко идущих выводов. Предоставив этим выводам идти туда в одиночестве, Андрей почистил зубы, быстро умылся и пошел к себе.
© Виктор Пелевин «Желтая стрела»
В результате оптимизации код стал не только быстрее отрабатывать, но и быть проще для восприятия, а значит более поддерживаемым и расширяемым. Поэтому смело заявляю: оптимизация «горячих» мест — корень всех благ!
UPDATE Судя по всему, я допустил ошибку в подсчете алгоритмической сложности, и то, что я называю линейным алгоритмом, представляет из себя O(n * m), спасибо большое @Yavanosta, faiwer, nvgordeev за существенные дополнения к статье в виде комментариев! Я согласен, что слишком сильно упростил подсчет сложности, но очень рад развернувшейся дискуссии, привлечения интереса к теме Big O и возможности открыть для себя что-то новое. В любом случае итоговый код стал проще в поддержке и восприятии, а на скорость могла повлиять особенность оптимизации маленьких функций в движке V8.
▍Напоследок
В прошлое время люди часто спорили, существует ли локомотив, который тянет нас за собой в будущее. Бывало, что они делили прошлое на свое и чужое. Но все осталось за спиной: жизнь едет вперед, и они, как видишь, исчезли. А что в высоте? Слепое здание за окном теряется в зыби лет. Нужен ключ, а он у тебя в руках – так как ты его найдешь и кому предъявишь? Едем под стук колес, выходим пост скриптум двери».
© Виктор Пелевин «Желтая стрела»