flatparse 0.1.0.2 → 0.1.1.1

raw patch · 8 files changed

+140/−37 lines, 8 filesdep +bytesmithdep +primitivePVP ok

version bump matches the API change (PVP)

Dependencies added: bytesmith, primitive

API changes (from Hackage documentation)

Files

• README.md +25/−17
• bench/Bench.hs +14/−0
• bench/Bytesmith.hs +63/−0
• flatparse.cabal +5/−2
• src/FlatParse/Basic.hs +9/−3
• src/FlatParse/Examples/BasicLambda/Lexer.hs +3/−1
• src/FlatParse/Examples/BasicLambda/Parser.hs +12/−11
• src/FlatParse/Stateful.hs +9/−3

@@ -9,7 +9,7 @@ 
 ## Features and non-features
 
-* __Excellent performance__. On microbenchmarks, `flatparse` is around 10 times faster than `attoparsec` or `megaparsec`. On larger examples with heavier use of source positions and spans and/or indentation parsing, the performance difference grows to 20-30 times. Compile times and exectuable sizes are also significantly better with `flatparse` than with `megaparsec` or `attoparsec`. `flatparse` interals make liberal use of unboxed tuples and GHC primops. As a result, pure validators (parsers returning `()`) in `flatparse` are not difficult to implement with zero heap allocation.
+* __Excellent performance__. On microbenchmarks, `flatparse` is around 10 times faster than `attoparsec` or `megaparsec`. On larger examples with heavier use of source positions and spans and/or indentation parsing, the performance difference grows to 20-30 times. Compile times and exectuable sizes are also significantly better with `flatparse` than with `megaparsec` or `attoparsec`. `flatparse` internals make liberal use of unboxed tuples and GHC primops. As a result, pure validators (parsers returning `()`) in `flatparse` are not difficult to implement with zero heap allocation.
 * __No incremental parsing__, and __only strict `ByteString`__ is supported as input. However, it can be still useful to convert from `Text`, `String` or other types to `ByteString`, and then use `flatparse` for parsing, since `flatparse` performance usually more than makes up for the conversion costs.
 * __Only little-endian 64 bit systems are currently supported__. This may change in the future. Getting good performance requires architecture-specific optimizations; I've only considered the most common setting at this point.
 * __Support for fast source location handling, indentation parsing and informative error messages__. `flatparse` provides a low-level interface to these. Batteries are _not included_, but it should be possible for users to build custom solutions, which are more sophisticated, but still as fast as possible. In my experience, the included batteries in other libraries often come with major unavoidable overheads, and often we still have to extend existing machinery in order to scale to production features.
@@ -26,27 +26,34 @@ 
 Informative tutorials are work in progress. See [`src/FlatParse/Examples`](src/FlatParse/Examples) for a lexer/parser example with acceptably good error messages.
 
-### Some benchmarks
+## Contribution
 
+Pull requests are welcome. I'm fairly quick to add PR authors as collaborators.
+
+## Some benchmarks
+
 Execution times below. See source code in [bench](bench). Compiled with GHC 8.8.4 `-O2 -fllvm`.
 
 |      benchmark              |  runtime   |
 |-----------------------------|-------------
