Эффект бабочки — как мы увеличили производительность линтера в 100 раз

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

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

Обнаружение проблемы

Мы всегда знали, что можем улучшить производительность правила линтера. Как и в других частях Nx, мы постоянно находили способы сэкономить еще 100 мс то тут, то там. Улучшение производительности было постоянным процессом. 

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

Не все циклы рождаются одинаковыми

На первый взгляд, ничего особенного. Код был логичным, не имел ненужных вложенных циклов, использовал современные функции высшего порядка Array — filter, map, reduce, что помогло сделать код короче и легче читаемым. Мы также использовали популярный трюк с Set для извлечения уникальных значений из массива.

Код выглядел следующим образом (для простоты мы заменили некоторые функции псевдокодом):

const allReachableProjects = Object.keys(graph.nodes)
  .filter(pathExistsBetweenSourceAndNode && graph.dependencies[project]);

const externalDependencies = allReachableProjects
  .map((project) =>
    graph.dependencies[project].filter(
      isDependencyExternal
    )
  )
  .filter((deps) => deps.length)
  .flat(1);

return Array.from(new Set(externalDependencies));
Вход в полноэкранный режим Выйти из полноэкранного режима

Мы отфильтровали все узлы, достижимые из нашего source node, которые имели зависимости. Затем мы сопоставили каждый из этих проектов с массивами их внешних зависимостей, отфильтровали те, у которых не было внешних зависимостей, и, наконец, сплющили двумерный массив до обычного массива.

Последняя строка — Array.from(new Set(...)) использует вышеупомянутый трюк для отсеивания дубликатов.
Функции высшего порядка — это очень хороший способ инкапсулировать код, который в противном случае был бы кодовым, но он сопряжен со скрытой ценой. Каждая итерация map, filter и reduce создает новый массив, объединяя элементы из предыдущей итерации и добавляя новый элемент.

Это привело к появлению скрытого внутреннего цикла. То, что первоначально выглядело как один цикл, в действительности было двумя циклами:

  • итерация по элементам исходного массива
  • итерация по элементам временного массива на каждом шаге.

Чтобы избежать этого, мы использовали циклы for с Array.push. Мы начинаем с пустого массива reachableProjects, и каждый раз, когда проект удовлетворяет условию, мы заталкиваем его в наш массив. Мы применили ту же логику к externalDependencies. Вместо map, filter и flat мы используем циклы и условия if. Мы вводим хэш-таблицу, чтобы гарантировать отсутствие дубликатов в нашей результирующей коллекции. Как только мы добавляем проект в массив, мы помечаем его в нашей хэш-таблице значком true, чтобы можно было быстро проверить, не добавили ли мы его уже.

Вот как выглядит полученный код:

if (!graph.externalNodes) {
  return [];
}
const reachableProjects = [];
const projects = Object.keys(graph.nodes);

for (let i = 0; i < projects.length; i++) {
  if (pathExistsBetweenSourceAndNode) {
    reachableProjects.push(projects[i]);
  }
}

const externalDependencies = [];
const externalDependenciesMap = {};
for (let i = 0; i < reachableProjects.length; i++) {
  const dependencies = graph.dependencies[reachableProjects[i]];
  if (dependencies) {
    for (let d = 0; d < dependencies.length; d++) {
      const dependency = dependencies[d];
      if (graph.externalNodes[dependency.target] && !externalDependenciesMap[dependency.target]) {
        externalDependencies.push(dependency);
        externalDependenciesMap[dependency.target] = true;
      }
    }
  }
}

return externalDependencies;
Вход в полноэкранный режим Выход из полноэкранного режима

Бенчмарк показал замедление на 2-3%, что значительно лучше, чем первоначальные 20%. В сочетании с дополнительным переключателем это стало приемлемым. Успех в улучшении производительности побудил нас проверить оставшийся код правил и посмотреть, можем ли мы применить аналогичный подход в других местах.

Принцип одной полки

К сожалению, было не так много функций filter или map для замены, а те, что были, не сильно изменили ситуацию. В основном замедление происходило из-за двух функций:

  • поиск исходного проекта на основе файла
  • поиск целевого проекта на основе импорта.

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

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

Перед:

{
  "nodes": {
    "project-a": {
      // ... other fields
      "data": {
        // ... other fields
        "files": [
          { 
            "file": "packages/project-a/a.ts", 
            "hash": "...", 
            "ext": "ts"
          },
          // ...
        ]
      }
    },
    // ... other projects
  },
  "externalNodes": { ... },
  "dependencies": [...]
}
Вход в полноэкранный режим Выход из полноэкранного режима

После (обратите внимание на раздел файлов):

{
  "nodes": {
    "project-a": {
      // ... other fields
      "data": {
        // ... other fields
        "files": {
          "packages/project-a/a": { 
            "file": "packages/project-a/a.ts", 
            "hash": "...", 
            "ext": "ts" 
          },
          // ...
        }
      }
    },
    // ... other projects
  },
  "externalNodes": { ... },
  "dependencies": [...]
}
Войти в полноэкранный режим Выйти из полноэкранного режима

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

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

{
  "nodes": {
    "project-a": {
      // ... other fields
      "data": {
        // ... other fields
        "files": [
          { 
            "file": "packages/project-a/a.ts", 
            "hash": "...", 
            "ext": "ts"
          },
      // ...
        ]
      }
    },
    // ... other projects
  },
  "externalNodes": { ... },
  "dependencies": [...],
  "allFiles": {
    "packages/project-a/a": "project-a",
    // ...
  }
}
Вход в полноэкранный режим Выход из полноэкранного режима

