понедельник, 11 января 2010 г.

Анализ доступных Open Source парсеров XML

1. Сравнение существующих моделей обработки XML документов

В ходе проведенного исследования были рассмотрены парсеры трех наиболее популярных моделей обработки XML документов: объектная модель документов DOM (Document Object Model), потоковая модель SAX (Simple API for XML), строковая модель с индексированием элементов (VTD-XML). Ниже приведены диаграммы, на которых приведена сравнительная характеристика парсеров.

clip_image002[4]

Рис 1. Сравнительные характеристики распознавания для файлов малого объема

clip_image004

Рис 2. Сравнительные характеристики для файлов среднего объема

clip_image006

Рис 3. Сравнительные характеристики для файлов большого объема

Контрольные задачи для определения сравнительных характеристик (benchmarks) тестируют следующие XML парсеры:

  • Xerces DOM (с полным и неполным построением DOM дерева)
  • Xerces SAX
  • Piccolo SAX
  • XPP (XML Pull Parser)
  • VTD-XML (с кэшированием и без кэширования распарсенного XML файла в буфер )

В бенчмарке участвовали XML документы различного объема и строения. В зависимости от размера, XML документы можно разделить на 3 категории: файлы малого объема (меньше 30 КБ), среднего объема (30 КБ – 4 МБ ), большого объема (свыше 4 МБ). Приложения бенчмарка выполняют следующие действия. Сначала в память читается XML документ, затем происходит разбор документа в течение большого количества итераций. Скорость распознавания считается делением величины, равной размеру файла, на среднее время работы каждой итерации. Результаты, представленные на диаграммах (рис 1, 2, 3), были получены на компьютере Pentium Core2 Duo T9300 2.5GHz , объем ОЗУ 2Гб.

