Библиотека сайта rus-linux.net
Разбор документов XML со скоростью света
Глава 4 из книги "Производительность приложений с открытым исходным кодом".
Оригинал: Parsing XML at the Speed of Light
Автор: Arseny Kapoulkine
Дата публикации: 21 Сентября 2012 г.
Перевод: А.Панин
Дата перевода: 10 Ноября 2013 г.
Введение
XML является стандартизированным языком разметки, для которого устанавливается ряд правил кодирования иерархически структурированных документов в читаемом человеком текстовом формате. Стандарт XML получил широкое распространение и применяется для формирования как очень компактных простых документов (таких, как запросы SOAP), так и многогигабайтных документов (применяемых проектом OpenStreetMap) со сложными зависимостями между данными (COLLADA). Для обработки документов XML пользователям обычно требуется специальная библиотека: она должна реализовывать механизм разбора документов XML, который преобразовывает документ из текстового во внутреннее представление. Стандарт XML является компромиссным решением в плане скорости разбора, пригодности для чтения пользователем, а также сложности кода для разбора - следовательно, наличие быстрой системы разбора документов XML может повлиять на предпочтительный выбор формата XML в качестве формата для хранения данных приложения.
В данной главе описываются различные приемы, направленные на повышение производительности описанной системы разбора и позволившие автору разработать чрезвычайно производительную систему разбора с использованием языка программирования C++: pugixml. Хотя эти приемы были использованы для системы разбора документов XML, большая их часть может быть применена в системах разбора документов других форматов или даже в абсолютно не связанных с описанными программных компонентах (например, алгоритмы управления памятью широко применяются и в не связанных с системами разбора текстовых документов областях).
Так как существует несколько в значительной степени отличающихся друг от друга подходов к разбору документов XML и система разбора должна выполнять дополнительные действия, о которых не знают даже имеющие опыт работы с документами XML лица, важно в первую очередь описать поставленную задачу перед подробным рассмотрением деталей реализации.
Модели систем разбора документов XML
- При использовании систем разбора на основе SAX (Simple API for XML - простой API для XML) пользователь получает в свое расположение программный компонент, ожидающий поток данных документа в качестве входных данных и предоставляющий несколько функций обратного вызова, таких, как "открытие тэга", "закрытие тэга", "символ внутри тэга". Система разбора использует функции обратного вызова в процессе обработки данных документа. Необходимый для разбора контекст ограничен глубиной дерева текущего элемента, что подразумевает значительное снижение требований к памяти. Этот тип системы разбора может использоваться для обработки передаваемых в потоковом режиме документов в том случае, когда в каждый момент времени доступна только часть документа.
- Pull-разбор аналогичен разбору на основе SAX в плане самого процесса - в каждый момент времени производится обработка одного элемента документа, но метод управления процессом разбора изменен: в системе разбора на основе SAX управление процессом разбора осуществляется самой системой с помощью функций обратного вызова, в то время, как при pull-разборе пользователь управляет процессом разбора с помощью похожего на итератор объекта.
- При использовании систем разбора на основе DOM (Document Object Model - объектная модель документа) пользователь передает системе разбора полный документ в виде буфера или потока текстовых данных, на основе которого система разбора генерирует в памяти объектное представление всего дерева элементов документа, использующее отдельные объекты для каждого определенного элемента или атрибута XML, а также набор допустимых операций (например, "получение всех дочерних элементов этого узла"). Библиотека pugxml использует эту модель.
- имеют такой небольшой размер, что могут полностью разместиться в памяти,
- имеют сложную структуру со ссылками между узлами, которые необходимо обойти, или
- требуют выполнения сложных преобразований документа.
Архитектурные решения в pugixml
При разработке Библиотеки pugixml внимание в значительной степени уделялось проблеме создания представления DOM, так как хотя и были доступны такие быстрые и легковесные системы разбора на основе SAX (как Expat), все доступные для промышленного использования системы разбора XML на основе DOM во время создания pugixml (2006 год) были либо не слишком легковесными, либо не слишком быстрыми. Исходя из этого, главной целью процесса разработки puixml является создание очень быстрой легковесной библиотеки для выполнения манипуляций с документами XML на основе модели DOM.
Формат XML описан в рекомендации W3C, которая устанавливает два различных типа процессов разбора: с проверкой и без проверки соответствия стандарту (другими словами, не проверяющие соответствие документа стандарту системы разбора проверяют синтаксис XML в то время, как проверяющие соответствие документа стандарту системы разбора в дополнение проверяют соответствие стандарту семантик данных). Даже не проверяющей соответствие документа стандарту системе приходится выполнять некоторые относительно ресурсоемкие задачи.
При рассмотрении производительности в качестве основной задачи разработки необходимо достигнуть компромисса между производительностью и соответствием стандарту. В случае pugixml достигнут следующий компромисс: любой корректно оформленный документ XML будет полностью разобран, включая выполнение всех необходимых преобразований за исключением обработки деклараций типа документа.1 Так как используются только те правила, выполнение которых может быть быстро проверено, некорректно отформатированный документ иногда также может быть успешно разобран.
Данные документа XML обычно должны быть преобразованы определенными способами до того, как они будут переданы пользователю. Эти преобразования включают в себя обработку окончаний строк, нормализацию значений атрибутов и раскрытие ссылок на символы. Эти преобразования связаны со снижением производительности; pugixml оптимизирует их настолько, насколько это возможно, предоставляя при этом способ их отключения для достижения максимальной производительности.
Поставленная задача заключалась в создании быстрой системы разбора на основе модели DOM, которая могла успешно разбирать корректно оформленные документы XML с условием выполнения необходимых преобразований, была настолько быстрой, насколько это было допустимо и подходила для промышленного использования. Исходя из необходимости достижения максимальной производительности, "возможность промышленного использования" главным образом подразумевает устойчивость к некорректным исходным данным. В данном случае устранение проверок переполнения буферов с целью повышения производительности не является допустимым.
Ниже мы обсудим процесс разбора данных, выполняемый средствами pugixml. В завершающих главу разделах мы опишем структуру данных, используемую в pugixml для хранения объектной модели документа, а также алгоритм, используемый в pugixml для резервирования памяти для этой структуры данных.
Продолжение статьи: Разбор документа.