Разбор документов XML со скоростью света

Глава 4 из книги "Производительность приложений с открытым исходным кодом".

Оригинал: Parsing XML at the Speed of Light
Автор: Arseny Kapoulkine
Перевод: А.Панин

Оптимизация механизма передачи управления

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

Система разбора использует цикл обработки данных, который читает символ из потока данных, не читает символов вообще, либо читает один или несколько символов после прочитанного символа (в зависимости от первого символа) для определения типа текущего тэга, после чего переходит к коду, с помощью которого производится разбор данных соответствующего тэга. Например, в том случае, если первым символом является символ <, нам придется считать как минимум еще один символ для установления того, является ли данный элемент начальным тэгом, конечным тэгом, комментарием или другим типом тэга. Pugixml также использует операторы goto для предотвращения прохода через цикл обработки данных в определенных случаях - например, разбор текстовых денных останавливается в конце потока данных или на символе <. Однако, в том случае, если следующим символом является символ <, нам не придется проходить цикл обработки данных только для того, чтобы снова считать символ и проверить, является ли он символом <; мы можем перейти через цикл прямо к тому коду, с помощью которого производится разбор тэгов.

Двумя важными оптимизациями такого кода являются упорядоченное ветвление и компоновка кода.

В системе разбора различные части кода обрабатывают различные формы исходных данных. Некоторые из них (такие, как части, ответственные за разбор имен тэгов и атрибутов) используются часто, в то время, как другие (такие, как части, ответственные за разбор декларации DOCTYPE) используются крайне редко. Даже в небольшом фрагменте кода различные входные данные могут оказаться с различной вероятностью. Например, после того, как система разбора кода сталкивается с открытым тэгом (<), наиболее вероятно, что следующим символом будет символ имени тэга. Следующим наиболее вероятным символом является символ /¹⁰, за которым могут следовать символы ! или ?.

Зная об этом, можно преобразовать код таким образом, чтобы он выполнялся быстрее. Во-первых, весь "холодный" код; это тот код, который вряд ли когда-нибудь будет исполняться или скорее всего не будет исполняться часто - в случае библиотеки pugixml это все функции обработки данных XML за исключением тэгов элементов с атрибутами и текстовых данных - должен быть перемещен из цикла разбора в отдельные функции. В зависимости от кода функции и компилятора может помочь добавление таких атрибутов, как noinline или специфическая маркировка вынесенных функций как "функций с холодным кодом". Идея заключается в ограничении объема кода, внесенного в главную функцию разбора, содержащую "горячий" код. Описанные подсказки позволяют компилятору оптимизировать функцию путем поддержания небольшого размера графов потоков исполнения, а также размещения "горячего" кода так компактно, как это возможно для минимизации промахов в кэше инструкций.

if (data[0] == '<')
{
  if (data[1] == '!') { ... }
  else if (data[1] == '/') { ... }
  else if (data[1] == '?') { ... }
  else { /* начальный тэг или неопознанный тэг */ }
}

if (data[0] == '<')
{
  if (PUGI__IS_CHARTYPE(data[1], ct_start_symbol)) { /* начальный тэг */ }
    else if (data[1] == '/') { ... }
    else if (data[1] == '!') { ... }
    else if (data[1] == '?') { ... }
    else { /* неопознанный тэг */ }
}

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

Обеспечение безопасности памяти

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

while (PUGI__IS_CHARTYPE(*s, ct_alpha))
  ++s;

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

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

Так как внутренний буфер памяти должен быть изменяемым для возможности выполнения непосредственного разбора, в библиотеке pugixml реализовано очень простое решение этой проблемы. Перед разбором последний символ буфера заменяется на завершающий нулевой символ, а значение замененного символа сохраняется. В этом случае единственными местами, где может понадобиться значение последнего символа, являются фрагменты кода, осуществляющие проверку корректности завершения документа. Для формата XML таких фрагментов не так много¹¹, поэтому в результате такой подход оказывается выигрышным.¹²

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

Продолжение статьи: Структуры данных для объектной модели документа.