Анализируя результаты данного бенчмарка, хорошо видно, что у парсера VTD-XML (версия, реализованная на C#) самые лучшие показатели. Рассмотрим его подробнее.

1.1. Основные характеристики VTD-XML

VTD-XML – парсер с открытым исходным кодом (свободно распространяется, доступен на сайте разработчиков по адресу http://vtd-xml.sourceforge.net). VTD-XML обладает кроссплатформенностью, имеет реализацию на языках C#, C и Java.

Основные принципы и характеристики технологии обработки и распознавания XML документа, которые легли в основу VTD-XML:

1. “Неизвлекаемый” (non-extractive) разбор XML документа

2. Документо-ориентированный XML (document-centric) парсер

3. Наличие нативного XML индексирования (native XML indexer)

4. “Инкрементное” изменение (incremental update) содержимого XML документа

5. Возможность разрезания XML документа на составные части, соединение частей в единый XML документ, перемещение узлов из одного XML документа в другой (slicer/splitter/assembler)

1. “Неизвлекаемый” (non-extractive) разбор XML документа

Понятие “неизвлекаемый” означает, что XML документ хранится в памяти как есть, а его элементы и лексемы представляются исключительно с помощью специальных значений, равных смещению и длине элементов (строковое представление). В противоположность модели DOM, SAX и других, в которых происходит выделение небольших участков памяти, куда потом копируются строковые значения элементов и лексем.

VTD-XML разбирает XML документ, основываясь на спецификации, называемой Virtual Token Descriptor (VTD). Структура VTD представляет собой 64-битовое целое число, которое включает в себя длину, смещение, глубину вложенности, тип XML лексемы. Битовое представление VTD приведено ниже:

clip_image007

Рис 4. Битовое представление записи VTD

  • Начальное смещение: 31 бит (b30 ~ b0) без поддержки пространства имен, или 30 бит с поддержкой пространства имен (b29~b0)
  • Длина: 20 бит (b51 ~ b32), максимальное значение 2^20-1 = 1M –1
  • Глубина вложенности: 8 бит (b59~b52), максимальное значение 2^8-1 = 255
  • Тип лексемы: 4 бита (b63~b60)

После распознавания XML документа VTD-XML хранит все записи VTD в буфере для элементов XML документа. Все VTD записи одинакового размера, в процессе работы можно выбирать записи из буфера по индексу.

Для организации эффективного произвольного доступа по VTD записям строятся специальные структуры Location Caches (LC), которые представлены в виде таблиц, для каждого уровня глубины XML документа строится своя таблица. Записи структуры LC представляют собой 64-битовое целое число, старшие 32 разряда которого определяют VTD запись для соответствующего элемента, а младшие 32 разряда – запись для первого дочернего элемента. Записи LC служат моделью иерархической структуры XML документа.

Ниже приведен рисунок, который показывает разницу между VTD-XML (non-extractive parsing) и DOM (extractive parsing).

clip_image009

Рис 5. Различие моделей extractive и non-extractive парсинга

2. Документо-ориентированный (document-centric) XML парсер

Традиционные модели обработки XML документов (такие как DOM, SAX) основываются на объектном представлении документов. На первом месте находятся объекты: узлы DOM (nodes), строковые объекты, и др., но не сам текст XML документа. Объектно-ориентированный подход, который применяется для обработки XML документов, существенно снижает производительность. Это происходит не только из-за создания и удаления объектов (эти операции достаточно ресурсоемки), но и из-за необходимости повторной сериализации данных даже при небольших изменениях.

clip_image011

Рис 6. Различие моделей extractive и non-extractive парсинга

Технология non-extractive парсинга, который используется в VTD, на первое место ставит непосредственно текст XML документа. Теперь при работе с XML документом, используется строковое представление, с помощью записей VTD можно оперировать байтами, массивами байт, целыми числами, смещениями, длинами, фрагментами. Сериализация и десериализация, используемые в объектной модели, заменены на парсинг и композицию (см. рис. 1-13).

Разница между объектной моделью и документно-ориентированной представлена ниже в таблице 3-1.

Таблица 1. Сравнение объектной модели и документно-ориентированной

 

Object Oriented XML Processing (DOM)

Document Centric XML Processing (VTD-XML)

Parsing

Slow due to object creation

Much Faster (5x~10x of DOM)

Memory Usage

High (5~10x document size)

Low (1.3x~1.5x of document size)

Indexing

No

Yes (eliminate parsing overhead)

Modification

Require re-serialization

Incremental

Cutting, Pasting, Splitting, Splicing

No

Yes

3. Наличие нативного XML индексирования (XML native indexer)

Поддержка индексирования XML документа позволяет избавиться от повторного парсинга XML документа. Таким образом, индексированный XML документ позволяет выполнять XPath запросы и другие операции над содержимым XML документа, экономя время, затрачиваемое на разбор документа.

4. «Инкрементное» изменение (incremental update) содержимого XML документа

VTD-XML является единственной технологией обработки XML документов, которая поддерживает «инкрементное» изменение. Поскольку запись VTD обозначает место в XML документе, где находится лексема, то при необходимости изменить значение лексемы нужно изменить значение в том самом месте. Это можно сравнить с действиями человека при изменении значения элемента с использованием текстового редактора. Чтобы отредактировать значение элемента, достаточно открыть XML документ в текстовом редакторе, установить курсор в нужную позицию, провести изменения и сохранить результат. Это и есть “инкрементное” изменение, которое не задействует не относящие к данному элементу другие части XML документа.

5. Возможность разрезания XML документа на составные части, соединение частей в единый XML документ, перемещение узлов из одного XML документа в другой (slicer/splitter/assembler)

VTD-XML предлагает следующие новые операции для управления содержанием XML документа:

  • Перемещение (Cut): VTD-XML предоставляет возможность вырезать узлы XML документа (например, атрибут, текстовый узел или элемент), при этом XML документ продолжает оставаться правильно оформленным (well-formed)
  • Вставка (Paste): VTD-XML позволяет вставить скопированный кусок XML документа в другой XML документ, при этом XML документ продолжает оставаться правильно оформленным (well-formed)
  • Расщепление (Split): VTD-XML может вырезать фрагменты или элементы из одного XML документа и вставлять каждый в свой собственный файл
  • Связывание (Assemble): VTD-XML позволяет соединять фрагменты или элементы различных XML файлов в один новый XML файл

На уровне API, VTD-XML состоит из следующих основных и важнейших классов:

  • VTDGen (VTD Generator) инкапсулирует функции для парсинга XML документа, создание и чтение индекса в XML файлах
  • VTDNav (VTD Navigator) содержит построенный на курсоре (cursor-based) API, который обеспечивает произвольный доступ (аналогично DOM) к иерархической структуре XML документа. Иерархия VTD-XML состоит исключительно из узлов-элементов, в отличие от модели DOM, которая рассматривает каждый узел в независимости от того, является узел атрибутом, текстовым узлом или элементом. Для каждого экземпляра класса VTDNav доступен только один курсор. Его можно перемещать по иерархии вперед и назад, но нельзя дублировать. Для сохранения текущей позиции курсора можно использовать стек. Изначально после парсинга документа курсор указывает на корневой элемент
  • Autopilot – класс, содержащий функции для работы с XPath и итераторами для обхода элементов документа. Вычисление XPath запросов происходит без сохранения состояния, так как VTD-XML возвращает узлы, удовлетворяющие условию запросу, по одному, в отличие от других моделей (DOM и др.), которые возвращают все множество узлов целиком.
1.2. Достоинства VTD-XML

По сравнению с такими моделями обработки XML документа (DOM, SAX и др.) VTD-XML обладает следующими преимуществами:

  • Удобство использования. VTD-XML предоставляет богатую функциональность для работы с XML документами, которая ни в чем не уступает функциональности DOM модели. Большинство функциональных возможностей легки для понимания и изучения, API, построенный на курсоре (cursor-based), намного проще узлового (node-based) API DOM модели
  • Скорость парсинга. DOM модель (DOM API) имеет довольно небольшую скорость XML документа, после построения иерархической структуры элементов в памяти, скорость навигации по XML документу несколько возрастает. Производительность SAX модели (Streaming API) теоретически должна быть больше, но с учетом всех проблем, возникающих при реализации (отсутствует произвольный доступ к элементам XML документа, так как потоковая модель представляет собой однонаправленный курсор, нет XPath), существенно затрудняет использование этой модели, в процессе разработки приходится вручную кэшировать нужные участки XML документа, проходить XML документ большое количество раз. Все это практически сводит на нет преимущество в скорости SAX модели над DOM моделью. VTD-XML быстрее DOM в 5-10 раз и в 1.5-2 раза больше максимальной скорости SAX
  • Использование памяти. Размер памяти, используемой VTD-XML, составляет примерно от 1.3 до 1.5 размера документа, в то время как DOM модель занимает в 5-7 раз больше размера XML документа
  • Поддержка индексирования (см. п. 1.1, п. 3)
  • “Инкрементное” изменение (см. п. 1.1., п. 4)
  • Произвольный доступ (random access). VTD-XML позволяет осуществлять навигацию по иерархической структуре XML документа, поддерживает XPath

Комментариев нет:

Отправить комментарий