This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: Exponential time and space requirements for compilation of nested try/finally blocks
Type: performance Stage: resolved
Components: Interpreter Core Versions: Python 3.10, Python 3.9
process
Status: closed Resolution: wont fix
Dependencies: Superseder:
Assigned To: Nosy List: Mark.Shannon, mark.dickinson, serhiy.storchaka
Priority: normal Keywords:

Created on 2021-01-09 12:00 by mark.dickinson, last changed 2022-04-11 14:59 by admin. This issue is now closed.

Messages (6)
msg384718 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-01-09 12:00
tl;dr - contrived (but relatively short) code involving nested try/finally blocks can produce disproportionately large bytecode. I'm not expecting or suggesting any action here, but the situation seemed at least worth noting. Feel free to close this issue as a "well don't do that, then" (a.k.a. "wont fix")

Longer: Python 3.9 changed the way that bytecode was generated for try/finally (see #33387). For a "try" block body that can do any of raise, return or fall-off-the-end-of-the-block, the corresponding finally block gets three separate paths in the bytecode. If such trys are nested <n> times, we get 3^n separate paths in the bytecode.

Example code:

----------------
def f():
    try:
        if something(): return
    finally:
        try:
            if something(): return
        finally:
            try:
                if something(): return
            finally:
                try:
                    if something(): return
                finally:
                    try:
                        if something(): return
                    finally:
                        do_cleanup()


import dis
dis.dis(f)
----------------

On my machine, running this and counting the do_cleanup invocations gives, as expected, a result of 243 = 3**5

% python3.9 nested_finally.py | grep do_cleanup | wc -l 
     243

That's fairly benign, but if I scale up to 10 nested blocks, the dis.dis call takes over 10 minutes to complete (the compilation itself still only takes a fraction of a second). The bytecode object is correspondingly large:

>>> len(f.__code__.co_code)
1741356

With 15 levels of nesting, compilation takes several seconds, and
the generated code is (again as expected) a couple of orders of magnitude larger:

>>> len(f.__code__.co_code)
533859040

I didn't try pushing this further than 15 levels of nesting.

As I said above, it's not clear to me whether this is actually an issue that needs to be addressed in practice. It seems unlikely that "real code" :TM: would run into this, but the effect seemed worth noting.
msg384721 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-01-09 12:19
For extra fun, you can add `break` and `continue` paths into the mix to get a 5-fold instead of 3-fold  code size increase per level of nesting. It's still contrived code, though.

Example where do_cleanup() ends up with 5**4 = 625 paths:

----

def f():
    while True:
        try:
            if something(): break
            elif something_else(): continue
            elif yet_something_else(): return
        finally:
            try:
                if something(): break
                elif something_else(): continue
                elif yet_something_else(): return
            finally:
                try:
                    if something(): break
                    elif something_else(): continue
                    elif yet_something_else(): return
                finally:
                    try:
                        if something(): break
                        elif something_else(): continue
                        elif yet_something_else(): return
                    finally:
                        do_cleanup()
----
msg384722 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2021-01-09 12:31
And there may be more than one return/break/continue statement in the try block. It increases the base of the degree.

At least for "return" we perhaps can merge different cases. But it would complicate the compiler and cannot help in other cases.
msg384724 - (view) Author: Mark Shannon (Mark.Shannon) * (Python committer) Date: 2021-01-09 12:38
I don't see what the problem is here.
People just don't write code like that, at least not if they do code review ;)

And even, in the *extremely* rare case that they do, the code executes correctly and reasonably quickly. It just uses a bit of extra memory.
msg384725 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-01-09 12:38
> And there may be more than one return/break/continue statement in the try block. It increases the base of the degree.

Ah, interesting. My understanding was that that can't happen, but I'll double check. In the control flow, all 'return' statements that leave a try block are going to the same place, so only one 'finally' branch needs to be generated no matter how many returns you have. And similarly for 'break' and 'continue'. IOW, what matters is the possible paths that can be taken when the finally block exits, and there are only up to 5 of those (for raise, return, break, continue, and leaving normally).
msg384726 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-01-09 12:42
> I don't see what the problem is here. People just don't write code like that.

Yes, agreed; as I said in the original post, I'm not expecting any action, but the effect did seem interesting enough to be worth noting in an issue (if only so that it can be recorded as a known "feature" and the resolution can be recorded for the future).

I'll close as won't fix.
History
Date User Action Args
2022-04-11 14:59:40adminsetgithub: 87039
2021-01-09 12:42:13mark.dickinsonsetstatus: open -> closed
resolution: wont fix
messages: + msg384726

stage: resolved
2021-01-09 12:38:21mark.dickinsonsetmessages: + msg384725
2021-01-09 12:38:15Mark.Shannonsetmessages: + msg384724
2021-01-09 12:31:38serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg384722
2021-01-09 12:19:47mark.dickinsonsetmessages: + msg384721
2021-01-09 12:00:18mark.dickinsoncreate