[New-bugs-announce] [issue21523] quadratic-time compilation in the number of 'and' or 'or' expressions

[Andrew Dalke]

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 <report at bugs.python.org>
<http://bugs.python.org/issue21523>
_______________________________________