-| s-exp/fpbasic               |  3.365 ms  |
-| s-exp/fpstateful            |  3.421 ms  |
-| s-exp/attoparsec            |  42.84 ms  |
-| s-exp/megaparsec            |  57.54 ms  |
-| s-exp/parsec                |  179.7 ms  |
-| long keyword/fpbasic        |  216.4 μs  |
-| long keyword/fpstateful     |  299.0 μs  |
-| long keyword/attoparsec     |  5.297 ms  |
-| long keyword/megaparsec     |  3.646 ms  |
-| long keyword/parsec         |  49.18 ms  |
-| numeral csv/fpbasic         |  743.5 μs  |
-| numeral csv/fpstateful      |  848.5 μs  |
-| numeral csv/attoparsec      |  20.64 ms  |
-| numeral csv/megaparsec      |  10.12 ms  |
-| numeral csv/parsec          |  78.52 ms  |
+| sexp/fpbasic                | 3.345 ms   |
+| sexp/fpstateful             | 3.441 ms   |
+| sexp/bytesmith              | 5.646 ms   |
+| sexp/attoparsec             | 43.58 ms   |
+| sexp/megaparsec             | 57.76 ms   |
+| sexp/parsec                 | 182.4 ms   |
+| long keyword/fpbasic        | 306.1 μs   |
+| long keyword/fpstateful     | 220.3 μs   |
+| long keyword/bytesmith      | 1.707 ms   |
+| long keyword/attoparsec     | 5.420 ms   |
+| long keyword/megaparsec     | 3.605 ms   |
+| long keyword/parsec         | 50.10 ms   |
+| numeral csv/fpbasic         | 898.4 μs   |
+| numeral csv/fpstateful      | 868.3 μs   |
+| numeral csv/bytesmith       | 2.412 ms   |
+| numeral csv/attoparsec      | 21.30 ms   |
+| numeral csv/megaparsec      | 10.37 ms   |
+| numeral csv/parsec          | 78.16 ms   |
 
 Object file sizes for each module containing the `s-exp`, `long keyword` and `numeral csv` benchmarks.
 
@@ -54,6 +61,7 @@ | -------    | ------------------------ |
 | fpbasic    |  26456                   |
 | fpstateful |  30008                   |
+| bytesmith  |  39240                   |
 | attoparsec |  83288                   |
 | megaparsec |  188696                  |
 | parsec     |  75880                   |

