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.

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

[jepler]

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

iD8DBQFDSam1Jd01MZaTXX0RAlcrAJsHKk87wjAQmqSdwKNXLa GRQfZCLwCggROk
Y6Ai9/sgiTzOyZFIRhRo9Lo=
=MRzz
-----END PGP SIGNATURE-----

[Neal Norwitz]

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

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

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!