Second pass of PyCode_Optimize

[llllllllll]

BPO	24014
Nosy	@brettcannon, @rhettinger, @tiran, @ericsnowcurrently, @1st1, @llllllllll
Files	secondpass.patch

^{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 2015-04-20.16:44:29.297>
created_at = <Date 2015-04-20.09:09:20.060>
labels = ['interpreter-core', 'performance']
title = 'Second pass of PyCode_Optimize'
updated_at = <Date 2015-04-20.16:44:29.295>
user = 'https://github.com/llllllllll'

bugs.python.org fields:

activity = <Date 2015-04-20.16:44:29.295>
actor = 'llllllllll'
assignee = 'none'
closed = True
closed_date = <Date 2015-04-20.16:44:29.297>
closer = 'llllllllll'
components = ['Interpreter Core']
creation = <Date 2015-04-20.09:09:20.060>
creator = 'llllllllll'
dependencies = []
files = ['39144']
hgrepos = []
issue_num = 24014
keywords = ['patch']
message_count = 9.0
messages = ['241626', '241641', '241647', '241652', '241654', '241659', '241660', '241662', '241669']
nosy_count = 6.0
nosy_names = ['brett.cannon', 'rhettinger', 'christian.heimes', 'eric.snow', 'yselivanov', 'llllllllll']
pr_nums = []
priority = 'normal'
resolution = None
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue24014'
versions = ['Python 3.5']

[llllllllll]

There are a lot of optimizations that are being missed by only running a single pass of PyCode_Optimize. I originally started by trying to optimize for De Morgan's Laws in if tests; however, I realized that the issue actually went away if you run the optimizer twice. I imagine that this would provide a lot of other performance increases because some of the patterns don't show up until the optimizer has already run once. For example:

>>> def f(a, b):
...     if not a and not b:
...         return True
...     return False
... 

On default, this generates:
>>> dis(f)
  2           0 LOAD_FAST                0 (a)
              3 UNARY_NOT
              4 POP_JUMP_IF_FALSE       18
              7 LOAD_FAST                1 (b)
             10 UNARY_NOT
             11 POP_JUMP_IF_FALSE       18

3 14 LOAD_CONST 1 (True)
17 RETURN_VALUE

4 >> 18 LOAD_CONST 2 (False)
21 RETURN_VALUE

If we run the optimizer again, we can collapse some of the UNARY_NOT -> POP_JUMP_IF_FALSE back into POP_JUMP_IF_TRUE, like this:
>>> dis(f)
  2           0 LOAD_FAST                0 (a)
              3 POP_JUMP_IF_TRUE        16
              6 LOAD_FAST                1 (b)
              9 POP_JUMP_IF_TRUE        16

3 12 LOAD_CONST 1 (True)
15 RETURN_VALUE

4 >> 16 LOAD_CONST 2 (False)
19 RETURN_VALUE

Also, Python/importlib.h blew up in the diff; should this be included in the patch?

[ericsnowcurrently]

Also, Python/importlib.h blew up in the diff; should this be included in
the patch?

Yes. It is the frozen bytecode for bootstrapping importlib as the import
system. So changes to bytecode generation like this will propagate there.

[1st1]

Is there any noticeable performance increase with the patch?

Please attach results from https://hg.python.org/benchmarks

[rhettinger]

I would like to keep the time spent in the optimizer itself to a minimum. Also, it should keep focused on patterns that actually occur in code as opposed to contrived bits of code. Tim and Guido let us put it the optimizer only on the condition that it be kept simple and with low overhead. The work that has been needed for a long time was to move a number of the optimizations (such as constant folding) out of the peepholer optimizer and replace them with AST manipulations just upstream from code generation (to reduce the need for the peepholer to partially disassemble and re-interpret the bytecode).

[tiran]

How about restricting double pass optimization to code objects that have the CO_OPTIMIZED bit set? It doesn't affect normal code execution.

[brettcannon]

Just FYI, http://bugs.python.org/issue11549 can act as a tracking issue for an AST optimization path that runs prior to the peepholer.

[llllllllll]

I am actually getting inconsistent results from running benchmark; I am pretty surprised by this. I could look into making the second pass only happen if the code has the CO_OPTIMIZED bit set; however, based on the results I am seeing from the benchmark runs, I am not sure it is worth it. Does the benchmark tool recompile the code every run?

[1st1]

Does the benchmark tool recompile the code every run?

Make sure you've bumped magic number in importlib/bootstrap; then make clean; make

[llllllllll]

I tried bumping the magic number; however, I still cannot get consistent results when running benchmark locally. I guess I will close this as I cannot consistently show an improvement.