flatparse: High-performance parsing from strict bytestrings

[ library, mit, parsing ] [ Propose Tags ]

Flatparse is a high-performance parsing library, focusing on programming languages and human-readable data formats. See the README for more information: https://github.com/AndrasKovacs/flatparse.


[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.1.0.0, 0.1.0.1, 0.1.0.2, 0.1.1.1, 0.1.1.2, 0.2.0.0, 0.2.1.0, 0.2.2.0, 0.3.0.0, 0.3.0.1, 0.3.0.2, 0.3.0.3, 0.3.1.0, 0.3.2.0, 0.3.3.0, 0.3.4.0, 0.3.5.0, 0.3.5.1, 0.4.0.0, 0.4.0.1, 0.4.0.2, 0.4.1.0, 0.5.0.0, 0.5.0.1, 0.5.0.2, 0.5.1.0
Dependencies base (>=4.7 && <5), bytestring, containers, template-haskell [details]
License MIT
Copyright 2021 András Kovács
Author András Kovács
Maintainer puttamalac@gmail.com
Category Parsing
Home page https://github.com/AndrasKovacs/flatparse#readme
Bug tracker https://github.com/AndrasKovacs/flatparse/issues
Source repo head: git clone https://github.com/AndrasKovacs/flatparse
Uploaded by AndrasKovacs at 2021-03-20T16:57:26Z
Distributions LTSHaskell:0.5.1.0, NixOS:0.5.0.1, Stackage:0.5.1.0
Reverse Dependencies 9 direct, 25 indirect [details]
Downloads 3243 total (112 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2021-03-20 [all 1 reports]

Readme for flatparse-0.1.1.2

[back to package description]

flatparse

Hackage CI

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 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 and FlatParse.Stateful. Both support a custom error type and a custom reader environment.

  • FlatParse.Basic only supports the above features. If you don't need indentation parsing, this is sufficient.
  • FlatParse.Stateful additionally supports a built-in Int worth of internal state. 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 LLVM optimization. The difference is more marked if we use native code backend instead of LLVM.

The reason for baking a reader into the parsers, is that if we need it, it's convenient, and if we don't, then GHC very reliably optimizes unused environments away. In contrast, GHC optimizes much less reliably if we try to wrap the existing Reader from transformers around our parsers.

Tutorial

Informative tutorials are work in progress. See 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. 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