Idle bytecode query on apparently unreachable returns

Discussion in 'Python' started by Tom Anderson, Oct 10, 2005.

  1. Tom Anderson

    Tom Anderson Guest

    Evening all,

    Here's a brief chat with the interpretator:

    Python 2.4.1 (#2, Mar 31 2005, 00:05:10)
    [GCC 3.3 20030304 (Apple Computer, Inc. build 1666)] on darwin
    Type "help", "copyright", "credits" or "license" for more information.
    >>> def fib(x):

    .... if (x == 1):
    .... return 1
    .... else:
    .... return x * fib((x - 1))
    ....
    >>> import dis
    >>> dis.dis(fib)

    2 0 LOAD_FAST 0 (x)
    3 LOAD_CONST 1 (1)
    6 COMPARE_OP 2 (==)
    9 JUMP_IF_FALSE 8 (to 20)
    12 POP_TOP

    3 13 LOAD_CONST 1 (1)
    16 RETURN_VALUE
    17 JUMP_FORWARD 19 (to 39)
    >> 20 POP_TOP


    5 21 LOAD_FAST 0 (x)
    24 LOAD_GLOBAL 1 (fib)
    27 LOAD_FAST 0 (x)
    30 LOAD_CONST 1 (1)
    33 BINARY_SUBTRACT
    34 CALL_FUNCTION 1
    37 BINARY_MULTIPLY
    38 RETURN_VALUE
    >> 39 LOAD_CONST 0 (None)

    42 RETURN_VALUE

    I'm no bytecode connoisseur, but having read
    <http://docs.python.org/lib/bytecodes.html>, i more or less get this.

    What puzzles me, though, are bytecodes 17, 39 and 42 - surely these aren't
    reachable? Does the compiler just throw in a default 'return None'
    epilogue, with routes there from every code path, even when it's not
    needed? If so, why?

    tom

    --
    News flash: there's no deep meaning or hidden message BECAUSE DAVID LYNCH IS INSANE
     
    Tom Anderson, Oct 10, 2005
    #1
    1. Advertising

  2. Tom Anderson

    Guest

    On Mon, Oct 10, 2005 at 12:20:13AM +0100, Tom Anderson wrote:
    > What puzzles me, though, are bytecodes 17, 39 and 42 - surely these aren't
    > reachable? Does the compiler just throw in a default 'return None'
    > epilogue, with routes there from every code path, even when it's not
    > needed? If so, why?

    I think the short answer is "yes". They're unreachable, and they're thrown in
    by default.

    It's possible that this could be fixed with a slightly smarter compiler, but
    the performance difference is likely to be in the noise. What's one cache miss
    (because the bytecode is slightly larger) compared to the total cycles used
    in, say, the LOAD_GLOBAL 'fib'?

    My bet is that this optimization would not pay off in measurable run-time
    gains.

    Jeff

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.1 (GNU/Linux)

    iD8DBQFDSam1Jd01MZaTXX0RAlcrAJsHKk87wjAQmqSdwKNXLaGRQfZCLwCggROk
    Y6Ai9/sgiTzOyZFIRhRo9Lo=
    =MRzz
    -----END PGP SIGNATURE-----
     
    , Oct 10, 2005
    #2
    1. Advertising

  3. Tom Anderson

    Neal Norwitz Guest

    Tom Anderson wrote:
    > Evening all,
    >
    > Here's a brief chat with the interpretator:


    [snip]

    > What puzzles me, though, are bytecodes 17, 39 and 42 - surely these aren't
    > reachable? Does the compiler just throw in a default 'return None'
    > epilogue, with routes there from every code path, even when it's not
    > needed? If so, why?


    I think the last RETURN_VALUE (None) isn't thrown in unless there is
    some sort of conditional the precedes it as in this example.

    As to why: it's easier and no one has done anything about fixing it.
    If you (or anyone else) are interested, the code is in
    Python/compile.c. Search for the optimize_code() function.

    n
     
    Neal Norwitz, Oct 10, 2005
    #3
  4. [Tom Anderson]:
    > What puzzles me, though, are bytecodes 17, 39 and 42 - surely these aren't
    > reachable? Does the compiler just throw in a default 'return None'
    > epilogue, with routes there from every code path, even when it's not
    > needed? If so, why?


    Since unreachable code is never executed, there is no performance
    payoff for optimizing it away. It is not hard to write a dead-code
    elimination routine, but why bother? It would save a few bytes, slow
    down compilation time, save nothing at runtime, and make the compiler
    more complex/fragile.

    FWIW, the peephole optimizer in Python/compile.c is mature -- the low
    hanging fruit has already been harvested, leaving the field of
    remaining optimizations somewhat barren.


    Raymond
     
    Raymond Hettinger, Oct 11, 2005
    #4
  5. Tom Anderson

    Tom Anderson Guest

    On Tue, 11 Oct 2005, Raymond Hettinger wrote:

    > [Tom Anderson]:
    >
    >> What puzzles me, though, are bytecodes 17, 39 and 42 - surely these
    >> aren't reachable? Does the compiler just throw in a default 'return
    >> None' epilogue, with routes there from every code path, even when it's
    >> not needed? If so, why?

    >
    > Since unreachable code is never executed, there is no performance payoff
    > for optimizing it away. It is not hard to write a dead-code elimination
    > routine, but why bother?


    Fair enough - it wasn't a criticism, i was just wondering if those
    bytecodes were serving some crucial function i hadn't appreciated!

    > It would save a few bytes, slow down compilation time, save nothing at
    > runtime, and make the compiler more complex/fragile.


    I have this vague idea that a compiler could be written in such a way
    that, rather than dead code being weeded out by some
    extra-complexity-inducing component, it would simply never be generated in
    the first place; that could perhaps even be simpler than the situation at
    present. I have tree reduction and SSA graphs frolicking in soft focus in
    my imagination. But, that said, i have no experience of actually writing
    compilers, so maybe this SSA stuff is harder than it sounds!

    tom

    --
    That's no moon!
     
    Tom Anderson, Oct 13, 2005
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Charlie
    Replies:
    0
    Views:
    458
    Charlie
    Aug 11, 2003
  2. Jacob

    Re: unreachable statements

    Jacob, Aug 16, 2004, in forum: Java
    Replies:
    2
    Views:
    398
    Joona I Palaste
    Aug 16, 2004
  3. Unreachable

    , Sep 6, 2003, in forum: Python
    Replies:
    1
    Views:
    407
    Bertel Lund Hansen
    Sep 6, 2003
  4. Unreachable

    , Sep 6, 2003, in forum: Python
    Replies:
    0
    Views:
    356
  5. Replies:
    0
    Views:
    273
Loading...

Share This Page