В прошлую пятницу моя отпускная поездка в Европу сорвалась благодаря какому-то клерку, который проштамповал мою новую визу как действующую с 27 февраля, а не с 27 января, так что вместо того, чтобы пить вкусное пиво в Праге и праздновать день рождения близкого друга, я У меня полно времени, чтобы сделать то, что в таком случае сделают все нормальные люди — я решил попробовать собрать быстрый http-роутер для Node.js с помощью кодогенерации.

TL;DR Это сработало просто отлично.

Разве наша http-маршрутизация уже недостаточно быстра?

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

Тогда зачем ты это делаешь?

http-маршрутизация — хорошо известная проблема, поэтому она подходит для иллюстрации codegen как полезного подхода, позволяющего выжимать некоторую дополнительную производительность, когда вы решаете реальные проблемы и застряли.

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

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

Хорошо, так с чего мы начнем? Мы учимся измерять.

Во-первых, нам нужно изучить существующие решения и создать инструмент для измерения наших неудач и успехов. В поисках существующих узловых модулей для http-маршрутизации я наткнулся на модуль trek-router (автор Fangdun Cai в качестве компонента для фреймворка Trek.js). Что важно, этот модуль включал бенчмарк для trek-routeritself и некоторых других модулей маршрутизации. Вот цифры для схемы URL GitHub на моем ноутбуке:

$ node benchmarks 
GitHub API, 203 routes:
trek-router x 6,963 ops/sec ±1.24% (87 runs sampled)
path-to-regexp x 606 ops/sec ±1.13% (87 runs sampled)
route-recognizer x 297 ops/sec ±1.56% (82 runs sampled)
route-trie x 2,032 ops/sec ±1.45% (88 runs sampled)
routington x 1,216 ops/sec ±1.50% (89 runs sampled)
wayfarer x 1,285 ops/sec ±1.67% (86 runs sampled)
Fastest is trek-router

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

Далее рисуем всю картину

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

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

Отказ от ответственности: вся работа была выполнена с использованием Node 7.4.0, Flowtype для объявлений типов, babel для избавления от типов потоков и переноса кода в es5.

Отказ от ответственности №2: большая часть кода в нашем маршрутизаторе, кроме фактической маршрутизации, не критична для производительности, поэтому я позволил себе использовать встроенные функции Array здесь и там или даже некоторые полезные функции ES2015+.

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

Во-первых, вспомогательные типы и функции:

Теперь давайте добавим класс Route, который будет представлять… маршрут (кто бы мог подумать?):

Теперь о самом Router:

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

Теперь, когда мы знаем, как хранить наши данные, давайте напишем фактический метод построения дерева для нашего Router:

Примечание: Вы можете заметить, что я постоянно фильтрую части URL после разбивки по косой черте — это создает массивы без пустых элементов (элементы до первой косой черты и после последней, поэтому в нашем дереве меньше уровней).

Звездочки обозначают позиции в URL-адресе, которые можно интерпретировать как параметры (например, :commentIdin /blog/:postId/comments/:commentId).

Многие маршруты могут иметь разные имена параметров в одной и той же позиции, поэтому мы сохраняем структуру paramNames, которая помогает нам найти, как этот параметр должен быть назван для конкретного маршрута, когда он будет соответствовать предоставленному URL-адресу.

Давайте посмотрим, что этот зверюга может построить для нас (вы сами можете это увидеть, раскомментировав отладочную печать в тесте):

Вау. Хотя это и некрасиво, мы могли ясно видеть, как наши маршруты входят в узлы дерева, где мы можем выбирать параметры из URL-адреса. Обратите внимание на свойство paramNames: { '2': 'postId', '3': 'postId' }, оно показывает, как разные маршруты будут получать значение в этой позиции URL-адреса (в этом примере они одинаковы, но легко могут отличаться).

Теперь, имея дерево, мы можем создать функцию маршрута:

Как вы могли заметить, эта часть гораздо больше похожа на ES5, мы все равно будем тестировать ее, поэтому вместо того, чтобы помнить, какие части ES2015+ уже работают быстро в v8 (как вы можете сейчас, многие вещи ES2015+ все еще медленнее, чем альтернативы ES5 ), я перешел на ES5.

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

