[Python-Dev] PEP 275: "Switching on Multiple Values", Rev 1.1 (original) (raw)

Mon, 12 Nov 2001 10:19:12 +0100

This PEP proposes strategies to enhance Python's performance
with respect to handling switching on a single variable having
one of multiple possible values.
Up to Python 2.2, the typical way of writing multi-value switches=20
has been to use long switch constructs of the following type:

if x =3D=3D 'first state':
    ...
elif x =3D=3D 'second state':
    ...
elif x =3D=3D 'third state':
    ...
elif x =3D=3D '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)
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 an 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.
 XXX This section currently only sketches the design.=20

 Issues:

     The new optimization should not change the current Python
     semantics (by reducing the number of __cmp__ calls and adding
     __hash__ calls in if-elif-else constructs which are affected
     by the optimiztation). To assure this, switching can only
     safely be implemented either if a "from __future__" style
     flag is used, or the switching variable is one of the builtin
     immutable types: int, float, string, unicode, etc. (not
     subtypes, since it's not clear whether these are still
     immutable or not)

     To prevent post-modifications of the jump-table dictionary
     (which could be used to reach protected code), the jump-table
     will have to be a read-only type (e.g. a read-only
     dictionary).

     The optimization should only be used for if-elif-else
     constructs which have a minimum number of n cases (where n is
     a number which has yet to be defined depending on performance
     tests).

 Implementation:

     It should be possible for the compiler to detect an
     if-elif-else construct which has the following signature:

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

     i.e. the left hand side always references the same variable,
     the right hand side a hashable immutable builtin type.  The
     right hand sides need not be all of the same type, but they
     should be comparable to the type of the left hand switch
     variable.

     The compiler could then setup a read-only (perfect) hash
     table, store it in the constants and add an opcode SWITCH in
     front of the standard if-elif-else byte code stream which
     triggers the following run-time behaviour:

     At runtime, SWITCH would check x for being one of the
     well-known immutable types (strings, unicode, numbers) and
     use the hash table for finding the right opcode snippet. If
     this condition is not met, the interpreter should revert to
     the standard if-elif-else processing by simply skipping the
     SWITCH opcode and procedding with the usual if-elif-else byte
     code stream.
 XXX This section currently only sketches the design.

 Syntax:

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

     (modulo indentation variations)

     The "else" part is optional. If no else part is given and
     none of the defined cases matches, a ValueError is raised.

 Implementation:

     The compiler would have to compile this into byte code
     similar to this:

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

     into (ommitting POP_TOP's and SET_LINENO's):

       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
   =20
    Where the 'SWITCH' opcode would jump to 14, 22, 30 or 38
    depending on 'x'.

Issues:

    The switch statement should not implement fall-through
    behaviour (as does the switch statement in C). Each case
    defines a complete and independent suite; much like in a
    if-elif-else statement. This also enables using break in
    switch statments inside loops.

    If the interpreter finds that the switch variable x is
    not hashable, it should raise a TypeError at run-time
    pointing out the problem.

    There have been other proposals for the syntax which reuse
    existing keywords and avoid adding two new ones ("switch" and
    "case"). Others have argued that the keywords should use new
    terms to avoid confusion with the C keywords of the same name
    but slightly different semantics (e.g. fall-through without
    break). Some of the proposed variants:

        case EXPR:
            of CONSTANT:
                SUITE =20
            of CONSTANT:
                SUITE =20
            else:
                SUITE =20

        case EXPR:
            if CONSTANT:
                 SUITE =20
            if CONSTANT:
                SUITE =20
            else:
                SUITE =20

        when EXPR:
            in CONSTANT_TUPLE:
                SUITE =20
            in CONSTANT_TUPLE:
                SUITE =20
            ...
        else:
             SUITE =20
   =20
    The switch statement could be extended to allow tuples of
    values for one section (e.g. case 'a', 'b', 'c': ...). Another
    proposed extension would allow ranges of values (e.g. case
    10..14: ...). These should probably be post-poned, but already
    kept in mind when designing and implementing a first version.

Examples:

     switch EXPR:                   switch x:
         case CONSTANT:                 case "first":
             SUITE                          print x
         case CONSTANT:                 case "second":
             SUITE                          x =3D 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 =3D "second"
         if CONSTANT:                   if "second":
             SUITE                          state =3D "third"
         else:                          else:
             SUITE                          state =3D "first"

     when EXPR:                     when state:
         in CONSTANT_TUPLE:             in ("first", "second"):
             SUITE                          print state
         in CONSTANT_TUPLE:                 state =3D
 XXX Explain "from __future__ import switch"
Martin von L=F6wis (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)
This document has been placed in the public domain.