[issue40225] max() performance regression (quadratic time)

brendon zhang added the comment: this affects ALL builtin functions (eg all(), any(), sum(), sorted(), etc...) that accept generator as input and exhaust it. -- ___ Python tracker

[issue40225] max() performance regression (quadratic time)

brendon zhang added the comment: 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 -- Added file: https://bugs.python.org/file49044/maxbug2.py

[issue40225] max() performance regression (quadratic time)

brendon zhang added the comment: 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]) -- ___ Python tracker

[issue40225] max() performance regression (quadratic time)

brendon zhang added the comment: Something about calling max() in deeply nested recursion context appears to make the overall complexity O(n^2) instead of O(n) -- ___ Python tracker

[issue40225] max() performance regression (quadratic time)

New submission from brendon zhang : 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. -- components: Library (Lib) files: maxbug.py messages: 365978 nosy: