[Перевод] Ultra-Fast Profiler, часть 1: Оптимизация сканеров

задняя часть Программа перевода самородков

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

Собственно наш цикл статей начинается с предыдущего этапа парсера. Парсер V8 получаетсканер(т.е. лексический анализатор - s) тег (токен), предоставленный в качестве входных данных. Токен связан вместе одним или несколькими символами, символом с семантическим значением одного блока, таким как строка, идентификатор или как++такой оператор. Сканер создает эти маркеры, комбинируя последовательные символы из основного потока символов.

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

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

Сканер будет искать до 4 символов вперед — это максимальная длина неоднозначной последовательности символов в JavaScript.[1]- этимвыберитеОпределенный метод сканера или токен. После выбора нравитсяScanString这样的方法，它会取走这个 token 余下的字符，并将不属于这个 token 的第一个字符缓冲，留给下一个扫描的 token。 существуетScanStringВ случае , он также копирует отсканированные символы в буфер, закодированный как Latin1 или UTF-16, и декодирует управляющие последовательности.

пробел

Токенам могут предшествовать различные пробельные символы, такие как символы новой строки, пробелы, табуляции, однострочные комментарии, многострочные комментарии и т. д. За одним типом пробела могут следовать другие типы пробела. Добавлено значение, если пробел вызывал новую строку перед двумя токенами: это могло привести кАвтоматически вставлять точки с запятой. Поэтому перед сканированием следующего токена все пробельные символы пропускаются, и если встречается новая строка, это регистрируется. Большая часть реального производственного кода JavaScript минимизирована, поэтому, к счастью, многосимвольные пробелы встречаются не очень часто. По этой причине V8 равномерно и независимо сканирует каждый пробел, как обычные токены. Например, если первый символ токена/, второй символ тоже/, V8 просканирует его как однострочный комментарий и вернетToken::WHITESPACE.这个过程会一直重复，до того какмы нашли тот, который неToken::WHITESPACEтокен. Это означает, что если перед следующей лексемой нет пробела, мы немедленно начинаем сканирование соответствующей лексемы без явной проверки наличия пробелов.

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

идентификатор сканирования

идентификатор— это самый сложный, а также самый распространенный токен, используемый в качестве имен переменных (среди прочего) в JavaScript. идентификатор иметьID_StartСимвол Юникода атрибута, за которым следует строка (необязательно) сID_Continueатрибутный характер. Проверьте, есть ли у символа UnicodeID_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 возможным начать ключевое слово, и продолжить символ (идентификаторID_StartиID_Continue-- Аннотация).

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

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

суррогатная пара

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

AdvanceUntil

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

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

Эпилог

Производительность сканирования является краеугольным камнем производительности парсера. Мы настроили сканер так, чтобы он был максимально эффективным. Это привело к общему повышению производительности примерно в 1,4 раза для сканирования отдельных токенов, в 1,3 раза для строк, в 2,1 раза для многострочных комментариев и в 1,2-1,5 раза для идентификаторов, в зависимости от длины идентификатора.

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

  1. <!--является началом комментария HTML и<!-распознаются как «меньше», «не», «минус».↩︎

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

Автор: Toon Verwaest (@tverwaes), позорный оптимизатор.

Сделайте репост этого поста!

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

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

Категории