Re: [cython-users] if condition transformation to switch-case

[Stefan Behnel]

Alok Singhal, 11.05.2013 22:52:
> Consider the following code:
>
> cdef extern from "errno.h":
> enum:
> EWOULDBLOCK
> EAGAIN
>
> cdef int is_eagain(int i):
> return i != EWOULDBLOCK and i != EAGAIN
>
> The code checks for EWOULDBLOCK and EAGAIN both, although they could be the
> same (on linux for example). This is mostly done for portability (for
> example, see the "Portability note" at
> http://www.gnu.org/savannah-checkouts/gnu/libc/manual/html_node/Error-Codes.html#index-EAGAIN-97
> ).
>
> Cython transforms the above code to:
>
> switch (__pyx_v_i) {
> case EWOULDBLOCK:
> case EAGAIN:
> __pyx_t_1 = 0;
> break;
> default:
> __pyx_t_1 = 1;
> break;
> }
>
> If EWOULDBLOCK == EAGAIN, this results in compilation error since the two
> case labels are the same.

Interesting corner case.


> For my immediate use, I changed my code to only test for EAGAIN, but is
> there a better way to write the code so that I can still use both
> EWOULDBLOCK and EAGAIN?

You can write

if i == EWOULDBLOCK:
return True
return i == EAGAIN

or any other paraphrases of the same thing that involves separate tests for
both enum values.

I would also suggest changing the return type of the function to "bint",
which makes it return True/False if you call it in a Python context.

Stefan

[Lisandro Dalcin]

I've also had problems with the switch optimization, but some <int>
casting helped me to disable it:
https://code.google.com/p/mpi4py/source/browse/src/MPI/commimpl.pxi#170

I think Cython should have a compiler directive to disable this
optimization. After all, enumeration values in C do not need to be
different:

$ cat enum.c
enum { A=0, B=0, C=0 };
$ gcc -Wall -c enum.c
<no output>


--
Lisandro Dalcin
---------------
CIMEC (INTEC/CONICET-UNL)
Predio CONICET-Santa Fe
Colectora RN 168 Km 472, Paraje El Pozo
3000 Santa Fe, Argentina
Tel: +54-342-4511594 (ext 1011)
Tel/Fax: +54-342-4511169

[Nathaniel Smith]

On 12 May 2013 09:59, "Lisandro Dalcin" <dal...@gmail.com> wrote:
>
> I've also had problems with the switch optimization, but some <int>
> casting helped me to disable it:
> https://code.google.com/p/mpi4py/source/browse/src/MPI/commimpl.pxi#170
>
> I think Cython should have a compiler directive to disable this
> optimization. After all, enumeration values in C do not need to be
> different:
>
> $ cat enum.c
> enum { A=0, B=0, C=0 };
> $ gcc -Wall -c enum.c
> <no output>

Is this really even an optimization? Or well, I guess technically an optimization is something that produces identical behaviour so obviously it fails in that sense, but I mean, in what circumstance is it even faster? C compilers can trivially optimize a simple chain of integer comparisons.

-n

[Stefan Behnel]

Nathaniel Smith, 12.05.2013 16:24:

I don't know, and I don't dare to guess. It's quite possible that there is
no advantage in the SwitchTransform. There definitely is an advantage in
having Cython transform complex tests into simple integer comparisons,
though, e.g.

cdef int x = get_value()
if x in b'abc\n\t':
print("found in some character values")
elif x in (42,43,44):
print("found in some integer values")
elif x in (ENUM_VALUE_1, ENUM_VALUE_2):
print("found in some enum values")
elif x == ENUM_VALUE_3:
print("found exact enum value")
else:
print("not found")

Currently, this will give you a single switch statement. If someone has the
time to do some tests, it would be interesting to see if the bare chain of
nested C if statements results in the same native code. Bonus points for
investigating different C compilers.

Stefan

[Nathaniel Smith]

Agreed that strength-reducing complicated operations to integer
comparisons is an obvious win, but I'm still pretty skeptical about
this switch transformation :-). I guess the question is, which is
worse: losing a tiny micro-optimization that only even matters at all
on some compilers, or keeping the micro-optimization but breaking
multiple people's perfectly valid code?

