Блог - Linux, программирование, Я!

Программирование → Бенчмарк 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 4HTML DOM парсер с подключаемыми бекендами.
    • html5libНаписанный на питоне DOM парсер, ориентированный на HTML5.
  • PyPy (те же парсеры, что и CPython, кроме lxml)
    • BeautifulSoup 3
    • BeautifulSoup 4
    • html5lib
  • Node.JS
    • cheerioнаписанный на JS HTML DOM парсер с поддержкой jQuery API
    • htmlparserHTML 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.

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

Тесты запускал последовательно на 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-009 html_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 он не дает.

Теги: , , , , , , , , , , , , , ,
23.12.2012 комментариев 13
  1. rushter
    2013-01-05 22:32:13 | #

    Не совсем понял чем nodejs лучше python+lxml. По графикам вроде бы разница минимальна, при этом lxml местами быстрей. Можете на пальцах пояснить. Например в чём я выйграю при парсинге 1 млн страниц в 100 соединений используя nodejs? В памяти, цпю и т.д.

    Ответить
    • P.S.
      2013-01-05 23:40:32 | #

      По сравнению с python+lxml у NodeJS нет преимуществ ни в памяти ни в CPU. Но по сравнению с парсерами на чистом Python (bsoup/html5lib) NodeJS быстрее.
      А что подразумевается под «в 100 соединений»?

      Ответить
      • rushter
        2013-01-05 23:51:31 | #

        Ну под 100 соединений я понимал асинхронные коннекты или простое потои. Не знаю как именно вы парсили. Думал попробывать nodejs, но вот не знаю теперь, если ли смысл переписывать парсеры с multicurl+lxml.

        Ответить
        • rushter
          2013-01-05 23:52:03 | #

          простые потоки*

          Ответить
        • P.S.
          2013-01-06 01:01:05 | #

          Простые потоки не советую использовать, т.к. это сложно да и не слишком эффективно:
          — Нужно заморачиваться с очередями и блокировками
          — Больше 100-200 потоков уже будет тормозить
          — Для сетевых пауков поток большую часть времени будет заблокирован на работе с сетью

          Тот парсер, который упоминается в статье изначально был на процессах ОС + urllib2 + lxml — больше 60 параллельных задач уже с трудом переваривал (занимал ~ 3Гб памяти и прилично CPU), то же самое с потоками. Скорость была ~10 страниц в секунду.

          Потом его переписал за пару дней на gevent (зеленые потоки) и запускал процессы ОС по числу ядер, в каждом по ~200-300 зеленых потоков. Работало гораздо лучше (~700Мб памяти при суммарной параллельности ~ 800 потоков) и до 50 страниц в секунду.

          Потом переписал на Erlang, и оно стало занимать ~500Мб памяти при такой же параллельности, но обрабатывало 100-140 страниц в секунду. При том, что HTML парсер у Erlang медленнее, чем lxml. Просто сам паук получился более эффективным.

          Если вы с Erlang связываться не хотите — берите gevent + urllib2 — не ошибетесь. Будет по скорости быстрее чем NodeJS и гораздо удобнее, т.к. не придется трахаться с коллбеками. По сравнению с gevent не вижу у NodeJS никаких преимуществ. Разве что драйвера к БД тоже неблокирующие.

          Ответить
          • rushter
            2013-01-06 02:47:38 | #

            А multicurl пробовали? Общался с разработчиком grab, он посоветовал попробовать multicurl (асинхронные запросы), в частности обёртку grab.spider для него. Скорость очень удивила. Бенчмарки я не устраивал, но 150 потоков работают идеально. Через прокси за пару часов обрабатывается миллон запросов. Не зря наверное его разработчики youtube использовали долгое время, а потом написали своё решение. Плюс multicurl советуют разработчики tornado, у них есть на выбор интерфейс urllib или curl.
            А про функционал в нём для работы с прокси вообще говорить не стоит, для работы с sock4/5 его просто нет.
            Erlang показался мне очень сложным, может это мнение сильно обманчиво?

            Ответить
            • P.S.
              2013-01-06 03:39:16 | #

              Multicurl не пробовал, но как то и не возникало желания. Gevent и urllib2 хорошо справлялись.

              Erlang может поначалу и сложный и простые системы на нем нет смысла писать. Но если нужно написать навороченный сервис с кучей логики, то просто идеален.

              Например, после того как переписал паука на Erlang смог полностью отказаться от MongoDB, через которую запущенные процессы взаимодействовали и в которой хранились всякие кукисы/сессии и пр.
              Ну и по ядрам процессора паук стал расползаться автоматически.

              Ответить
          • Денис
            2013-02-01 16:52:10 | #

            Ну не знаю у меня прямо противоположные вещи выходили ))
            http://stackoverflow.com/questions/12996254/what-are-the-advantages-of-multithreaded-programming-in-python

            Ответить
            • P.S.
              2013-02-01 19:10:18 | #

              Странненько. Но вообще код из StackOverflow весьма специфический — он на localhost выполняется… Логичнее было бы попробовать удалённый сервер просканировать.
              И ещё ты не замерил потребление памяти. Я уверен, что в случае с Thread() её отъело гораздо больше.

              Кстати, на SO у тебя там баг в коде:

                                                      
    open_ports = [i for i in s.run()]
    print 'CPython time: %s (sec) open: %s' % (now - time.time(),
                                                len(open_ports))

              нужно заменить s.run() на s.run_std()

              Ответить
              • Денис
                2013-02-06 10:34:56 | #

                Да по памяти там вообще ад если сравнивать. Ты на PyConf в Ебург едешь ?

                Ответить
                • P.S.
                  2013-02-06 15:51:48 | #

                  На PyCon пока не планировал ехать. Но может передумаю.

                  Ответить

Теги

8.04 (), apache (), base64 (), bash (), coroutines (), cp1251 (), DNS (), DOM (), Erlang (), gtk+-2.0 (), hardy (), html (), Jabber (), javascript (), linux на сервере (), mysql (), NetworkManager (), Nginx (), NodeJS (), patch (), php (), plugin (), proftpd (), Python (), redmine (), Ruby (), smtp (), svn (), tornado (), ubuntu (), virtualbox (), vpn (), windows xp (), WordPress (), x-org (), Ульяновск (), Установка из исходников (), виртуальные машины (), домен (), кодировка (), конференция (), протокол (), сервер (), скрипт (), стачка (),