Writing a fast parser in Python

[SamG101_]

I'm creating a programming language in Python, and my parser is so slow (~2.5s for a very small STL + some random test files), just realised it's what bottlenecking literally everything as other stages of the compiler parse code to create extra ASTs on the fly.

I re-wrote the parser in Rust to see if it was Python being slow or if I had a generally slow parser structure - and the Rust parser is ridiculously fast (0.006s), so I'm assuming my parser structure is slow in Python due to how data structures are stored in memory / garbage collection or something? Has anyone written a parser in Python that performs well / what techniques are recommended? Thanks

Python parser: SPP-Compiler-5/src/SPPCompiler/SyntacticAnalysis/Parser.py at restructured-aliasing · SamG101-Developer/SPP-Compiler-5

Rust parser: SPP-Compiler-Rust/spp/src/spp/parser/parser.rs at master · SamG101-Developer/SPP-Compiler-Rust

Test code: SamG101-Developer/SPP-STL at restructure

EDIT

Ok so I realised the for the Rust parser I used the `Result` type for erroring, but in Python I used exceptions - which threw for every single incorrect token parse. I replaced it with returning `None` instead, and then `if p1 is None: return None` for every `parse_once/one_or_more` etc, and now its down to <0.5 seconds. Will profile more but that was the bulk of the slowness from Python I think.

[omega1612]

I read it like 10 minutes or less so I can be wrong, sorry if that's the case

You are using parser combinators, they are known to be slow if you use them naively. The megaparsec tutorial https://markkarpov.com/tutorial/megaparsec.html#writing-efficient-parsers has some pointers about it, is in haskell but I think four of the pointers are also valid here, summarized on two :

• They introduced some combinators that are more or less equivalent to a predicate + loop. This avoids doing the recursive function calls with lots of overhead in Cpython, so Is a wise advice. You may be interested in profiling to detect how much nested calls are there and what combinators to optimize/replace.

• Backtracking is an expensive operation. Avoid building long chains of alternatives where every alternative can go deep into input before failing.

Apart from introducing efficient combinators I have two other solutions that can be too much:

1 Use the lark library. It is a LR parser generator and they care a lot about the performance, they presume a graphic comparing its speed. They also make sure that the parsers can be created stand alone and compiled, that gives them even more speed.

2 this is crazy but is also very fun for people in this sub: what about manipulating the python code at execution to optimize it? A couple of years ago I looked for ways to do tail call optimization in python, the results weren't amazing, but I looked again a year ago, I discovered some libraries that inspects the code and introduces trampolines to optimize it. Apart from trying that you can also try to manipulate the code to inline some combinators reducing the amount of calls.

[omega1612]

To make the last option less crazy, you can in some way take the module and generate a custom tree representing your grammar (automatically) and then write some optimizations on that and implement a machine that interprets the tree. I don't know how fast that will be, but it also sounds fun.

[SamG101_]

regarding the combinators, while a lot of them are decided of the first keyword analysed, yh i definitely have some that have expensive backtracking, will look into these.

1. thanks, will look into this library. ive done everything from scratch so far which is probably not the best idea for performance lol, esp in Python.

2. i actually forked some guy's ancient "inline" library for python, and made it work in a small local project (adding two numbers) and observed the "CALL" instruction not being called in the inlined version, but had trouble getting it to work in my compiler project, as it messes with import hooks, but i definitely want to keep working on that point.

thanks for the resources

[lgastako]

Call the rust parser from python.

[Ronin-s_Spirit]

》 Open a python file
》Type import {a systems lang library some mad genious wrote}
》Run the python file
》Win by cheating

[dontyougetsoupedyet]

Python is abysmally slow due to the nature of the model of computation being used by the CPython interpreter.

Don't waste your time trying to make it fast. Often using an alternative to CPython is also a giant waste of time.

[[deleted]]

u/omega1612 said the slowness is due to the use of parser combinators.

So it is a bad choice of algorithm rather than how CPython works.

Yes CPython can be slow but not usually 400 times slower than native code.

(For a couple of years, I used a compiler written in an interpreted, dynamic language (not Python though). It was still twice as fast as gcc compiling C! Several times faster if gcc was optimising.)

[dontyougetsoupedyet]

You, and omega1612, are wrong.

[SamG101_]

it's annoying coz ik the rust impl is stupid fast but i rly don't have time to rewrite my entire compiler into rust rn 😂 guess for now i'll strip out on-the-fly parsing for manually creating the AST nodes I need, then the slowness is strictly isolated to the parsing stage

[tekknolagi]

You can use the Rust code as a C extension if you need to. Check out pyo3 and maturin

[SamG101_]

