Библиотека сайта rus-linux.net
Разбор документов XML со скоростью света
Глава 4 из книги "Производительность приложений с открытым исходным кодом".
Оригинал: Parsing XML at the Speed of Light
Автор: Arseny Kapoulkine
Перевод: А.Панин
Разбор документа
Задачей системы разбора на основе модели DOM является получение входных данных - строки, представляющей собой документ XML, и формирование дерева объектов, которое представляет тот же документ в памяти. Работа системы разбора обычно обычно разделяется на два этапа: лексический анализ и разбор. Подсистеме лексического анализа передается поток исходных символов, на основе которого формируется поток токенов. (Для системы разбора XML набор токенов может включать в себя открытые угловые скобки, метки кавычек, имена тэгов и имена атрибутов.) Система разбора принимает поток токенов и формирует синтаксическое дерево на основе грамматики, используя один из множества алгоритмов разбора, такой, как алгоритм рекурсивного спуска. При появлении токена со строковыми данными, такого, как имя тэга, подсистема лексического анализа или разбора копирует данные строки в память и сохраняет указатель на строку в узле дерева.
Для улучшения производительности системы разбора библиотека pugixml отходит от стандартной практики обработки данных несколькими способами.
Поток токенов против потока символов
Как упоминалось ранее, системы разбора обычно используют лексические анализаторы для преобразования потока символов в поток токенов. Это мероприятие позволяет повысить производительность в случаях, когда системе разбора требуется много раз обратиться к уже обработанным данным, но в случае систем разбора XML этап работы лексического анализатора является дополнительным уровнем усложнения, который приводит к большим затратам ресурсов на обработку каждого символа. Поэтому библиотека pugixml работает на уровне потока символов вместо уровня потока токенов.
В нормальных условиях поток данных состоит из символов в кодировке UTF-8 и библиотека pugixml производит побайтовое чтение этого потока. Из-за особенностей кодировки UTF-8 нет необходимости в разборе байтовых последовательностей UTF-8 тогда, когда вам не требуется искать специфические, не входящие в таблицу ASCII символы, так как в корректных потоках символов UTF-8 все меньшие 128 байтовые значения представляют отдельные символы из таблицы ASCII (т.е., не являются частью символов UTF-8).2
Непосредственный разбор
В типичной реализации системы разбора существует несколько неэффективных механизмов. Один из них заключается в копировании строковых данных в память. Эта операция подразумевает резервирование большого количества блоков памяти различных размеров от нескольких байт до мегабайт, а также требует от нас копирования всех строк из потока в память. Уход от операции копирования позволяет нам устранить оба источника дополнительной работы. В случае использования техники, известной под названием "непосредственный разбор" (или "местный разбор"), система разбора может напрямую использовать данные из потока. Это стратегия разбора, используемая в рамках библиотеки pugixml.
Простейшая система непосредственного разбора принимает исходную строку, сохраненную в непрерывном буфере в памяти, обрабатывает эту строку как набор символов и создает необходимую древовидную структуру. При достижении являющейся частью модели данных строки, такой, как имя тэга, система разбора сохраняет указатель на строку и ее длину (вместо сохранения всей строки).3
По существу, в данном случае мы сталкиваемся с компромиссом между производительностью и потреблением памяти. Непосредственный разбор обычно быстрее разбора с копированием строк в память, но он может потребовать больший объем памяти. Система непосредственного разбора должна хранить оригинальный поток данных в памяти в дополнение к собственным описывающим структуру документа данным. Система, не производящая непосредственный разбор, вместо этого может хранить в памяти только необходимые части оригинального потока данных.
Рисунок 4.1 - Применение техники непосредственного разбора для выделения завершающихся нулевым символом строк
- Обработка символов завершения строк: исходный документ может содержать различные типы меток окончания строк, поэтому система разбора должна нормализовывать их следующим образом: любая двухсимвольная последовательность, состоящая из одного символа возврата каретки (ASCII 0xD) и одного символа переноса строки (ASCII 0xA), а также любой отдельный символ возврата каретки должен быть заменен на символ переноса строки. Например, строка
`line1\xD\xAline2\xDline3\xA\xA`
должна быть преобразована в строку`line1\xAline2\xAline3\xA\xA`. - Раскрытие ссылок на символы: XML поддерживает специальные escape-символы, описываемые с помощью кодов Unicode символов в десятичном или шестнадцатеричном представлении. Например, escape-символ
aдолжен быть преобразован вaи escape-символøдолжен быть преобразован в ø. - Раскрытие ссылок на специальные элементы: XML поддерживает обобщенные ссылки на специальные символы, использующие формат &имя, где имя является именем специального символа. Существует пять предварительно заданных специальных символов:
<(<),>(>),"("),'(') и&(&). - Нормализация значений атрибутов: в дополнение к раскрытию ссылок на символы система разбора должна выполнять нормализацию пробелов при обработке значений атрибутов. Все символы пробелов (пробел, табуляция, возврат каретки и перенос строки) должны быть заменены на пробел. Дополнительно, в зависимости от типа атрибута, пробелы в начале и в конце строки должны быть удалены и последовательности пробелов в самой строке должны быть сокращены до одного пробела.
Вполне возможно добавить поддержку выполнения произвольных изменений имеющейся строки в систему разбора путем модификации символов строки, но при этом следует учитывать одно важное ограничение: в ходе преобразования никогда не должна возрастать длина строки. В противном случае данные результирующей строки могут быть записаны поверх важных данных документа. К счастью, все описанные выше преобразования удовлетворяют этому требованию.4
Операция раскрытия ссылок на специальные символы не соответствует этому ограничению. Так как библиотека pugixml не поддерживает обработку деклараций DOCTYPE и из-за того, что никакие специальные символы не могут быть описаны без использования декларации DOCTYPE, любой поддерживаемый документ может быть полностью обработан в ходе непосредственного разбора.5
Рисунок 4.2 - Преобразования текста в ходе его непосредственного разбора
Любопытно то, что непосредственный разбор документа может осуществляться путем использовании операций ввода-вывода по отношению к отображенному в память файлу.6 Поддержка операций обработки завершающихся нулевым символом строк и преобразования текста требует использования специального режима отображения файла в память, известного как копирование при записи (copy-on-write) для предотвращения модификации файла на диске.
- Ядро обычно имеет возможность отображать страницы памяти, выделенные для хранения кэша файловой системы, непосредственно в адресное пространство процесса, исключая тем самым операцию копирования данных файла в память, которая выполняется при использовании стандартных операций ввода-вывода.
- В том случае, если данные файла еще не добавлены в кэш, ядро может считывать части файла с диска, позволяя эффективно осуществлять разбор параллельно с выполнением операций ввода-вывода.
- Так как физическая память должна резервироваться только для модифицированных страниц, потребление памяти при обработке документов с большими фрагментами текста может быть в значительной степени сокращено.
Продолжение статьи: Оптимизация символьных операций.