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

[(Anonymous)]

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

[thedeemon.livejournal.com]

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

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

[justy-tylor.livejournal.com]

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

[thedeemon.livejournal.com]

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

[lionet.livejournal.com]

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

[thedeemon.livejournal.com]

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

[sleepy-drago.livejournal.com]

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

[potan.livejournal.com]

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

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

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

[potan.livejournal.com]

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

[thedeemon.livejournal.com]

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

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

[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 (из-за этого бага, похоже)

[nealar.livejournal.com]

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

[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.

[(Anonymous)]

Написал пару парсеров на Lua LPEG (http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html) - может, пригодится для сравнения. Получилось быстрее, чем на Хаскеле(неск. раз) - при этом все работает на VM.

"Grammar 1" - более-менее честный XML парсер, "Grammar 2" оптимизирован
в предложенном стиле (стал раза в 2 быстрее).

Код на Github (http://gist.github.com/379183)

-- PEG Grammar 1:
local GG1 = [[
  osm    <- '<?xml' (!'?' .)+ '?>' <xml> <ws>
  xml    <- <node>* -> {}
  node   <- <ws> '<' {:tag: <name> :} <param>*
            <ws> ('/>' / '>' <xml> <ws> '</' <ws> =tag <ws> '>')
  param  <- (<ws> <name> '=' <string> <ws>) -> processData
  string <- '"' { (!'"' .)* } '"'
  name   <- { %w+ }
  ws     <- %s*
]]

-- PEG Grammar 2:
local GG2 = [[
  osm     <- ((<ws> '<' (<node> / <tag>))*)  <ws>
  node    <- 'node' <param>* <ws> <endnode>
  endnode <- '/>'
           / (!'</node>' .)* '</node>'
  param   <- (<ws> <name> '=' <string> <ws>) -> processData
  tag     <- (!'>' .)* '>'
  string  <- '"' { (!'"' .)* } '"'
  name    <- { %w+ }
  ws      <- %s*
]]

[thedeemon.livejournal.com]

Спасибо большое!
Попробую запустить и включить в сравнение.

[sleepy-drago.livejournal.com]

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

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

[little-arhat.livejournal.com]

antilamer недавно давал наводку на "new ghc io manager" -- который скоряет IO.
после гугления нашлось вот такое:
http://www.serpentine.com/blog/2010/03/03/whats-in-a-parsing-library-1/
http://www.serpentine.com/blog/2010/03/03/whats-in-a-parser-attoparsec-rewired-2/
http://hackage.haskell.org/package/attoparsec

может стоит сравнить? :)

[thedeemon.livejournal.com]

Спасибо за наводку! Если останется время, можно будет попробовать.

[nealar.livejournal.com]

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

[thesz.livejournal.com]

import Text.ParserCombinators.Parsec
import qualified Text.ParserCombinators.Parsec.Token as Token
import Text.ParserCombinators.Parsec.Language (emptyDef)
import System.CPUTime
import System.Environment 

data Bounds = Bounds { minlat, maxlat, minlon, maxlon :: !Double } deriving (Show)

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

update_lon lon bnd = bnd { 
    minlon = min lon (minlon bnd), maxlon = max lon (maxlon bnd) }

lexer = Token.makeTokenParser emptyDef
p_positive_float = Token.float lexer
p_float =  ((char '-' >> return negate) <|> (return id)) >>= \f -> p_positive_float >>= (return . f)

latlon = do
  param <- do
     name <- many1 letter
     char '='
     char '"'
     return name
  case param of
    "lat" -> p_float >>= (updateState . update_lat)
    "lon" -> p_float >>= (updateState . update_lon)
    _ -> (many $ noneOf "\"") >> return ()
  char '"'
  return ()

p_param = do
  many1 letter
  string "=\""
  many $ noneOf "\""
  char '"'
  return ()
  
p_node_param = latlon
  
p_endnode = 
  try (string "/>") <|> manyTill anyChar (try (string ""))
  
p_ws = many $ oneOf " \t\n"
  
p_node = do
  string "

[Error: Irreparable invalid markup ('<node">') in entry. Owner must fix manually. Raw contents below.]

<pre
>import Text.ParserCombinators.Parsec
import qualified Text.ParserCombinators.Parsec.Token as Token
import Text.ParserCombinators.Parsec.Language (emptyDef)
import System.CPUTime
import System.Environment

data Bounds = Bounds { minlat, maxlat, minlon, maxlon :: !Double } deriving (Show)

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

update_lon lon bnd = bnd {
minlon = min lon (minlon bnd), maxlon = max lon (maxlon bnd) }

lexer = Token.makeTokenParser emptyDef
p_positive_float = Token.float lexer
p_float = ((char '-' >> return negate) <|> (return id)) >>= \f -> p_positive_float >>= (return . f)

latlon = do
param <- do
name <- many1 letter
char '='
char '"'
return name
case param of
"lat" -> p_float >>= (updateState . update_lat)
"lon" -> p_float >>= (updateState . update_lon)
_ -> (many $ noneOf "\"") >> return ()
char '"'
return ()

p_param = do
many1 letter
string "=\""
many $ noneOf "\""
char '"'
return ()

p_node_param = latlon

p_endnode =
try (string "/>") <|> manyTill anyChar (try (string "</node>"))

p_ws = many $ oneOf " \t\n"

p_node = do
string "<node"
many (p_ws >> p_node_param)
p_endnode

p_tag = between (char '<') (char '>') (many (noneOf ">"))

p_osm = do
many $ (try p_node <|> p_tag) >> p_ws
bnd <- getState
return $ show bnd

bnd0 = Bounds 1000.0 (-1000.0) 1000.0 (-1000.0)

parse_osm_file fname = do
input <- readFile fname
case runParser p_osm bnd0 fname input of
Right str -> putStrLn str
Left err -> do
putStr "parse error at "
print err

main = do
args <- getArgs
case args of
[] -> putStrLn "usage: bounds osmfile"
fname:_ -> do
t0 <- getCPUTime
parse_osm_file fname
t1 <- getCPUTime
putStrLn $ show $ 1.0e-12 * (fromInteger $ t1 - t0)
</pre
>Вот такой вариант.

ghc -O3 -o bounds --make -fvia-C -funbox-strict-fields -optc-ffast-math -optc-O3 -optc-mfpmath=sse b.hs

ghc 6.10.1

+10..15% к скорости. Правда, ругается, что SSE отключен.

Есть у меня подозрение, что дело в работе с плавающей точкой, а не в самом разборщике.

[http://users.livejournal.com/_adept_/]

Happy/alex, parsec 2 и polyparse дают примерно одинаковую скорость.

Parse 3 дает скорость примерно в 3-10 раз меньше (долго рассказывать, почему).

Если надо парсить не-UTF8 (или сравнивать с решениями, которые парсят байтовый поток), то стоит смотреть на attoparsec или его аналоги.

[thedeemon.livejournal.com]

Спасибо!

[thesz.livejournal.com]

Но я ещё посмотрю, что можно сделать.

[antilamer.livejournal.com]

Вообще-то Parsec 3 был очень медленный, но потом его ускорили до скорости Parsec 2. Но, вроде бы, еще не выложили в официальный репозиторий.

Попробуй вот эту версию http://community.haskell.org/~aslatter/code/parsec/cps/ (см. тред http://www.mail-archive.com/haskell-cafe@haskell.org/msg67893.html )

[nponeccop.livejournal.com]

Недавно вышел 3.1, может, это он и есть?

[antilamer.livejournal.com]

Точно, оно.

[sleepy-drago.livejournal.com]

ну мне как сантехнику было интересно про перформанс - парсеры я уже лет семь не видел :)
Краткий диагноз - хаскель cpu bound. плюсы IO bound.
Дальше речь идет о хрюшке x86 тк померять линупс на работе лениво - туда еще хаскель через одминов пропихивать, семерку дома лениво - надо дома сползти с дивана. Макось меня послала скачивать новый xcode иначе haskell platform из портов не ставится - так что тоже лениво.
На холодном файловом кэше код который я привел побить неудается.
С более точным таймером (timeBeginPeriod(1),timeGetTime()) предложенный код работает ~167ms (собранный целиком статикой с stlport и тп)(горячий кэш). На холодном 170-200ms.
На горячем кеше предел мечтаний в районе 115-130ms но дергается - антивирус может быть а может и еще какая ерунда. Имхо написание потокового парсера может оправдать только требование кушать реально большие файлы. Как показало вскрытие pugixml делает fread( filesize ) что быстро удаляется от оптимума при росте размера xml файлов дальше десятков мб.
Вот собсно и все про перформанс _этого_ примера - спасибо пост и комментарии про lpeg и от thesz были весьма интересны - я даже полистал доки spirita - там возможно решение на PEG портируется без переделок алгоритма.

[sleepy-drago.livejournal.com]

sorry прогнал почти обо всем кроме спасибо :)
разумеется для горячего файлового кэша плюсы тоже сpu bound - так что можно еще в пару раз.
перф. для меня это хобби для отдыха :) Если вспомню с какой стороны парсеры можно будет пойти на спортивный результат :D

