Lark: Where is the code used to do the benchmarks in the README.md?

[evandrocoan]

I would like to mention these results in my thesis to justify why I am using Lark. But without a way to reproduce the experiments on the first page (README.md) I cannot reliably cite them.

[erezsh]

The code I used to run the benchmark is currently sitting in an unplugged computer in storage :)

Lark's json parser is in examples/json_parser.py

You can look at this issue for the Parsimonious code: https://github.com/lark-parser/lark/issues/218

I'm sure it won't take long to find and adapt the parsers for PyParsing and ANTLR, since they are accessible from their websites.

Sorry, perhaps I should have included those files in the git, it just seemed extraneous and no one's asked me so far.

[evandrocoan]

No problem. For now I won't be able to use it because I already defended my thesis and I need to post the final version next week and there are more serious problems I need to fix.

If someday you can get hold of the source code on that old computer, it would be nice to have these sources on GitHub, for future references.

[goodmami]

I've started collecting benchmarking implementations at my python-parsing-benchmarks repository. I don't necessarily have the same implementations used in @erezsh's tests, but for Lark and Parsimonious I have very similar code to that in #218. I also wish to expand to other parsing tasks that can highlight the strengths of different libraries.

I'm not yet testing memory or producing pretty charts, either, but I hope to do so. i welcome any contributions to add new or improve existing implementations, as well as ideas for additional tasks.

[erezsh]

pe looks very nice! I wonder if you can remain objective now :)

Interesting that your code was so much faster for JSON. What are you doing differently than parsimonious?

If you're looking for ideas for more tests, there are many example grammars in textbooks that are meant to challenge parsers. Some very basic, like a: "b" a "b" | "a" which parses the infinite string ..bbbabbb...

Also, this issue (https://github.com/lark-parser/lark/pull/418#issue-302742732) contains a short example that's somewhat challenging.

If you're looking for practical examples, ini files are interesting, because their values aren't always quoted. Something like this: https://github.com/lark-parser/lark/blob/master/examples/conf_lalr.py

Anyway, looks like a good start!

[goodmami]

pe looks very nice! I wonder if you can remain objective now :)

Yes, good point! I started by making pe and running benchmarks locally, then I thought there would be use in having the benchmarks separately defined. I hope to have advanced users of the various libraries contribute fixes to the implementations so as to best make use of their respective features. That, at least, could help it remain objective, but only if there's uptake. Otherwise I'm not terribly compelled (and don't have time) to become an advanced user of each library, in which case the results would be a bit less comparable.

(As an aside, of the various libraries I have used so far, Lark was the most delightful to use and also results in the most readable code. Thanks for your efforts!)

Interesting that your code was so much faster for JSON. What are you doing differently than parsimonious?

Grammar optimization, mainly, and also I avoid creating ASTs. I defined each operator to have a semantic signature (i.e., the shape of the returned values). Optimizations are fine as long as they don't change the signature of grammar rules with associated actions. The combination of rule inlining and conversion to regex improves things quite a bit. With optimizations turned off, I think it might be slower than parsimonious. Also, I don't do memoization for JSON because the overhead is worse than the gain for this task. I'm not sure if you can disable Parsimonious's memoization.

Btw, the regex optimizations are interesting because I had to do a bit of work to make sure the regular expression backtracking doesn't change the parser's behavior. I found a neat trick using lookaheads and back-references to avoid backtracking in Python's standard re module. For instance, (a|ab)c will match abc in regex but not in PEG, but (?=(a|ab))\1c avoids backtracking and thus does not match abc. The regex is ugly but it performs pretty well. Some other regex engines have "atomic groups" or "possessive quantifiers" to accomplish the same thing.

If you're looking for ideas for more tests...

Thanks for the pointers! I'll look into those. I was thinking TOML but it may be too easy compared to INI files, considering unquoted strings.

[erezsh]

That's neat! I wonder if some of these grammar optimizations are applicable to Lark. Definitely joining anonymous terminals can make it a little faster. I did a manual test for JSON once and I think I saw something around a 10% speedup.

Maybe some loop unrolling? Could be an interesting experiment.

(As an aside, of the various libraries I have used so far, Lark was the most delightful to use and also results in the most readable code. Thanks for your efforts!)

Thanks, I appreciate it! Making it pleasant to work with was actually my main focus when building it.

P.S. You should also benchmark with PyPy. It gives very different performance signatures, and it's hard to ignore if you care about speed.

P.P.S. You can also benchmark repetitive parsing of very short strings. i.e. to measure the start-up time of each parser.

[goodmami]

I wonder if some of these grammar optimizations are applicable to Lark.

That'd be great. I don't have time to submit PRs, but I'd be happy to answer any questions about the optimizations.

I did a manual test for JSON once and I think I saw something around a 10% speedup.

I think that was here in #218. I had some trouble replicating this in my benchmarks, and I thought it was because even though things like _COMMA include whitespace, the grammar still has %ignore WS so I'm afraid it is still checking for whitespace between each term (I'm not sure, though). When I try to remove that %ignore WS line, I have trouble passing the tests and I couldn't figure out the problem. If you can make it work I'd be happy to update the benchmark.

P.S. You should also benchmark with PyPy. It gives very different performance signatures, and it's hard to ignore if you care about speed.

I have run some tests but I haven't included them in the benchmark results yet because I haven't properly "warmed up" PyPy. Currently Lark pulls ahead of pe in the JSON task, but they are very similar.

And yes, grammar start-up time is another benchmark I want to include. Thanks for the suggestions!

[erezsh]

Ah yes, there it is. I don't mind looking into it. Is there a way to run your benchmarks only for Lark? And also to only run it once for debugging? I tried playing around with it but going through a pip install phase for every change, and then waiting for it to run for a minute was a bit much :)

I don't know pytest very well, but it's easy to do something like python -m tests.validate.lark or similar, so you can use a relative import (pip not required), and be specific about what you want to run.

(pytest has -k but everything is under the same test_json right now)

Also, in the thread you mentioned, there's a link to textparser, which has a lot of benchmark code for json:
https://github.com/eerimoq/textparser/tree/master/examples/benchmarks/json

You probably already noticed, but I just thought I'd point that out.

[goodmami]

Is there a way to run your benchmarks only for Lark?

Yes:

$ pytest --bench=lark

And also to only run it once for debugging?

Do you mean only validating the parser and not running the timing benchmark? Then yes, try:

$ pytest --bench=lark --benchmark-skip

I tried playing around with it but going through a pip install phase for every change, and then waiting for it to run for a minute was a bit much :)