-n

[Robert Bradshaw]

Let's see some data.

> or keeping the micro-optimization but breaking
> multiple people's perfectly valid code?

+1 to a directive to disable it in the meantime at the very least.

- Robert

[Robert Bradshaw]

​I'm still in favor of a directive to disable this, and possibly higher thresholds, but I just did some simple benchmarks which show pretty clearly that the chained if clauses have degrading performance (at least for the specific toolchain I used, gcc on the sage math cloud). It is pretty inconclusive until one gets to dozens of cases though (which is less common but something I've still run into a number of times in performance critical loops, e.g. parsers and interpreters).

- Robert

---------------------------------------------

import cython

import random

import time

def shuffle(L):

    L = list(L)

    random.shuffle(L)

    return L

def create_benchmark(nvalues, nstats=None, switch=True):

    if nstats is None:

        nstats = nvalues

    to_add = shuffle(range(nstats))

    cases = []

    for k in range(nstats):

        cases.append("elif %s: x += %s" % (' or '.join('x == %s' % t for t in range(k*nvalues/nstats, (k+1)*nvalues/nstats)), to_add[k]))

    cases[0] = cases[0][2:]

    if not switch:

        cases.append("elif x*x < x + 10: x += 1  # will never reach here")

    return """

def foo(int x, int times):

    cdef int _

    for _ in range(times):

        %(cases)s

        if x >= %(n)s:

            x -= %(n)s

    return x

""" % {'n': nvalues, 'cases': '\n        '.join(cases)};

def create_benchmark_func(*args):

    return cython.inline(create_benchmark(*args) + "\nreturn foo", x=int(0), times=int(0))

def time_benchmark(*args):

    func = create_benchmark_func(*args)

    times = []

    for _ in range(10):

        t = time.time()

        func(1, 1e7)

        times.append(time.time() - t)

    return min(times)

[Alok Singhal]

I did the same benchmark as yours but with a patch to Cython that has the directive to disable switch transform (https://github.com/cython/cython/pull/287).  So I didn't need the extra "if not switch:..." condition in your benchmark.

I get similar results as you.  So I think having a directive might be the best option for now.

--

---
You received this message because you are subscribed to the Google Groups "cython-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cython-users...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Andreas van Cranenburgh]

I am a bit puzzled by the decision to enable the switch transform by default (as the latest CHANGES.rst says).
Previously, code was posted that showed it can lead to Cython producing incorrect code.
Now, benchmarks are published showing that in the common case of a small number of conditions, if-statements are more efficient.
The threshold in SwitchTransform seems to be to transform any if-statement with 2 or more conditions.

Wouldn't it be better to disable use_switch by default, or at least have a conservative threshold of >10 conditions?

[Alok Singhal]

+1. The default should lean toward correctness, even if it means slow
code. For code that needs this transform, it's easy to add the
directive.

-Alok

[Stefan Behnel]

Alok Singhal, 04.05.2014 02:12:

> On Sat, May 3, 2014 at 7:12 AM, Andreas van Cranenburgh wrote:
>> I am a bit puzzled by the decision to enable the switch transform by default
>> (as the latest CHANGES.rst says).
>> Previously, code was posted that showed it can lead to Cython producing
>> incorrect code.
>> Now, benchmarks are published showing that in the common case of a small
>> number of conditions, if-statements are more efficient.
>> The threshold in SwitchTransform seems to be to transform any if-statement
>> with 2 or more conditions.
>>
>> Wouldn't it be better to disable use_switch by default, or at least have a
>> conservative threshold of >10 conditions?
>
> +1. The default should lean toward correctness, even if it means slow
> code. For code that needs this transform, it's easy to add the
> directive.

Well, it's always safe for integers, so we could still keep it as it is for
all-integer values, but I agree that we should change the default for enums
and other names (although that's likely a very common case).

Also, I think it's worth investigating if there isn't a way to generate
better performing code for if-statements in general. The current nesting
and temporary value setting may just be making it unnecessarily hard for
the C compiler to recognise an optimisable case.

Stefan