High performance
Programming
HTML
26 December 2012

Бенчмарк HTML парсеров

Переписывал в островке кусок одного сервиса с Python на Erlang. Сам сервис занимается тем, что скачивает по HTTP значительное количество однотипных HTML страниц и извлекает из них некоторую информацию. Основная CPU нагрузка сервиса приходится на парсинг HTML в DOM дерево.

Сперва захотелось сравнить производительность Erlang парсера mochiweb_html с используемым из Python lxml.etree.HTML(). Провел простейший бенчмарк, нужные выводы сделал, а потом подумал что неплохо было бы добавить в бенчмарк ещё парочку-другую парсеров и платформ, оформить покрасивее, опубликовать код и написать статью.
На данный момент успел написать бенчмарки на Erlang, Python, PyPy, NodeJS и С в следующих комбинациях:
  • Erlang — mochiweb_html
  • CPython — lxml.etree.HTML
  • CPython — BeautifulSoup 3
  • CPython — BeautifulSoup 4
  • CPython — html5lib
  • PyPy — BeautifulSoup 3
  • PyPy — BeautifulSoup 4
  • PyPy — html5lib
  • Node.JS — cheerio
  • Node.JS — htmlparser
  • Node.JS — jsdom
  • C — libxml2 (скорее для справки)

В тесте сравниваются скорость обработки N итераций парсера и пиковое потребление памяти.

Интрига: кто быстрее — Python или PyPy? Как сказывается иммутабельность Erlang на скорости парсинга и потреблении памяти? Насколько быстра V8 NodeJS? И как на всё это смотрит код на чистом C.

Термины


Скорее всего вы с ними знакомы, но почему бы не повторить?

Нестрогий HTML парсер — парсер HTML, который умеет обрабатывать некорректный HTML код (незакрытые теги, знаки > < внутри тегов <script>, незаэскейпленные символы амперсанда &, значения атрибутов без кавычек и т.п.). Понятно, что не любой поломанный HTML можно восстановить, но можно привести его к тому виду, к которому его приводит браузер. Примечательно, что большая часть HTML, которая встречается в интернете, является в той или иной степени невалидной!
DOM дерево — Document Object Model если говорить строго, то DOM это тот API, который предоставляется яваскрипту в браузере для манипуляций над HTML документом. Мы немного упростим задачу и будем считать, что это структура данных, которая представляет из себя древовидное отображение структуры HTML документа. В корне дерева находится элемент <html>, его дочерние элементы — <head> и <body> и так далее. Например, в Python документ
<html lang="ru-RU">
    <head></head>
    <body>Hello, World!</body>
</html>

Можно в простейшем виде представить как
("html", {"lang": "ru-RU"}, [
    ("head", {}, []),
    ("body", {}, ["Hello, World!"])
])

Обычно HTML преобразуют в DOM дерево для трансформации или для извлечения данных. Для извлечения данных из дерева очень удобно использовать XPath или CSS селекторы.

Конкурсанты


  • Erlang
    • Mochiweb html parser. Единственный нестрогий HTML парсер для Erlang. Написан на эрланге.

  • CPython
    • lxml.etree.HTML биндинг libxml2. Cython
    • BeautifulSoup 3 Написанный на python HTML DOM парсер (3-я версия).
    • BeautifulSoup 4 HTML DOM парсер с подключаемыми бекендами.
    • html5lib Написанный на питоне DOM парсер, ориентированный на HTML5.

  • PyPy (те же парсеры, что и CPython, кроме lxml)
    • BeautifulSoup 3
    • BeautifulSoup 4
    • html5lib

  • Node.JS
    • cheerio написанный на JS HTML DOM парсер с поддержкой jQuery API
    • htmlparser HTML DOM парсер на чистом JS
    • jsdom написанный на JS HTML DOM парсер с навороченным API, похожем на API браузера

  • C
    • libxml2 Написанный на C нестрогий HTML SAX/DOM парсер.



Цели


Вообще, парсинг HTML (как и JSON) интересен тем, что документ нужно просматривать посимвольно. В нём нет инструкций вроде «следующие 10Кб — это сплошной текст, его копируем как есть». Если мы встретили в тексте тег <p>, то нам нужно последовательно просматривать все последующие символы на наличие конструкции </. Тот факт, что HTML может быть невалидным, заставляет «перепроверять всё по 2 раза». Потому что, например, если мы встретили тег <option>, то далеко не факт, что встретим закрывающий </option>. Вторая проблема, которая обычно возникает с такими форматами — экранирование спецсимволов. Например, если весь документ это <html>...100 мегабайт текста... &amp; ...ещё 100 мегабайт текста...</html>, то парсер будет вынужден создать в памяти полную копию содержимого тега с единственным изменением — "&amp;", преобразованный в "&" (хотя некоторые парсеры просто разбивают такой текст на 3 отдельных куска).

