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

[brendon zhang]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[brendon zhang]

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

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[brendon zhang]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[brendon zhang]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[brendon zhang]

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: brendon-zh...@hotmail.com
priority: normal
severity: normal
status: open
title: max() performance regression (quadratic time)
type: performance
versions: Python 3.7
Added file: https://bugs.python.org/file49043/maxbug.py

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com