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

[thedeemon]

Помня о том, какое бурление вызвало сравнение скорости Лиспа с другими языками в прошлом номере ПФП, прошу помощи зала не допустить несправедливости. Я сейчас доделываю сравнение скорости разных методов парсинга, сделал вариант на Хаскеле на базе Parsec2, и получившаяся скорость мне совсем не нравится. До этого на Хаскеле не писал, поэтому наверняка мог сильно налажать. Исходник (~70 строк) выложил здесь.
Суть программы - чтение карты формата OpenStreetMap и вычисление ее реальных границ - минимальных и максимальных значений широты и долготы встреченных точек. Собирал ее с GHC 6.8.3 и 6.10.1, Parsec 2.1.0.1, команда для сборки:

ghc -O2 -package parsec bounds.hs -o bounds

Сейчас скорость получается около 3 МБ/с.
Пример простой карты тут. Скорость тестировал на карте Сингапура (архив 1.2 МБ).

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

Comments

[thedeemon.livejournal.com]

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

[potan.livejournal.com]

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

[thedeemon.livejournal.com]

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

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

[thedeemon.livejournal.com]

Попробовал. Стало на несколько процентов побыстрее.

Что занятно, гораздо большее ускорение получилось после добавления ключика -threaded при компиляции. Без него программа частенько падала в конце, будучи собрана GHC 6.10.1 (из-за этого бага, похоже)

[potan.livejournal.com]

Съесть ни чего не выплюнув парсер символу не может - язык чисто функциональный.
Проблема будет если написать p_tag <|> p_node. Здесь p_node распознается как p_tag и как p_node его разобрать не попробуют.

[thedeemon.livejournal.com]

*Main> let prs = string "<node>" <|> string "<way>"
Loading package parsec-2.1.0.1 ... linking ... done.
*Main> :t prs
prs :: GenParser Char st String
*Main> runParser prs () "" "<node>"
Right "<node>"
*Main> runParser prs () "" "<way>"
Left (line 1, column 1):
unexpected "w"
expecting "<node>"

Съел открывающую скобку, и альтернативу стал применять к остатку строки, а не с ее начала. Потому и нужен try.