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) * |
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
|
|
Date |
User |
Action |
Args |
2022-04-11 14:59:29 | admin | set | github: 84406 |
2020-04-11 12:09:29 | Mark.Shannon | set | keywords:
+ patch stage: patch review pull_requests:
+ pull_request18828 |
2020-04-11 11:59:10 | Mark.Shannon | set | messages:
+ msg366204 |
2020-04-11 10:53:25 | remi.lapeyre | set | messages:
+ msg366200 |
2020-04-09 17:18:21 | serhiy.storchaka | set | nosy:
+ Mark.Shannon, serhiy.storchaka
|
2020-04-09 15:53:29 | vstinner | set | nosy:
- vstinner
|
2020-04-09 13:40:28 | brendon-zhang@hotmail.com | set | messages:
+ msg366053 |
2020-04-09 13:37:19 | brendon-zhang@hotmail.com | set | messages:
+ msg366052 |
2020-04-09 13:36:38 | brendon-zhang@hotmail.com | set | messages:
+ msg366051 |
2020-04-09 13:21:31 | remi.lapeyre | set | messages:
+ msg366050 |
2020-04-09 13:03:44 | brendon-zhang@hotmail.com | set | messages:
+ msg366049 |
2020-04-09 13:02:14 | brendon-zhang@hotmail.com | set | files:
+ consumerbug.py
messages:
+ msg366048 |
2020-04-09 11:25:23 | remi.lapeyre | set | nosy:
+ remi.lapeyre messages:
+ msg366041
|
2020-04-09 11:17:55 | brendon-zhang@hotmail.com | set | nosy:
+ rhettinger, vstinner
|
2020-04-09 11:15:03 | brendon-zhang@hotmail.com | set | messages:
+ msg366040 |
2020-04-09 11:08:17 | brendon-zhang@hotmail.com | set | title: generator exhaustion for builtin functions in nested call is O(depth) -> recursive call within generator expression is O(depth) |
2020-04-08 13:08:44 | brendon-zhang@hotmail.com | set | title: 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:39 | brendon-zhang@hotmail.com | set | title: max() performance regression (quadratic time) -> generator exhaustion for builtin functions in recursion is O(depth) |
2020-04-08 13:05:08 | brendon-zhang@hotmail.com | set | messages:
+ msg365984 |
2020-04-08 12:50:29 | brendon-zhang@hotmail.com | set | files:
+ maxbug2.py
messages:
+ msg365983 |
2020-04-08 12:20:46 | brendon-zhang@hotmail.com | set | messages:
+ msg365981 |
2020-04-08 12:18:50 | brendon-zhang@hotmail.com | set | messages:
+ msg365979 |
2020-04-08 12:10:27 | brendon-zhang@hotmail.com | create | |