Idle bytecode query on apparently unreachable returns

[Tom Anderson]

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..... if (x == 1):
.... return 1
.... else:
.... return x * fib((x - 1))
.... 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)
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 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

 

[jepler]

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-----

 

[Neal Norwitz]

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

 

[Raymond Hettinger]

[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

 

[Tom Anderson]

[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