Забытое распространение O(n²)

Некоторые пользователи сообщали, что линтер слишком медленный для них. Один из наших клиентов сообщил о невероятных значениях, когда правило enforce-module-boundaries выполнялось в течение минуты на проект и потребляло до 96% всей работы по линтингу.

Мы были рады протестировать это новое улучшение на их решении. К нашему удивлению, улучшение оказалось «всего лишь» 6-кратным. Линтование проекта по-прежнему занимало почти 10 секунд.

Мы начали копать и отслеживать время каждого блока кода с помощью console.time, пока не поняли, что почти все это время было потрачено на проверку круговых зависимостей. Код, который проверял наличие круговых зависимостей, был прост — у нас есть матрица смежности:

  • Учитывая каждую пару проектов (A, B), если проект B достижим из проекта A, мы помечаем это поле в матрице true.
  • Чтобы проверить, существует ли круговая зависимость, мы проверяем, достижим ли A из B, где B является прямой зависимостью от A.

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

function buildMatrix(graph) {
  const dependencies = graph.dependencies;
  const nodes = Object.keys(graph.nodes);
  const adjList = {};
  const matrix = {};

  const initMatrixValues = nodes.reduce((acc, value) => {
    return { ...acc, [value]: false };
  }, {});

  for (let i = 0; i < nodes.length; i++) {
    const v = nodes[i];
    adjList[v] = [];
    matrix[v] = { ...initMatrixValues };
  });

  for (let proj in dependencies) {
    for (let dep of dependencies[proj]) {
      if (graph.nodes[dep.target]) {
        adjList[proj].push(dep.target);
      }
    }
  }

  const traverse = (s: string, v: string) => {
    matrix[s][v] = true;

    for (let adj of adjList[v]) {
      if (matrix[s][adj] === false) {
        traverse(s, adj);
      }
    }
  };

  nodes.forEach((v) => {
    traverse(v, v);
  });

  return {
    matrix,
    adjList,
  };
}
Вход в полноэкранный режим Выход из полноэкранного режима

Как вы могли узнать из этой статьи, использование reduce — не самое разумное решение, когда вы заботитесь о производительности, поэтому первым нашим шагом было заменить reduce на цикл for и Array.push. Затем мы сосредоточились на обычном подозреваемом — рекурсии в функции traverse. Но все потенциальные улучшения не дали результата. Поэтому мы снова добавили console.time, чтобы выяснить, что происходит. Оказалось, что проблемной была строка:

matrix[v] = { ...initMatrixValues };
Войти в полноэкранный режим Выход из полноэкранного режима

Что же там происходило?

Сначала мы создаем объект initMatrixValues, хэш-карту по умолчанию, где имя проекта указывает на false. Затем мы проходим по узлам и устанавливаем значения в матрице, где каждый проект указывает на копию initMatrixValues. Это казалось хорошей идеей.

К сожалению, мы забыли, что при распространении объекта происходит итерация по всем его членам, эффективно делая еще один внутренний цикл в forEach. Он также создает временный объект на каждом шаге и копирует все члены в новый объект на каждом шаге пути. Вы правильно догадались — это добавляет еще один цикл, эффективно давая O(n³) сложность.

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

for (let i = 0; i < nodes.length; i++) {
  const node = nodes[i];
  adjList[node] = [];
  const initMatrixValues = {};
  for (let j = 0; j < nodes.length; j++) {
    initMatrixValues[nodes[j]] = false;
  });
  matrix[node] = { ...initMatrixValues };
});
Вход в полноэкранный режим Выход из полноэкранного режима

И тут Стефан, который помогал с исследованием производительности, сделал блестящее открытие — мы явно используем false, чтобы отметить, что между двумя узлами нет связи. Тем не менее, мы также можем предположить, что отсутствие значения означает отсутствие связи. Вместо того чтобы генерировать объект с предварительно заполненными узлами с явным значением false, мы могли бы начать с пустого объекта. Это, наконец, привело нас к идеальному O(n) и дало нам 100-кратное улучшение по сравнению с первоначальным запуском (сама функция работает экспоненциально быстрее, как видно из этого бенчмарка).
Теперь код выглядел следующим образом:

for (let i = 0; i < nodes.length; i++) {
  const node = nodes[i];
  adjList[node] = [];
  matrix[node] = {};
});
Вход в полноэкранный режим Выйти из полноэкранного режима

Оригинальный твит показал цифры улучшения производительности на проекте клиента:

Miro
@meeroslav
🤫 Скоро появится в вашем монорежиме @NxDevTools.

Больше информации позже…

10:01 AM — 21 Jul 2022

Заключение

В этой статье мы показали, как небольшие изменения могут оказать огромное влияние на производительность вашего кода. Даже такое простое изменение, как slice вместо replace + regex может сократить время. Современные функции высшего порядка делают ваш код более гладким, но за это часто приходится платить.

Если вы выполняете цикл над небольшой коллекцией, вы, скорее всего, не заметите никакой разницы от внедрения таких микрооптимизаций.

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

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

Кредиты

Спасибо Стефану Ван де Ворену, который помог провести сравнительный анализ улучшений на репозитории своей компании и предоставил ценные материалы, а также обратил наше внимание на серьезность проблемы производительности на линтере. Благодарим также Юрия Штрумпфлонера за ценную обратную связь при рецензировании этой статьи.

Оцените статью
devanswers.ru
Добавить комментарий