Необходимость строить в памяти довольно большую структуру — дерево из мелких объектов, накладывает довольно жесткие требования на управление памятью, сборщик мусора, на оверхед на создание множества мелких объектов.

Нашим бенчмарком хотим:
  • Сравнить производительность и потребление памяти различных нестрогих HTML DOM парсеров.
  • Изучить стабильность работы парсера. Возрастет ли время обработки одной страницы и объём потребляемой памяти с ростом числа итераций?
  • Как зависит скорость парсинга и потребление памяти от размера HTML документа.
  • Ну и оценить эффективность платформы: скорость работы со строками, эффективность менеджмента памяти

Проверять качество работы парсера в плане полноты восстановления поломанных документов не будем. Сравнение удобства API и наличие инструментов для работы с деревом тоже оставим за кадром.

Условия и методика тестирования


Программа один раз считывает документ с диска в память и затем N раз последовательно парсит его в цикле.
Парсер на каждой итерации должен строить в памяти полное DOM дерево.
После N итераций программа печатает время работы цикла и завершается.

Каждый парсер запускаем на наборе из нескольких HTML документов на N = 10, 50, 100, 400, 600 и 1000 итераций.
Измеряем User CPU, System CPU, Real runtime и (примерное?) пиковое потребление памяти с помощью /usr/bin/time.
HTML документы:
  • page_google.html (116Kb) — выдача гугла, 50 результатов на странице. Очень много встроенного в страницу HTML и JS, мало текста, весь HTML в одну строку.
  • page_habrahabr-70330.html (1,6Mb) — статья на хабре с 900 комментариями. Очень большая страница, много тегов, пробелов и табуляции.
  • page_habrahabr-index.html (95Kb) — главная страница habrahabr. Типичная страница блога.
  • page_wikipedia.html (99Kb) — статья на wikipedia. Хотел страничку, на которой будет много текста и мало тегов, но выбрал не самую удачную. В итоге много тегов и встроенного CSS.

На самом деле понял, что большинство документов одинакового размера только под конец, но переделывать не стал, т.к. сам процесс измерения занимает довольно много времени. А так было бы интересно отследить различные зависимости ещё и от размера страницы. UPD: готовится вторая часть статьи, в ней будем парсить сайты из TOP1000 Alexa.

Тесты запускал последовательно на Ubuntu 3.5.0-19-generic x86_64, процессор Intel Core i7-3930K CPU @ 3.20GHz × 12. (Нафига 12 ядер, если тесты запускать последовательно? Эхх...)

Код


Весь код доступен на github. Можете попробовать запустить самостоятельно, подробные инструкции есть в README файле. Даже нет — настоятельно рекомендую не верить мне, а проверить как поведут себя тесты на вашем окружении!
Tip: если хотите протестировать только часть платформ (например, не хотите устанавливать себе Erlang или PyPy), то это легко задается переменной окружения PLATFORMS.
Буду рад пулл-реквестам с реализацией парсеров на других языках (PHP? Java? .NET? Ruby?), постараюсь добавить в результаты (в первую очередь интересны нативные реализации — биндинги к libxml как правило не отличаются по скорости). Интересно было бы попробовать запустить тесты на каких-нибудь других интересных HTML файлах (большая вложенность тегов, различные размеры файлов).

Результаты


Вот сырые результаты измерений в виде CSV файлов results-1000.csv results-600.csv results-400.csv results-100.csv results-50.csv results-10.csv. Попробуем их проанализировать, для этого воспользуемся скриптом на языке R (находится в репозитории с бенчмарком в папке stats/).

Скорость


Для исследования зависимости скорости работы парсера от числа итераций, построим гистограммы зависимости [времени на обработку одной страницы] от [числа итераций]. Время на обработку одной страницы считаем как время работы парсера, разделенное на число итераций. В идеальном варианте скорость работы парсера не должна зависеть от числа итераций, а лучше — должна возрастать (за счет JIT например).
Все графики кликабельны! Не ломайте глаза!

