[issue21523] quadratic-time compilation in the number of 'and' or 'or' expressions
Roundup Robot added the comment: New changeset cd62cc331572 by Antoine Pitrou in branch '3.4': Issue #21523: Fix over-pessimistic computation of the stack effect of some opcodes in the compiler. http://hg.python.org/cpython/rev/cd62cc331572 New changeset e61462e18112 by Antoine Pitrou in branch 'default': Issue #21523: Fix over-pessimistic computation of the stack effect of some opcodes in the compiler. http://hg.python.org/cpython/rev/e61462e18112 New changeset 49588a510ed4 by Antoine Pitrou in branch '2.7': Issue #21523: Fix over-pessimistic computation of the stack effect of some opcodes in the compiler. http://hg.python.org/cpython/rev/49588a510ed4 -- nosy: +python-dev ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue21523 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21523] quadratic-time compilation in the number of 'and' or 'or' expressions
Antoine Pitrou added the comment: This should be fixed now! -- resolution: - fixed stage: patch review - resolved status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue21523 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21523] quadratic-time compilation in the number of 'and' or 'or' expressions
Antoine Pitrou added the comment:
You're right, CPU time is burnt by stackdepth_walk().
The underlying issue is that max stacksize is computed a bit pessimistically
with the new opcodes (JUMP_IF_{TRUE,FALSE}_OR_POP). On normal functions there
wouldn't be a sizable difference, but on pathological cases such as yours, a
code object could end up claiming a large stack size (as large of the number of
such opcodes) rather than a very small number.
Still, of course, stackdepth_walk() should not blow up when computing a large
stack size, but fixing the opcode's stack effect in compile.c seems to fix the
issue anyway.
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue21523
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21523] quadratic-time compilation in the number of 'and' or 'or' expressions
Antoine Pitrou added the comment: Here is a patch. -- keywords: +patch Added file: http://bugs.python.org/file35315/stackdepth.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue21523 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21523] quadratic-time compilation in the number of 'and' or 'or' expressions
Antoine Pitrou added the comment: Updated patch adding some tests. -- stage: - patch review versions: -Python 3.3 Added file: http://bugs.python.org/file35316/stackdepth2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue21523 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21523] quadratic-time compilation in the number of 'and' or 'or' expressions
Raymond Hettinger added the comment: The patch looks like the correct solution. That said, I'm more impressed that you were able to test it so cleanly :-) -- nosy: +rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue21523 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21523] quadratic-time compilation in the number of 'and' or 'or' expressions
Changes by Raymond Hettinger raymond.hettin...@gmail.com: -- nosy: +pitrou ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue21523 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21523] quadratic-time compilation in the number of 'and' or 'or' expressions
Antoine Pitrou added the comment: Andrew, have you tried to bisect the Mercurial repository to find where the regression was introduced? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue21523 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21523] quadratic-time compilation in the number of 'and' or 'or' expressions
Andrew Dalke added the comment:
Live and learn. I did my first bisect today.
The first bad revision is:
changeset: 51920:ef8fe9088696
branch: legacy-trunk
parent: 51916:4e1556012584
user:Jeffrey Yasskin jyass...@gmail.com
date:Sat Feb 28 19:03:21 2009 +
summary: Backport r69961 to trunk, replacing JUMP_IF_{TRUE,FALSE} with
I confirmed that the parent did not have the problem.
If you want me to diagnose this further, then I'll need some hints on what to
do next.
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue21523
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21523] quadratic-time compilation in the number of 'and' or 'or' expressions
New submission from Andrew Dalke: Python's compiler has quadratic-time time behavior based on the number of and or or expressions. A profile shows that stackdepth_walk is calling itself in a stack at least 512 levels deep. (My profiler doesn't go higher than that.) I've reduced it to a simple test case. Compiling functions of the form def f(x): x * x # Repeat N times takes linear time in the number of lines N, while functions of the form def g(x): x and x # Repeat N times takes quadratic time in N. Here's an example of running the attached demonstration code on a fresh build of Python from version control: Results from 3.5.0a0 (default:de01f7c37b53, May 18 2014, 13:18:43) numusing using tests'*' 'and' 100 0.002 0.002 200 0.003 0.004 400 0.005 0.010 800 0.012 0.040 1600 0.023 0.133 3200 0.042 0.906 6400 0.089 5.871 12800 0.188 27.581 25600 0.404 120.800 The same behavior occurs when I replace 'and' with 'or'. The same behavior also occurs under Python 2.7.2, 3.3.5, 3.4.0. (I don't have builds of 3.1 or 3.2 for testing.) However, the demonstration code shows linear time under Python 2.6.6: Results from 2.6.6 (r266:84374, Aug 31 2010, 11:00:51) numusing using tests'*' 'and' 100 0.003 0.001 200 0.002 0.002 400 0.006 0.008 800 0.010 0.010 1600 0.019 0.022 3200 0.039 0.045 6400 0.085 0.098 12800 0.176 0.203 25600 0.359 0.423 51200 0.726 0.839 I came across this problem because my code imports a large machine-generated module. It was originally written for Python 2.6, where it worked just fine. When I tried to import it under new Pythons, the import appeared to hang, and I killed it after a minute or so. As a work-around, I have re-written the code generator to use chained if-statements instead of the short-circuit and operator. -- components: Interpreter Core files: quadratic_shortcircuit_compilation.py messages: 218742 nosy: dalke priority: normal severity: normal status: open title: quadratic-time compilation in the number of 'and' or 'or' expressions type: performance versions: Python 2.7, Python 3.3, Python 3.4, Python 3.5 Added file: http://bugs.python.org/file35279/quadratic_shortcircuit_compilation.py ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue21523 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21523] quadratic-time compilation in the number of 'and' or 'or' expressions
Changes by Antoine Pitrou pit...@free.fr: -- nosy: +benjamin.peterson, brett.cannon, georg.brandl, ncoghlan ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue21523 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
