Недавняя статья о важности использования линейных алгоритмов вдохновила меня на оптимизацию «горячей» квадратической функции, о том как я это сделал, и к каким результатам это привело — я сегодня расскажу. Завари в чашке Пу Эр, откинься на спинку кресла:
▍Всё — JavaScript
…в сущности, никакого счастья нет, есть только сознание счастья. Или, другими словами, есть только сознание.
© Виктор Пелевин «Желтая стрела»
В начале этого кода года (или в конце прошлого) среди движков статического анализатора putout появился новый игрок: движок Процессор. Теперь проверять, и исправлять можно не только 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— склеивает исправленный code>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() { 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) { 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; }А в идеальном варианте, функции с циклами вынесены, и вызываются из главной функции:
function process() { const files = getFiles(runners); const getResults = getResults(files); return getResults; } function getFiles(runners) { const files = []; for (const run of runners) { files.push(...run()); } return files; } function getResults(files) { const results = []; for (const file of files) { results.push(processFile(file)); } return results; }
▍Снимаем замеры
Весь этот мир — попавшая в тебя жёлтая стрела, поезд, на котором ты едешь к разрушенному мосту.
© Виктор Пелевин «Желтая стрела»
Для снятия замеров я использовал 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”. Последнее время в ходу были совсем другие лица, в духе предвоенных тридцатых, из чего напрашивалось множество далеко идущих выводов. Предоставив этим выводам идти туда в одиночестве, Андрей почистил зубы, быстро умылся и пошел к себе.
© Виктор Пелевин «Желтая стрела»
В результате оптимизации код стал не только быстрее отрабатывать, но и быть проще для восприятия, а значит более поддерживаемым и расширяемым. Поэтому смело заявляю: оптимизация «горячих» мест — корень всех благ!
▍Напоследок
В прошлое время люди часто спорили, существует ли локомотив, который тянет нас за собой в будущее. Бывало, что они делили прошлое на свое и чужое. Но все осталось за спиной: жизнь едет вперед, и они, как видишь, исчезли. А что в высоте? Слепое здание за окном теряется в зыби лет. Нужен ключ, а он у тебя в руках – так как ты его найдешь и кому предъявишь? Едем под стук колес, выходим пост скриптум двери».
© Виктор Пелевин «Желтая стрела»
ссылка на оригинал статьи https://habr.com/ru/company/ruvds/blog/562226/
Добавить комментарий