Czy kombinatory parserów mogą być wydajne?

Około 6 lat temu, porównałem moje własne kombinatory parserów w OCaml i odkryłem, że były ~5× wolniejsze niż Generatory parserów w ofercie w tym czasie. Niedawno zrewidowałem ten temat i porównałem Parsec Haskella z prostym ręcznie zwijanym parserem , napisanym w F# i byłem zaskoczony, że F # jest 25× szybszy od Haskella.

Oto Kod Haskella, którego użyłem do odczytania dużego wyrażenia matematycznego z pliku, analizy i oceny it: 

import Control.Applicative
import Text.Parsec hiding ((<|>))

expr = chainl1 term ((+) <$ char '+' <|> (-) <$ char '-')

term = chainl1 fact ((*) <$ char '*' <|> div <$ char '/')

fact = read <$> many1 digit <|> char '(' *> expr <* char ')'

eval :: String -> Int
eval = either (error . show) id . parse expr "" . filter (/= ' ')

main :: IO ()
main = do
    file <- readFile "expr"
    putStr $ show $ eval file
    putStr "\n"

A oto mój samodzielny parser wspinaczkowy W F#: 

let rec (|Expr|) = function
  | P(f, xs) -> Expr(loop (' ', f, xs))
  | xs -> invalidArg "Expr" (sprintf "%A" xs)
and loop = function
  | ' ' as oop, f, ('+' | '-' as op)::P(g, xs)
  | (' ' | '+' | '-' as oop), f, ('*' | '/' as op)::P(g, xs) ->
      let h, xs = loop (op, g, xs)
      match op with
      | '+' -> (+) | '-' -> (-) | '*' -> (*) | '/' | _ -> (/)
      |> fun op -> loop (oop, op f h, xs)
  | _, f, xs -> f, xs
and (|P|_|) = function
  | '('::Expr(f, ')'::xs) -> Some(P(f, xs))
  | c::_ as xs when '0' <= c && c <= '9' ->
      let rec loop n = function
        | c2::xs when '0' <= c2 && c2 <= '9' -> loop (10*n + int(string c2)) xs
        | xs -> Some(P(n, xs))
      loop 0 xs
  | _ -> None
Mam wrażenie, że nawet najnowocześniejsze kombinatory parserów tracą dużo czasu na śledzenie wstecz. Zgadza się? Jeśli tak, to czy możliwe jest pisanie kombinatorów parserów, które generują maszyny stanowe w celu uzyskania konkurencyjnej wydajności, czy też konieczne jest użycie generowania kodu?

EDIT:

Oto skrypt OCaml, którego użyłem do wygenerowania wyrażenia ~2MB dla "benchmarking": {]} 

open Printf

let rec f ff n =
  if n=0 then fprintf ff "1" else
    fprintf ff "%a+%a*(%a-%a)" f (n-1) f (n-1) f (n-1) f (n-1)

let () =
  let n = try int_of_string Sys.argv.(1) with _ -> 3 in
  fprintf stdout "%a\n" f n
Author: Jon Harrop, 2010-12-30
Source

4 answers

Obecnie pracuję nad kolejną wersją FParsec (V.0. 9), która w wielu sytuacjach poprawi wydajność nawet o współczynnik 2 w stosunku do aktualnej wersji.

[Aktualizacja: fparsec 0.9 został wydany, zobacz http://www.quanttec.com/fparsec ]

Przetestowałem implementację F # parsera Jona pod kątem dwóch implementacji FParsec. Pierwszy parser FParsec jest bezpośrednim tłumaczeniem parsera djahandarie. Drugi wykorzystuje wbudowany FParsec komponent pierwszeństwa operatora. Jako wejście użyłem napisu wygenerowanego skryptem OCaml Jona z parametrem 10, który daje mi wielkość wejścia około 2,66 MB. Wszystkie parsery zostały skompilowane w trybie release i były uruchamiane na 32-bitowym CLR.NET 4. Zmierzyłem tylko czysty czas parsowania i nie uwzględniłem czasu uruchamiania ani czasu potrzebnego do zbudowania łańcucha wejściowego (dla parserów FParsec) lub listy znaków (parser Jona).

Zmierzyłem następujące numery (zaktualizowane numery dla V. 0. 9 w parens): {]}

  • ręczny Parser Jona: ~230ms
  • fparsec parser # 1: ~270ms (~235ms)
  • fparsec parser # 2: ~110ms (~102ms)

W świetle tych liczb, powiedziałbym, że kombinatory parserów mogą zdecydowanie oferować konkurencyjną wydajność, przynajmniej dla tego konkretnego problemu, zwłaszcza jeśli wziąć pod uwagę, że FParsec

  • automatycznie generuje bardzo czytelne komunikaty o błędach,
  • obsługuje bardzo duże pliki jako wejście (z dowolny backtracking), oraz
  • jest dostarczany z deklaratywnym, konfigurowalnym modułem parsera pierwszeństwa operatora.

Oto kod dla dwóch implementacji FParsec:

Parser #1 (tłumaczenie parsera djahandarie):

open FParsec

