Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Generate C switch if possible

  • Author: DagSverreSeljebotn, Robert Bradshaw
  • Status: Implemented

This is easily implemented, but then again the gains are probably small in many cases.

StefanBehnel: This is actually non-trivial in a couple of cases, but the gain depends on the C compiler and can be quite noticeable.

The idea is that this code:

#!python
if a == 1:
    BLOCK
elif 2 == a:
    BLOCK
elif a in [3, 4, 5]:
  ...
elif a == 6 or a == 7:
  ...
else:
    BLOCK
can be translated to a C switch statement. The rules are simple, it applies to if-elif-else statements where every clause operates on the same variable (say a), and:
  • a is of a simple ordinal type
  • Either, a is on one side of a == expression, with a compile-time-evaluatable ordinal value on the other side. (Or more clauses like that seperated by or)
  • Or, the variable appears in a in-statement against a compile-time-evaluatable list or tuple containing only ordinal values of the same type.

The C code to generate from this should be obvious. If one of these rules are violated, simply skip transforming the code to a switch statement and leave it as a list of ifs.

(The place where one will see performance gains I think is in the "a in [2,3,4]" part)

Comments

The a in [2,3,4] part could actually be a seperate transform done to all "in-compile-time-evaluatable-to-ordinal-list" expressions, as doing this rewrite:

(a in [x_1, x_2, ...])
=>
(a == x_1 or a == x_2 or ...)

in all situations will always be faster than starting to construct a Python list object and then run through it to check for member variables. (Hmm. Is this true? The list object is created at program startup, and if it is then sorted then a binary search could be used instead. However whenever it is possible to type the list out in source the number of elements are likely so small that the chained == is the right apporach.)

This might already be done? I don't know.

StefanBehnel: Note that deciding that the same variable is used in all cases is not necessarily trivial. Think of the case where an entry in a struct is used ("mystruct.some.entry").

DagSverreSeljebotn: Still, it is possible to demand that the exact same variable is used and not do anything otherwise. This means that if a switch C-side is wanted one has to do

x = mystruct.some.entry
if x == ...

Even being just a little bit smarter, supporting the following, has problems:

if mystruct.some.entry == 1: ...
elif mystruct.some.entry == 2: ...

because fields with property access methods would have to be excluded, potentially being a source of confusing inconsistency (but I'm not sure - can such fields be typed to a native C ordinal type?). Anything looked up within Python objects would have to be excluded of course.

The reason for these problems is that the C switch syntax clearly only does the lookup once, while supporting this latest snippet would mean converting multiple lookups into one lookup which is a more fundamental semantic change than converting a list of if-s to a switch.

I.e., what this draft is about I think is documented behaviour for creating a C switch, rather than a magic optimization, so that at least this time around simply requiring the exact same basic non-looked-up variable will do the trick.

Background

On Mar 12, 2008, at 11:32 AM, Simon Burton wrote:

> > Does anyone know if gcc can optimise a switch done with nested if's
> > as well as it optimises a real switch ? (eg. using computed-gotos)

I did some experiments with this, and the results seemed to indicated
it does not. Also, nested ifs performed poorly compared to a flat
list of ifs (for a medium-sized (5-50) set of conditions).

It would be nice to have some syntax for switch statements. Several
alternatives have been rejected for Python: http://www.python.org/dev/
peps/pep-3103/

- Robert
Something went wrong with that request. Please try again.