Другие моменты, которые вы могли заметить:

  • array[array.length] = x вместо array.push(x). Это старый трюк, позволяющий сделать вставку массива быстрее, чем вызов метода, и вызов метода для массива внутри цикла может помешать v8 использовать некоторые оптимизации. Насколько я знаю, некоторые из последних версий v8 сделали array.push() быстрее, но я не проверял это, потому что за пределами очень специфических задач это не будет иметь существенного значения для моей работы.
  • замена .filter(Boolean) простым циклом for. В этом случае на самом деле делается некоторая незначительная разница. Обратите внимание — хотя многие вещи можно было бы сделать быстрее в пользовательской среде, по сравнению с нативными методами v8 это не всегда так. Не переписывайте вслепую каждый метод стандартных библиотек — есть случаи, и многие из них, когда нативные методы будут быстрее — другими словами, измерьте, прежде чем делать какие-либо оптимизации.

Как я узнал, что нужно искать замену .filter() ? Я использовал статистический профайлер, встроенный в v8. Есть много статей о том, как использовать его с node.js и в Chrome DevTools, так что погуглите. Например, на веб-сайте Node.js было очень простое введение в профилирование узлов — по крайней мере, прочитайте его. Хотя у статистического профилировщика есть свои недостатки (например, он не очень полезен для профилирования многих чередующихся задач с большим объемом операций ввода-вывода в вашем коде), он по-прежнему остается незаменимым инструментом, когда вам нужно найти узкие места в выполнении вашего JavaScript.

Хорошо, давайте вернемся к нашему тесту и посмотрим, как мы пойдем среди других.

$ node benchmarks
GitHub API, 203 routes:
hardcore-naive x 2,719 ops/sec ±1.10% (89 runs sampled)
trek-router x 6,863 ops/sec ±1.62% (86 runs sampled)
path-to-regexp x 566 ops/sec ±1.22% (86 runs sampled)
route-recognizer x 301 ops/sec ±2.44% (83 runs sampled)
route-trie x 1,977 ops/sec ±1.03% (89 runs sampled)
routington x 1,097 ops/sec ±2.60% (81 runs sampled)
wayfarer x 1,328 ops/sec ±1.86% (85 runs sampled)
Fastest is trek-router

Неплохо. Мы вторые, уступив только trek-router(мы ехали как hardcore-naive, извините за пафосное название, но я все равно скучаю по отпуску).

Хорошо, пойдем и напишем немного

Кодеген, наконец

Нет, не сейчас. Вы можете задаться вопросом, зачем вообще заморачиваться с кодегеном и есть ли у него какая-то практическая польза? Из верхней части моей головы есть по крайней мере два примера:

  • ajv от Allan Ebdrup — самый быстрый (насколько мне известно) валидатор схемы JSON, который использует шаблоны doT для создания очень быстрых функций валидатора, которые хорошо оптимизируются v8 (о, боже, я помню времена, когда мы использовали jayschema для проверки JSON) . Посмотрите на сравнительный график:

  • node-mysql2 от Андрей Сидоров — более быстрая альтернатива node-mysql, почти полная замена, использует подход codegen внутри для создания быстрых парсеров пакетов протокола mysql в сочетании с реальной поддержкой подготовленных операторов, показывает заметный прирост производительности по сравнению с до node-mysql.

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

Теперь, клянусь,

Кодеген

Я буду использовать подход «для бедняков», т. е. никаких причудливых AST-инструментов JavaScript, только старую простую конкатенацию строк.

Посмотрим:

Итак, что мы имеем здесь:

  • во-первых, мы определяем две вспомогательные функции — function add() для формирования тела нашей функции с использованием отступов, и рекуррентную function processNode(), которая рекурсивно проходит по нашему дереву и пишет окончательный код.
  • фактическая генерация начинается с набора операторов var, где мы заранее определяем почти все переменные, которые нам понадобятся.
  • затем мы создаем предложение if для каждого метода http, которое мы могли бы обработать и начать рекурсивную обработку из корня дерева, специфичного для метода, используя processNode()
  • давайте посмотрим на сам processNode() поближе.