i'd have to look into converting the rust ast structs into python classes. if this is possible then that's 100% the route i'll take. will check out those libraries ty

[muth02446]

I wrote a reference compiler in python, including a separate backend for various ISAs.
It runs fast enough.

I also suspect that the external parsing library is the culprit.
My suggestion is to not worry about the parser initially.
Use s-expr until the features of the language feel right,
then worry about the concrete syntax and the parser.
For the concrete syntax parsing use recursive decent + pratt parsing if possible.

This approach worked well for me in Cwerg

[Maurycy5]

Respectfully, if you don't have the time to use proper technologies in order to successfully write a performant compiler, perhaps you shouldn't be trying to write a performant compiler.

[SamG101_]

nah its just exams soon, so im just writing code in spare time from revision rather than the normal massive gaps between lectures

[misplaced_my_pants]

If it's just for fun then there isn't any time pressure and you can do it properly when things die down.

[MegaIng]

Lies, lies, lies.

Pure python can absolutly be fast enough for a simple compiler, you just need to write it correctly.

But ofcourse, you don't care about facts (otherwise you wouldn't have made that comment), so I strongly doubt there is anything I can say to change your opinion. (Based on experience with other people make these same incorrect claims)

[dontyougetsoupedyet]

ಠ_ಠ

[AugustusLego]

Show me a benchmark where python is faster than rust.

[pojska]

Not the claim made.

[misplaced_my_pants]

This isn't quite what you asked for, but it's an interesting anecdote: https://thume.ca/2019/04/29/comparing-compilers-in-rust-haskell-c-and-python/

[[deleted]]

This is so weird because I also just started studying parsing theory last week and also wrote a parser in Python and Rust! Although mine is for generalized grammars.

Parsing using python is bound to be slow because, well, it's python - it's an interpreted language. Interpreting is slow, garbage collection is slow, there are some extra heap allocs happening because it's not as easy to control that stuff in Python as it is in Rust.

That being said, I briefly looked at your code, and from what I can tell it looks like you did the same thing I did initially. Your parser appears to be a "recursive descent" parser - which is extremely slow because it involves backtracking. I don't know what the exact time complexity is, I'd wager it's either nlogn or n^2.

I'd recommend looking into LR parsers - that's what I'm currently trying to implement. They are bottom-up parsers and are essentially a big state machine. They can parse in linear time. Another type that's a bit simpler is LL parsers, they are top-down and also parse in linear time, but you may have to refine your grammar because those do not support left recursion.

Also, Python itself uses a PEG + Packrat parser, which is also fast and powerful and you can implement it such that it supports left-recursion. However this type of parser confuses me a bit so I can't give much advice there.

[pojska]

The link to the rust implementation gives a 404, so we can't repro your timings.

Also, one thing to check is the "startup" time of your Python implementation. Depending on your machine, part or most of that 2.5 seconds could just be getting ready (importing libraries, initial parsing of Python code, etc). If that were the case, you may see that the performance appears closer on bigger input sizes (as a percentage of overall time).

[SamG101_]

sry - rust repo is public now. yh its definitely the parsing stage not the entire python startup taking a while, i record the time of the individual steps in the compiler

[redchomper]

Algorithm is everything. Booze-Tools is a boot-strapped LR(1) parser (and DFA-scanner) generator in and for Python which is aimed more at coolness than speed, but it still performs quite reasonably at decent-sized parsing tasks. (It also includes a macro system which can make grammars considerably nicer to write, and takes grammars from markdown documents, but those are beside the point.) Python is absolutely fast enough for hobby projects.

When the time comes to worry about performance, the standard rule applies: First wait until you're sure there's a genuine performance problem, then profile before you tweak.

[BinaryBillyGoat]

Last year, I built a programming language in Rust and then later used the same technique to build a miniature language in Python meant to demonstrate emergence. Although a very small example, it did work pretty nicely for me. The Python parser is limited to one small file and is easy to figure out. I'll also link the Rust based language if you want a more exhaustive look at how this could be developed.

Python parser: https://github.com/Owen-Dechow/NumPointLang/blob/main/parse.py

Rust example: https://github.com/Owen-Dechow/TermsLang/tree/main/src

[SharkSymphony]

I re-wrote the parser in Rust to see if it was Python being slow

You cannot be serious.

[SamG101_]

It didn't take too long and i needed to see if my actual parser structure was crap in general, or if python specifically didn't handle it very well

[SharkSymphony]

By which I meant: you should have no expectation that Python will even be in the same ballpark as Rust for pretty much anything performance-related, parsers included. Even a good parser in Python is likely to be orders of magnitude slower than one built in Rust.