Молниеносно быстрое парсинг, часть 1: оптимизация сканнера

Чтобы выполнить JavaScript-программу, исходный текст необходимо обработать, чтобы V8 мог его понять. V8 начинает с парсинга исходного текста в абстрактное синтаксическое дерево (AST), набор объектов, представляющих структуру программы. Это AST компилируется в байткод с помощью Ignition. Производительность этапов парсинга и компиляции важна: V8 не может выполнить код до завершения компиляции. В этой серии статей блога мы сосредоточимся на парсинге и работе, проделанной в V8, чтобы создать молниеносно быстрый парсер.

Фактически, мы начнем серию на одном этапе раньше парсера. Парсер V8 потребляет «токены», предоставленные «сканнером». Токены — это блоки из одного или нескольких символов, имеющих единственное семантическое значение: строка, идентификатор, оператор, такой как ++. Сканнер создает эти токены, объединяя последовательные символы из базового потока символов.

Сканнер обрабатывает поток символов Unicode. Эти символы Unicode всегда декодируются из потока кодовых единиц UTF-16. Поддерживается только одна кодировка, чтобы избежать ветвлений или создания специализированных версий сканнера и парсера для различных кодировок, и мы выбрали UTF-16, потому что это кодировка строк JavaScript, и исходные позиции должны быть предоставлены относительно этой кодировки. UTF16CharacterStream предоставляет (возможно, буферизированное) представление UTF-16 поверх базовой кодировки Latin1, UTF-8 или UTF-16, которую V8 получает из Chrome, а Chrome, в свою очередь, получает из сети. Кроме того, поддержка более одной кодировки и разделение между сканнером и потоком символов позволяет V8 прозрачно сканировать, как будто весь исходный код доступен, даже если мы получили только часть данных через сеть.

Интерфейс между сканнером и потоком символов — это метод с именем Utf16CharacterStream::Advance(), который возвращает либо следующую кодовую единицу UTF-16, либо -1 для обозначения конца ввода. UTF-16 не может кодировать каждый символ Unicode в одной кодовой единице. Символы вне Основной Многоязычной Плоскости кодируются двумя кодовыми единицами, также называемыми парами замен. Однако сканнер работает с символами Unicode, а не с кодовыми единицами UTF-16, поэтому он оборачивает этот интерфейс низкоуровневого потока в метод Scanner::Advance(), который декодирует кодовые единицы UTF-16 в полные символы Unicode. Текущий декодированный символ буферизуется и используется методами сканирования, такими как Scanner::ScanString().

Сканнер выбирает определенный метод сканера или токен на основе максимального предсказания в 4 символа — самой длинной неоднозначной последовательности символов в JavaScript¹. Как только выбран метод, например ScanString, он потребляет оставшиеся символы для этого токена, буферизируя первый символ, который не является частью токена, для следующего отсканированного токена. В случае ScanString он также копирует отсканированные символы в буфер, закодированный как Latin1 или UTF-16, декодируя при этом escape-последовательности.

Пробелы

Токены могут быть разделены различными типами пробелов, например, перевод строки, пробел, табуляция, однострочные комментарии, многострочные комментарии и т.д. Один тип пробела может следовать за другим типом пробела. Пробел добавляет значение, если он вызывает разрыв строки между двумя токенами: это может привести к автоматическому вставлению точки с запятой. Поэтому перед сканированием следующего токена все пробелы пропускаются, при этом отслеживается, произошел ли перевод строки. Большинство реального производственного JavaScript-кода минимизировано, поэтому многосимвольные пробелы, к счастью, встречаются не часто. По этой причине V8 равномерно сканирует каждый тип пробела независимо, как если бы они были регулярными токенами. Например, если первый символ токена — /, за которым следует другой /, V8 сканирует это как однострочный комментарий, который возвращает Token::WHITESPACE. Этот цикл просто продолжает сканирование токенов до тех пор, пока мы не найдем токен, отличный от Token::WHITESPACE. Это означает, что если следующий токен не предшествует пробел, мы немедленно начинаем сканирование соответствующего токена, не проверяя наличие пробелов.

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

Сканирование идентификаторов

Самый сложный, но также и самый распространенный токен — это токен идентификатора, который используется для имен переменных (и других элементов) в JavaScript. Идентификаторы начинаются с Unicode-символа с свойством ID_Start, за которым, возможно, следует последовательность символов с свойством ID_Continue. Проверка, имеет ли Unicode-символ свойство ID_Start или ID_Continue, довольно затратна. Вставляя кэш картирования символов на их свойства, мы можем немного ускорить процесс.

