flatparse 0.3.0.1 → 0.3.0.2
raw patch · 2 files changed
+112/−81 lines, 2 files
Files
- README.md +83/−74
- flatparse.cabal +29/−7
README.md view
@@ -1,74 +1,83 @@-# flatparse - -[](https://hackage.haskell.org/package/flatparse) - - -`flatparse` is a high-performance parsing library, focusing on __programming languages__ and __human-readable data formats__. The "flat" in the name -refers to the `ByteString` parsing input, which has pinned contiguous data, and also to the library internals, which avoids indirections and heap allocations -whenever possible. - -## 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` 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. -* The __backtracking model__ of `flatparse` is different to parsec libraries, and is more close to the [nom](https://github.com/Geal/nom) library in Rust. The idea is that _parser failure_ is distinguished from _parsing error_. The former is used for control flow, and we can backtrack from it. The latter is used for unrecoverable errors, and by default it's propagated to the top. `flatparse` does not track whether parsers have consumed inputs. In my experience, what we really care about is the failure/error distinction, and in `parsec` or `megaparsec` the consumed/non-consumed separation is often muddled and discarded in larger parser implementations. By default, basic `flatparse` parsers can fail but can not throw errors, with the exception of the specifically error-throwing operations. Hence, `flatparse` users have to be mindful about grammar, and explicitly insert errors where it is known that the input can't be valid. - -`flatparse` comes in two flavors: [`FlatParse.Basic`][basic] and [`FlatParse.Stateful`][stateful]. Both support a custom error type. - -* [`FlatParse.Basic`][basic] only supports the above features. If you don't need indentation - parsing, this is sufficient. -* [`FlatParse.Stateful`][stateful] additionally supports a built-in `Int` worth of internal state - and an additional `Int` reader environment. This can support a wide range of indentation parsing - features. There is a slight overhead in performance and code size compared to `Basic`. However, in - small parsers and microbenchmarks the difference between `Basic` and `Stateful` is often reduced - to near zero by GHC and/or LLVM optimization. - -## Tutorial - -Informative tutorials are work in progress. See [`src/FlatParse/Examples`](src/FlatParse/Examples) -for a lexer/parser example with acceptably good error messages. - -## 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 | -|-----------------------------|------------- -| 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. - -| library | object file size (bytes) | -| ------- | ------------------------ | -| fpbasic | 26456 | -| fpstateful | 30008 | -| bytesmith | 39240 | -| attoparsec | 83288 | -| megaparsec | 188696 | -| parsec | 75880 | - -[basic]: https://hackage.haskell.org/package/flatparse/docs/FlatParse-Basic.html -[stateful]: https://hackage.haskell.org/package/flatparse/docs/FlatParse-Stateful.html +# flatparse++[](https://hackage.haskell.org/package/flatparse)+++`flatparse` is a high-performance parsing library, focusing on __programming languages__ and __human-readable data formats__. The "flat" in the name+refers to the `ByteString` parsing input, which has pinned contiguous data, and also to the library internals, which avoids indirections and heap allocations+whenever possible.++## LLVM flag++`flatparse` by default builds with the [`-fllvm` option](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/codegens.html#llvm-code-generator-fllvm). You can disable this by turning off the `llvm` package flag. Using a [`cabal.project` file](https://cabal.readthedocs.io/en/latest/cabal-project.html#cfg-field-constraints), this is most conveniently done by adding the following:++ constraints: flatparse -llvm++[Using `stack.yaml`](https://docs.haskellstack.org/en/stable/yaml_configuration/#flags), you can add the following:++ flags:+ flatparse:+ llvm: false++## 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` 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.+* The __backtracking model__ of `flatparse` is different to parsec libraries, and is more close to the [nom](https://github.com/Geal/nom) library in Rust. The idea is that _parser failure_ is distinguished from _parsing error_. The former is used for control flow, and we can backtrack from it. The latter is used for unrecoverable errors, and by default it's propagated to the top. `flatparse` does not track whether parsers have consumed inputs. In my experience, what we really care about is the failure/error distinction, and in `parsec` or `megaparsec` the consumed/non-consumed separation is often muddled and discarded in larger parser implementations. By default, basic `flatparse` parsers can fail but can not throw errors, with the exception of the specifically error-throwing operations. Hence, `flatparse` users have to be mindful about grammar, and explicitly insert errors where it is known that the input can't be valid.++`flatparse` comes in two flavors: [`FlatParse.Basic`][basic] and [`FlatParse.Stateful`][stateful]. Both support a custom error type.++* [`FlatParse.Basic`][basic] only supports the above features. If you don't need indentation+ parsing, this is sufficient.+* [`FlatParse.Stateful`][stateful] additionally supports a built-in `Int` worth of internal state+ and an additional `Int` reader environment. This can support a wide range of indentation parsing+ features. There is a slight overhead in performance and code size compared to `Basic`. However, in+ small parsers and microbenchmarks the difference between `Basic` and `Stateful` is often reduced+ to near zero by GHC and/or LLVM optimization.++## Tutorial++Informative tutorials are work in progress. See [`src/FlatParse/Examples`](src/FlatParse/Examples)+for a lexer/parser example with acceptably good error messages.++## 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.10.7 `-O2 -fllvm`. Executed on Intel 1165G7 CPU at 28W power draw.++| benchmark | runtime |+|-----------------------------|-------------+|sexp/fpbasic | 1.625 ms |+|sexp/fpstateful | 1.815 ms |+|sexp/attoparsec | 21.75 ms |+|sexp/megaparsec | 33.12 ms |+|sexp/parsec | 98.65 ms |+|long keyword/fpbasic | 115.9 μs |+|long keyword/fpstateful | 117.7 μs |+|long keyword/attoparsec | 2.955 ms |+|long keyword/megaparsec | 2.185 ms |+|long keyword/parsec | 29.91 ms |+|numeral csv/fpbasic | 549.3 μs |+|numeral csv/fpstateful | 595.5 μs |+|numeral csv/attoparsec | 10.82 ms |+|numeral csv/megaparsec | 6.581 ms |+|numeral csv/parsec | 39.33 ms |++Object file sizes for each module containing the `s-exp`, `long keyword` and `numeral csv` benchmarks.++| library | object file size (bytes) |+| ------- | ------------------------ |+| fpbasic | 23752 |+| fpstateful | 25920 |+| attoparsec | 93584 |+| megaparsec | 257000 |+| parsec | 134296 |++[basic]: https://hackage.haskell.org/package/flatparse/docs/FlatParse-Basic.html+[stateful]: https://hackage.haskell.org/package/flatparse/docs/FlatParse-Stateful.html
flatparse.cabal view
@@ -5,7 +5,7 @@ -- see: https://github.com/sol/hpack name: flatparse-version: 0.3.0.1+version: 0.3.0.2 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:@@ -31,6 +31,16 @@ type: git location: https://github.com/AndrasKovacs/flatparse +flag dump+ description: dump core, stg and cmm to files+ manual: True+ default: False++flag llvm+ description: use llvm for building+ manual: False+ default: True+ library exposed-modules: FlatParse.Basic@@ -45,6 +55,7 @@ default-extensions: BangPatterns BlockArguments+ CPP ExplicitNamespaces LambdaCase MagicHash@@ -52,14 +63,17 @@ PatternSynonyms TemplateHaskell TupleSections- CPP- ghc-options: -Wall -Wno-name-shadowing -Wno-unused-binds -Wno-unused-matches -Wno-missing-signatures -O2 -fllvm+ ghc-options: -Wall -Wno-missing-signatures -Wno-name-shadowing -Wno-unused-binds -Wno-unused-matches -O2 build-depends: base >=4.7 && <5 , bytestring , containers , integer-gmp , template-haskell+ if flag(dump)+ ghc-options: -ddump-simpl -ddump-stg -ddump-cmm -dsuppress-all -dno-suppress-type-signatures -ddump-to-file+ if flag(llvm)+ ghc-options: -fllvm default-language: Haskell2010 test-suite spec@@ -72,6 +86,7 @@ default-extensions: BangPatterns BlockArguments+ CPP ExplicitNamespaces LambdaCase MagicHash@@ -79,15 +94,18 @@ PatternSynonyms TemplateHaskell TupleSections- CPP ExtendedDefaultRules- ghc-options: -Wall -Wno-name-shadowing -Wno-unused-binds -Wno-unused-matches -Wno-missing-signatures -O2 -fllvm -Wno-type-defaults+ ghc-options: -Wall -Wno-missing-signatures -Wno-name-shadowing -Wno-unused-binds -Wno-unused-matches -O2 -Wno-type-defaults build-depends: HUnit , base >=4.7 && <5 , bytestring , flatparse , hspec+ if flag(dump)+ ghc-options: -ddump-simpl -ddump-stg -ddump-cmm -dsuppress-all -dno-suppress-type-signatures -ddump-to-file+ if flag(llvm)+ ghc-options: -fllvm default-language: Haskell2010 benchmark bench@@ -106,6 +124,7 @@ default-extensions: BangPatterns BlockArguments+ CPP ExplicitNamespaces LambdaCase MagicHash@@ -113,8 +132,7 @@ PatternSynonyms TemplateHaskell TupleSections- CPP- ghc-options: -Wall -Wno-name-shadowing -Wno-unused-binds -Wno-unused-matches -Wno-missing-signatures -O2 -fllvm+ ghc-options: -Wall -Wno-missing-signatures -Wno-name-shadowing -Wno-unused-binds -Wno-unused-matches -O2 build-depends: attoparsec , base >=4.7 && <5@@ -125,4 +143,8 @@ , megaparsec , parsec , primitive+ if flag(dump)+ ghc-options: -ddump-simpl -ddump-stg -ddump-cmm -dsuppress-all -dno-suppress-type-signatures -ddump-to-file+ if flag(llvm)+ ghc-options: -fllvm default-language: Haskell2010