classification
Title: recursive call within generator expression is O(depth)
Type: performance Stage: patch review
Components: Library (Lib) Versions: Python 3.7
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: Mark.Shannon, brendon-zhang@hotmail.com, remi.lapeyre, rhettinger, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2020-04-08 12:10 by brendon-zhang@hotmail.com, last changed 2020-04-11 12:09 by Mark.Shannon.

Files
File name Uploaded Description Edit
maxbug.py brendon-zhang@hotmail.com, 2020-04-08 12:10 code and benchmarks
maxbug2.py brendon-zhang@hotmail.com, 2020-04-08 12:50
consumerbug.py brendon-zhang@hotmail.com, 2020-04-09 13:02
Pull Requests
URL Status Linked Edit
PR 19473 merged Mark.Shannon, 2020-04-11 12:09
Messages (15)
msg365978 - (view) Author: brendon zhang (brendon-zhang@hotmail.com) * Date: 2020-04-08 12:10
There is a performance regression of the max (and also min) function implementation starting in python 3.7.

I provide code and associated benchmarks in the file attachment.
msg365979 - (view) Author: brendon zhang (brendon-zhang@hotmail.com) * Date: 2020-04-08 12:18
Something about calling max() in deeply nested recursion context appears to make the overall complexity O(n^2) instead of O(n)
msg365981 - (view) Author: brendon zhang (brendon-zhang@hotmail.com) * Date: 2020-04-08 12:20
You can get the replicate this issue even when removing lru_cache(None) and calling max with iterable of size 1.

eg.
best = max(solve(j) for j in [i-1])
msg365983 - (view) Author: brendon zhang (brendon-zhang@hotmail.com) * Date: 2020-04-08 12:50
update:
it is specifically caused by passing in a generator expression to max(), where the generator invokes recursive function.

I added another file to demonstrate this
msg365984 - (view) Author: brendon zhang (brendon-zhang@hotmail.com) * Date: 2020-04-08 13:05
this affects ALL builtin functions (eg all(), any(), sum(), sorted(), etc...) that accept generator as input and exhaust it.
msg366040 - (view) Author: brendon zhang (brendon-zhang@hotmail.com) * Date: 2020-04-09 11:15
update 2:
This affects ALL functions which exhaust a generator expression. If that generator expression makes a recursive call, then the cost of evaluating it is O(depth), when it should be only O(1).

You can see demonstrate that this doesn't just affect builtins, by replacing max() with a custom implementation such as,

def custommax(it):
    best = -9999999
    for x in it:
        if x > best:
            best = x
    return best
msg366041 - (view) Author: Rémi Lapeyre (remi.lapeyre) * Date: 2020-04-09 11:25
Hi brendon, can you write a complete minimal example that shows the issue, it seems that you are heving an issue when consuming recursive generators and that it's actually not related to max().

I'm confused about the details and have not been able to write an example that exposes the issue from the various pieces of code you posted.
msg366048 - (view) Author: brendon zhang (brendon-zhang@hotmail.com) * Date: 2020-04-09 13:02
Okay, I attached a complete minimal example below.

In your shell, run 
ulimit -S -s unlimited

Then try executing with various python versions 3.6 and 3.7
python3.6 benchbug.py
python3.7 benchbug.py

You will notice that python 3.7 has a significant performance regression. It is likely a bug.
msg366049 - (view) Author: brendon zhang (brendon-zhang@hotmail.com) * Date: 2020-04-09 13:03
hmm, I can't edit my previous posts. I meant to say

python3.6 consumerbug.py
python3.7 consumerbug.py
msg366050 - (view) Author: Rémi Lapeyre (remi.lapeyre) * Date: 2020-04-09 13:21
I'm unable to run the example as it segfaults on my computer because of the linear recursion but do you notice the same behavior with:

from time import time
from sys import setrecursionlimit

setrecursionlimit(10000000)

def recurse(i):
    if i < 0:
        return
    recurse(i-1)

