Улучшение регулярных выражений в V8

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

Стратегия повышения уровня для RegExp

Мы хотим использовать «лучшее из двух миров» для регулярных выражений. Для этого мы сначала компилируем все регулярные выражения в байткод и интерпретируем их. Таким образом, мы экономим много памяти, а в целом (с новым, более быстрым интерпретатором) снижение производительности приемлемо. Если регулярное выражение с тем же шаблоном используется снова, мы считаем его «горячим», поэтому перекомпилируем в машинный код. С этого момента мы продолжаем выполнение как можно быстрее.

В V8 существует множество различных путей выполнения кода регулярных выражений, в зависимости от вызываемого метода, является ли оно глобальным или неглобальным регулярным выражением, и идем ли мы по быстрому либо медленному пути. Учитывая это, мы стремимся к максимальной централизации принятия решения о повышении уровня. Мы добавили поле ticks (тиков) в объект RegExp в V8, которое инициализируется определенным значением во время выполнения. Это значение представляет количество раз, которое регулярное выражение будет интерпретироваться перед повышением уровня до компилятора. Каждый раз, когда регулярное выражение интерпретируется, мы уменьшаем значение ticks на 1. В встроенном методе, написанном на CodeStubAssembler, который вызывается для всех регулярных выражений, мы проверяем значение ticks при каждом выполнении. Когда значение ticks достигает 0, мы знаем, что необходимо перекомпилировать регулярное выражение в машинный код, и переходим к выполнению этой задачи в режиме времени выполнения.

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

Ускорение интерпретатора RegExp

Устранение накладных расходов во время выполнения

Когда регулярное выражение выполняется, вызывается встроенный метод, написанный на CodeStubAssembler. Ранее этот встроенный метод проверял, содержало ли поле code объекта JSRegExp скомпилированный машинный код, который можно было выполнить напрямую, и в противном случае вызывал метод в режиме времени выполнения для компиляции (или интерпретации в режиме без JIT) регулярного выражения. В режиме без JIT каждое выполнение регулярного выражения проходило через время выполнения V8, что довольно дорого, поскольку требовалась смена между стеком выполнения JavaScript и C++.

Начиная с версии v7.8 V8, когда компилятор RegExp генерирует байткод для интерпретации регулярного выражения, к trampoline интерпретатора RegExp теперь добавляется в поле code объекта JSRegExp вместе с сгенерированным байткодом. Таким образом, интерпретатор теперь вызывается напрямую через встроенный метод без обходного пути через режим времени выполнения.

Новый метод диспетчеризации

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

Мы изменили метод диспетчеризации на метод поточного кода в версии v7.8 V8. Этот метод позволяет предсказателю ветвлений процессора прогнозировать следующий байткод на основе текущего выполняемого байткода, уменьшая количество ошибок предсказаний. Более детально, мы используем таблицу диспетчеризации, которая хранит отображение между каждым идентификатором байткода и адресом обработчика, реализующего байткод. Интерпретатор V8 Ignition также использует этот подход. Однако большое отличие между интерпретатором Ignition и интерпретатором RegExp заключается в том, что обработчики байткодов Ignition написаны на CodeStubAssembler, тогда как весь интерпретатор RegExp написан на C++ с использованием [вычисленных goto]s (https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html) (расширение GNU также поддерживается clang), который легче читать и поддерживать, чем CSA. Для компиляторов, которые не поддерживают вычисленные goto, мы возвращаемся к старому методу диспетчеризации на основе switch.

Оптимизация байткода в стиле «пифхоль»

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

const re = /[^_]*/;
const str = 'a0b*c_ef';
re.exec(str);
// → совпадение с 'a0b*c'

Для этого простого шаблона компилятор RegExp создает три байткода, которые выполняются для каждого символа. В общем виде они таковы:

1. Загрузить текущий символ.
2. Проверить, равен ли символ '_'.
3. Если нет, передвинуть текущую позицию в строке и goto 1.

Для нашей строки необходимо интерпретировать 17 байткодов, пока не найдем несовпадающий символ. Идея оптимизации через малые окна заключается в том, что мы заменяем последовательности байткодов новым оптимизированным байткодом, который объединяет функциональность нескольких байткодов. В нашем примере мы можем даже обработать неявный цикл, созданный goto, явно в новом байткоде, таким образом один байткод обрабатывает все совпадающие символы, сохраняя 16 переходов.

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

Результаты

Рисунок 1 показывает влияние на память различных стратегий tier-up при просмотре историй в Facebook, Reddit, Twitter и Tumblr. По умолчанию показан размер JIT-кода, затем отображается размер кода регулярок, который мы используем (размер байткода, если не используем tier-up, размер нативного кода, если используем) для операций с начальным значением 1, 10 и 100. Наконец, показан размер кода регулярок, если интерпретируются все регулярные выражения. Мы использовали эти результаты и другие тесты, чтобы решить включить tier-up с инициализацией тиков до 1, то есть мы интерпретируем регулярное выражение один раз, а затем используем tier-up.

Используя эту стратегию tier-up, мы уменьшили размер кода в куче V8 на 4–7% на реальных сайтах и эффективный размер V8 на 1–2%.

Рисунок 2 показывает влияние на производительность интерпретатора RegExp для всех улучшений, описанных в этом блоге¹ на наборе тестов RexBench. Для справки также показана производительность JIT-компилированного RegExp (Native).

Новый интерпретатор работает до 2× быстрее старого, в среднем примерно на 1.45× быстрее. Мы даже приближаемся к производительности JIT-компилированного RegExp для большинства тестов, с исключением Regex DNA. Причина, по которой интерпретируемые RegExp значительно медленнее JIT-компилированных в этом тесте, заключается в длинных строках (~300,000 символов), которые используются. Несмотря на то, что мы свели к минимуму накладные расходы на переходы, накладные расходы суммируются на строках длиной более 1,000 символов, что приводит к медленному выполнению. Поскольку интерпретатор намного медленнее на длинных строках, мы добавили эвристический метод, который активно использует tier-up для таких строк.

Заключение

Начиная с V8 v7.9 (Chrome 79) мы используем tier-up для регулярных выражений вместо их немедленной компиляции. Таким образом, интерпретатор, ранее использовавшийся только в V8 без JIT, теперь используется везде. В результате мы экономим память. Мы ускорили интерпретатор, чтобы сделать это возможным. Но это не конец — в будущем можно ожидать еще больше улучшений.

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

Footnotes

1. Показанные здесь результаты также включают улучшение регулярных выражений, уже описанное в заметках о выпуске V8 v7.8. ↩