Наши партнеры

UnixForum

Библиотека сайта rus-linux.net

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

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

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

Заключение

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

  1. Декларации типов документов (DOCTYPE) разбираются, но их данные игнорируются. Это решение было принято ввиду проблем с производительностью, сложности реализации обработчиков и отсутствия необходимости данной функции.
  2. Следует помнить, что соответствующие стандарту системы разбора документов XML должны отклонять определенные коды Unicode. Библиотека pugixml не проводит подобного анализа для повышения производительности.
  3. Здесь создается зависимость на все время существования документа - буфер исходных данных должен сохраняться дольше всех узлов древовидного представления для функционирования данной техники.
  4. Это очевидно для всех преобразований, за исключением, скорее всего, преобразований строк Unicode. В этом случае и кодировка UTF-8, и кодировка UTF-16 позволяют хранить строку более компактно, чем шестнадцатеричное или десятичное представление кодов Unicode, поэтому замена одного на другое никогда не приводит к увеличению длины строки.
  5. Есть возможность поддерживать общие ссылки на элементы с непосредственным разбором путем разделения каждой строки, содержащей ссылку на элемент, на три узла: узел со строкой префикса перед ссылкой на элемент, узел специального типа, который содержит идентификатор ссылки, а также узел со строкой суффикса, которая может быть подвергнута последующему разделению. Этот подход используется в системе разбора XML от компании Microsoft (по другим причинам).
  6. Обратитесь к статье http://en.wikipedia.org/wiki/Memory-mapped_file.
  7. Конечно же, данные для этого должны быть выровнены подходящим образом; дополнительно эта техника нарушает строгие правила использования указателей из стандартов языков программирования C/C++, что может быть, а может и не быть проблемой при практическом использовании.
  8. Обратитесь к главе 12: "Работа с Big Data в области биоинформатики", если хотите рассмотреть другой пример этой проблемы.
  9. Библиотека pugixml позволяет пользователю отключить эти функции в процессе работы приложения для повышения производительности и в целях сохранения данных. Например, вы можете работать с документами, где важно сохранить точный тип последовательностей переносов строк или где ссылки на элементы не должны раскрываться системой разбора документов XML для последующей обработки.
  10. Причина, по которой появление символа / менее вероятно, чем появление символа имени тэга, заключается в том, что каждому завершающему тэгу соответствует начальный тэг, но существуют также тэги пустых элементов, такие, как <node/>.
  11. Например, если процесс поиска имен тэгов остановился на нулевом символе, то документ является некорректно оформленным, так как не существует корректно оформленных документов XML, в которых символ, находящийся перед последним символом, является частью имени тэга.
  12. Конечно же, разбор становится более сложным из-за того, что некоторые операции сравнения используют значение последнего символа, а все другие должны пропускать его для повышения производительности. Набор модульных тестов с хорошим покрытием кода и нечетким алгоритмом генерации данных позволяет поддерживать реализацию системы разбора документов в рабочем состоянии благодаря использованию различных исходных данных для тестов.
  13. Модификация дерева важна - хотя и существуют более эффективные, чем реализованные в pugixml, способы представления не изменяющихся деревьев, изменение деревьев является крайне востребованной возможностью для алгоритмов создания документов без исходных данных и алгоритмов модификации существующих документов.
  14. Более сложная логика также может быть использована.
  15. Поле размера требуется для реализации возможности амортизированного добавления данных в течение фиксированного интервала времени. Обратитесь к статье http://en.wikipedia.org/wiki/Dynamic\_array для получения подробной информации.
  16. Это обстоятельство подразумевает ограничение в 232 дочерних узлов.
  17. По соображениям производительности эта реализация не предполагает добавления сдвига к значению выравнивания. Вместо этого она ожидает того, что все хранимые типы выравниваются по размеру указателя и все запросы резервирования задают размер с выравниванием по размеру указателя.
  18. В библиотеке pugixml этот показатель усовершенствования может быть измерен.
  19. Это, конечно же, означает, что все узлы или атрибуты не могут существовать без документа - что является вполне допустимым архитектурным решением для связи узлов в рамках языка C++.
  20. Это может быть сделано без хранения дополнительных данных с использованием выравнивания страниц, значение которого больше размера страницы (т.е., резервирование всех страниц с использованием фрагментов памяти размером в 64кб с выравниванием по границе 64кб), но невозможно использовать выравнивания по границам больших значений переносимым способом без больших дополнительных затрат памяти.

Вернуться к началу статьи.