if __name__ == '__main__':
    lo = 8
    hi = 16
    t = {}

    for sh in range(lo, hi):
        b4 = time()
        x = 1 << sh
        ret = recurse(x)
        after = time()
        t[sh] = after - b4

    for sh in range(lo+1, hi):
        print(t[sh] / t[sh-1])
msg366051 - (view) Author: brendon zhang (brendon-zhang@hotmail.com) * Date: 2020-04-09 13:36
No, the example you provided does not trigger the same bug. It is explicitly to do with calling recursively from within the generator expression.
msg366052 - (view) Author: brendon zhang (brendon-zhang@hotmail.com) * Date: 2020-04-09 13:37
reduce the upper bound for the recursion depth until it does not segfault

eg
hi = 12
msg366053 - (view) Author: brendon zhang (brendon-zhang@hotmail.com) * Date: 2020-04-09 13:40
did you remember to run `ulimit -S -s unlimited`? If you don't increase the soft stack limit, your OS will kill the program.
msg366200 - (view) Author: Rémi Lapeyre (remi.lapeyre) * Date: 2020-04-11 10:53
I've been looking at this, I find the effect more visible when you don't do the division in the last print().

After bisecting, it looks like ae3087c6382011c47db82fea4d05f8bbf514265d may account for most of the performance gap between 3.6 and 3.7.
msg366204 - (view) Author: Mark Shannon (Mark.Shannon) * (Python committer) Date: 2020-04-11 11:59
The problem is that generators always raise an exception, even when they terminate normally.
They don't in 2.7 and didn't prior to https://github.com/python/cpython/commit/1f7ce62bd61488d5d721896a36a1b43befab88b5#diff-23c87bfada1d01335a3019b9321502a0
History
Date User Action Args
2020-04-11 12:09:29Mark.Shannonsetkeywords: + patch
stage: patch review
pull_requests: + pull_request18828
2020-04-11 11:59:10Mark.Shannonsetmessages: + msg366204
2020-04-11 10:53:25remi.lapeyresetmessages: + msg366200
2020-04-09 17:18:21serhiy.storchakasetnosy: + Mark.Shannon, serhiy.storchaka
2020-04-09 15:53:29vstinnersetnosy: - vstinner
2020-04-09 13:40:28brendon-zhang@hotmail.comsetmessages: + msg366053
2020-04-09 13:37:19brendon-zhang@hotmail.comsetmessages: + msg366052
2020-04-09 13:36:38brendon-zhang@hotmail.comsetmessages: + msg366051
2020-04-09 13:21:31remi.lapeyresetmessages: + msg366050
2020-04-09 13:03:44brendon-zhang@hotmail.comsetmessages: + msg366049
2020-04-09 13:02:14brendon-zhang@hotmail.comsetfiles: + consumerbug.py

messages: + msg366048
2020-04-09 11:25:23remi.lapeyresetnosy: + remi.lapeyre
messages: + msg366041
2020-04-09 11:17:55brendon-zhang@hotmail.comsetnosy: + rhettinger, vstinner
2020-04-09 11:15:03brendon-zhang@hotmail.comsetmessages: + msg366040
2020-04-09 11:08:17brendon-zhang@hotmail.comsettitle: generator exhaustion for builtin functions in nested call is O(depth) -> recursive call within generator expression is O(depth)
2020-04-08 13:08:44brendon-zhang@hotmail.comsettitle: generator exhaustion for builtin functions in recursion is O(depth) -> generator exhaustion for builtin functions in nested call is O(depth)
2020-04-08 13:07:39brendon-zhang@hotmail.comsettitle: max() performance regression (quadratic time) -> generator exhaustion for builtin functions in recursion is O(depth)
2020-04-08 13:05:08brendon-zhang@hotmail.comsetmessages: + msg365984
2020-04-08 12:50:29brendon-zhang@hotmail.comsetfiles: + maxbug2.py

messages: + msg365983
2020-04-08 12:20:46brendon-zhang@hotmail.comsetmessages: + msg365981
2020-04-08 12:18:50brendon-zhang@hotmail.comsetmessages: + msg365979
2020-04-08 12:10:27brendon-zhang@hotmail.comcreate