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)
num using 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)
num using 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
