Мне нужно знать, как на производительность различных инструментов XML (анализаторы, валидаторы, оценщики выражений XPath и т.д.) Влияют размер и сложность входного документа. Существуют ли ресурсы, в которых описывается, как время процессора и использование памяти зависят от... ну, что? Размер документа в байтах? Количество узлов? И являются ли отношения линейными, полиномиальными или хуже?
Обновить
В статье в журнале IEEE Computer Magazine, том 41, номер 9, сентябрь 2008 г. авторы рассматривают четыре популярные модели синтаксического анализа XML (DOM, SAX, StAX и VTD). Они запускают несколько базовых тестов производительности, которые показывают, что пропускная способность DOM-парсера уменьшается вдвое при увеличении размера входного файла с 1-15 КБ до 1-15 МБ или примерно в 1000 раз больше. Пропускная способность других моделей существенно не пострадала.
К сожалению, они не провели более детальных исследований, таких как пропускная способность/использование памяти как функция количества узлов/размера.
Статья здесь.
Обновить
Я не смог найти формального решения этой проблемы. Что бы это ни стоило, я провел несколько экспериментов по измерению количества узлов в документе XML как функции размера документа в байтах. Я работаю над системой управления складом, и XML-документы являются типичными складскими документами, например, уведомление о доставке и т.д.
На приведенном ниже графике показана взаимосвязь между размером в байтах и количеством узлов (которая должна быть пропорциональна размеру памяти документа в модели DOM). Разные цвета соответствуют разным видам документов. Шкала лог/лог. Черная линия лучше всего подходит для синих точек. Интересно отметить, что для всех видов документов соотношение между размером байта и размером узла является линейным, но коэффициент пропорциональности может быть очень разным.
(источник: flickr.com)
Если бы я столкнулся с этой проблемой и не смог найти что-либо в google, я бы, вероятно, попытался сделать это сам.
Некоторые вещи "назад-на-evelope", чтобы понять, куда они идут. Но мне было бы нужно иметь представление о том, как сделать XML-парсер. Для не-алгоритмических ориентиров смотрите здесь:
Я думаю, что слишком много переменных связаны с простой метрикой сложности, если вы не делаете много предположений.
Простой парсер SAX должен быть линейным с точки зрения размера документа и плоской памяти.
Что-то вроде XPath невозможно описать с точки зрения только входного документа, так как сложность выражения XPath играет огромную роль.
Аналогично для проверки схемы большая, но простая схема может быть линейной, тогда как меньшая схема, которая имеет гораздо более сложную структуру, будет показывать худшую производительность во время выполнения.
Как и в большинстве вопросов производительности, единственный способ получить точные ответы - измерить его и посмотреть, что произойдет!
Роб Уокер прав: проблема не указана достаточно подробно. Учитывая только синтаксические анализаторы (и игнорируя вопрос о том, выполняют ли они валидацию), существуют два основных аспекта: древовидный - думаю, DOM - и потоковая /event -based-think SAX (нажмите) и StAX (pull). Говоря в огромных общих чертах, древовидные подходы потребляют больше памяти и медленнее (потому что вам нужно закончить анализ всего документа), тогда как потоковые/события-подходы потребляют меньше памяти и быстрее. Парсинг на основе дерева обычно считается более простым в использовании, хотя StAX был объявлен как огромное улучшение (в простоте использования) по SAX.
Я планировал загружать в приложение очень большие XML файлы. Я задал здесь вопрос о переполнении стека: Самая быстрая обработка XML-документов для очень больших документов.
И да, это была парсинговая часть, это было узким местом.
Я вообще не использовал синтаксические анализаторы XML. Вместо этого я анализировал символы один за другим настолько эффективно, насколько это возможно, чтобы оптимизировать скорость. Это привело к скорости 40 МБ в секунду на ПК с частотой 3 ГГц для чтения, разбора и загрузки внутренней структуры данных.
Мне было бы очень интересно узнать, как различные режимы синтаксического анализа XML сравниваются с этим.