Rejection Notice

A similar PEP for Python 3000, PEP 3103, was already rejected, so this proposal has no chance of being accepted either.

Abstract

This PEP proposes strategies to enhance Python’s performance with respect to handling switching on a single variable having one of multiple possible values.

Problem

Up to Python 2.5, the typical way of writing multi-value switches has been to use long switch constructs of the following type:

if x == 'first state':
    ...
elif x == 'second state':
    ...
elif x == 'third state':
    ...
elif x == 'fourth state':
    ...
else:
    # default handling
    ...

This works fine for short switch constructs, since the overhead of repeated loading of a local (the variable x in this case) and comparing it to some constant is low (it has a complexity of O(n) on average). However, when using such a construct to write a state machine such as is needed for writing parsers the number of possible states can easily reach 10 or more cases.

The current solution to this problem lies in using a dispatch table to find the case implementing method to execute depending on the value of the switch variable (this can be tuned to have a complexity of O(1) on average, e.g. by using perfect hash tables). This works well for state machines which require complex and lengthy processing in the different case methods. It does not perform well for ones which only process one or two instructions per case, e.g.

def handle_data(self, data):
    self.stack.append(data)

A nice example of this is the state machine implemented in pickle.py which is used to serialize Python objects. Other prominent cases include XML SAX parsers and Internet protocol handlers.

Proposed Solutions

This PEP proposes two different but not necessarily conflicting solutions:

1. Adding an optimization to the Python compiler and VM which detects the above if-elif-else construct and generates special opcodes for it which use a read-only dictionary for storing jump offsets.
2. Adding new syntax to Python which mimics the C style switch statement.

The first solution has the benefit of not relying on adding new keywords to the language, while the second looks cleaner. Both involve some run-time overhead to assure that the switching variable is immutable and hashable.

Both solutions use a dictionary lookup to find the right jump location, so they both share the same problem space in terms of requiring that both the switch variable and the constants need to be compatible to the dictionary implementation (hashable, comparable, a==b => hash(a)==hash(b)).

if x == 'first':...
elif x == 'second':...
else:...

switch EXPR:
    case CONSTANT:
        SUITE
    case CONSTANT:
        SUITE
    ...
    else:
        SUITE

def whatis(x):
    switch(x):
        case 'one':
            print '1'
        case 'two':
            print '2'
        case 'three':
            print '3'
        else:
            print "D'oh!"

   6  LOAD_FAST         0 (x)
   9  LOAD_CONST        1 (switch-table-1)
  12  SWITCH            26 (to 38)

  14  LOAD_CONST        2 ('1')
  17  PRINT_ITEM
  18  PRINT_NEWLINE
  19  JUMP 43

  22  LOAD_CONST        3 ('2')
  25  PRINT_ITEM
  26  PRINT_NEWLINE
  27  JUMP 43

  30  LOAD_CONST        4 ('3')
  33  PRINT_ITEM
  34  PRINT_NEWLINE
  35  JUMP 43

  38  LOAD_CONST        5 ("D'oh!")
  41  PRINT_ITEM
  42  PRINT_NEWLINE

>>43  LOAD_CONST        0 (None)
  46  RETURN_VALUE

case EXPR:
    of CONSTANT:
        SUITE
    of CONSTANT:
        SUITE
    else:
        SUITE

case EXPR:
    if CONSTANT:
         SUITE
    if CONSTANT:
        SUITE
    else:
        SUITE

when EXPR:
    in CONSTANT_TUPLE:
        SUITE
    in CONSTANT_TUPLE:
        SUITE
    ...
else:
     SUITE

switch EXPR:                   switch x:
    case CONSTANT:                 case "first":
        SUITE                          print x
    case CONSTANT:                 case "second":
        SUITE                          x = x**2
    ...                                print x
    else:                          else:
        SUITE                          print "whoops!"


case EXPR:                     case x:
    of CONSTANT:                   of "first":
        SUITE                          print x
    of CONSTANT:                   of "second":
        SUITE                          print x**2
    else:                          else:
        SUITE                          print "whoops!"


case EXPR:                     case state:
    if CONSTANT:                   if "first":
         SUITE                         state = "second"
    if CONSTANT:                   if "second":
        SUITE                          state = "third"
    else:                          else:
        SUITE                          state = "first"


when EXPR:                     when state:
    in CONSTANT_TUPLE:             in ("first", "second"):
        SUITE                          print state
    in CONSTANT_TUPLE:                 state = next_state(state)
        SUITE                      in ("seventh",):
    ...                                print "done"
else:                                  break    # out of loop!
     SUITE                     else:
                                   print "middle state"
                                   state = next_state(state)

switch type(x).__name__:
    case 'int':
        SUITE
    case 'string':
        SUITE

Scope

XXX Explain “from __future__ import switch”

Credits

• Martin von Löwis (issues with the optimization idea)
• Thomas Wouters (switch statement + byte code compiler example)
• Skip Montanaro (dispatching ideas, examples)
• Donald Beaudry (switch syntax)
• Greg Ewing (switch syntax)
• Jack Jansen (type switching examples)

References

Copyright

This document has been placed in the public domain.