let str s = pstring s
let expr, exprRef = createParserForwardedToRef()

let fact = pint32 <|> between (str "(") (str ")") expr
let term =   chainl1 fact ((str "*" >>% (*)) <|> (str "/" >>% (/)))
do exprRef:= chainl1 term ((str "+" >>% (+)) <|> (str "-" >>% (-)))

let parse str = run expr str

Parser # 2 (implementacja Idiomatic FParsec):

open FParsec

let opp = new OperatorPrecedenceParser<_,_,_>()
type Assoc = Associativity

let str s = pstring s
let noWS = preturn () // dummy whitespace parser

opp.AddOperator(InfixOperator("-", noWS, 1, Assoc.Left, (-)))
opp.AddOperator(InfixOperator("+", noWS, 1, Assoc.Left, (+)))
opp.AddOperator(InfixOperator("*", noWS, 2, Assoc.Left, (*)))
opp.AddOperator(InfixOperator("/", noWS, 2, Assoc.Left, (/)))

let expr = opp.ExpressionParser
let term = pint32 <|> between (str "(") (str ")") expr
opp.TermParser <- term

let parse str = run expr str
 31
Author: Stephan Tolksdorf,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-04-27 18:43:10

Wymyśliłem rozwiązanie Haskella, które jest 30× szybsze niż rozwiązanie Haskella, które napisałeś (z moim wymyślonym wyrażeniem testowym).

Główne zmiany:

  1. Zmień Parsec / String Na Attoparsec / ByteString
  2. w funkcji fact Zmień read & many1 digit do decimal
  3. Wykonane chainl1 rekurencja ścisła (Usuń $! dla wersji lazier).
Starałem się, żeby wszystko inne było jak najbardziej podobne. 
import Control.Applicative
import Data.Attoparsec
import Data.Attoparsec.Char8
import qualified Data.ByteString.Char8 as B

expr :: Parser Int
expr = chainl1 term ((+) <$ char '+' <|> (-) <$ char '-')

term :: Parser Int
term = chainl1 fact ((*) <$ char '*' <|> div <$ char '/')

fact :: Parser Int
fact = decimal <|> char '(' *> expr <* char ')'

eval :: B.ByteString -> Int
eval = either (error . show) id . eitherResult . parse expr . B.filter (/= ' ')

chainl1 :: (Monad f, Alternative f) => f a -> f (a -> a -> a) -> f a
chainl1 p op = p >>= rest where
  rest x = do f <- op
              y <- p
              rest $! (f x y)
           <|> pure x

main :: IO ()
main = B.readFile "expr" >>= (print . eval)

I guess what I concluded z tego wynika, że większość spowolnienia dla kombinatora parserów polegała na tym, że siedział on na nieefektywnej podstawie, a nie że był kombinatorem parserów, per se.

Wyobrażam sobie, że z większą ilością czasu i profilowaniem może to pójść szybciej, ponieważ zatrzymałem się, gdy przeszedłem znak 25×.

Nie wiem, czy byłoby to szybsze niż Parser wspinaczkowy przeniesiony do Haskell. Może to byłby interesujący test?

 58
Author: Darius Jahandarie,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-12-30 06:51:35

W skrócie, kombinatory parserów są wolne dla lexingu.

Była biblioteka Haskell combinator do budowania lexerów ( zobacz" Lazy Lexing is Fast " Manuel M. T. Chakravarty) - ponieważ tabele były generowane w czasie wykonywania, nie było kłopotów z generowaniem kodu. Biblioteka trochę się zużyła - początkowo była używana w jednym z preprocesorów FFI, ale nie sądzę, aby kiedykolwiek została załadowana do Hackage ' a, więc może była trochę zbyt niewygodna dla zwykłego użytkowania.

W kodzie OCaml powyżej, parser jest bezpośrednio dopasowywany na listach znaków, więc może być tak szybki, jak destrukcja listy jest w języku hosta (byłby znacznie szybszy niż Parsec, gdyby został ponownie zaimplementowany w Haskell). Christian Lindig miał bibliotekę OCaml, która miała zestaw kombinatorów parsera i zestaw kombinatorów lexer - kombinatory lexer były z pewnością znacznie prostsze niż Manuel Chakravarty ' s, i może warto byłoby śledzić tę bibliotekę i bench-znakowanie go przed napisaniem lexer generator.

 13
Author: stephen tetley,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-12-30 08:35:57

Czy próbowałeś jednej ze znanych bibliotek szybkiego parsera? Celem Parsec nigdy tak naprawdę nie była szybkość, ale łatwość użycia i przejrzystość. Porównywanie z czymś takim jak attoparsec może być bardziej sprawiedliwym porównaniem, zwłaszcza, że typy łańcuchów mogą być bardziej równe (ByteString zamiast String).

Zastanawiam się również, które flagi kompilacji zostały użyte. Jest to kolejny trollingowy post autorstwa niesławnego Jona Harropa, nie zdziwiłoby mnie, gdyby w ogóle nie użyto optymalizacji dla Haskella kod.

 8
Author: Axman6,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-05-29 16:44:05