Он начинается с условия завершения обхода дерева, которое строит результирующий массив совпадающих маршрутов с сопровождающим объектом params для каждого параметра, выбранного для маршрута (здесь мы используем ту тарабарщину route.parametersMap, которую мы видели в определении Route в начале. Хотя теперь мы все параметры позиционируем заранее , нам не нужно перебирать массивы в поисках совпадающих значений, мы просто выполняем операции доступа к паре массивов по постоянным позициям, характерным для совпадающего маршрута (вы увидите пример ниже).

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

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

Для той же карты маршрутов, которую мы использовали ранее и просматривали сгенерированное дерево, наша функция компиляции генерирует следующий код:

Вау, страшно (но мы можем проверить, что это работает, используя наш тест из наивной реализации, помните?).

Ключевые моменты:

  1. Повторяющаяся строка, которая выбирает позиции для каждой части URL
nextSlashPos = _url.indexOf(“/”, leftWindowPos + 1); rightWindowPos = nextSlashPos === -1 ? uLen : nextSlashPos;

изначально был моим собственным эквивалентом в виде:

rightWindowPos = leftWindowPos + 1; while (_url[rightWindowPos++] !== \’/\’ && rightWindowPos < _url.length) {}; leftWindowPos = rightWindowPos;

потому что, знаете ли, мои циклы всегда быстрее. Но эксперименты показали обратное — переход на .indexOf() дал значительный прирост по сравнению с предыдущей версией.

2. как видите, во время компиляции мы создаем фрагменты, которые заполняют params хэша, чтобы сопровождать наши маршруты return [{route: routes[x], params: { ... THIS ...}}]. Эти объекты всегда будут иметь один и тот же скрытый класс, поскольку они одинаковы для каждого маршрута. Таким образом, если они позже пришли в качестве аргументов вашему обработчику, они не будут деоптировать их.

3. Странная строка в начале var _url = "" + url.slice(sliceFrom, sliceTo); Почему мы объединяем результат среза с пустой строкой? Я думаю, что за кулисами это может изменить фактическую реализацию строки за переменной _url (честно говоря, я угадываю здесь, и я все еще под впечатлением от последнего поста «Приключения в стране подстрок и регулярных выражений» автор Вячеслав Егоров, но изменение производительности видно на тестах).

Измерить снова

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

$ node benchmarks
GitHub API, 203 routes:
hardcore-clean-naive x 2,683 ops/sec ±1.25% (86 runs sampled)
hardcore-clean-compiled x 9,817 ops/sec ±4.17% (89 runs sampled)
trek-router x 6,893 ops/sec ±1.39% (89 runs sampled)
path-to-regexp x 557 ops/sec ±1.43% (83 runs sampled)
route-recognizer x 288 ops/sec ±2.18% (78 runs sampled)
route-trie x 1,984 ops/sec ±1.94% (85 runs sampled)
routington x 1,162 ops/sec ±1.49% (87 runs sampled)
wayfarer x 1,228 ops/sec ±1.42% (88 runs sampled)
Fastest is hardcore-clean-compiled

Хм, похоже, мы добились значительного улучшения как по сравнению с нашей первой алгоритмически неэффективной версией (наш наивный подход также мог бы выиграть от использования parametersMap), так и с другими. Хотя я не настолько опрометчив, чтобы сказать, что я сделал самый быстрый маршрут (наверняка, возможно, есть масса ошибок и крайних случаев, которые я не рассмотрел должным образом, и я бы скромно), это тоже неплохой результат. В конце концов, каждое из этих ops — это 203 операции маршрутизации, поэтому мы совершали почти 2 000 000 операций маршрутизации в секунду.

Послесловие

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

Итак, 1) измерить и профилировать, 2) оптимизировать, 3) повторить.

Надеюсь, этот пост был для вас полезен — не стесняйтесь обращаться ко мне в Twitter (dolphin278), оставляйте комментарии или пишите мне на почту — [email protected].