Repository navigation
Faster parser #19776
Description
Mypy uses the Python stdlib ast module for parsing. Currently parsing can take from 20% to 30% of the runtime when type checking without using the incremental cache. When processing third-party dependencies, the fraction tends to be higher, since function bodies get processed during parsing but won't be type checked.
A Python-level AST is currently constructed more than once. First the ast module constructs an AST, and this is converted into a mypy AST. If we'd use a different parser, we could only build a Python-level AST once. (ast also first constructs a C-level AST, but this is probably relatively fast.)
It seems to me that the most promising approach is to adapt an existing parser library written in a lower-level language such as C or Rust (I will call this the "low-level parser"). We'd generate a serialized AST in the low-level parser using the efficient binary format we now support for incremental cache files, and mypy would deserialize the output directly into a mypy AST. I'm hoping that this would improve parsing efficiency (including time needed to build the mypy AST) by 50-100%. Overall mypy performance would be improved by roughly 5% to 15%, and possibly more once we further optimize other parts of mypy.
The deserialization based approach also has a few other benefits:
- We can run the low-level parser in parallel by using the
threadingmodule, on all supported Python versions, since it doesn't need to hold the GIL during parsing. - If the low-level parser can also produce a list of reachable import statements, we can build a module dependency graph without building a mypy AST. This would simplify parallel type checking using multiple processes.
- It will be easy to only deserialize a subset of the AST for a module. We could perhaps use this to lazily process imported modules, or to implement incremental parsing in mypy daemon.
- We can hopefully drop most function and method bodies in third-party dependencies without allocating a Python AST for them.
The Ruff parser and tree-sitter are the low-level parser options I've looked at so far. Based on some quick benchmarking, the Ruff parser appears to be much faster. The tree-sitter parser seems slow enough that it might not bring us significant performance gains (at least without multi-threading).
Integrating a new parser will be a substantial amount of work, so we should first do some prototyping to make sure the performance gains are feasible.
Activity
JukkaL commentedon Sep 2, 2025
There are a few other implementation approaches I'm ignoring for now.
Implement a custom parser in C/Rust. Writing a recursive descent parser is not super complicated, but it will take effort to handle every corner case correctly (and it sounds a bit redundant, since parsers have been implemented multiple times for Python already). And it's not clear if we can make this much faster end-to-end than the Ruff parser, for example, even if we tune this to our use case. If using an existing parser doesn't work out for some reason, we will always have this option as a fallback.
Implement a custom parser in Python and compile it using mypyc. This would require some new mypyc features that are still not available to be efficient, and even then there will be some performance hit compared to C/Rust (and it's very hard to predict the level of performance until mypyc has all these new features). An interpreted version would also likely be quite slow, which could slow tests.
A5rocks commentedon Sep 2, 2025
It would be a shame to put this much work into a parser and not support:
(Both of these have issues open, and depend on having a custom parser)
I'm not sure whether we would want to have these in a first draft, but whatever we choose should be able to support both IMO. (And then we can have more justification for our own parser!)
JukkaL commentedon Sep 3, 2025
All of the options I discussed above should be able to support these. Even if reuse an existing parser, we can fork it and add support for mypy-specific type ignores. And since the parser wouldn't be implemented in Python, we don't need to restrict Python version support based on the Python version mypy is running on.
JukkaL commentedon Oct 13, 2025
I've done some prototyping, and have PoC that supports a tiny subset of Python syntax. Based on the prototype, single-threaded performance seems significantly better -- maybe 1.5x to 2x parsing speed compared to current perf (when compiled). With parallelism the impact should be bigger. Even if using an interpreted mypy, the performance might get a little better.
Next steps:
A5rocks commentedon Oct 13, 2025
For number 4 maybe we could use some regex thing? It's probably harder to attach type-ignores to a relevant AST node than to just worry about line numbers. (this might make the case that for number 3 we just need a function that transforms an array of character positions into line/col numbers)
For number 2, does the AST really have to be serialized? I assume the cache only matters if a) the file was not edited and b) something the file depends on was edited. Probably that's not that common?
What strategy did you use? (just curious about how easy it could be to eventually make some sort of recoverable parser...)
JukkaL commentedon Oct 13, 2025
I'm using the Ruff parser. It's currently a Rust command-line utility that writes a serialized Ruff AST to stdout and it's called from Python using
subprocess-- it's very much a PoC :-)The Ruff parser seems to provide error recovery (produce an AST even if there are syntax errors), and it can probably be adapted for incremental parsing by just parsing the whole source code and throwing away unmodified parts of the AST -- it seems fast enough for that.
That seems to be the easiest way to support fast parallel type checking using multiple processes. We don't want to construct a mypy AST twice, first in the main coordinator process (to build a dependency graph), and another time in the worker process (to actually type check the code). Now we can just use the serialized form in the main process and send the serialized bytes to the worker, which is much faster than constructing two ASTs.
Also this way the Rust part doesn't need to call into mypy. It would be tricky to get the Rust extension to construct mypy AST node instances directly (and efficiently). This is the only alternative I can think of that would provide similar (or better) performance without writing a fully custom parser.
We are not going to cache/store the serialized AST, at least initially. It will just be used to transfer data from Rust to Python efficiently, and it will be immediately thrown away afterwards. The reference to caching above was about mypy incremental caching, which is otherwise unrelated but can use a similar implementation technique as AST serialization (but the incremental cache effectively caches symbol tables, not full ASTs).
Ruff already has something that is almost what we want, but my first impression is that it doesn't produce column numbers but byte offsets from line start (which is significant for UTF-8 files), but this shouldn't be hard to tweak.
JukkaL commentedon Feb 2, 2026
Now the prototype
ast_serializeextension is available in this repository: https://github.com/mypyc/ast_serializeThere is also some basic documentation in the README above.
The mypy parser prototype is in the new-parser branch in this repository.
I'll create some issues in the ast_serialize repository about missing functionality and bugs.
Add work-in-progress implementation of a new Python parser (#20856)
ilevkivskyi commentedon Sep 26, 2026
Now that the native parser is default in master, I propose to close this.