Re: [Cython] switch statement

On Mar 13, 2008, at 1:55 AM, Stefan Behnel wrote:

> Hi,
>
> Robert Bradshaw top-posted:
>> 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 indicate
>> it does not. Also, nested ifs performed poorly compared to a flat
>> list of ifs (for a medium-sized (5-50) set of conditions).
>
> Interesting. Does that also hold for boolean "and/or" expressions?  
> Cython
> translates those to nested ifs. (I guess that's difficult to  
> compare, though,
> as it short-circuits.)

The thing about Cython's nested ifs is that (in Python) the cost of  
evaluating the truth statement is non-trivial (e.g. a function call  
at least), so short-circuits are nearly always a gain. Because the  
statements may have side effects, this is mandatory to enforce.

>> 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/
>
> That's because they have Python semantics, not C semantics.  
> Python's language
> semantics make it a bit harder to come up with a meaningful  
> "switch" design
> than a plain C language "check this integer value against a list of  
> other
> integers" switch statement.
>
> Regarding syntax: my opinion on this is that we should just do  
> without any new
> syntax, take our cool plugin optimiser infrastructure and just  
> replace the
> most obvious
>
>     if c_int_val == 1:
>         code1()
>     elif c_int_val == 2:
>         code2()
>     elif c_int_val == some_other_constant_c_int:
>         code3()
>     else:
>         code4()
>
> by a straight C switch statement. No special casing if it involves  
> variable
> values, Python values, or otherwise non compile-time known values  
> (i.e. DEF is
> allowed), or any other comparison operators than "==". Just an  
> optimisation
> for the most simple case that a C switch statement can handle:
>
> - if-elif-else chain with exactly one operator at each step: '=='
>   -> decidable right after parsing (or even in the parser)
> - lhs always the same plain C integer variable
>   -> "same name" decidable right after parsing, "type" after type  
> annalysis
> - rhs a compile-time constant C integer value
>   -> "type" decidable after type annalysis
>
> This should be easy and fast enough to decide.
>
> That way, people can decide what trade-off between Python semantics  
> and
> optimisation they want. And if we find more cases that we can  
> support, we can
> improve the plugin instead of the syntax.

Dag Sverre wrote a similar writeup: http://wiki.cython.org/ 
enhancements/switch . I think it's a good idea. For small lists the  
savings will be minimal, but for larger ones there can be significant  
gains.

- Robert