Haskell, Parsec 2 и тормоза

[thedeemon]

Помня о том, какое бурление вызвало сравнение скорости Лиспа с другими языками в прошлом номере ПФП, прошу помощи зала не допустить несправедливости. Я сейчас доделываю сравнение скорости разных методов парсинга, сделал вариант на Хаскеле на базе Parsec2, и получившаяся скорость мне совсем не нравится. До этого на Хаскеле не писал, поэтому

Comments

[anonymous]

А какие реализации будут сравниваться? Boost.Spirit будет?

[thedeemon]

Я очень хотел бы сравнить и с ним тоже. Но варианта решения на нем у меня пока еще нет. Если поможете - буду очень благодарен!

Сейчас готовы цифры по таким вариантам:
OcamlYacc, классические парсер-комбинаторы на Окамле, их модификация без списков, оптимизирующие парсер-комбинаторы на Окамле (это тема статьи), C#/System.Xml, Haskell/Parsec2.
Планируется еще добавить Boost.Spirit. Если есть еще предложения - буду рад услышать.

[alexott]

только бери 2-й спирит, он сильно быстрее

[thedeemon]

Так ведь уже:
http://thedeemon.livejournal.com/15606.html

[justy_tylor]

Лет семь назад Parsec был такой же прикольный и медленный. Для излечения его патчили под применение других типов (вместо String, который [Char]). В Parsec 3 вроде что-то иное, не смотрел. А мне советовали использовать Happy - чему разумеется не последовал, меня интересовала система описания грамматик, а не использование Хаскеля для production.

[thedeemon]

Я когда эту тему обсуждал с организаторами, мне рекомендовали из Парсеков брать именно второй, т.к. третий медленнее.

[lionet]

Happy/Alex на bytestring'fх примерно в три раза медленнее, чем ocamlyacc/ocamllex на парсинге JSON'а.

[thedeemon]

Здесь Парсек вчетверо медленнее ocamlyacc'a, т.е. разница по скорости с Happy невелика, похоже. Об этом adept тоже упоминал.

[sleepy_drago]

да библиотечные строки грустные совсем. собрал у себя и запустил ~4 сек. Для сравнения http://code.google.com/p/pugixml/ считывает в DOM и выполняет обход с выводом имени каждого узла в cout за 0.2 сек

[nealar]

Некорректное сравнение. Если сравнивать готовый XML-парсер, то не с парсечной реализацией, а с готовым XML-парсером.

[sleepy_drago]

разумеется некорректно тк потоковый парсер будет существенно быстрее :) Я просто провел baseline - для перформанса. Там строится полный DOM (это тормоз номер раз) и для каждого нода делается 1 strcmp и 2 atof (это тормоз номер два тк парсер имеет это значение быстрее).

Вот собсно код http://www.everfall.com/paste/id.php?br3cu0ui8ere
(61 строка). Собиралось 10м экспрессом (в пустой проект добавить этот файл и все 4 файлика пуги. Время работы релиза со статикой ~0.17 сек. Результат практически такой же ( другая точность распечатки плавучки ) и я поленился на мессаджи :)

[nealar]

Да, я тоже думаю, что HaXml будет медленней. Тем не менее, либу их коробки, разбирающую ДОМ, корректно сравнивать с ним. А наколенник на bison - с наколенником на Happy, в крайнем случае на парсеке.

[potan]

Да, Parsec не быстрый. И еще ленивость может сюрприз преподнести - скорость работы может зависеть от того, что потом с результатом делается.

Кстати, в Haskell можно работать со структурами аналогично OCaml:

update_lat lat bnd = bnd {
minlat = min lat (minlat bnd),
maxlat = max lat (maxlat bnd)
}

[thedeemon]

Результат (состояние парсера после окончания его работы) выводится на экран, ответ совпадает с остальными методами, т.е. файл парсится целиком, сюрпризов пока не видно.

Про структуры спасибо за хинт, поправлю.

[potan]

Да, еще можно попробовать лишние try убрать. Из-за них (опять таки в связи с ленивостью) может заметно тормозить.

[thedeemon]

А которые там лишние?
Документация говорит, что комбинатор альтернативы не делает сам откат в случае неудачи первого варианта, а для корректной работы откаты эти нужны, поэтому я в непоследние альтернативы повставлял try.

[potan]

Ну там где откат не должен происходить. Думаю что большенство :-).
Проблема в том, что в ленивом языке комбинатор, аналогичный <|>, в случае удачи с первой альтернативой должен идти дальше и возвращаться к следующими альтернативам в случаях обломов. Для этого он должен все помнить. Что бы избежать этой проблемы, <|> находит первый сработавший парсер и забывает про остальные.
"Идеологически правильное" поведение можно востановить с помощью try (как именно уже не помню), но нужно это сравнительно редко.

[thedeemon]

Нипанятна.
Возьмем простой пример. Файл состоит из XML тэгов, тэг может быть node, а может быть какой-то другой, нам не интересный. Сейчас это описано как
try p_node <|> p_tag
Если убрать try, то парсер попробует разобрать очередной тэг как node, и если не получилось, то с _текущей_ позиции будет пытаться разбирать tag, но часть символов (как минимум открывающая скобка) уже будет съедена, что приведет к ошибке. Т.е. нужно вернуться на начало тэга, для этого и try. Или я все неправильно понял?

По идее, try можно убрать из тех мест, где начала альтернатив точно не пересекаются, например при разборе флоатов. Попробую.