[pypy-issue] [issue1145] Exponential time on iterative numpy function

[Chris Emerson]

New submission from Chris Emerson <pypy-bug at mail.nosreme.org>:

I've found a case where in PyPy with numpypy, a relatively simple function takes 
exponential time in the input (attached).  It's a reduced version of the CPython 
numpy.i0.

The test runs _chbevl(x, l) with increasing values of l, which each take ~2x the 
previous time (it should be linear), until it runs out of memory.  All the time 
seems to be taken when accessing the result array; it's very quick if you eg 
only look at the shape of the result but don't access any entries.

Some of the output (l, time in seconds) on PyPy on Win32 (similar with 1.8 or 
the last Win32 nightly build):

...
19 0.495367886011
20 1.02301351871
21 2.02426845859
22 3.96347008585
23 8.85665853394
Traceback (most recent call last):
  File "app_main.py", line 51, in run_toplevel
  File "test.py", line 26, in <module>
    t = timer.timeit(number=1)
  File "C:\cme\software\pypy-1.8\lib-python\2.7\timeit.py", line 194, in timeit
    timing = self.inner(it, self.timer)
  File "<timeit-src>", line 20, in inner
  File "<timeit-src>", line 16, in test
MemoryError

and the same with Python 2.7:
...
19 7.35256188663e-05
20 0.000114715363467
21 0.000160139567793
22 8.27644400851e-05
23 9.00785068833e-05
24 8.8923654231e-05
25 9.12333595357e-05
26 9.46979174927e-05
27 9.85474263339e-05
28 0.000101627033407
29 0.000106246444016

Regards,

Chris

----------
files: test.py
messages: 4319
nosy: pypy-issue
priority: performance bug
status: unread
title: Exponential time on iterative numpy function

________________________________________
PyPy bug tracker <tracker at bugs.pypy.org>
<https://bugs.pypy.org/issue1145>
________________________________________
-------------- next part --------------

import sys
try:
    from numpypy import arange
except ImportError:
    from numpy import arange

try:
    from timeit import Timer
    for i in range(2, 30):
        timer = Timer(setup="""
from numpy import arange
results = []

def _chbevl(x, l):
    b0 = 0

    for i in range(1,l):
        b0 = x*b0 - b0

    return b0

def test(x, y):
    results.append(_chbevl(x, len(y))[0])
""", stmt='test(arange(1), arange(%d))' % i)
        t = timer.timeit(number=1)
        print i, t
except KeyboardInterrupt:
    pass