Как я ускорил движок на 13%11.06.2021 18:01

Недавняя статья о важности использования линейных алгоритмов вдохновила меня на оптимизацию «горячей» квадратической функции, о том как я это сделал, и к каким результатам это привело — я сегодня расскажу. Завари в чашке Пу Эр, откинься на спинку кресла:

▍Всё — 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». Последнее время в ходу были совсем другие лица, в духе предвоенных тридцатых, из чего напрашивалось множество далеко идущих выводов. Предоставив этим выводам идти туда в одиночестве, Андрей почистил зубы, быстро умылся и пошел к себе.
© Виктор Пелевин «Желтая стрела»

В результате оптимизации код стал не только быстрее отрабатывать, но и быть проще для восприятия, а значит более поддерживаемым и расширяемым. Поэтому смело заявляю: оптимизация «горячих» мест — корень всех благ!

▍Напоследок

В прошлое время люди часто спорили, существует ли локомотив, который тянет нас за собой в будущее. Бывало, что они делили прошлое на свое и чужое. Но все осталось за спиной: жизнь едет вперед, и они, как видишь, исчезли. А что в высоте? Слепое здание за окном теряется в зыби лет. Нужен ключ, а он у тебя в руках — так как ты его найдешь и кому предъявишь? Едем под стук колес, выходим пост скриптум двери».
© Виктор Пелевин «Желтая стрела»