Зависимость времени на обработку документа от числа итераций парсера (здесь и далее — для каждой HTML страницы отдельный график).
html_parser_bench_pre-001 html_parser_bench_pre-002 html_parser_bench_pre-003 html_parser_bench_pre-004
Столбики одинаковой высоты — хорошо, разной — плохо. Видно, что для большинства парсеров зависимости нет (все столбики одинаковой высоты). Исключение составляют только BeautifulSoup 4 и html5lib под PyPy; по какой-то причине у них с ростом числа итераций производительность снижается. То есть если ваш парсер на PyPy должен работать продолжительное время, то производительность будет постепенно снижаться. Неожиданно…

Теперь самый интересный график — средняя скорость обработки одной странички каждым парсером. Построим box-plot диаграмму.
Среднее время на обработку документа.
html_parser_bench_pre-005 html_parser_bench_pre-006 html_parser_bench_pre-007 html_parser_bench_pre-008
Чем выше находится бокс — тем медленнее работает парсер. Чем больше бокс по площади, тем больше разброс значений (т.е. выше зависимость производительности от числа итераций). Видно, что парсер на C лидирует, за ним следуют lxml.etree, почти вплотную парсеры на NodeJS и Erlang, потом bsoup3 парсер на PyPy, парсеры на CPython и потом с большим отрывом те же парсеры, запущенные на PyPy. Вот так сюрприз! PyPy всем сливает.
Ещё одна странность — bsoup 3 парсеру на Python чем-то не понравилась страничка википедии :-).

Пример табличных данных:
> subset(res, (file=="page_google.html") & (loops==1000))[ c("platform", "parser", "parser.s", "real.s", "user.s") ]
    platform                parser   parser.s real.s user.s
6  c-libxml2 libxml2_html_parser.c   2.934295   2.93   2.92
30    erlang     mochiweb_html.erl  13.346997  13.51  13.34
14    nodejs     cheerio_parser.js   5.303000   5.37   5.36
38    nodejs  htmlparser_parser.js   6.686000   6.72   6.71
22    nodejs       jsdom_parser.js  98.288000  98.42  98.31
33      pypy      bsoup3_parser.py  40.779929  40.81  40.62
57      pypy      bsoup4_parser.py 434.215878 434.39 433.91
41      pypy    html5lib_parser.py 361.008080 361.25 360.46
65    python      bsoup3_parser.py  78.566026  78.61  78.58
49    python      bsoup4_parser.py  33.364880  33.45  33.43
60    python    html5lib_parser.py 200.672682 200.71 200.70
67    python        lxml_parser.py   3.060202   3.08   3.08


Память


Теперь посмотрим на использование памяти. Сперва посмотрим, как потребление памяти зависит от числа итераций. Снова построим гистограммы. В идеале все столбики одного парсера должны быть одинаковой высоты. Если потребление растет с увеличением числа итераций, то это указывает на утечки памяти или проблемы со сборщиком мусора.
Потребление памяти в зависимости от числа итераций парсера.
html_parser_bench_pre-009html_parser_bench_pre-010
Занятно. Bsoup4 и html5lib под PyPy заняли по 5Гб памяти после 1000 итераций по 1Мб файлу. (Привел здесь только 2 графика, т.к. на остальных такая же картина). Видно, что с ростом числа итераций практически линейно растет и потребляемая память. Получается, что PyPy просто не совместим с Bsoup4 и html5lib парсерами. С чем это связано и кто виноват я не знаю, но зато понятно, что использование PyPy без тщательной проверки совместимости со всеми используемыми библиотеками — весьма рискованное занятие.
Выходит, что комбинация PyPy с этими парсерами выбывает. Попробуем убрать их с графиков:
Потребление памяти в зависимости от числа итераций парсера (без Bsoup4 и html5lib на PyPy).
html_parser_bench_dropped_pre-009 html_parser_bench_dropped_pre-010 html_parser_bench_dropped_pre-011 html_parser_bench_dropped_pre-012
Видим, что для парсера на C все столбики практически идентичной высоты. То же самое для lxml.etree. Для большинства парсеров потребление памяти при 10 итерациях немного меньше. Возможно просто time не успевает её замерить. NodeJS парсер jsdom ведет себя довольно странно — у него потребление памяти для некоторых страниц скачет весьма случайным образом, но в целом виден рост потребления памяти со временем. Возможно какие-то проблемы со сборкой мусора.

