Skip to content

Move unwinding of stack for "pseudo exceptions" from interpreter to compiler. #61811

Closed

Description

@markshannon
BPO 17611
Nosy @nascheme, @rhettinger, @mdickinson, @ncoghlan, @pitrou, @tiran, @benjaminp, @tpn, @markshannon, @serhiy-storchaka, @serprex
PRs
  • [WIP] bpo-17611: Move unwinding of stack from interpreter to compiler #2827
  • bpo-17611: Move unwinding of stack from interpreter to compiler #4682
  • bpo-17611. Move unwinding of stack for "pseudo exceptions" from interpreter to compiler. #5006
  • bpo-17611. Move unwinding of stack for "pseudo exceptions" from interpreter to compiler. #5071
  • bpo-17611. Move unwinding of stack for "pseudo exceptions" from interpreter to compiler. (alt) #5143
  • Dependencies
  • bpo-24340: co_stacksize estimate can be highly off
  • bpo-32416: Refactor and add new tests for the f_lineno setter
  • Files
  • b16527f84774.diff
  • unwinding.patch
  • perf_unwind_stack.txt
  • Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

    Show more details

    GitHub fields:

    assignee = None
    closed_at = <Date 2018-02-25.14:02:36.230>
    created_at = <Date 2013-04-01.16:31:20.149>
    labels = ['interpreter-core', 'type-feature', '3.8']
    title = 'Move unwinding of stack for "pseudo exceptions" from interpreter to compiler.'
    updated_at = <Date 2018-02-25.14:02:36.229>
    user = 'https://github.com/markshannon'

    bugs.python.org fields:

    activity = <Date 2018-02-25.14:02:36.229>
    actor = 'serhiy.storchaka'
    assignee = 'none'
    closed = True
    closed_date = <Date 2018-02-25.14:02:36.230>
    closer = 'serhiy.storchaka'
    components = ['Interpreter Core']
    creation = <Date 2013-04-01.16:31:20.149>
    creator = 'Mark.Shannon'
    dependencies = ['24340', '32416']
    files = ['29646', '35094', '47253']
    hgrepos = ['181']
    issue_num = 17611
    keywords = ['patch']
    message_count = 81.0
    messages = ['185741', '185909', '185916', '185946', '185950', '185951', '185952', '185954', '185955', '217534', '228816', '228817', '231250', '258673', '267329', '267418', '268456', '298910', '298934', '298935', '298943', '298949', '298960', '298972', '305684', '307477', '307478', '307479', '307497', '307548', '307549', '307555', '307558', '307564', '307570', '307572', '307577', '307582', '307584', '307585', '307656', '307671', '307680', '307687', '307827', '308928', '308939', '308969', '309015', '309138', '309139', '309141', '309161', '309163', '309169', '309170', '309181', '309182', '309185', '309202', '309211', '309333', '309335', '309339', '309341', '309348', '309349', '309363', '309366', '309372', '309385', '309388', '309424', '309740', '309742', '309771', '310043', '310044', '310046', '312596', '312815']
    nosy_count = 11.0
    nosy_names = ['nascheme', 'rhettinger', 'mark.dickinson', 'ncoghlan', 'pitrou', 'christian.heimes', 'benjamin.peterson', 'trent', 'Mark.Shannon', 'serhiy.storchaka', 'Demur Rumed']
    pr_nums = ['2827', '4682', '5006', '5071', '5143']
    priority = 'normal'
    resolution = 'fixed'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = 'enhancement'
    url = 'https://bugs.python.org/issue17611'
    versions = ['Python 3.8']

    Activity

    1. markshannon commented on Apr 1, 2013

      @markshannon
      MemberAuthor

      The handling of "pseudo exceptions" (return, break and continue) are currently handled in the interpreter. This make the interpreter loop more complex and slower than it needs to be. This change moves the handling of pseudo exceptions into the compiler.

      The net effects of this patch are:

      Simpler interpreter loop: no 'psuedo-exceptions', fewer bytecodes and some simplifed bytecodes.

      Eliminate the 'why_code' state variable in the interpreter. Execution is always in the 'normal' state except during explicit exception handling.

      Small increase in size and complexity of compiler.

      Speedup of 1.5% (Intel i7); this should be considered a happy side-effect rather than a motivation for the change.

    2. pitrou commented on Apr 3, 2013

      @pitrou
      Member

      Simplifying the eval loop is a rather good thing. Could you post examples of bytecode disassembly before and after the patch?

    3. skrah commented on Apr 3, 2013

      skrahmannequin
      Mannequin

      The change seems to slow down the pi float benchmark. Run this and hit
      Ctrl-C after the first decimal result appears:

      ./python Modules/_decimal/tests/bench.py

      I've run the benchmark seven times and the average for float is
      something like 8-10% slower (64-bit Linux, Core 2 Duo). Decimal
      is not affected.

    4. markshannon commented on Apr 3, 2013

      @markshannon
      MemberAuthor

      Stefan,
      I tried running your pi_bench (increasing the numer of iterations by x10 to reduce jitter). The run to run variation exceed the difference between the two versions. Here are the fastest of 7 runs on my machine.
      i3-2370M CPU @ 2.40GHz × 4. linux 64bit.

      With patch:
      1.154152s

      Without patch:
      1.157730s

      I'm somewhat surprised by the slowdown on your machine. There should be no difference in the bytecodes executed or their implementation in the pi_float loop.

    5. markshannon commented on Apr 3, 2013

      @markshannon
      MemberAuthor

      Antoine,
      Two bytecode examples.

      For the following function:
      >>> def f(x):
      ...     try:
      ...         return x
      ...     except:
      ...         pass

      Without the patch:
      2 0 SETUP_EXCEPT 8 (to 11)

      3 3 LOAD_FAST 0 (x)
      6 RETURN_VALUE
      7 POP_BLOCK
      8 JUMP_FORWARD 8 (to 19)

      4 >> 11 POP_TOP
      12 POP_TOP
      13 POP_TOP

      5 14 POP_EXCEPT
      15 JUMP_FORWARD 1 (to 19)
      18 END_FINALLY
      >> 19 LOAD_CONST 0 (None)
      22 RETURN_VALUE

      With the patch:
      2 0 SETUP_EXCEPT 9 (to 12)

      3 3 LOAD_FAST 0 (x)
      6 POP_BLOCK
      7 RETURN_VALUE
      8 POP_BLOCK
      9 JUMP_FORWARD 8 (to 20)

      4 >> 12 POP_TOP
      13 POP_TOP
      14 POP_TOP

      5 15 POP_EXCEPT
      16 JUMP_FORWARD 1 (to 20)
      19 RERAISE
      >> 20 LOAD_CONST 0 (None)
      23 RETURN_VALUE

      The difference is the 'POP_BLOCK' inserted at offset 7 *before* the 'RETURN_VALUE', so that the RETURN_VALUE bytecode does not have to do any unwinding of the block stack.

      For loops the SETUP_LOOP and the matching POP_BLOCK are eliminated:

      >>> def f(x):
      ...    for y in x:
      ...        g(x)

      Without the patch:
      2 0 SETUP_LOOP 24 (to 27)
      3 LOAD_FAST 0 (x)
      6 GET_ITER
      >> 7 FOR_ITER 16 (to 26)
      10 STORE_FAST 1 (y)

      3 13 LOAD_GLOBAL 0 (g)
      16 LOAD_FAST 1 (y)
      19 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
      22 POP_TOP
      23 JUMP_ABSOLUTE 7
      >> 26 POP_BLOCK
      >> 27 LOAD_CONST 0 (None)
      30 RETURN_VALUE

      With the patch:
      2 0 LOAD_FAST 0 (x)
      3 GET_ITER
      >> 4 FOR_ITER 16 (to 23)
      7 STORE_FAST 1 (y)

      3 10 LOAD_GLOBAL 0 (g)
      13 LOAD_FAST 0 (x)
      16 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
      19 POP_TOP
      20 END_ITER 4
      >> 23 LOAD_CONST 0 (None)
      26 RETURN_VALUE

      END_ITER is a synonym for JUMP_ABSOLUTE. It is needed so that frame.set_lineno() can identify loop blocks.

    6. skrah commented on Apr 3, 2013

      skrahmannequin
      Mannequin

      I'm surprised, too, but after a couple of retries the results stay the
      same. On an i7 there's also a difference, but not quite as large. I'm
      using b16527f84774.diff, which applies cleanly apart from importlib.h
      (which I just regenerated).

      With an increased loop count the difference is also the same (10% on
      the Core2 Duo).

      Core2 Duo, 3.16GHz, Linux 64-bit
      ================================

      patched:
      --------
      (0.10855+0.10901+0.1168+0.1119+0.1095+0.1090+0.1084+0.1130+0.1235+0.1183) / 10 = 0.113

      unpatched:
      ----------
      (0.0995+0.1049+0.1009+0.1021+0.0986+0.1005+0.0988+0.10171+0.0987+0.0992) / 10 = 0.10

      (i7, 2.80GHz, Linux 64-bit)
      ============================

      patched:
      --------
      (0.1021+0.1078+0.1072+0.1058+0.1091+0.1067+0.1064+0.1071+0.1069+0.1067) / 10 = 0.107

      unpatched:
      ----------
      (0.1029+0.1033+0.1023+0.1029+0.1050+0.1020+0.1031+0.1024+0.10149+0.10247) / 10 = 0.103

    7. skrah commented on Apr 3, 2013

      skrahmannequin
      Mannequin

      BTW, there's no general slowdown on the Core2 Duo: In the patched version,
      the telco benchmark is consistently 4% faster.

    8. pitrou commented on Apr 3, 2013

      @pitrou
      Member

      BTW, there's no general slowdown on the Core2 Duo: In the patched version,
      the telco benchmark is consistently 4% faster.

      It's customary for even innocent changes in ceval to produce small
      changes in some benchmarks. It's only really important to consider the
      global average.

    9. skrah commented on Apr 3, 2013

      skrahmannequin
      Mannequin

      Antoine Pitrou <report@bugs.python.org> wrote:

      It's customary for even innocent changes in ceval to produce small
      changes in some benchmarks. It's only really important to consider the
      global average.

      Yes, the float benchmark appears to be particularly sensitive. In the
      3.3.0 release it also runs 8% slower than it does now (unpatched).

      I'm trying to keep track of changes because in 2.7 the (float) benchmark runs
      something like 25% faster than in 3.3.0.

    10. pitrou commented on Apr 29, 2014

      @pitrou
      Member

      Here is an updated patch keeping up with recent changes in the source tree.

    11. pitrou commented on Oct 8, 2014

      @pitrou
      Member

      END_ITER is a synonym for JUMP_ABSOLUTE. It is needed so that frame.set_lineno() can identify loop blocks.

      I was thinking about this. Isn't it enough to consider all backwards edges as ending a loop block?

    12. pitrou commented on Oct 8, 2014

      @pitrou
      Member

      Ah, no, I guess "continue" would also create a backwards edge. Nevermind, sorry.

    13. serhiy-storchaka commented on Nov 16, 2014

      @serhiy-storchaka
      Member

      I like the idea. I have not make faultfinding review yet, but one thing is questionable to me.

      Is it necessary to get rid of the END_FINALLY opcode?

      Currently Python code

      try:
          stmt1
      finally:
          stmt2
      

      is compiled to:

      SETUP_FINALLY L1
      // stmt1
      POP_BLOCK
      LOAD_CONST None
      

      L1: // stmt2
      END_FINALLY

      With the patch it is compiled to:

      SETUP_FINALLY L1
      // stmt1
      POP_BLOCK
      // stmt2
      JUMP_ABSOLUTE L2
      

      L1: // stmt2
      RERAISE
      L2:

      Finally body is duplicated. In case of large finally body this increases the size of the bytecode. Line numbers are duplicated in disassembly listing, this is confused. And I afraid that due to increasing the size of the bytecode, some relative jumps can became too long.

      If it is absolutely necessary to remove the END_FINALLY opcode, I suggest to generate following bytecode:

      SETUP_FINALLY L1
      // stmt1
      POP_BLOCK
      LOAD_CONST None
      

      L1: // stmt2
      POP_JUMP_IF_FALSE L2
      RERAISE
      L2:

      But it looks to me that special END_FINALLY opcode which combines POP_JUMP_IF_FALSE/RERAISE would be better for performance and compiled code size.

    14. 58 remaining items

    15. markshannon commented on Jan 2, 2018

      @markshannon
      MemberAuthor

      It looks like the build core dumped on Travis-CI

      I failed to account for the extra stuff left on the stack when handling exceptions and jumping out of a finally block due to a break. Caught by Serhiy's tests in #5078.
      I could add a work around, but it would be a bit hacky.

      I'm now convinced that code duplication is the only way to do this properly. The only real advantage of JSR-style finally blocks is the ease of implementation of frame.set_lineno().

      Rather than go around in circles any more, I suggest that we merge Serhiy's PR (PR 5006). I can then cherry-pick my commits to clean up the implementation of the with statement (as a new PR).

      I then plan to implement try-finally using code duplication, but that might not make it into 3.7 and we shouldn't hold up this issue any longer.

    16. pitrou commented on Jan 2, 2018

      @pitrou
      Member

      Le 02/01/2018 à 18:13, Mark Shannon a écrit :

      Rather than go around in circles any more, I suggest that we merge Serhiy's PR (PR 5006). I can then cherry-pick my commits to clean up the implementation of the with statement (as a new PR).

      Fair enough. I'm making a final review round on Serhiy's PR and
      hopefully this will be in.

      Also looking forward to the cleanup followup.

    17. nascheme commented on Jan 3, 2018

      @nascheme
      Member

      On 2017-12-29, Mark Shannon wrote:

      One point I didn't cover is jumping to a new line in the debugger.
      Implementing that reliably for finally blocks with code
      duplication is tricky and would mean adding a number of marker
      bytecodes. Which is a big point in favour of the JSR style.

      Could we virtually execute the code, forwards or backwards,
      starting from f_lasti? For conditional jumps, we would follow both
      branches. Stop when we find the line number we want. If we hit an
      opcode that causes a fblock push or pop, abort.

      I started implementing this as a proof of concept but didn't finish.
      It seems to fit most naturally as an exported function of
      Python/peephole.c. That file already does a lot of similar stuff.

    18. serhiy-storchaka commented on Jan 9, 2018

      @serhiy-storchaka
      Member

      PR 5143 is yet one alternative. It is a variant of PR 5006 that restores SETUP_EXCEPT and gets rid of the new opcode BEGIN_FINALLY. SETUP_FINALLY, SETUP_WITH and SETUP_ASYNC_WITH now push NULL on the stack instead.

      PR 5143 removes and add fewer opcodes than PR 5006, but changes the behavior of more opcodes. I don't know what of them looks simpler.

    19. markshannon commented on Jan 9, 2018

      @markshannon
      MemberAuthor

      Can we stick to the one PR, please?
      Once it is merged then we can improve things.

      Also, I don't like leaving NULLs on the stack, they are an invitation to seg-fault. PR 5143 leaves more NULLs on the stack for longer.

    20. pitrou commented on Jan 10, 2018

      @pitrou
      Member

      Please let's stick with PR 5006.

    21. serhiy-storchaka commented on Jan 16, 2018

      @serhiy-storchaka
      Member

      What should be done for PR 5006? Changes of this PR have been minimized for easier review. But many interesting things can made after merging it. For example simplify 'with'-related opcodes. Or implement static blocks (this will make the 'try' statement zero-overhead, make checks in frame.f_lineno setter more reliable, and unblock some bytecode optimizations). It would be better to have more time before a feature freeze.

    22. pitrou commented on Jan 16, 2018

      @pitrou
      Member

      Apparently PR 5006 has a conflict. Otherwise, is it ready for review?

    23. pitrou commented on Jan 16, 2018

      @pitrou
      Member

      Simplifying "with"-related opcodes (and perhaps "finally" ones) sounds nice.

      "try" blocks are already zero-overhead for practical purposes (i.e. I don't think I've met any workload where moving a "try" around did improve performance significantly).

    24. serhiy-storchaka commented on Feb 22, 2018

      @serhiy-storchaka
      Member

      New changeset 520b7ae by Serhiy Storchaka in branch 'master':
      bpo-17611. Move unwinding of stack for "pseudo exceptions" from interpreter to compiler. (GH-5006)
      520b7ae

    25. serhiy-storchaka commented on Feb 25, 2018

      @serhiy-storchaka
      Member

      Finally it is merged, and seems successfully. Thank you all involved, and first at all Mark, the original author.

      This unblocked further changes, bpo-32489 and bpo-32949. And we can try implement other ideas.

      Changes in the f_lineno setter fixed crashes in bpo-17288 and bpo-28883. But while writing tests for it I found other crashers, will open new issues soon.

    26. transferred this issue fromon Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

    Metadata

    Metadata

    Assignees

    No one assigned

      Labels

      3.8 (EOL)end of lifeinterpreter-core(Objects, Python, Grammar, and Parser dirs)type-featureA feature request or enhancement

      Projects

      No projects

        Milestone

        No milestone

        Relationships

        None yet

        Development

        No branches or pull requests

        Issue actions