flatparse 0.5.3.0 → 0.5.3.1
raw patch · 11 files changed
+349/−37 lines, 11 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- README.md +29/−24
- bench/Attoparsec.hs +44/−1
- bench/Bench.hs +18/−1
- bench/Common.hs +9/−0
- bench/FPBasic.hs +41/−1
- bench/FPStateful.hs +41/−1
- bench/Megaparsec.hs +49/−1
- bench/Parsec.hs +70/−3
- flatparse.cabal +2/−1
- src/FlatParse/Basic/Integers.hs +2/−2
- test/Test.hs +44/−2
README.md view
@@ -17,7 +17,7 @@ ## Features and non-features -* __Excellent performance__. On microbenchmarks, `flatparse` is around 5-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 is greater. Compile times and executable 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.+* __Excellent performance__. On microbenchmarks, `flatparse` is 2-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 may be greater, because `flatparse`-s handling of source positions is heavily optimized. Compile times and executable 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 systems are currently supported as the host machine__. This may change in the future. However, `flatparse` does include primitive integer parsers with specific endianness. * __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.@@ -45,37 +45,42 @@ ## Some benchmarks -Execution times below. See source code in [bench](bench). Compiled with GHC-9.8.3. `-O2 -fllvm` with `flatparse-0.5.2.1`. Executed on Intel 1345U CPU. Uses-`nightly-2024-11-11` Stackage snapshot for the involved packages.+Execution times below. See source code in [bench](bench). Compiled with GHC 9.10.2 `-O2 -fllvm` with+`flatparse-0.5.3.1`. Executed on AMD 9800X3D CPU. Uses `lts-24.7` Stackage snapshot for the involved+packages. | benchmark | runtime | |-----------------------------|--------------|sexp/fpbasic | 3.262 ms |-|sexp/fpstateful | 2.523 ms |-|sexp/attoparsec | 15.28 ms |-|sexp/megaparsec | 36.03 ms |-|sexp/parsec | 67.16 ms |-|long keyword/fpbasic | 0.079 ms |-|long keyword/fpstateful | 0.078 ms |-|long keyword/attoparsec | 0.705 ms |-|long keyword/megaparsec | 2.014 ms |-|long keyword/parsec | 8.813 ms |-|numeral csv/fpbasic | 0.482 ms |-|numeral csv/fpstateful | 0.580 ms |-|numeral csv/attoparsec | 4.661 ms |-|numeral csv/megaparsec | 7.415 ms |-|numeral csv/parsec | 24.54 ms |+|sexp/fpbasic | 1.80 ms|+|sexp/fpstateful | 1.25 ms|+|sexp/attoparsec | 10.2 ms|+|sexp/megaparsec | 6.92 ms|+|sexp/parsec | 39.9 ms|+|long keyword/fpbasic | 0.054 ms |+|long keyword/fpstateful | 0.062 ms |+|long keyword/attoparsec | 0.308 ms |+|long keyword/megaparsec | 0.687 ms |+|long keyword/parsec | 3.50 ms |+|numeral csv/fpbasic | 0.540 ms |+|numeral csv/fpstateful | 0.504 ms |+|numeral csv/attoparsec | 3.17 ms |+|numeral csv/megaparsec | 1.09 ms |+|numeral csv/parsec | 13.8 ms |+|lambda term/fpbasic | 1.52 ms|+|lambda term/fpstateful | 1.56 ms|+|lambda term/attoparsec | 4.94 ms|+|lambda term/megaparsec | 5.35 ms|+|lambda term/parsec | 17.7 ms| Object file sizes for each module containing the `s-exp`, `long keyword` and `numeral csv` benchmarks. | library | object file size (bytes) | | ------- | ------------------------ |-| fpbasic | 26704 |-| fpstateful | 31064 |-| attoparsec | 91216 |-| megaparsec | 219712 |-| parsec | 113152 |+| fpbasic | 71088 |+| fpstateful | 73576 |+| attoparsec | 242816 |+| megaparsec | 402984 |+| parsec | 329008 | [basic]: https://hackage.haskell.org/package/flatparse/docs/FlatParse-Basic.html [stateful]: https://hackage.haskell.org/package/flatparse/docs/FlatParse-Stateful.html
bench/Attoparsec.hs view
@@ -1,8 +1,10 @@ -module Attoparsec (runSexp, runLongws, runNumcsv) where+module Attoparsec (runSexp, runLongws, runNumcsv, runTm) where import Control.Applicative import Data.Attoparsec.ByteString.Char8+import Common+import qualified Data.ByteString as B isLatinLetter :: Char -> Bool isLatinLetter c = ('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z')@@ -28,3 +30,44 @@ comma = char ',' >> ws numcsv = numeral >> skipMany1 (comma >> numeral) >> endOfInput runNumcsv = parseOnly numcsv+++--------------------------------------------------------------------------------++ident' :: Parser B.ByteString+ident' = takeWhile1 (\c -> isLatinLetter c || isDigit c) <* ws++equal = char '=' >> ws+semi = char ';' >> ws+dot = char '.' >> ws+addOp = char '+' >> ws+mulOp = char '*' >> ws+parl = char '(' >> ws+parr = char ')' >> ws++chainl :: (b -> a -> b) -> Parser b -> Parser a -> Parser b+chainl f start elem = start >>= go where+ go b = do {!a <- elem; go $! f b a} <|> pure b+{-# inline chainl #-}++add :: Parser Tm+add = chainl Add mul (addOp *> mul)++mul :: Parser Tm+mul = chainl Mul spine (mulOp *> spine)++spine :: Parser Tm+spine = chainl App atom atom++atom :: Parser Tm+atom =+ (Int <$> (decimal <* ws))+ <|> (Var <$> ident')+ <|> (parl *> tm <* parr)++tm :: Parser Tm+tm = (do {_ <- string "fun"; ws; x <- ident'; dot; t <- tm; pure (Lam x t)})+ <|> (do {_ <- string "let"; ws; x <- ident'; equal; t <- tm; semi; u <- tm; pure (Let x t u)})+ <|> add++runTm = parseOnly (ws *> tm <* endOfInput)
bench/Bench.hs view
@@ -15,9 +15,11 @@ import qualified ReadInteger import qualified Data.ByteString.UTF8-import qualified FlatParse.Common.Assorted+import FlatParse.Common.Assorted (strToUtf8) import qualified FlatParse.Basic +import Common+ sexpInp :: B.ByteString sexpInp = B.concat $ "(" : replicate 33333 "(foo (foo (foo ((bar baza)))))" ++ [")"]@@ -35,6 +37,13 @@ longString = concat $ "(" : replicate 33333 "(foo (foo (foo ((bar baza)))))" ++ [")"] +tmInp :: B.ByteString+tmInp = B.pack (unlines (do+ x <- [0..3000::Int]+ pure ("let x" ++ show x ++ " = fun f. fun g. fun x. fun y. f (f (f ((g x y + g x y) * g x y * g x y * 13500)));")+ ++ ["x1000"]))++ main :: IO () main = defaultMain [ {-@@ -70,6 +79,14 @@ bench "attoparsec" $ whnf Attoparsec.runNumcsv numcsvInp, bench "megaparsec" $ whnf Megaparsec.runNumcsv numcsvInp, bench "parsec" $ whnf Parsec.runNumcsv numcsvInp+ ],++ bgroup "lambda term" [+ bench "fpbasic" $ whnf FPBasic.runTm tmInp,+ bench "fpstateful" $ whnf FPStateful.runTm tmInp,+ bench "attoparsec" $ whnf Attoparsec.runTm tmInp,+ bench "megaparsec" $ whnf Megaparsec.runTm tmInp,+ bench "parsec" $ whnf Parsec.runTm tmInp ], bgroup "readInt/readInteger" [
+ bench/Common.hs view
@@ -0,0 +1,9 @@+{-# language Strict #-}++module Common where++import qualified Data.ByteString as B++type Name = B.ByteString+data Tm = Var Name | App Tm Tm | Lam Name Tm | Let Name Tm Tm | Int Int | Add Tm Tm | Mul Tm Tm+ deriving Show
bench/FPBasic.hs view
@@ -2,9 +2,12 @@ module FPBasic ( runSexp , runLongws- , runNumcsv) where+ , runNumcsv+ , runTm) where import FlatParse.Basic+import Common+import qualified Data.ByteString as B ws, open, close, ident, sexp, src :: Parser () () ws = skipMany $(switch [| case _ of " " -> pure (); "\n" -> pure () |])@@ -25,3 +28,40 @@ comma = $(char ',') >> ws numcsv = numeral >> skipMany (comma >> numeral) >> eof runNumcsv = runParser numcsv+++--------------------------------------------------------------------------------++ident' :: Parser () B.ByteString+ident' = byteStringOf (skipSome (skipSatisfyAscii \c -> isLatinLetter c || isDigit c)) <* ws++equal = $(string "=") <* ws+semi = $(string ";") <* ws+dot = $(string ".") <* ws+addOp = $(string "+") <* ws+mulOp = $(string "*") <* ws+parl = $(string "(") <* ws+parr = $(string ")") <* ws++add :: Parser () Tm+add = chainl Add mul (addOp *> mul)++mul :: Parser () Tm+mul = chainl Mul spine (mulOp *> spine)++spine :: Parser () Tm+spine = chainl App atom atom++atom :: Parser () Tm+atom =+ (Int <$> (anyAsciiDecimalInt <* ws))+ <|> (Var <$> ident')+ <|> (parl *> tm <* parr)++tm :: Parser () Tm+tm = $(switch [| case _ of+ "fun" -> do {ws; x <- ident'; dot; t <- tm; pure (Lam x t)}+ "let" -> do {ws; x <- ident'; equal; t <- tm; semi; u <- tm; pure (Let x t u)}+ _ -> add |])++runTm = runParser (ws *> tm <* eof)
bench/FPStateful.hs view
@@ -2,9 +2,12 @@ module FPStateful ( runSexp , runLongws- , runNumcsv) where+ , runNumcsv+ , runTm) where import FlatParse.Stateful+import Common+import qualified Data.ByteString as B ws, open, close, ident, sexp, src :: Parser () () () ws = skipMany $(switch [| case _ of " " -> pure (); "\n" -> pure () |])@@ -25,3 +28,40 @@ comma = $(char ',') >> ws numcsv = numeral >> skipMany (comma >> numeral) >> eof runNumcsv = runParser numcsv () 0+++--------------------------------------------------------------------------------++ident' :: Parser () () B.ByteString+ident' = byteStringOf (skipSome (skipSatisfyAscii \c -> isLatinLetter c || isDigit c)) <* ws++equal = $(string "=") <* ws+semi = $(string ";") <* ws+dot = $(string ".") <* ws+addOp = $(string "+") <* ws+mulOp = $(string "*") <* ws+parl = $(string "(") <* ws+parr = $(string ")") <* ws++add :: Parser () () Tm+add = chainl Add mul (addOp *> mul)++mul :: Parser () () Tm+mul = chainl Mul spine (mulOp *> spine)++spine :: Parser () () Tm+spine = chainl App atom atom++atom :: Parser () () Tm+atom =+ (Int <$> (anyAsciiDecimalInt <* ws))+ <|> (Var <$> ident')+ <|> (parl *> tm <* parr)++tm :: Parser () () Tm+tm = $(switch [| case _ of+ "fun" -> do {ws; x <- ident'; dot; t <- tm; pure (Lam x t)}+ "let" -> do {ws; x <- ident'; equal; t <- tm; semi; u <- tm; pure (Let x t u)}+ _ -> add |])++runTm = runParser (ws *> tm <* eof) () 0
bench/Megaparsec.hs view
@@ -1,10 +1,12 @@ -module Megaparsec (runSexp, runLongws, runNumcsv) where+module Megaparsec (runSexp, runLongws, runNumcsv, runTm) where import Control.Applicative import qualified Data.ByteString as B import Text.Megaparsec+import Text.Megaparsec.Byte.Lexer import Data.Char+import Common type Parser = Parsec () B.ByteString @@ -14,12 +16,18 @@ char8 :: Char -> Parser () char8 c = () <$ single (fromIntegral (ord c)) +{-# inline skipWhile #-} skipWhile :: (Char -> Bool) -> Parser () skipWhile f = () <$ takeWhileP Nothing (f . chr . fromIntegral) +{-# inline skipWhile1 #-} skipWhile1 :: (Char -> Bool) -> Parser () skipWhile1 f = () <$ takeWhile1P Nothing (f . chr . fromIntegral) +{-# inline takeWhile1 #-}+takeWhile1 :: (Char -> Bool) -> Parser B.ByteString+takeWhile1 f = takeWhile1P Nothing (f . chr . fromIntegral)+ ws, open, close, ident, sexp :: Parser () ws = skipWhile (\c -> c == ' ' || c == '\n') open = char8 '(' >> ws@@ -38,3 +46,43 @@ comma = single (fromIntegral (ord ',')) >> ws numcsv = numeral >> skipSome (comma >> numeral) >> eof runNumcsv = runParser numcsv ""++--------------------------------------------------------------------------------++ident' :: Parser B.ByteString+ident' = takeWhile1 (\c -> isLatinLetter c || isDigit c) <* ws++equal = char8 '=' >> ws+semi = char8 ';' >> ws+dot = char8 '.' >> ws+addOp = char8 '+' >> ws+mulOp = char8 '*' >> ws+parl = char8 '(' >> ws+parr = char8 ')' >> ws++chainl :: (b -> a -> b) -> Parser b -> Parser a -> Parser b+chainl f start elem = start >>= go where+ go b = do {!a <- elem; go $! f b a} <|> pure b+{-# inline chainl #-}++add :: Parser Tm+add = chainl Add mul (addOp *> mul)++mul :: Parser Tm+mul = chainl Mul spine (mulOp *> spine)++spine :: Parser Tm+spine = chainl App atom atom++atom :: Parser Tm+atom =+ (Int <$> (decimal <* ws))+ <|> (Var <$> ident')+ <|> (parl *> tm <* parr)++tm :: Parser Tm+tm = (do {_ <- chunk "fun"; ws; x <- ident'; dot; t <- tm; pure (Lam x t)})+ <|> (do {_ <- chunk "let"; ws; x <- ident'; equal; t <- tm; semi; u <- tm; pure (Let x t u)})+ <|> add++runTm = runParser (ws *> tm <* eof) ""
bench/Parsec.hs view
@@ -1,12 +1,19 @@ -module Parsec (runSexp, runLongws, runNumcsv) where+module Parsec (runSexp, runLongws, runNumcsv, runTm) where -import Text.Parsec+import Control.Monad+import Text.Parsec hiding (chainl, digit) import Text.Parsec.ByteString+import qualified Data.ByteString as B+import Data.Char hiding (isDigit)+import Common isLatinLetter :: Char -> Bool isLatinLetter c = ('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z') +isDigit :: Char -> Bool+isDigit c = '0' <= c && c <= '9'+ ws, open, close, ident, sexp :: Parser () ws = skipMany (satisfy \c -> c == ' ' || c == '\n') open = char '(' >> ws@@ -15,8 +22,14 @@ sexp = (open *> skipMany1 sexp <* close) <|> ident runSexp = parse sexp "" +byteString :: B.ByteString -> Parser ()+byteString b = do+ i <- getInput+ guard $ B.isPrefixOf b i+ setInput $ B.drop (B.length b) i+ longw, longws :: Parser ()-longw = () <$ string "thisisalongkeyword"+longw = () <$ byteString "thisisalongkeyword" longws = skipMany1 (longw *> ws) <* eof runLongws = parse longws "" @@ -25,3 +38,57 @@ comma = char ',' >> ws numcsv = numeral >> skipMany1 (comma >> numeral) >> eof runNumcsv = parse numcsv ""++--------------------------------------------------------------------------------++{-# inline byteStringOf #-}+byteStringOf :: Parser a -> Parser B.ByteString+byteStringOf p = do+ i <- getInput+ _ <- p+ i' <- getInput+ pure $! B.take (B.length i - B.length i') i++ident' :: Parser B.ByteString+ident' = byteStringOf (skipMany1 (satisfy \c -> isLatinLetter c || isDigit c)) <* ws++equal = char '=' >> ws+semi = char ';' >> ws+dot = char '.' >> ws+addOp = char '+' >> ws+mulOp = char '*' >> ws+parl = char '(' >> ws+parr = char ')' >> ws++chainl :: (b -> a -> b) -> Parser b -> Parser a -> Parser b+chainl f start elem = start >>= go where+ go b = do {!a <- elem; go $! f b a} <|> pure b+{-# inline chainl #-}++digit :: Parser Int+digit = digitToInt <$> satisfy isDigit++decimal :: Parser Int+decimal = chainl (\x n -> 10*x + n) digit digit++add :: Parser Tm+add = chainl Add mul (addOp *> mul)++mul :: Parser Tm+mul = chainl Mul spine (mulOp *> spine)++spine :: Parser Tm+spine = chainl App atom atom++atom :: Parser Tm+atom =+ (Int <$> (decimal <* ws))+ <|> (Var <$> ident')+ <|> (parl *> tm <* parr)++tm :: Parser Tm+tm = (do {byteString "fun"; ws; x <- ident'; dot; t <- tm; pure (Lam x t)})+ <|> (do {byteString "let"; ws; x <- ident'; equal; t <- tm; semi; u <- tm; pure (Let x t u)})+ <|> add++runTm = parse (ws *> tm <* eof) ""
flatparse.cabal view
@@ -5,7 +5,7 @@ -- see: https://github.com/sol/hpack name: flatparse-version: 0.5.3.0+version: 0.5.3.1 synopsis: High-performance parsing from strict bytestrings description: @Flatparse@ is a high-performance parsing library for strict bytestring input. See the README for more information: <https://github.com/AndrasKovacs/flatparse>.@@ -139,6 +139,7 @@ main-is: Bench.hs other-modules: Attoparsec+ Common FPBasic FPStateful Megaparsec
src/FlatParse/Basic/Integers.hs view
@@ -127,7 +127,7 @@ -- | Parse any 'Word' (native size) (CPS). withAnyWord :: (Word -> ParserT st e r) -> ParserT st e r-withAnyWord p = ParserT \fp eob buf st -> case 8# <=# minusAddr# eob buf of+withAnyWord p = ParserT \fp eob buf st -> case SIZEOF_HSWORD# <=# minusAddr# eob buf of 0# -> Fail# st _ -> let w# = indexWordOffAddr# buf 0# in runParserT# (p (W# w#)) fp eob (plusAddr# buf SIZEOF_HSWORD#) st@@ -135,7 +135,7 @@ -- | Parse any 'Int' (native size) (CPS). withAnyInt :: (Int -> ParserT st e r) -> ParserT st e r-withAnyInt p = ParserT \fp eob buf st -> case 8# <=# minusAddr# eob buf of+withAnyInt p = ParserT \fp eob buf st -> case SIZEOF_HSWORD# <=# minusAddr# eob buf of 0# -> Fail# st _ -> let i# = indexIntOffAddr# buf 0# in runParserT# (p (I# i#)) fp eob (plusAddr# buf SIZEOF_HSWORD#) st
test/Test.hs view
@@ -368,10 +368,52 @@ it "fails on insufficient input" $ FB.anyWord32 `shouldParseFail` "\xff\xff\xff" + describe "anyWord64" $ do+ -- Byte order is unspecified, so just assert that it succeeds.+ it "succeeds" $ FB.anyWord64 `shouldParse` "\xef\xbe\xae\x7e\xff\xb1\xc2\xd3"++ it "fails on empty input" $ FB.anyWord64 `shouldParseFail` ""+ it "fails on insufficient input" $+ FB.anyWord64 `shouldParseFail` "\xff\xff\xff\xff\xff\xff\xff"+ describe "anyWord" $ do- -- This combinator is inherently non-portable, but we know a Word is at- -- least some bytes.+ -- Byte order is unspecified, so just assert that it succeeds.+ it "succeeds" $ FB.anyWord `shouldParse` B.replicate SIZEOF_HSWORD 0xef+ it "fails on FB.empty input" $ FB.anyWord `shouldParseFail` ""++ describe "anyInt8" $ do+ it "reads a byte" $ FB.anyInt8 `shouldParseWith` ("\x2f", 0x2f)+ it "fails on FB.empty input" $ FB.anyInt8 `shouldParseFail` ""++ describe "anyInt16" $ do+ -- Byte order is unspecified, so just assert that it succeeds.+ it "succeeds" $ FB.anyInt16 `shouldParse` "\xef\xbe"++ it "fails on FB.empty input" $ FB.anyInt16 `shouldParseFail` ""+ it "fails on insufficient input" $ FB.anyInt16 `shouldParseFail` "\xff"++ describe "anyInt32" $ do+ -- Byte order is unspecified, so just assert that it succeeds.+ it "succeeds" $ FB.anyInt32 `shouldParse` "\xef\xbe\xae\x7e"++ it "fails on empty input" $ FB.anyInt32 `shouldParseFail` ""+ it "fails on insufficient input" $+ FB.anyInt32 `shouldParseFail` "\xff\xff\xff"++ describe "anyInt64" $ do+ -- Byte order is unspecified, so just assert that it succeeds.+ it "succeeds" $ FB.anyInt64 `shouldParse` "\xef\xbe\xae\x7e\xff\xb1\xc2\xd3"++ it "fails on empty input" $ FB.anyInt64 `shouldParseFail` ""+ it "fails on insufficient input" $+ FB.anyInt64 `shouldParseFail` "\xff\xff\xff\xff\xff\xff\xff"++ describe "anyInt" $ do+ -- Byte order is unspecified, so just assert that it succeeds.+ it "succeeds" $ FB.anyInt `shouldParse` B.replicate SIZEOF_HSWORD 0xef++ it "fails on FB.empty input" $ FB.anyInt `shouldParseFail` "" describe "anyChar" $ do it "reads 1-byte char" $ FB.anyChar `shouldParseWith` (UTF8.fromString "$", '$')