Repository navigation
Build-out an AST optimizer, moving some functionality out of the peephole optimizer #55758
Description
| BPO | 11549 |
|---|---|
| Nosy | @birkenfeld, @rhettinger, @terryjreedy, @mdickinson, @ncoghlan, @pitrou, @vstinner, @benjaminp, @Trundle, @methane, @davidmalcolm, @meadori, @durban, @jeremyhylton, @eltoder, @ericsnowcurrently, @berkerpeksag, @serhiy-storchaka, @phmc, @pstch, @mbdevpl |
| Dependencies | |
| Files |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
assignee = None
closed_at = <Date 2020-01-26.06:07:31.706>
created_at = <Date 2011-03-15.04:46:42.255>
labels = ['interpreter-core', '3.7']
title = 'Build-out an AST optimizer, moving some functionality out of the peephole optimizer'
updated_at = <Date 2020-01-26.06:07:31.705>
user = 'https://github.com/eltoder'bugs.python.org fields:
activity = <Date 2020-01-26.06:07:31.705>
actor = 'rhettinger'
assignee = 'none'
closed = True
closed_date = <Date 2020-01-26.06:07:31.706>
closer = 'rhettinger'
components = ['Interpreter Core']
creation = <Date 2011-03-15.04:46:42.255>
creator = 'eltoder'
dependencies = ['11682']
files = ['21198', '21199', '21200', '21201', '21202', '42810', '46467', '46542']
hgrepos = []
issue_num = 11549
keywords = ['patch']
message_count = 81.0
messages = ['130955', '131070', '131071', '131072', '131074', '131083', '131084', '131085', '131166', '131172', '131210', '131214', '131392', '131396', '131952', '131953', '132310', '132312', '132313', '132314', '132346', '132348', '132349', '132350', '132361', '132362', '132382', '132453', '132455', '132473', '132476', '137785', '137788', '137819', '137906', '138413', '139395', '160608', '160662', '168146', '169894', '169895', '169896', '169897', '169898', '169899', '169900', '169902', '169903', '185286', '193656', '193657', '265296', '265553', '265554', '265607', '265613', '265621', '286503', '286528', '286530', '286531', '286532', '286534', '286535', '286539', '286542', '286588', '286589', '286591', '286592', '286668', '286697', '286725', '286726', '286730', '287120', '287121', '287187', '287217', '360721']
nosy_count = 26.0
nosy_names = ['georg.brandl', 'rhettinger', 'terry.reedy', 'mark.dickinson', 'ncoghlan', 'pitrou', 'vstinner', 'techtonik', 'nadeem.vawda', 'benjamin.peterson', 'Trundle', 'methane', 'dmalcolm', 'meador.inge', 'daniel.urban', 'Jeremy.Hylton', 'santoso.wijaya', 'eltoder', 'eric.snow', 'jcon', 'berker.peksag', 'serhiy.storchaka', 'pconnell', 'isoschiz', 'pstch', 'mbdevpl']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue11549'
versions = ['Python 3.7']
Activity
eltoder commentedon Mar 15, 2011
As pointed out by Raymond, constant folding should be done on AST rather than on generated bytecode. Here's a patch to do that. It's rather long, so overview first.
The patch replaces existing peephole pass with a folding pass on AST and a few changes in compiler. Feature-wise it should be on par with old peepholer, applying optimizations more consistently and thoroughly, but maybe missing some others. It passes all peepholer tests (though they seem not very extensive) and 'make test', but more testing is, of course, needed.
I've split it in 5 pieces for easier reviewing, but these are not 5 separate patches, they should all be applied together. I can upload it somewhere for review or split it in other ways, let me know. Also, patches are versus 1e00b161f5f5, I will redo against head.
TOC:
In detail:
a) Merge Num, Str, Bytes and Ellipsis constructors into a single Lit (literal) that can hold anything. For one thing, this removes a good deal of copy-paste in the code, since these are always treated the same. (There were a couple of places where Bytes ctor was missing for no apparent reason, I think it was forgotten.) Otherwise, I would have to introduce at least 4 more node types: None, Bool, TupleConst, SetConst. This seemed excessive.
b) Docstring is now an attribute of Module, FunctionDef and ClassDef, rather than a first statement. Docstring is a special syntactic construction, it's not an executable code, so it makes sense to separate it. Otherwise, optimizer would have to take extra care not to introduce, change or remove docstring. For example:
Without optimizations foo doesn't have a docstring. After folding, however, the first statement in foo is a string literal. This means that docstring depends on the level of optimizations. Making it an attribute avoids the problem.
c) 'None', 'True' and 'False' are parsed as literals instead of names, even without optimizations. Since they are not redefineable, I think it makes most sense to treat them as literals. This isn't strictly needed for folding, and I haven't removed all the artefacts, in case this turns out controversial.
Constant folding (and a couple of other tweaks) is performed by a visitor. The visitor is auto-generated from ASDL and a C template. C template (Python/ast_opt.ct) provides code for optimizations and rules on how to call it. Parser/asdl_ct.py takes this and ASDL and generates a visitor, that visits only nodes which have associated rules (but visits them via all paths).
The code for optimizations itself is pretty straight-forward.
The generator can probably be used for symtable.c too, removing ~200 tedious lines of code.
Changes to compiler are in 3 categories
a) Updates for AST changes.
b) Changes to generate better code and not need any optimizations. This includes tuple unpacking optimization and if/while conditions.
c) Simple peephole pass on compiler internal structures. This is a better form for doing this, than a bytecode. The pass only deals with jumps to jumps/returns and trivial dead code.
I've also made 'raise' recognized as a terminator, so that 'return None' is not inserted after it.
4, 5. No big surprises here.
smontanaro commentedon Mar 15, 2011
I'm confused. Why aren't there review links?
eltoder commentedon Mar 15, 2011
Because I don't know how to make them. Any pointers?
pitrou commentedon Mar 15, 2011
Martin is hacking on the tool these days... So it's no surprise it
doesn't work perfectly yet ;)
If you have a Google account you can upload these patches to
http://codereview.appspot.com/, though.
eltoder commentedon Mar 16, 2011
Thanks. Review link: http://codereview.appspot.com/4281051
ncoghlan commentedon Mar 16, 2011
The review links didn't come up automatically because 336137a359ae isn't a hg.python.org/cpython revision ID.
eltoder commentedon Mar 16, 2011
I see. Should I attach diffs vs. some revision from hg.python.org?
ncoghlan commentedon Mar 16, 2011
No need, since you manually created a review on appspot. The local Reitveld links are just a convenience that can avoid the need to manually create a review instance.
eltoder commentedon Mar 16, 2011
Any comments on the code so far or suggestions on how we should move forward?
ncoghlan commentedon Mar 16, 2011
I've been focusing on softer targets during the sprints - I'll dig into this once I'm back home and using my desktop machine again.
eltoder commentedon Mar 17, 2011
I've updated patches on Rietveld with some small changes. This includes better code generation for boolops used outside of conditions and cleaned up optimize_jumps(). This is probably the last change before I get some feedback.
Also, I forgot to mention yesterday, patches on Rietveld are vs. ab45c4d0b6ef
eltoder commentedon Mar 17, 2011
Just for fun I've run pystones. W/o my changes it averages to about 70k, with my changes to about 72.5k.
terryjreedy commentedon Mar 19, 2011
A couple of somewhat related issues:
bpo-10399 AST Optimization: inlining of function calls
bpo-1346238 A constant folding optimization pass for the AST
Obviously, ast optimizers should work together and not duplicate.
Nice to see increased attention.
eltoder commentedon Mar 19, 2011
AFAICT my patch has everything that bpo-1346238 has, except BoolOps, which can be easily added (there's a TODO). I don't want to add any new code, though, until the current patch will get reviewed -- adding code will only make reviewing harder.
bpo-10399 looks interesting, I will take a look.
56 remaining items
methane commentedon Feb 1, 2017
Then, may I remove ast.Lit, and use Constant and NameConstant?
I think backward compatibility is not guaranteed.
But there are some usage of ast. (https://github.com/search?l=Python&p=2&q=ast.Num&type=Code&utf8=%E2%9C%93 )
So I think we should make change small as possible.
OK.
I know. I want to move this patch forward, but I'm not frontend (parser, AST, and compiler) expert.
I can't make design decision without expert's advice. Thanks for your reply.
Then, may I update the patch in following direction?
vstinner commentedon Feb 1, 2017
If you would like to implement constant folding at the AST level, I suggest
you to look at my fatoptimizer project:
https://github.com/haypo/fatoptimizer/blob/master/fatoptimizer/const_fold.py
The tricky part is to avoid operations when we know that it will raise an
exception or create an object too big according to our constraints.
I would prefer to implement an AST optimizer in Python, but converting C
structures to Python objects and then back to C structures has a cost. I'm
not sure that my optimizer implemented in Python is fast enough.
By the way, an idea would be to skip all optimizations in some cases like
for script.py when running python3 script.py.
methane commentedon Feb 1, 2017
Before trying advanced optimizations, I want move suspended obvious optimizations forwards.
For example, removing unused constants is suspended because constant folding
should be moved from peephole to AST. This is why I found this issue.
After that, I'm thinking about shrinking stacksize. frame_dealloc (scans whole stack) is one of hot functions.
brettcannon commentedon Feb 1, 2017
Dropping ast.Lit is fine. As for the docstring part, I'm torn. Yes it's nice as that will show up semantically in the Python code, but it's also easy to check for by just looking if the first statement is a Str (or Constant if that's what we make all strings). So I'll say I'm +0 on the docstring part.
vstinner commentedon Feb 1, 2017
At the AST level, you have a wide range of possible optimizations. See the optimizations that I implemented in fatoptimizer (FAT Python) to have an idea:
http://fatoptimizer.readthedocs.io/en/latest/optimizations.html
FAT Python adds guards checked at runtime, something not possible (not wanted) here.
But if you start with constant folding, why not implementing constant propagation as well? What about loop unrolling?
Where is the limit? If you implement the AST optimizer in C, the limit will probably be your C skills and your motivation :-) In Python, the limit is more the Python semantics which is... hum... not well defined. For example, does it break the Python semantics to replace [i for i in (1, 2, 3)] with [1, 2, 3]?
What if you use a debugger? Do yo expect a list comprehension or a literal list?
FYI I suspended my work on FAT Python because almost no other core developer was interested. I didn't get any support, whereas I need support to push core FAT Python features like function specialization and runtime checks (PEP-510, see also PEP-511). Moreover, I failed to show any significant speedup on non-trivial functions. I abandoned before investigating function inlining, even if FAT Python already has a basic support for function inlining.
This issue is open since 2011. The question is always the same: is it worth it?
An alternative is to experiment an AST optimizer outside CPython and come back later with more data to drive the design of such optimizer. With FAT Python, I chose to add hooks in the Python compiler, but different people told me that it's possible to do that without such hook but importlib (importlib hooks).
What do you think Naoki?
eltoder commentedon Feb 2, 2017
Yes, doing optimizations on AST in CPython is unlikely to give any sizable speed improvements in real world programs. Python as a language is not suited for static optimization, and even if you manage to inline a function, there's still CPython's interpreted overhead and boxed types that dwarf the effect of the optimization.
The goal of this patch was never to significantly improve the speed. It was to replace the existing bytecode peephole pass with cleaner and simpler code, which also happens to produce slightly better results.
methane commentedon Feb 2, 2017
My motivation is improve speed, reduce memory usage, and quicker
startup time for real world applications. If some optimization in
FAT optimizer has significant speedup, I want to try it.
But this time, my motivation is I felt "everyone think constant folding
should go to AST from peephole, there is a patch about it, but unfortunately
it was suspended (because of lack of reviewers, maybe)."
As reading bpo-28813, I think there are consensus about constant folding
should go AST.
vstinner commentedon Feb 2, 2017
INADA Naoki added the comment:
Ah, if the motivation is performance, I would like to see benchmark
results :-) I understand that an AST optimizer would help to produce
more efficient bytecode, right?
I noticed an issue with the peephole optimizer: the constant folding
step keeps original constants. Moving constant folding to the AST
stage fixes this issue by design.
You mean faster import time on precompiled .pyc files, right? It's
related to the hypothetical faster bytecode.
See http://fatoptimizer.readthedocs.io/en/latest/microbenchmarks.html#microbench
FYI it took me something like 2 months to build FAT Python
"infrastructure": fix CPython bugs, design guards, design the AST
optimizer, write unit tests, etc. I didn't spend much time on
efficient optimizations. But for my first rule was to not break the
CPython test suite! Not break the Python semantics, otherwise it would
be impossible to put enable the optimizer by default in CPython, which
is my long term goal.
methane commentedon Feb 6, 2017
I've tried to update ast_opt.c[t] without changing AST.
But I can't find clear way to solve "foo" + "bar" docstring problem.
This patch adds only docstring to AST.
vstinner commentedon Feb 6, 2017
Naoki: Can you please open a new issue for your ast-docstring.patch change? I like it, but this issue became too big, and I'm not sure that everyone in the nosy list is interested by this specific change.
methane commentedon Feb 7, 2017
I submit new issues:
Note that this issue contains more peephole -> AST optimization changes.
But I want to start these two patch to ease review and discussion.
vstinner commentedon Feb 7, 2017
I created the issue bpo-29471: "AST: add an attribute to FunctionDef to distinguish functions from generators and coroutines".
rhettinger commentedon Jan 26, 2020
I think this particular issue can be closed in now. After it was written, the AST optimizer has been built-out and some peephole logic has moved.
Other adjustments and improvements can be continue to be done in the other open issues.