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

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

Допустим у нас 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. Рискну предположить что разница из-за какого-то другого изменения. А тактов стало меньше потому что автор разделил функцию на три и они просто между ними размазались.

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

Не понял ничего. Изначальный и конечный код у вас асимптотически идентичен. 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). Т.е. одно и то же.

O(1) — константная сложность, идеальный вариант, сколько данных — столько и операций.

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;
}

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;
}

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