[issue40114] support maxsize argument for lru_cache's user_function option
Change by brendon zhang : -- components: Library (Lib) nosy: brendon-zh...@hotmail.com, rhettinger priority: normal severity: normal status: open title: support maxsize argument for lru_cache's user_function option type: behavior versions: Python 3.8 ___ Python tracker <https://bugs.python.org/issue40114> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40114] support maxsize argument for lru_cache's user_function option
Change by brendon zhang : -- keywords: +patch pull_requests: +18588 stage: -> patch review pull_request: https://github.com/python/cpython/pull/19226 ___ Python tracker <https://bugs.python.org/issue40114> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40114] support maxsize argument for lru_cache's user_function option
New submission from brendon zhang : Existing implementation of lru_cache user_function option supports typed_code argument, but does not support maxsize argument, because when we pass in the user function as a positional argument, it gets assigned to the maxsize parameter, and therefore there is no way to pass the actual maxsize value. The PR implementation supports both signatures lru_cache(maxsize=128, typed=False) lru_cache(user_function, maxsize=128, typed=False) -- ___ Python tracker <https://bugs.python.org/issue40114> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40114] support maxsize argument for lru_cache's user_function option
brendon zhang added the comment: Two concerns is 1. the method signature (inspect.signature(lru_cache)) is not (maxsize=128, typed=False) anymore, and so it is poor documentation. 2. not good reuse of TypeErrors related to incorrect number of inputs / type of inputs. -- ___ Python tracker <https://bugs.python.org/issue40114> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40114] support maxsize argument for lru_cache's user_function option
brendon zhang added the comment: update: ignore concern #1. I used __text_signature__ attribute to reset the inspect signature to something useful https://github.com/python/cpython/pull/19226/commits/eea367f64d2a83d0987a3f7a155ac015306e960b -- ___ Python tracker <https://bugs.python.org/issue40114> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40114] support maxsize argument for lru_cache's user_function option
brendon zhang added the comment: "lru_cache(maxsize=128, typed=False)(user_function)" oh ok! I overlooked that you could do this. There isn't really a need then for supporting user_function w/ the maxsize argument in single call. "The code in the PR is valiant attempt but is way too tricky for my tastes" Yeah. I think only after looking back at the code after writing it I see it is too convoluted. I guess the code can remain as some artifact to show why not to down this path (unless some convenient way to implement it is introduced in the future). -- ___ Python tracker <https://bugs.python.org/issue40114> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40114] support maxsize argument for lru_cache's user_function option
Change by brendon zhang : -- resolution: -> rejected stage: patch review -> resolved status: open -> closed ___ Python tracker <https://bugs.python.org/issue40114> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40114] support maxsize argument for lru_cache's user_function option
brendon zhang added the comment: np! -- ___ Python tracker <https://bugs.python.org/issue40114> ___ ___ 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)
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 <https://bugs.python.org/issue40225> ___ ___ 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 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 <https://bugs.python.org/issue40225> ___ ___ 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 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 <https://bugs.python.org/issue40225> ___ ___ 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 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 <https://bugs.python.org/issue40225> ___ ___ 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 added the comment: this affects ALL builtin functions (eg all(), any(), sum(), sorted(), etc...) that accept generator as input and exhaust it. -- ___ Python tracker <https://bugs.python.org/issue40225> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40225] generator exhaustion for builtin functions in recursion is O(depth)
Change by brendon zhang : -- title: max() performance regression (quadratic time) -> generator exhaustion for builtin functions in recursion is O(depth) ___ Python tracker <https://bugs.python.org/issue40225> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40225] generator exhaustion for builtin functions in nested call is O(depth)
Change by brendon zhang : -- title: generator exhaustion for builtin functions in recursion is O(depth) -> generator exhaustion for builtin functions in nested call is O(depth) ___ Python tracker <https://bugs.python.org/issue40225> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40225] recursive call within generator expression is O(depth)
Change by brendon zhang : -- title: generator exhaustion for builtin functions in nested call is O(depth) -> recursive call within generator expression is O(depth) ___ Python tracker <https://bugs.python.org/issue40225> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40225] recursive call within generator expression is O(depth)
brendon zhang added the comment: 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 = -999 for x in it: if x > best: best = x return best -- ___ Python tracker <https://bugs.python.org/issue40225> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40225] recursive call within generator expression is O(depth)
Change by brendon zhang : -- nosy: +rhettinger, vstinner ___ Python tracker <https://bugs.python.org/issue40225> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40225] recursive call within generator expression is O(depth)
brendon zhang added the comment: 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. -- Added file: https://bugs.python.org/file49047/consumerbug.py ___ Python tracker <https://bugs.python.org/issue40225> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40225] recursive call within generator expression is O(depth)
brendon zhang added the comment: hmm, I can't edit my previous posts. I meant to say python3.6 consumerbug.py python3.7 consumerbug.py -- ___ Python tracker <https://bugs.python.org/issue40225> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40225] recursive call within generator expression is O(depth)
brendon zhang added the comment: No, the example you provided does not trigger the same bug. It is explicitly to do with calling recursively from within the generator expression. -- ___ Python tracker <https://bugs.python.org/issue40225> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40225] recursive call within generator expression is O(depth)
brendon zhang added the comment: reduce the upper bound for the recursion depth until it does not segfault eg hi = 12 -- ___ Python tracker <https://bugs.python.org/issue40225> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue40225] recursive call within generator expression is O(depth)
brendon zhang added the comment: did you remember to run `ulimit -S -s unlimited`? If you don't increase the soft stack limit, your OS will kill the program. -- ___ Python tracker <https://bugs.python.org/issue40225> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