Сравним усредненное потребление памяти для оставшихся парсеров. Построим box-plot.
Усредненное потребление памяти.
html_parser_bench_dropped_pre-013 html_parser_bench_dropped_pre-014 html_parser_bench_dropped_pre-015 html_parser_bench_dropped_pre-016
Видим, что расстановка примерно такая же, как в сравнении скорости, но у Erlang потребление памяти оказалось ниже, чем у NodeJS. lxml.etree требует памяти примерно в 2 раза больше, чем C libxml2, но меньше чем любой другой парсер. NodeJS парсер jsdom несколько выпадает из общей картины, потребляя ~ в 2 раза больше памяти, чем другие NodeJS парсеры — видимо у него значительный оверхед, связанный с созданием дополнительных атрибутов у элементов DOM дерева.
Пример табличных данных:
> subset(res, (file=="page_google.html") & (loops==1000))[ c("platform", "parser", "maximum.RSS") ]
    platform                parser maximum.RSS
6  c-libxml2 libxml2_html_parser.c        2240
30    erlang     mochiweb_html.erl       21832
14    nodejs     cheerio_parser.js       49972
38    nodejs  htmlparser_parser.js       48740
22    nodejs       jsdom_parser.js      119256
33      pypy      bsoup3_parser.py       61756
57      pypy      bsoup4_parser.py     1701676
41      pypy    html5lib_parser.py     1741944
65    python      bsoup3_parser.py       42192
49    python      bsoup4_parser.py       54116
60    python    html5lib_parser.py       45496
67    python        lxml_parser.py        9364


Оверхед на запуск программы


Это уже не столько тест HTML парсера, сколько попытка выяснить какую платформу стоит использовать для написания консольных утилит. Просто небольшое дополнение (раз у нас уже есть данные). Оверхед платформы — это время, которое программа тратит не на непосредственно работу, а на подготовку к ней (инициализация библиотек, считывание HTML файла и т.п.). Что бы его вычислить, вычтем из времени, которое вывела утилита time — «time.s», время, которое замерили вокруг цикла парсера — «parser.s».

html_parser_bench_overhead_pre-001

Видно, что оверхед в большинстве случаев несущественный. Примечательно, что у Erlang он сравнимый с Python. Можно предположить, что он зависит от массивности библиотек, которые программа импортирует.

Выводы


Как видим — реализация на C впереди планеты всей (но и кода в ней получилось побольше).

Биндинг libxml2 к питону (lxml.etree.HTML) работает практически с такой же скоростью, но потребляет в 2 раза больше памяти (скорее всего оверхед собственно интерпретатора). Выходит, предпочтительный парсер на Python — это lxml.

Парсер на голом Erlang показывает на удивление высокие результаты, несмотря на приписываемые эрлангу «копирования данных на каждый чих» ©. Скорость сравнима с простыми парсерами на NodeJS и выше, чем у Python парсеров. Потребление памяти ниже только у C и lxml. Стабильность отличная. Такой парсер можно выпускать в продакшн (что я и сделал).

Простые парсеры на NodeJS работают очень быстро — в 2 раза медленнее сишной libxml. V8 работает крайне эффективно. Но памяти потребляют на уровне с Python, причем память расходуется не слишком стабильно (расход памяти может вырасти при увеличении числа итераций с 10 до 100, но потом стабилизируется). Парсер jsdom для простого парсинга явно не подходит, т.к. у него слишком высокие накладные расходы. Так что для парсинга HTML в NodeJS лучший выбор — cheerio.

Парсеры на чистом Python сливают как по скорости, так и по потреблению памяти, причем результаты сильно скачут на разных страницах. Но при этом ведут себя стабильно на разном количестве итераций (GC работает равномерно?)

Но больше всех удивил PyPy. То ли какие-то проблемы с GC, то ли задача для него не подходящая, то ли парсеры реализованы неудачно, то ли я где-то накосячил, но производительность парсеров на PyPy снижается с ростом числа итераций, а потребление памяти линейно растет. Bsoup3 парсер более-менее справляется, но его показатели находятся на уровне с CPython. Т.е. для парсинга на PyPy подходит только Bsoup3, но заметных преимуществ перед CPython он не дает.

Ссылки


Код бенчмарка Мой блог
Document Object Model

Присылайте свои реализации! Это очень просто!

UPD:
Результаты для добавленных парсеров (графики, CSV):
golang (3 шт, один быстрее С(!!!))
haskell (крайне неплохо)
java (openjdk, oracle-jre) (автоматически параллелится, занимая ~150% CPU, user CPU > real CPU)
perl
php + tidy
ruby (биндинг к libxml)
dart (очень медленный)
mono (2 шт) (автоматически параллелится, занимая ~150% CPU, user CPU > real CPU)

Полноценную статью + исследование зависимости скорости и потребления памяти от размера страницы по TOP1000 Alexa будет позже (надеюсь).

+60
76.5k 283
Comments 36
Top of the day