Any thoughts about a control flow optimizer for CPython?
Hey all, From my CS theory, a control flow graph models a program flow and one of its main characteristics is it has one entry and exit point. IIRC, CPython’s compilation process involves generation of a control flow graph. Contrary to peephole optimizations, optimizations on the control flow graph are more global allowing us to have complex and global optimizations like branch and checkpoint eliminations etc. I have seen several implementations of control flow optimizations. The one I am familiar with is the V8 control flow optimizer. I tried to investigate this for one of my directed courses last fall but I want to know if there are people who have been thinking about this for CPython and what their thoughts are. -- Best, Joannah Nanjekye *"You think you know when you learn, are more sure when you can write, even more when you can teach, but certain when you can program." Alan J. Perlis*
Hi Joannah, On 03/04/2020 4:13 pm, joannah nanjekye wrote:
Hey all,
From my CS theory, a control flow graph models a program flow and one of its main characteristics is it has one entry and exit point. IIRC,
CPython's CFG has multiple exit points, but that shouldn't matter.
CPython’s compilation process involves generation of a control flow graph. I started playing with moving the CFG optimizations from the peepholer to their own pass back at the core sprints in London. I've worked on it a bit since, but not for a while. My branch is here: https://github.com/python/cpython/compare/master...markshannon:cfg-optimizer
One thing that is blocking progress is the line-number table format. There is no way to say that an instruction does not have a line number attached to it. That makes handling and transforming of compiler generated code (implicit `return None`s, for example) harder. See https://bugs.python.org/issue39537 It's not an insurmountable obstacle, but it is something to be aware of.
Contrary to peephole optimizations, optimizations on the control flow graph are more global allowing us to have complex and global optimizations like branch and checkpoint eliminations etc.
Checkpoints for tracing or concurrent GC are not something we need to worry about. Because Python is so dynamic, there is little we can do in the way of further optimizations in the bytecode compiler apart from control flow improvements. However, Python does have some fairly complex control flow, so there is room for improvement.
I have seen several implementations of control flow optimizations. The one I am familiar with is the V8 control flow optimizer.
I'm not familiar with it. Is there a summary online?
I tried to investigate this for one of my directed courses last fall but I want to know if there are people who have been thinking about this for CPython and what their thoughts are.
There won't be much of a speed up, maybe 2 or 3%, but adding an explicit CFG optimisation pass will improve maintainability as we won't need to regenerate the CFG after bytecode layout. I'd be happy to offer advice and review any PRs. Cheers, Mark.
-- //Best, Joannah Nanjekye /"You think you know when you learn, are more sure when you can write, even more when you can teach, but certain when you can program." Alan J. Perlis/
_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/I376QAAW... Code of Conduct: http://python.org/psf/codeofconduct/
I'm not familiar with it. Is there a summary online?
I followed mostly the implementation here : https://github.com/v8/v8/tree/4b9b23521e6fd42373ebbcb20ebe03bf445494f9/src/c...
started playing with moving the CFG optimizations from the peepholer
My doubts have been on whether it was too radical to completely replace the peephole optimizer with this CFG optimization pass. If replacing the peephole optimizer is not a problem, how are we going to ensure compatibility for the related peephole optimizer C-API? Just have a stub?
I'd be happy to offer advice and review any PRs.
My schedule may lighten this summer so I will try to look more but I wanted to know if we think its worth investigating first. If anyone wanted to make contributions to this, is such an implementation trivial enough to be just a PR? I guess what am trying to say; I hope if I one tried to open a PR, he/she wont be told, first write a PEP. Best, Joannah On Fri, Apr 3, 2020 at 1:15 PM Mark Shannon <mark@hotpy.org> wrote:
Hi Joannah,
On 03/04/2020 4:13 pm, joannah nanjekye wrote:
Hey all,
From my CS theory, a control flow graph models a program flow and one of its main characteristics is it has one entry and exit point. IIRC,
CPython's CFG has multiple exit points, but that shouldn't matter.
CPython’s compilation process involves generation of a control flow graph. I started playing with moving the CFG optimizations from the peepholer to their own pass back at the core sprints in London. I've worked on it a bit since, but not for a while. My branch is here:
https://github.com/python/cpython/compare/master...markshannon:cfg-optimizer
One thing that is blocking progress is the line-number table format. There is no way to say that an instruction does not have a line number attached to it. That makes handling and transforming of compiler generated code (implicit `return None`s, for example) harder.
See https://bugs.python.org/issue39537 It's not an insurmountable obstacle, but it is something to be aware of.
Contrary to peephole optimizations, optimizations on the control flow graph are more global allowing us to have complex and global optimizations like branch and checkpoint eliminations etc.
Checkpoints for tracing or concurrent GC are not something we need to worry about.
Because Python is so dynamic, there is little we can do in the way of further optimizations in the bytecode compiler apart from control flow improvements. However, Python does have some fairly complex control flow, so there is room for improvement.
I have seen several implementations of control flow optimizations. The one I am familiar with is the V8 control flow optimizer.
I'm not familiar with it. Is there a summary online?
I tried to investigate this for one of my directed courses last fall but I want to know if there are people who have been thinking about this for CPython and what their thoughts are.
There won't be much of a speed up, maybe 2 or 3%, but adding an explicit CFG optimisation pass will improve maintainability as we won't need to regenerate the CFG after bytecode layout.
I'd be happy to offer advice and review any PRs.
Cheers, Mark.
-- //Best, Joannah Nanjekye /"You think you know when you learn, are more sure when you can write, even more when you can teach, but certain when you can program." Alan J. Perlis/
_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at
https://mail.python.org/archives/list/python-dev@python.org/message/I376QAAW...
Code of Conduct: http://python.org/psf/codeofconduct/
-- Best, Joannah Nanjekye *"You think you know when you learn, are more sure when you can write, even more when you can teach, but certain when you can program." Alan J. Perlis*
03.04.20 18:13, joannah nanjekye пише:
From my CS theory, a control flow graph models a program flow and one of its main characteristics is it has one entry and exit point. IIRC, CPython’s compilation process involves generation of a control flow graph.
Contrary to peephole optimizations, optimizations on the control flow graph are more global allowing us to have complex and global optimizations like branch and checkpoint eliminations etc.
I have seen several implementations of control flow optimizations. The one I am familiar with is the V8 control flow optimizer.
I tried to investigate this for one of my directed courses last fall but I want to know if there are people who have been thinking about this for CPython and what their thoughts are.
I implemented the CFG optimizer, but the problem was that it removed bytecode which served a marker for the lineno setter in the frame object. The lineno setter checked if it valid to jump to the specified instruction by counting instructions specific to some sybtax constructions. And if you have unconditional break, continue or return in the with or try block, the code for normal leaving the block was removed, and the lineno setter was not able to determine when we jump in or out of the block. Until we radically change the algorithm of the lineno setter it is hard to implement a true CFG optimizer. The peepholer contains special exceptions for such codes, but the CFG optimizer is more aggressive.
On 4/3/20 11:13 AM, joannah nanjekye wrote:
Hey all, From my CS theory, a control flow graph models a program flow and one of its main characteristics is it has one entry and exit point. IIRC, CPython’s compilation process involves generation of a control flow graph.
Contrary to peephole optimizations, optimizations on the control flow graph are more global allowing us to have complex and global optimizations like branch and checkpoint eliminations etc.
I have seen several implementations of control flow optimizations. The one I am familiar with is the V8 control flow optimizer.
I tried to investigate this for one of my directed courses last fall but I want to know if there are people who have been thinking about this for CPython and what their thoughts are.
Please make it possible to disable any optimizations. Sometimes programs are run to understand the program, not for speed (for example, during debugging, or coverage measurement.) --Ned.
-- //Best, Joannah Nanjekye /"You think you know when you learn, are more sure when you can write, even more when you can teach, but certain when you can program." Alan J. Perlis/
_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/I376QAAW... Code of Conduct: http://python.org/psf/codeofconduct/
Hi, On 05/04/2020 12:47 pm, Ned Batchelder wrote:
On 4/3/20 11:13 AM, joannah nanjekye wrote:
Hey all, From my CS theory, a control flow graph models a program flow and one of its main characteristics is it has one entry and exit point. IIRC, CPython’s compilation process involves generation of a control flow graph.
Contrary to peephole optimizations, optimizations on the control flow graph are more global allowing us to have complex and global optimizations like branch and checkpoint eliminations etc.
I have seen several implementations of control flow optimizations. The one I am familiar with is the V8 control flow optimizer.
I tried to investigate this for one of my directed courses last fall but I want to know if there are people who have been thinking about this for CPython and what their thoughts are.
Please make it possible to disable any optimizations. Sometimes programs are run to understand the program, not for speed (for example, during debugging, or coverage measurement.)
I have to disagree. The behavior of a program should not depend on whether a flag is set or not. It makes debugging harder, IMO, if the behavior changes depending on some flag. For example, `pass` statements should never be executed. This is an "optimization", but it is easier to understand if `pass` is never executed. It becomes confusing it "executes" some of the time, depending on some compiler flag. IMO, a coverage tool should be not rely on `pass`, `while True:` and other similarly trivial statements existing in the bytecode. By "trivial statements", I mean any unconditional control flow statements, conditional control flow statements with a constant test, "pass", and any expression statements that are constant and without side effect. E.g. the following statements are "trivial": try: while False: pass 1 + 1 On the other hand, other more powerful optimization should always preserve the observable behavior of the program. Since the observable behavior is unchanged, there would be no need to turn them off. Cheers, Mark.
--Ned.
-- //Best, Joannah Nanjekye /"You think you know when you learn, are more sure when you can write, even more when you can teach, but certain when you can program." Alan J. Perlis/
_______________________________________________ Python-Dev mailing list --python-dev@python.org To unsubscribe send an email topython-dev-leave@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived athttps://mail.python.org/archives/list/python-dev@python.org/message/I376QAAW... Code of Conduct:http://python.org/psf/codeofconduct/
_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-leave@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/UGEVQQWB... Code of Conduct: http://python.org/psf/codeofconduct/
On 4/6/20 5:41 AM, Mark Shannon wrote:
Hi,
On 05/04/2020 12:47 pm, Ned Batchelder wrote:
On 4/3/20 11:13 AM, joannah nanjekye wrote:
Hey all, From my CS theory, a control flow graph models a program flow and one of its main characteristics is it has one entry and exit point. IIRC, CPython’s compilation process involves generation of a control flow graph.
Contrary to peephole optimizations, optimizations on the control flow graph are more global allowing us to have complex and global optimizations like branch and checkpoint eliminations etc.
I have seen several implementations of control flow optimizations. The one I am familiar with is the V8 control flow optimizer.
I tried to investigate this for one of my directed courses last fall but I want to know if there are people who have been thinking about this for CPython and what their thoughts are.
Please make it possible to disable any optimizations. Sometimes programs are run to understand the program, not for speed (for example, during debugging, or coverage measurement.)
I have to disagree. The behavior of a program should not depend on whether a flag is set or not. It makes debugging harder, IMO, if the behavior changes depending on some flag. I agree. But perhaps we need to be clearer what we mean by behavior. I don't think an optimizer should change the behavior of a program, that is, the results it produces. If an optimizer meets that criterion, then enabling or disabling it doesn't affect the behavior of the program.
For example, `pass` statements should never be executed. This is an "optimization", but it is easier to understand if `pass` is never executed. It becomes confusing it "executes" some of the time, depending on some compiler flag.
IMO, a coverage tool should be not rely on `pass`, `while True:` and other similarly trivial statements existing in the bytecode. By "trivial statements", I mean any unconditional control flow statements, conditional control flow statements with a constant test, "pass", and any expression statements that are constant and without side effect.
The results of a coverage tool depend very much on exactly which lines get executed. If an optimizer decides it can skip a certain line, then the coverage results will show that line as unexecuted. This alarms users, and causes bug reports. See https://bugs.python.org/issue2506 for an example that has caused me headaches since 2008. When you work in C, do you ever use the -O0 flag to disable optimizations? If so, why do you use it? Why does Python not have the same problems, and why does it not deserve a similar solution?
E.g. the following statements are "trivial": try: while False: pass 1 + 1
On the other hand, other more powerful optimization should always preserve the observable behavior of the program. Since the observable behavior is unchanged, there would be no need to turn them off.
My point is that coverage measurement is a different kind of observation. Please don't overlook developers' needs in this regard. --Ned
Cheers, Mark.
BTW, so that we don't have to completely retrace our steps, this topic was also discussed in depth on Python-Ideas in May 2014: https://mail.python.org/archives/list/python-ideas@python.org/thread/X6VCB2E... --Ned. On 4/6/20 6:56 AM, Ned Batchelder wrote:
Hi,
On 05/04/2020 12:47 pm, Ned Batchelder wrote:
On 4/3/20 11:13 AM, joannah nanjekye wrote:
Hey all, From my CS theory, a control flow graph models a program flow and one of its main characteristics is it has one entry and exit point. IIRC, CPython’s compilation process involves generation of a control flow graph.
Contrary to peephole optimizations, optimizations on the control flow graph are more global allowing us to have complex and global optimizations like branch and checkpoint eliminations etc.
I have seen several implementations of control flow optimizations. The one I am familiar with is the V8 control flow optimizer.
I tried to investigate this for one of my directed courses last fall but I want to know if there are people who have been thinking about this for CPython and what their thoughts are.
Please make it possible to disable any optimizations. Sometimes programs are run to understand the program, not for speed (for example, during debugging, or coverage measurement.)
I have to disagree. The behavior of a program should not depend on whether a flag is set or not. It makes debugging harder, IMO, if the behavior changes depending on some flag. I agree. But perhaps we need to be clearer what we mean by behavior. I don't think an optimizer should change the behavior of a program,
On 4/6/20 5:41 AM, Mark Shannon wrote: that is, the results it produces. If an optimizer meets that criterion, then enabling or disabling it doesn't affect the behavior of the program.
For example, `pass` statements should never be executed. This is an "optimization", but it is easier to understand if `pass` is never executed. It becomes confusing it "executes" some of the time, depending on some compiler flag.
IMO, a coverage tool should be not rely on `pass`, `while True:` and other similarly trivial statements existing in the bytecode. By "trivial statements", I mean any unconditional control flow statements, conditional control flow statements with a constant test, "pass", and any expression statements that are constant and without side effect.
The results of a coverage tool depend very much on exactly which lines get executed. If an optimizer decides it can skip a certain line, then the coverage results will show that line as unexecuted. This alarms users, and causes bug reports. See https://bugs.python.org/issue2506 for an example that has caused me headaches since 2008.
When you work in C, do you ever use the -O0 flag to disable optimizations? If so, why do you use it? Why does Python not have the same problems, and why does it not deserve a similar solution?
E.g. the following statements are "trivial": try: while False: pass 1 + 1
On the other hand, other more powerful optimization should always preserve the observable behavior of the program. Since the observable behavior is unchanged, there would be no need to turn them off.
My point is that coverage measurement is a different kind of observation. Please don't overlook developers' needs in this regard.
--Ned
Cheers, Mark.
participants (4)
-
joannah nanjekye -
Mark Shannon -
Ned Batchelder -
Serhiy Storchaka