Большинство исходного кода JavaScript написано с использованием ASCII-символов. Из символов диапазона ASCII только a-z, A-Z, $ и _ являются началами идентификаторов. ID_Continue дополнительно включает 0-9. Мы ускоряем процесс сканирования идентификаторов, создавая таблицу с флагами для каждого из 128 ASCII-символов, указывая, является ли символ ID_Start, ID_Continue и т.д. Если символы, которые мы рассматриваем, находятся в диапазоне ASCII, мы ищем соответствующие флаги в этой таблице и проверяем свойство с помощью одного ветвления. Символы являются частью идентификатора до тех пор, пока мы не увидим первый символ, который не имеет свойства ID_Continue.

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

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

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

Конвертация минимизированных идентификаторов

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

Ключевые слова

Ключевые слова — это особая подгруппа идентификаторов, определенная языком, например, if, else и function. Сканер V8 возвращает разные токены для ключевых слов, чем для идентификаторов. После сканирования идентификатора нам нужно распознать, является ли идентификатор ключевым словом. Поскольку все ключевые слова в JavaScript содержат только строчные буквы a-z, мы также сохраняем флаги, указывающие, являются ли символы ASCII возможными начальными и продолжающими символами ключевых слов.

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

Лучше использовать технику, называемую идеальное хеширование. Поскольку список ключевых слов статичен, мы можем вычислить идеальную хеш-функцию, которая для каждого идентификатора даст нам не более одного кандидата на ключевое слово. V8 использует gperf для вычисления этой функции. Результат вычисляет хеш из длины и первых двух символов идентификатора, чтобы найти единственное кандидатное ключевое слово. Мы сравниваем идентификатор с ключевым словом только в том случае, если длина этого ключевого слова совпадает с длиной входного идентификатора. Это особенно ускоряет случай, когда идентификатор не является ключевым словом, поскольку нам требуется меньше ветвлений, чтобы это выяснить.

Пары суррогатов

Как упоминалось ранее, наш сканер работает с потоком символов, кодированных в UTF-16, но обрабатывает символы Unicode. Символы в дополнительных плоскостях имеют особое значение только для токенов идентификаторов. Например, если такие символы встречаются в строке, они не завершают её. Отдельные суррогаты поддерживаются JS и просто копируются из исходного кода. По этой причине лучше избегать объединения пар суррогатов до тех пор, пока это не станет абсолютно необходимым, и позволить сканеру работать напрямую с кодовыми единицами UTF-16 вместо символов Unicode. Когда мы сканируем строку, нам не нужно искать пары суррогатов, объединять их, а затем снова разделять при создании литерала. Остались только два места, где сканеру нужно обрабатывать пары суррогатов. В начале сканирования токена, только если мы не распознаём символ как что-либо ещё, нам нужно объединять пары суррогатов, чтобы проверить, является ли результат началом идентификатора. Аналогично, нам нужно объединять пары суррогатов на медленном пути сканирования идентификатора, обрабатывающего не-ASCII символы.

AdvanceUntil

Интерфейс между сканером и UTF16CharacterStream делает разделение достаточно зависимым от состояния. Поток отслеживает свою позицию в буфере, которую увеличивает после каждого потреблённого кодовой единицы. Сканер сохраняет полученную кодовую единицу перед возвращением к методу сканирования, запросившему символ. Этот метод читает сохранённый символ и продолжает обработку на основе его значения. Такая организация создаёт хорошую слоистость, но работает довольно медленно. Прошлой осенью наш стажёр Флориан Саттлер придумал улучшенный интерфейс, который сохраняет преимущества слоистости, обеспечивая при этом более быстрый доступ к кодовым единицам в потоке. Шаблонная функция AdvanceUntil, специализированная для конкретного вспомогательного сканера, вызывает вспомогательную функцию для каждого символа в потоке, пока она не вернёт false. Это предоставляет сканеру прямой доступ к исходным данным без нарушения абстраций. Это фактически упрощает функции вспомогательных сканеров, так как им не нужно обрабатывать EndOfInput.

AdvanceUntil особенно полезен для ускорения функций сканирования, которым может потребоваться обработать большое количество символов. Мы использовали его для ускорения обработки идентификаторов, о чём уже упоминалось выше, а также строк² и комментариев.

Вывод

Производительность сканирования является основой производительности парсинга. Мы оптимизировали наш сканер, чтобы он был максимально эффективным. Это привело к улучшениям во всех аспектах: производительность сканирования одиночного токена улучшилась примерно в 1.4×, сканирования строк — в 1.3×, сканирования многострочных комментариев — в 2.1×, а сканирования идентификаторов — в 1.2–1.5× в зависимости от длины идентификатора.

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

Footnotes

1. <!-- — это начало HTML-комментария, тогда как <!- сканируется как «меньше чем», «не», «минус». ↩

2. Строки и идентификаторы, которые не могут быть закодированы в Latin1, в настоящее время более затратны, так как мы сначала пытаемся буферизовать их в виде Latin1, преобразовывая их в UTF-16, когда встречаем символ, который не может быть закодирован в Latin1. ↩