Ускоряем JS до предела C

В этой статье я попробую заглянуть за пределы возможностей языка JavaScript и оценить, как производительность может существенно различаться при написании выразительного, декларативного и лаконичного кода по сравнению с оптимизированным. На примере функции, определяющей, является ли строка палиндромом, я покажу несколько вариантов решения задачи с замерами времени на исполнение. Затем напишу модуль на C, который буду вызывать наряду с методами на JavaScript для замера скорости. Проведу низкоуровневые оптимизации. Все это стало возможно благодаря развитию ИИ.

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

const isPalindromeJSBase = (s) => {
    const clear = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
    return clear === [...clear].reverse().join('');
}

Возьмем ее за основу.

Далее будут применены оптимизации:

Оптимизация 1: Ускорение за счет исключения ненужных преобразований и использования регулярных выражений.

export function isPalindromeJSFast(s) {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
      while (left < right && !isAlphanumeric(s[left])) {
          left++;
      }
      while (left < right && !isAlphanumeric(s[right])) {
          right--;
      }
      if (s[left] !== s[right]) {
          if (s[left].toLowerCase() !== s[right].toLowerCase()) {
              return false;
          }
      }
      left++;
      right--;
  }
  return true;
}

function isAlphanumeric(c) {
  return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

Эта оптимизация позволяет ускорить выполнение функции в 4.5 раза!

Оптимизация 2: Допущение об одинаковом регистре

Делаю допущение, что в большинстве случаев строки будут в одном регистре, и только при несовпадении привожу их к единому регистру:

// isPalindromeJSFast
    if (s[left] !== s[right]) {
          if (s[left].toLowerCase() !== s[right].toLowerCase()) {
              return false;
          }
      }

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

Оптимизация 3: Использование C для максимальной производительности

С помощью ChatGPT я написал модуль на C, который показывает уже 20-кратное улучшение производительности по сравнению с базовой функцией. Данный модуль можно использовать в JS-коде. Также можно использовать в TypeScript, покрыв типами.
Код на C можно посмотреть в репозитории в закрепе.

Оптимизация 4: Использование SIMD-инструкций

На MacBook Air M1 с использованием SIMD-инструкций (аналоги AVX в x86)удалось добиться ускорения в 224 раза по сравнению с базовой функцией. Работоспособность в x86 не проверял, в коде есть условия для перевода в x86.

Результаты

• isPalindromeJSFast: ускорение в 4.5 раза.

• isPalindromeJSSuperFast: ускорение в 7 раз.

• вынос расчетов в C-модуль: ускорение в 20 раз.

• SIMD-инструкции: ускорение в 224 раза (на MacBook Air M1).

Условия тестирования

Данные для тестирования брались с учетом того, что длина строки была 10_000_000 символов, а время замеров производилось за 50 прогонов. Перед замером времени выполнения коду давалась возможность "подогреться", чтобы оптимизаторы смогли сделать необходимые оптимизации. Перед тестом MacBook Air M1 давали остыть.

224-кратное ускорение — это очень большая разница, но она важна при очень больших значениях. В реальных условиях такой производительности достичь сложно, особенно на небольших данных, как жонглирование с JSON-ками, где оптимизация особо не поможет. Например, бекенд на Nest.js создает столько лишних телодвижений, что мои вкрапления кода кажутся мизерными. Пока до меня доходит HTTP-запрос, созданный библиотекой node:http, на него накладывают логику от Express.js, далее Nest.js оборачивает их в Observable (RxJS).

Например, в бенчмарке:

• Node.js получает 64 779 очков

• Fastify — 56 794 очков

• Nest.js — 35 814 очков (вероятно под капотом Express.js)

Из-за этого очень сложно оптимизировать код, персентили могут показывать проблемы с внешними факторами или работой GC. Поэтому остается сокращать время выполнения своего кода, конкретно изолировать необходимый участок и давать одинаковые данные.

Разработчик среднего уровня на JavaScript может написать код, который будет лишь в 2-3 раза медленнее C (что очень даже хорошо). Если же важна исключительная производительность, то добро пожаловать в мир C, где уже придется учитывать архитектуры процессоров, но зато с помощью магии оптимизации на низкоуровневом C можно достичь значительного ускорения, на которое компиляторы JavaScript не способны. Это не значит, что я откажусь от регулярных выражений. С лавинообразным ростом использования эмоджи, только благодаря новым функциям в regex можно точно определить длину строк, содержащих эмоджи, и выполнять текстовую верстку. Операторы rest и spread - это дар с небес, позволяющий не запоминать новые методы массивов, объектов или строк.

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