Repository navigation
Make multiple passes of the peephole optimizer until bytecode cannot be optimized further #81452
Description
| BPO | 37271 |
|---|---|
| Nosy | @tim-one, @brettcannon, @rhettinger, @serhiy-storchaka, @pablogsal |
| PRs |
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/tim-one'
closed_at = <Date 2021-07-13.19:51:59.766>
created_at = <Date 2019-06-14.01:58:30.571>
labels = ['interpreter-core', '3.9']
title = 'Make multiple passes of the peephole optimizer until bytecode cannot be optimized further'
updated_at = <Date 2021-07-13.19:51:59.766>
user = 'https://github.com/pablogsal'bugs.python.org fields:
activity = <Date 2021-07-13.19:51:59.766>
actor = 'pablogsal'
assignee = 'tim.peters'
closed = True
closed_date = <Date 2021-07-13.19:51:59.766>
closer = 'pablogsal'
components = ['Interpreter Core']
creation = <Date 2019-06-14.01:58:30.571>
creator = 'pablogsal'
dependencies = []
files = []
hgrepos = []
issue_num = 37271
keywords = ['patch']
message_count = 9.0
messages = ['345543', '345638', '345701', '345705', '345706', '345707', '345710', '345713', '345715']
nosy_count = 5.0
nosy_names = ['tim.peters', 'brett.cannon', 'rhettinger', 'serhiy.storchaka', 'pablogsal']
pr_nums = ['14068']
priority = 'normal'
resolution = 'out of date'
stage = 'resolved'
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue37271'
versions = ['Python 3.9']
Activity
pablogsal commentedon Jun 14, 2019
The peephole optimizer currently does not optimize the result of its own optimization when its possible. For example, consider the following code:
The bytecode for this is:
2 0 LOAD_GLOBAL 0 (a)
2 POP_JUMP_IF_FALSE 32
4 4 LOAD_GLOBAL 1 (b)
6 POP_JUMP_IF_FALSE 24
5 8 LOAD_GLOBAL 2 (c)
10 POP_JUMP_IF_TRUE 16
6 12 LOAD_GLOBAL 3 (d)
14 POP_JUMP_IF_FALSE 30
7 >> 16 LOAD_GLOBAL 4 (foo)
18 CALL_FUNCTION 0
20 POP_TOP
22 JUMP_ABSOLUTE 38
9 >> 24 LOAD_GLOBAL 5 (bar)
26 CALL_FUNCTION 0
28 POP_TOP
>> 30 JUMP_FORWARD 6 (to 38)
11 >> 32 LOAD_GLOBAL 6 (baz)
34 CALL_FUNCTION 0
36 POP_TOP
>> 38 LOAD_CONST 0 (None)
40 RETURN_VALUE
Notice that the 14 POP_JUMP_IF_FALSE 30 jumps to another jump (30 JUMP_FORWARD 6 (to 38)). If we repeat the optimizations until the resulting bytecode does not change more we get:
2 0 LOAD_GLOBAL 0 (a)
2 POP_JUMP_IF_FALSE 32
4 4 LOAD_GLOBAL 1 (b)
6 POP_JUMP_IF_FALSE 24
5 8 LOAD_GLOBAL 2 (c)
10 POP_JUMP_IF_TRUE 16
6 12 LOAD_GLOBAL 3 (d)
5 14 POP_JUMP_IF_FALSE 38
7 >> 16 LOAD_GLOBAL 4 (foo)
18 CALL_FUNCTION 0
20 POP_TOP
22 JUMP_ABSOLUTE 38
9 >> 24 LOAD_GLOBAL 5 (bar)
26 CALL_FUNCTION 0
28 POP_TOP
30 JUMP_FORWARD 6 (to 38)
11 >> 32 LOAD_GLOBAL 6 (baz)
34 CALL_FUNCTION 0
36 POP_TOP
>> 38 LOAD_CONST
Notice that in this example the original instruction now is (14 POP_JUMP_IF_FALSE 38).
rhettinger commentedon Jun 14, 2019
FWIW, when the peephole optimizer was originally accepted, it was partly on the condition that we kept it simple and fast. Perhaps, the sentiment has changed, perhaps not.
serhiy-storchaka commentedon Jun 15, 2019
We should handle this with care and prove that the optimization loop is finite.
pablogsal commentedon Jun 15, 2019
We can add a #define for a maximum numbers of iterations. The pyperformance test suite shows speed ups of 2-3% without PGO/LTO. I will ran more concise experiments including PGO but even with a max cap of iterations (10 in my experiments) we get nice improvements without much more complexity.
pablogsal commentedon Jun 15, 2019
Probably is not that easy, but a naive thought respecting loops:
As the peephole optimizer only produces code that is the same length or smaller and it works by feeling noops and deleting them, the only loop would be code that is of the same length but different, but that cannot happen by adding noops and removing them, right?
rhettinger commentedon Jun 15, 2019
Tim, do you have any thoughts on this?
In the past, there was an implicit red-line that we would not cross even if a performance improvement was possible. Given that that was a long time ago and that the newer devs are both more aggressive and more fearless, we ought to re-examine whether the red-line should be made explicit or whether it no longer applies.
For this particular patch, a source of discomfort is that the optimization step takes longer (due to multiple passes). So, we sometimes get faster wordcode but that time it takes to get there is longer.
pablogsal commentedon Jun 15, 2019
Is worth noting that the (very small) overhead to obtain the wordcode happens once but the benefits of the resulting opcode will be felt every time you execute it.
rhettinger commentedon Jun 15, 2019
I'm familiar with the trade-offs (I'm the original designer of this code), but it is possible to use that reasoning to talk yourself into thinking that any optimization to code generation is worth it.
The speed of the compile does matter as well (think about uses of exec() in dataclasses for example). Also, the level of complexity matters as well. The last time we introduced recursive passes for part of the peepholer (in constant folding), it took years to get it fully debugged and it caused a number of bug reports with respect to total compilation time.
FWIW, Guido was never sold on the merits of having a peephole optimizer and the tool spent much of its life on the verge of being ripped-out. To accommodate his wishes and our design instincts, we agreed at the outset to keep this "dirt simple". (Put another way, for over a decade every developer who looked at this resisted going down this obvious line of development).
That said, I'll leave it to Tim to decide. He helped talked Guido into letting me add this and he is the one who first proposed setting tight limits on how far we would go.
(One last thought, be sure to coordinate with Serhiy who is actively transferring responsibilities upstream to the AST level manipulations so they can be analyzed at a higher level.)
serhiy-storchaka commentedon Jun 15, 2019
I afraid that the time of the peephole optimization is nothing in comparison with the cost of deduplicating constants in compile.c.