Agreed. The setup could be improved. It helps a lot if you install in "editable" mode:

$ pip install -e .

That way you don't need to reinstall each time you make a change. If you do this, I suggest making a new virtual environment to make sure the old files are gone. I'll think about how to make it work without installing.

textparser, which has a lot of benchmark code for json

Thanks! I haven't looked at that parser for a while so I'd forgotten about the benchmarking code.

[erezsh]

Nice, these really helped :)

Well, I got it to work without %ignore. I don't know if it's actually faster though, because my laptop is too inconsistent for benchmarking.

Behold the horror:

    ?start: _WS? value _WS? ";"

    ?value: object
          | array
          | string
          | NUMBER      -> number
          | "true"             -> true
          | "false"            -> false
          | "null"             -> null

    array  : _BRACK1 [value (_COMMA value)*] _BRACK2
    object : _CURLY1 [pair (_COMMA pair)*] _CURLY2
    pair   : string _COLON value

    _COLON: /\s*:\s*/
    _COMMA: /\s*,\s*/
    _CURLY1: /\s*{\s*/
    _CURLY2: /\s*}\s*/
    _BRACK1: /\s*\[\s*/
    _BRACK2: /\s*\]\s*/

    string : STRING
    STRING: "\"" INNER* "\""
    INNER: /[ !#-\[\]-\U0010ffff]*/
         | /\\(?:["\/\\bfnrt]|u[0-9A-Fa-f]{4})/

    NUMBER : INTEGER FRACTION? EXPONENT?
    INTEGER: ["-"] ("0" | "1".."9" INT?)
    FRACTION: "." INT
    EXPONENT: ("e"|"E") ["+"|"-"] INT

    _WS: /\s+/

    %import common.INT

[goodmami]

Excellent, thanks! This actually looks very similar to what I had, but I had some problem getting the visitor to work on the start node. In any case your version works well.

The pytest-benchmark code runs the test a minimum of 5 times in order to estimate the variance (but I think there's an option to control this). Make sure you're looking at the "Mean" (3rd) column and not the "Min" (1st). I'm also on a laptop but I'm getting a fairly low stddev as long as I don't do anything else while it runs. It shows about a 5% improvement, which is something, but maybe not enough to justify the less-intuitive grammar? Ideally this sort of optimization would be automatic, of course.

[erezsh]

I guess it depends if you want to maximize for performance, or keep the code somewhat idiomatic for balance. I think I can make it work automatically, but not sure it's worth the 5%. There might be other things I can do.

Oh, almost forgot. Might be worth benchmarking with python -O, to remove assertions and such, so not to punish safe-code practices.

[goodmami]

I guess it depends if you want to maximize for performance, or keep the code somewhat idiomatic for balance.

Right now the criteria are that the implementations are correct and plausible. The latter is not very specific, I guess, but it means that it shouldn't use hacks and knowledge of the parser internals to gain speed, but only use documented features or well-known parsing tactics. There's probably a bit of gray area here.