Repository navigation
Peephole creates duplicate and unused constants #55671
Description
| BPO | 11462 |
|---|---|
| Nosy | @Yhg1s, @rhettinger, @terryjreedy, @mdickinson, @abalkin, @pitrou, @eltoder |
| Superseder | |
| 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 = 'https://github.com/rhettinger'
closed_at = <Date 2011-03-11.22:26:43.056>
created_at = <Date 2011-03-11.00:55:58.819>
labels = ['interpreter-core', 'performance']
title = 'Peephole creates duplicate and unused constants'
updated_at = <Date 2011-03-19.05:23:26.843>
user = 'https://github.com/eltoder'bugs.python.org fields:
activity = <Date 2011-03-19.05:23:26.843>
actor = 'terry.reedy'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2011-03-11.22:26:43.056>
closer = 'rhettinger'
components = ['Interpreter Core']
creation = <Date 2011-03-11.00:55:58.819>
creator = 'eltoder'
dependencies = []
files = ['21074', '21075', '21076', '21077']
hgrepos = []
issue_num = 11462
keywords = ['patch']
message_count = 24.0
messages = ['130537', '130538', '130539', '130543', '130544', '130562', '130574', '130584', '130585', '130586', '130587', '130588', '130590', '130591', '130592', '130595', '130621', '130631', '130634', '130656', '130659', '130661', '130662', '131391']
nosy_count = 7.0
nosy_names = ['twouters', 'rhettinger', 'terry.reedy', 'mark.dickinson', 'belopolsky', 'pitrou', 'eltoder']
pr_nums = []
priority = 'low'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = '11549'
type = 'performance'
url = 'https://bugs.python.org/issue11462'
versions = ['Python 3.3']
Activity
eltoder commentedon Mar 11, 2011
Peephole optimizer performs constant folding, however
The result is that code object after folding has more constants that it needs and so uses more memory.
Attached are patches to address this. Patch for 1) comes in 2 versions. PlanA is simple (it only needs changes in peephole.c), but does linear searches through co_consts and duplicates some logic from compiler.c. PlanB needs changes in both peephole.c and compiler.c, but is free from such problems. I favour PlanB.
Patch for 2) can be applied on top of either A or B.
eltoder commentedon Mar 11, 2011
(either plana or planb should be applied)
eltoder commentedon Mar 11, 2011
(test case)
rhettinger commentedon Mar 11, 2011
Sorry Eugene, but I'm not willing to add that much complexity to save a few bytes. This was a known issue and long ago we choose to leave it as-is. In the future when constant folding is done at the AST level, we'll get more extensive optimizations and they won't produce duplicate or unused constants as a by-product.
eltoder commentedon Mar 11, 2011
I think the changes are fairly trivial. dedup_const_planb.patch is about 10 lines of new code with all the rest being trivial plubming. unused_consts.patch may look big, but only because I factored out fix ups into a separate function; there are only about 25 lines of new code.
pitrou commentedon Mar 11, 2011
Style nit: you have tabs in your code. Please only use spaces for indentation.
On the principle, looks worthwhile, and the changes don't look really complicated.
eltoder commentedon Mar 11, 2011
Antoine, sure, I'll fix it with any other suggested changes if patches will be accepted.
rhettinger commentedon Mar 11, 2011
I'm disinclined to accept this patch. There is only minor space savings and no actual speed-up.
When constant folding was introduced, a design decision was made to ignore the issue of orphan constants. The rationale behind that decision still stands.
The peepholer has aspired to be very conservative and is considered a high-risk area for changes. Since its introduction, Guido has constantly teetered on the edge of entirely ripping out the peepholer. Right now, the stability of that code is its greatest asset and we should be reluctant to modify it.
Also, the peephole optimizer was developed before the AST branch was added to Python. Constant folding more properly belongs at the AST level, not in the peepholer itself. Our strategy is to move as much as possible into an AST optimizer and to stop building out the peephole optimizer.
Right now, the pattern is tokenize -> parse -> AST -> genbytecode -> peephole optimization (which disassembles the bytecode, analyzed it and rewrites it) -> final bytecode. The correct pattern is tokenize -> parse -> AST -> optimize -> genbytecode -> peephole optimization with minimal disassembly, analysis, and opcode rewrites -> final bytecode.
pitrou commentedon Mar 11, 2011
About dedup_const_planb.patch: _PyCode_AddObj() should be added to Include/code.h, even if it's private (rather than declared extern in peephole.c).
About consts_test.patch: "def mapping" deserves a better name, and perhaps a comment or explanation. Same for "def fix".
About unused_consts.patch:
code like
constuse = (int *)PyMem_Malloc(numconst * sizeof(int));
is better spelt
constuse = PyMem_NEW(int, numconst);
why the "#ifndef NDEBUG" path?
You probably need to regenerate this patch against latest hg, by the way...
Thanks for posting this.
pitrou commentedon Mar 11, 2011
Who is working on this "strategy"?
Until someone takes it to task to implement the "correct pattern", I
think iterative improvement of the peepholer is a reasonable thing.
eltoder commentedon Mar 11, 2011
pitrou commentedon Mar 11, 2011
I think it is confusing indeed. If you want to do a check in debug mode
only, just use assert() (and perhaps add a comment if the check doesn't
look obvious).
eltoder commentedon Mar 11, 2011
assert() doesn't quite work here. I need to check that this entry in the table is not used in the next loop. I'd need to put assert in that loop, but by that time I have no easy way to tell which entries are bad, unless I mark them in the first loop. so I mark them under !NDEBUG.
eltoder commentedon Mar 11, 2011
btw, that you for reviewing the patch.
pitrou commentedon Mar 11, 2011
I guess we don't usually try to optimize that, but you can omit
PyAPI_FUNC indeed.
eltoder commentedon Mar 11, 2011
Actually, optimizing on AST is not ideal too. Ideally you should convert it into a specialized IR, preferably in SSA form and with explicit control flow.
Re size saving: I've ran make test with and without my patch and measured total size of all generated pyc files:
without patch: 16_619_340
with patch: 16_467_867
So it's about 150KB or 1% of the size, not just a few bytes.
Yhg1s commentedon Mar 11, 2011
What is the actual performance impact of this change? As far as I can see the difference is almost entirely in .pyc (on-disk) size, as when loading most of these constants are interned anyway. Even the on-disk change is minimal - and I say that as a person who actually cares a lot about the size of .pyc files. Considering the extra work that needs to be done, I expect planA to be a measurable performance drop, and planB to be indistinguishable. Perhaps I'm wrong, so feel free to prove it so by providing some (unladen-swallow) benchmarks :)
I'm not sure this change is worth it unless there's a clear performance benefit. The peephole optimizer is very limited, fragile, and an uncomfortable place to edit (and I say *that* as a person who has introduced way too many subtle, stupid bugs in the past.) As Raymond says, the right thing to do with the peepholer is to rip it out and replace it with an AST-based optimizer, which wouldn't bypass or duplicate all manner of sanity- and safety-checks. Perhaps this should be a GSoC project.
About the patches themselves: the plan-A patch is a bad idea, I wouldn't consider it; duplicating the compiler checks seems pointless. In the plan-B patch, PyCode_Optimize is an exported symbol so it should not change; you need to change the name and provide the old interface in a macro. The extern declaration of _PyCode_AddObj in peephole.c is now unnecessary. The name of that function is rather non-obvious, since it doesn't do anything with a code object at all -- but I don't have a better suggestion.
rhettinger commentedon Mar 11, 2011
Sorry Eugene. As the person who designed, implemented, and maintains the peephole optimizer, I need to reject the patch.
If better constant folding is wanted, the work needs to be done with AST, not with bytecode. I would welcome a patch.
Thomas, thanks for your input.
eltoder commentedon Mar 11, 2011
Thomas, can you clarify, does loading interns all constants in co_consts, or do you mean that they are mostly small numbers and the like?
Without interning I think that in-memory size difference is even bigger than on-disk, as you get one entry in tuple and the object itself. I'm sure I can cook up a test that will show some perf difference, because of cache misses or paging. You can say that this is not real world code, and you will likely be right. But in real world (before you add inlining and constant propagation) constant folding doesn't make a lot of difference too, yet people asked for it and peepholer does it. Btw, Antoine just improved it quite a bit (bpo-11244), so size difference with my patch should increase.
My rationale for the patch is that 1) it's real very simple 2) it removes feeling of half-done job when you look at the bytecode.
abalkin commentedon Mar 12, 2011
Eugene, how does your optimization differ from the one proposed in bpo-2493?
eltoder commentedon Mar 12, 2011
Alexander, my patch does 2 optimizations: doesn't insert a new constant if one already exist and removes unused constants after peephole is done. You patch seems to do only the latter. It's very similar, from a quick look at your patch:
Feel free to look at the patch and tell me if you don't agree.
rhettinger commentedon Mar 12, 2011
Please cease development of this patch. It has been rejected.
The peephole optimizer should be considered somewhat off-limits at this point and any further development efforts directed at an AST optimizer.
eltoder commentedon Mar 12, 2011
Raymond, you can be assured that I'm not developing this patch, unless I'm told it has chances to be accepted. I don't like to waste my time. On a related note, your review of my other patches is appreciated.
terryjreedy commentedon Mar 19, 2011
Eugene has started work on AST optimizer in bpo-11549