@@ -1,6 +1,7 @@  module Main where +import Data.Primitive.ByteArray import Gauge import qualified Data.ByteString.Char8 as B @@ -9,6 +10,7 @@ import qualified Parsec import qualified FPStateful import qualified FPBasic+import qualified Bytesmith  sexpInp :: B.ByteString sexpInp =@@ -20,11 +22,21 @@ numcsvInp :: B.ByteString numcsvInp = B.concat ("0" : [B.pack (",  " ++ show n) | n <- [1..100000::Int]]) +sexpInp' :: ByteArray+sexpInp' = Bytesmith.strToByteArray $ B.unpack sexpInp++longwsInp' :: ByteArray+longwsInp' = Bytesmith.strToByteArray $ B.unpack longwsInp++numcsvInp' :: ByteArray+numcsvInp' = Bytesmith.strToByteArray $ B.unpack numcsvInp+ main :: IO () main = defaultMain [   bgroup "sexp" [     bench "fpbasic"     $ whnf FPBasic.runSexp    sexpInp,     bench "fpstateful"  $ whnf FPStateful.runSexp sexpInp,+    bench "bytesmith"   $ whnf Bytesmith.runSexp  sexpInp',     bench "attoparsec"  $ whnf Attoparsec.runSexp sexpInp,     bench "megaparsec"  $ whnf Megaparsec.runSexp sexpInp,     bench "parsec"      $ whnf Parsec.runSexp     sexpInp@@ -33,6 +45,7 @@   bgroup "long keyword" [     bench "fpbasic"    $ whnf FPBasic.runLongws    longwsInp,     bench "fpstateful" $ whnf FPStateful.runLongws longwsInp,+    bench "bytesmith"  $ whnf Bytesmith.runLongws  longwsInp',     bench "attoparsec" $ whnf Attoparsec.runLongws longwsInp,     bench "megaparsec" $ whnf Megaparsec.runLongws longwsInp,     bench "parsec"     $ whnf Parsec.runLongws     longwsInp@@ -41,6 +54,7 @@   bgroup "numeral csv" [     bench "fpbasic"    $ whnf FPBasic.runNumcsv    numcsvInp,     bench "fpstateful" $ whnf FPStateful.runNumcsv numcsvInp,+    bench "bytesmith"  $ whnf Bytesmith.runNumcsv  numcsvInp',     bench "attoparsec" $ whnf Attoparsec.runNumcsv numcsvInp,     bench "megaparsec" $ whnf Megaparsec.runNumcsv numcsvInp,     bench "parsec"     $ whnf Parsec.runNumcsv     numcsvInp

@@ -0,0 +1,63 @@+{-# language RankNTypes #-}++module Bytesmith (runSexp, runLongws, runNumcsv, strToByteArray) where++import Control.Applicative++import GHC.Exts++import qualified Data.Bytes.Parser       as P+import qualified Data.Bytes.Parser.Ascii as A++import Data.Primitive.ByteArray+import Data.Char++strToByteArray :: String -> ByteArray+strToByteArray = fromList . map (fromIntegral . ord)++byteArrayToStr :: ByteArray -> String+byteArrayToStr = map (chr . fromIntegral) . toList++parseByteArray :: (forall s. Parser s) -> ByteArray -> Bool+parseByteArray p b = case P.parseByteArray p b of+  P.Failure{} -> False+  _           -> True+{-# inline parseByteArray #-}++data U = U+instance Semigroup U where (<>) _ _ = U+instance Monoid U    where mempty   = U++type Parser s = P.Parser U s ()++many_ :: Parser s -> Parser s+many_ p = go where+  go = (p >> go) <|> pure ()+{-# inline many_ #-}++some_ :: Parser s -> Parser s+some_ p = p >> many_ p+{-# inline some_ #-}++ws :: Parser s+ws = many_ do+  P.any U >>= \case+    32 -> pure ()      -- ' '+    10 -> pure ()      -- '\n'+    _  -> P.fail U++open    = A.char U '(' >> ws+close   = A.char U ')' >> ws+ident   = A.skipAlpha1 U >> ws+sexp    = (open >> some_ sexp >> close) <|> ident+src     = sexp >> P.endOfInput U+runSexp = parseByteArray src++longw     = P.cstring U (Ptr "thisisalongkeyword"#)+longws    = some_ (longw >> ws) >> P.endOfInput U+runLongws = parseByteArray longws++numeral   = A.skipDigits1 U >> ws+comma     = A.char U ',' >> ws+numcsv    = numeral >> many_ (comma >> numeral) >> P.endOfInput U+runNumcsv = parseByteArray numcsv

@@ -4,10 +4,10 @@ -- -- see: https://github.com/sol/hpack ----- hash: df83ba622236fe722641b9c67f9617e027392e36c25387858a3beffc734f05be+-- hash: aa216bc46905b15bd49381505a4e05c27e49635a2d8d9bfbe8ef1f5db26a0d08  name:           flatparse-version:        0.1.0.2+version:        0.1.1.1 synopsis:       High-performance parsing from strict bytestrings description:    @Flatparse@ is a high-performance parsing library, focusing on programming languages and                 human-readable data formats. See the README for more information:@@ -53,6 +53,7 @@   main-is: Bench.hs   other-modules:       Attoparsec+      Bytesmith       FPBasic       FPStateful       Megaparsec@@ -65,9 +66,11 @@   build-depends:       attoparsec     , base >=4.7 && <5+    , bytesmith     , bytestring     , flatparse     , gauge     , megaparsec     , parsec+    , primitive   default-language: Haskell2010

@@ -28,6 +28,7 @@   , fails   , try   , optional+  , optional_   , optioned   , cut   , cutting@@ -224,7 +225,7 @@         pure (OK a (B.drop (I# offset) b))       Fail# ->         pure Fail-{-# noinline runParser #-}+{-# inlinable runParser #-}  -- | Run a parser on a `String` input. Reminder: @OverloadedStrings@ for `B.ByteString` does not --   yield a valid UTF-8 encoding! For non-ASCII `B.ByteString` literal input, use `runParserS` or@@ -288,6 +289,11 @@ optional p = (Just <$> p) <|> pure Nothing {-# inline optional #-} +-- | Convert a parsing failure to a `()`.+optional_ :: Parser r e a -> Parser r e ()+optional_ p = (() <$ p) <|> pure ()+{-# inline optional_ #-}+ -- | CPS'd version of `optional`. This is usually more efficient, since it gets rid of the --   extra `Maybe` allocation. optioned :: Parser r e a -> (a -> Parser r e b) -> Parser r e b -> Parser r e b@@ -782,8 +788,8 @@         if pos == p then           ((i, (line, col)):) <$> go line col poss         else do-          c <- anyWord8-          if ord '\n' == fromIntegral c then+          c <- anyChar+          if '\n' == c then             go (line + 1) 0 ((i, pos):poss)           else             go line (col + 1) ((i, pos):poss)

@@ -4,9 +4,11 @@ demonstrates a simple but decently informative implementation of error message propagation. -} +{-# language StrictData #-}+ module FlatParse.Examples.BasicLambda.Lexer where -import FlatParse.Basic hiding (Parser, runParser, string, char, cut, err)+import FlatParse.Basic hiding (Parser, runParser, string, char, cut)  import qualified FlatParse.Basic as FP import qualified Data.ByteString as B

@@ -11,7 +11,7 @@ import Data.Char (ord) import qualified Data.ByteString as B -import FlatParse.Basic hiding (Parser, runParser, string, char, err, cut)+import FlatParse.Basic hiding (Parser, runParser, string, char, cut) import FlatParse.Examples.BasicLambda.Lexer  --------------------------------------------------------------------------------@@ -62,7 +62,7 @@ int = token $   snd <$> chainr (\n (!place, !acc) -> (place*10,acc+place*n)) digit ((10,) <$> digit) --- | Parse a literal, identifier or parenthsized expression.+-- | Parse a literal, identifier or parenthesized expression. atom :: Parser Tm atom =        (Var           <$> ident)@@ -71,9 +71,12 @@    <|> (IntLit        <$> int)    <|> ($(symbol "(") *> tm <* $(cutSymbol ")")) +expectAtom :: [Expected]+expectAtom = [Msg "identifier", Lit "true", Lit "false", Msg "parenthesized expression"]+ -- | Parse an `App`-level expression. app :: Parser Tm-app = chainl App (atom `cut` [Msg "identifier", Lit "true", Lit "false"]) atom+app = chainl App (atom `cut` expectAtom) atom  -- | Parse a `Mul`-level expression. mul :: Parser Tm@@ -128,17 +131,15 @@  -- | Parse a complete source file. src :: Parser Tm-src = ws *> tm <* eof `cut`-  [Msg "end of input", Msg "identifier", Lit "true", Lit "false",-   Msg "integer literal", Msg "parenthesized expression"]+src = ws *> tm <* eof `cut` (Msg "end of input" : expectAtom)   -- Examples --------------------------------------------------------------------------------  -- testParser src p1--- p1 = unlines [---   "let f = lam x. lam y. x (x (x y)) in",---   "let g = if f true then false else true in",---   "f g g h"---   ]+p1 = unlines [+  "let f = lam x. lam y. x (x (x y)) in",+  "let g = if f true then false else true in",+  "f g g h"+  ]

@@ -31,6 +31,7 @@   , fails   , try   , optional+  , optional_   , optioned   , cut   , cutting@@ -227,7 +228,7 @@         pure (OK a (I# n) (B.drop (I# offset) b))       Fail# ->         pure Fail-{-# noinline runParser #-}+{-# inlinable runParser #-}  -- | Run a parser on a `String` input. Reminder: @OverloadedStrings@ for `B.ByteString` does not --   yield a valid UTF-8 encoding! For non-ASCII `B.ByteString` literal input, use `runParserS` or@@ -308,6 +309,11 @@ optional p = (Just <$> p) <|> pure Nothing {-# inline optional #-} +-- | Convert a parsing failure to a `()`.+optional_ :: Parser r e a -> Parser r e ()+optional_ p = (() <$ p) <|> pure ()+{-# inline optional_ #-}+ -- | CPS'd version of `optional`. This is usually more efficient, since it gets rid of the --   extra `Maybe` allocation. optioned :: Parser r e a -> (a -> Parser r e b) -> Parser r e b -> Parser r e b@@ -803,8 +809,8 @@         if pos == p then           ((i, (line, col)):) <$> go line col poss         else do-          c <- anyWord8-          if ord '\n' == fromIntegral c then+          c <- anyChar+          if '\n' == c then             go (line + 1) 0 ((i, pos):poss)           else             go line (col + 1) ((i, pos):poss)