[thedeemon.livejournal.com]

Какой-то спортивный интерес в этом есть, конечно, но конкретно в данной задаче чтение всего файла не выход: карта России уже больше 2 гигов.

[sleepy-drago.livejournal.com]

да карта России представляет собой определенный вызов :) 2844М.
правда и хаскельный вариант на хрюше 32 упал с
bounds.exe: out of memory

интересно под Win64 есть возможность собрать ваш пример на хаскеле? или только 32 ?

[sleepy-drago.livejournal.com]

sorry спрашивать такое лучше у гугля - нашел http://hackage.haskell.org/trac/ghc/ticket/1884

[sleepy-drago.livejournal.com]

посмотрел на ситуацию с потоковым разбором - вроде смысла руками делать то что в expat'е реализовано нет. На мелких примерах он медленнее всего раза в 2 что весьма и весьма неплохо.
Если захотеть поглумиться над industrial c++ то нужно выманить на спор деятелей с xerces или msxml на потоковый парсинг. пусть заюзают какой-нибудь sax2 и почувствуют разницу с каким-нибудь фп-yacc :).

[alexott.livejournal.com]

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

[thedeemon.livejournal.com]

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

[thedeemon.livejournal.com]

Глянул на LPEG, там всю работу делает Си-шный модуль, на Lua только интерфейс к нему. Собрать его под винду у меня пока не вышло, так что сделать замер пока не могу.

[alexott.livejournal.com]

а, пропустил

[thedeemon.livejournal.com]

Попробовал Parsec 3.1.0.
Если с ним собирать программу без изменений, то работает в 2 раза медленней, чем c 2.1.0.1.
Если переписать на использование ByteString, то в 3 раза медленней.