Which Parser?

[alensiljak]

Trying to identify the best parser approach for Ledger grammar.

The existing parsers are using parser libraries, not hand-written parsers. I'd like to experiment with different parser libraries available in Rust and compare the results.
Another possibility is to create a hand-written parser.

LL, LR, or PEG?

Existing implementations:

• dinero is using pest
• grossbuch uses chumsky
• ledger parser is using nom
• Tackler is using antlr

Known Rust parsers and other resources are listed at Parser Resources wiki page.

Specific implementations:

• antlr, ANTLR-based parser #31
• pest, Pest grammar/parser #30
• lalrpop, LALRPOP #28
• nom, nom-based parser #32
• custom / Ledger rewrite, Custom parser #33

[alensiljak]

I've started experimenting with pest

[alensiljak]

Some interesting links:

• https://github.com/rust-bakery/parser_benchmarks

[35VLG84]

The input is generated, but it's stable e.g. you get same input always. It's distributing the N transactions over one year period, and generates 378 different accounts: 12 for "assets" (a:ay<year>:am<month>) and 366 for "expenses" (e:ey<year>:em<month>:ed<day>).

There are also encoded checksum features into those transactions, so it should be possible to detect e.g. if some of them are dropped off. Below are two samples of 1E6 set:

2016-01-18 (#0049999) '1E6 txn-49999
 e:ey2016:em01:ed18  18.0000001
 a:ay2016:am01

2016-01-18 (#0050000) '1E6 txn-50000
 e:ey2016:em01:ed18  18.0000001
 a:ay2016:am01

It should be trivial to modify the generator for different syntax if needed. It should be fairly good stress test for parsing, because the input is exercising different arms of parse trees / parsers. Also selected set of features is about similar between different ledger-likes.

It also stress tests how application and parser are handling parse trees / AST. Either if the parser is streaming kind or if transactions are split over multiple files, that will help with resource allocations.

[35VLG84]

Benchmark for fun with Ledger-cli

Here are the numbers with Ledger-Cli, same data. And we have winner! 😉

/usr/bin/time -f "\nreal\t%es\nuser\t%Us\nsys\t%Ss\nmem\t%Mk (max)\ncpu\t%P" ledger --no-pager -f data/txns-1E6.txn balance

real	8.08s
user	6.90s
sys	1.14s
mem	2227428k (max)
cpu	99%

[alensiljak]

It should be fairly good stress test for parsing

Yes, I'm adding a line for stress testing into #6

And we have winner!

Whoa! I wonder if the pest results will be just as devastating.
For the Antlr implementation - I think it is the Rust code generator that is causing such performance hit. It has been built by one person and not reviewed by many Rust devs.

This is also an argument to rewrite the custom Ledger parser in Rust and use as a benchmark for all the generic parsers. Should the performance difference be not so high, however, it would probably be better to have a more maintainable one (i.e. the one with a grammar file).

Interesting findings!

[35VLG84]

Even with these kind of differences, the argument still stands, that the parser's performance doesn't matter, imho.

Especially IFF there is clear separation between parser/AST and actual ledger kernel, then the parser can be replaced later when it starts matter. There is enormous amount of stuff to do (to get feature parity with Ledger), so the easiest, clearest and fastest way to have some correct parser is good for now in my opinion. It could be pest or something else, but to have clear and easy to extend, to debug and to maintain implementation of parser would be big win for now.

Also these tests are good to put into perspective of personal / small org finance tool:

• The 1E4->1E5->1E6 test cases are good to detect pathological design errors (e.g. usage of exponential algos, etc.) in the tool
• 1E6 is about 2 transactions for every minute, full day, for every day, for whole year
• 1E6 is about 4 transactions per hour, for 8 hour shift, for 1000 people org, every day, for one month

and

• 1E4 is about a transaction for every 5th minute, full day, for every day, for one month
• 1E4 is about 10 transactions per hour, for 8 hour shift, for 4 people team, for every day, for one month
• 1E4 is about 3-4 transactions per day, for 100 people each, every day, for one month

The run times for 1E4 transactions are:

• ledger ~0.12s
• hledger ~0.70s
• tackler-rs ~0.45s

And all of these are pretty fast for humans 😉
https://www.pubnub.com/blog/how-fast-is-realtime-human-perception-and-technology/

If there is need to deal with 1E5-1E6 transactions sets, then there will be ingestion service / API, and again, any reasonable batch size of transactions will be fast enough even with these parsing techniques. So I don't see the need for perf-tuned custom parser at the moment. Unless ledger-rs wants to be the fastest of the pack. 😁

[alensiljak]

the parser's performance doesn't matter

Still, I have to add - my desired use case is running the app in the browser, on the phone, providing the data to a web app GUI. That's a lot of additional narrowing down of available power and increasing the load with all the layers in between.

Right now, I'm running the server in Termux. The part that calculates the performance of a security in the asset allocation is a disaster. There are many calls to Ledger to get the calculation values and it quickly adds up.
However, it may be true that the parser part performance does not matter too much - in case REPL is used. That reduces parsing to happen only once, which is then fine, overall. This is something I'll have to try - starting Ledger REPL when the server starts and shutting it down on exit, instead of making separate invocations of Ledger for every query.

[alensiljak]

Based on @35VLG84 's tests, I went in the direction of re-implementing Ledger's parser in ledger-rs-lib. There are several repositories with attempts to reconstruct the Ledger's parsing directly. However, that did not go well, transferring the C++ concepts into Rust.
The version in ledger-rs-lib implements Ledger's concepts but is implemented in Rust.

All the options are still open and it should be possible to swap parsers, should a more-performant option appears.

As a result, there is an ENBF syntax diagram for the journal format in the ReadMe file and the test suite should follow.