Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Carl Cerecke: goto in python. Yes. Really.

Carl Cerecke: goto in python. Yes. Really.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Carl Cerecke:
goto in python. Yes. Really.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
@ Kiwi PyCon 2014 - Sunday, 14 Sep 2014 - Track 2
http://kiwi.pycon.org/

**Audience level**

Experienced

**Description**

Unfortunately, python is missing the goto keyword. This talk rights this historical wrong by presenting a module that allows the use of goto within a function. An overview of the implementation is provided, along with rationale and performance results. Knowing what a decorator is will be helpful for understanding the technical part of this talk.

**Abstract**

goto in Python

- A brief history of the goto statement.
- Why have a goto in Python?
- Previous attempts at goto in Python
- Dynamically rewriting byte codes
- Problematic constructs
- Performance results
- Future work

**YouTube**

https://www.youtube.com/watch?v=DdU8I09BGsU

New Zealand Python User Group

September 14, 2014
Tweet

More Decks by New Zealand Python User Group

Other Decks in Programming

Transcript

  1. goto in Python 3. Yes. Really. Kiwi PyCon 2014 Carl

    Cerecke [email protected] https://github.com/cdjc/goto September 13-14, 2014
  2. History In the beginning was the goto 1958 Heinz Zemanek

    expresses doubts about goto at pre-ALGOL meeting. 1968 Edsgar Dijkstra “GOTO Considered Harmful” 1974 Don Knuth “Structured Programming with go to statements” 1987 Frank Rubin ‘ “GOTO Considered Harmful” Considered Harmful’
  3. Why add goto to Python? It seemed like a good

    idea at the time... Also useful for: State machines Breaking out of a nested loop Generating python code programmatically Translating goto-filled code to python
  4. But it’s already been done before! April 1 2004, http://entrian/goto

    Uses sys.settrace Checks before the execution of every line for goto. Slow Module scope, not function scope.
  5. Goto using bytecode manipulation Python source code is compiled into

    python bytecode instructions. Each bytecode instruction is 1-3 bytes long. Python bytecodes already have gotos: JUMP FORWARD(delta) JUMP ABSOLUTE(target) also exotics like JUMP IF FALSE OR POP(target) CPython only. See the dis module.
  6. Simple example function from goto import goto @goto # enables

    goto in decorated function def simple(n): goto .skip print(n) label .skip We can see python bytecodes: import dis dis.dis(fn) # pretty print byte code
  7. Disassembly of simple function (without goto decorator) line addr opcode

    par interpretation 302 0 LOAD GLOBAL 0 (goto) 3 LOAD ATTR 1 (skip) 6 POP TOP 303 7 LOAD GLOBAL 2 (print) 10 LOAD FAST 0 (n) 13 CALL FUNCTION 1 (1 positional, 0 keyword pair) 16 POP TOP 304 17 LOAD GLOBAL 3 (label) 20 LOAD ATTR 1 (skip) 23 POP TOP 24 LOAD CONST 0 (None) 27 RETURN VALUE
  8. Changes required for goto Python treats goto statement as attribute

    access. Likewise for label statement. Need to change goto into JUMP_ABSOLUTE and label into NOP
  9. Byte code with goto changes line addr opcode par interpretation

    302 0 JUMP ABSOLUTE 24 3 LOAD ATTR 1 (skip) 6 POP TOP 303 7 LOAD GLOBAL 2 (print) 10 LOAD FAST 0 (n) 13 CALL FUNCTION 1 (1 positional, 0 keyword pair) 16 POP TOP 304 17 NOP 18 NOP 19 NOP 20 NOP 21 NOP 22 NOP 23 NOP target 24 LOAD CONST 0 (None) 27 RETURN VALUE
  10. How to change bytecodes? Decorator outline (code at http://github.com/cdjc/goto )

    c = fn.__code__ # code object. Not read only :-) c.co_code # bytecode string. Read only :-( Find all labels and gotos in c.co_code NOP all labels. Make gotos into JUMP_ABSOLUTE Make new code object fn.__code__ = new code object return fn
  11. Problems! @goto def infinite(n): label .start for i in ’oops’:

    goto .start At loop-start, python adds a ’block’. At loop-end python does POP_BLOCK Jumping out of a loop must POP_BLOCK before jump. Illegal: Jump into a loop (Segmentation Fault on POP_BLOCK) Jump into/out of try, except, finally, with Multiple identical labels (or missing label) Jump out of loop nested more than four deep.
  12. Performance even odd n += 1 n += 1 Function-based

    state machine within a class Goto-based state machine within a function while loop in plain code The even state breaks at n = 100000000 Python 3.3.1 on Linux VM
  13. Performance (function-based state machine) class state_machine: def even_state(self): ... return

    self.odd_state def odd_state(self): ... return self.even_state def go(): state = self.even_state while state: state = state() 35.0 seconds
  14. Performance (plain while loop) n = 0 while n !=

    limit: n += 1 # even -> odd n += 1 # odd -> even 11.5 seconds
  15. Performance (goto-based state machine) @goto def goto_state_machine(limit): n = 0

    label .state_even ### even_state if n == limit: return n += 1 goto .state_odd ################ label .state_odd ### odd_state n += 1 goto .state_even
  16. Performance (goto-based state machine) @goto def goto_state_machine(limit): n = 0

    label .state_even ### even_state if n == limit: return n += 1 goto .state_odd ################ label .state_odd ### odd_state n += 1 goto .state_even 7.2 seconds! (over 4 seconds faster than a while loop!)
  17. Performance (goto-based state machine) @goto def goto_state_machine(limit): n = 0

    label .state_even ### even_state if n == limit: return n += 1 goto .state_odd ################ label .state_odd ### odd_state n += 1 goto .state_even 7.2 seconds! (over 4 seconds faster than a while loop!) But... while loop inside function: 7.1 seconds. :-(