gmane.comp.python.cython.devel

[Cython] Boundchecking question

I've been playing with the (very cool!) buffer stuff Dag did getting  
ready for the SciPy conference. I've seen a 20% increase in speed not  
adjusting for negative indices, but making sure the indices are  
unsigned is a pain (especially if there is arithmetic involved). One  
proposal that has been brought up is to make positive integer  
constants unsigned, which could lead to complications elsewhere and  
would still require care. Another proposal that I'd like to throw out  
there is to have negative index realigning part of bounds checking,  
i.e. negative indices are not checked for if bounds checking is off.

Thoughts?

- Robert

headers

Dag Sverre Seljebotn | 17 Aug 09:19

Re: [Cython] Boundchecking question

I'm not sure what you mean -- a negative bound is only checked for once per dimension. I.e. Positive ints are
only checked for negativity once per dim.

(Remember that one must also check for the negative bound, i.e. -n, but this is only done for negative numbers).

There is potential for optimizing the exceptional case when bounds are off (but the code would be a little
less clean and exceptional cases are just that).

Could you perhaps post some C code modified as you suggest?

Finally, if what you propose is a change in semantics, then this already met resistance on the numpy list.
Perhaps a buffer-unsigned-indices-only compiler directive.

(However I think that it is possible to write your code using unsigneds so that you use unsigned everywhere
instead of signed, and then this comes automatically...)

I don't care too much about constants, they're not likely to be used in performance critical code I think.

Dag Sverre Seljebotn
-----Original Message-----
From: Robert Bradshaw <robertwb@...>
Date: Sunday, Aug 17, 2008 6:55 am
Subject: [Cython] Boundchecking question
To: Cython-dev <cython-dev@...>Reply-To: cython-dev@...

I've been playing with the (very cool!) buffer stuff Dag did getting  
>ready for the SciPy conference. I've seen a 20% increase in speed not  
>adjusting for negative indices, but making sure the indices are  
>unsigned is a pain (especially if there is arithmetic involved). One  
>proposal that has been brought up is to make positive integer

(Continue reading)

headers

Robert Bradshaw | 17 Aug 10:11

Re: [Cython] Boundchecking question

On Aug 17, 2008, at 12:23 AM, Dag Sverre Seljebotn wrote:

> I'm not sure what you mean -- a negative bound is only checked for  
> once per dimension. I.e. Positive ints are only checked for  
> negativity once per dim.
>
> (Remember that one must also check for the negative bound, i.e. -n,  
> but this is only done for negative numbers).

I am talking about the case where bounds checking is turned off, and  
"once per dimension" is relatively expensive. Even when it predicts  
correctly it still does the test. I've got some code using 2D buffers  
in the inner loop. Here's the timings:

CPU time: 1.50 s,  Wall time: 1.52 s -- standard buffers
CPU time: 1.00 s,  Wall time: 1.01 s -- boundscheck=False
CPU time: 0.77 s,  Wall time: 0.78 s -- unsigned indices

(Note, I'm not even going to time the non-buffer version, but its  
certainly on the order of minutes--buffers are awsome!).

> There is potential for optimizing the exceptional case when bounds  
> are off (but the code would be a little less clean and exceptional  
> cases are just that).
>
> Could you perhaps post some C code modified as you suggest?

Essentially it's the C code one gets if one manually casts the  
indices to unsigned ints. It's just that that makes the code  
significantly uglier.

(Continue reading)

headers

Carl Witty | 17 Aug 18:36

Re: [Cython] Boundchecking question

On Sun, Aug 17, 2008 at 1:11 AM, Robert Bradshaw
<robertwb@...> wrote:
> Constants will be optimized away. But if I write "i+1" where i is an
> unsigned int, the result is still signed.

Are you talking about Cython or C here?  In C, if i is an unsigned
int, then i+1 is also an unsigned int.  If that's not the case in
Cython, I think it should be changed to match C.

Carl

headers

Robert Bradshaw | 18 Aug 19:28

Re: [Cython] Boundchecking question

On Sun, 17 Aug 2008, Carl Witty wrote:

> On Sun, Aug 17, 2008 at 1:11 AM, Robert Bradshaw
> <robertwb@...> wrote:
>> Constants will be optimized away. But if I write "i+1" where i is an
>> unsigned int, the result is still signed.
>
> Are you talking about Cython or C here?  In C, if i is an unsigned
> int, then i+1 is also an unsigned int.  If that's not the case in
> Cython, I think it should be changed to match C.

Ah, so in C, signed ints get promoted to unsigned ints. Interesting. 
Cython should be fixed to reflect this, and this will make declaring 
indices non-negative much easier (though I'm not going to do that until 
next release as there may be unintended side effects).

- Robert

headers

Dag Sverre Seljebotn | 17 Aug 09:57

Re: [Cython] Boundchecking question

ah, arithmetic on the indices. Yes, that is a bit inconvenient.

Another thing you could try in your tests is tuning branch prediction (unlikely(...))..

Dag Sverre Seljebotn
-----Original Message-----
From: "Dag Sverre Seljebotn" <dagss@...>
Date: Sunday, Aug 17, 2008 9:26 am
Subject: Re: [Cython] Boundchecking question
To: <cython-dev@...>Reply-To: cython-dev@...

I'm not sure what you mean -- a negative bound is only checked for once per dimension. I.e. Positive ints are
only checked for negativity once per dim.
>
>(Remember that one must also check for the negative bound, i.e. -n, but this is only done for negative numbers).
>
>There is potential for optimizing the exceptional case when bounds are off (but the code would be a little
less clean and exceptional cases are just that).
>
>Could you perhaps post some C code modified as you suggest?
>
>Finally, if what you propose is a change in semantics, then this already met resistance on the numpy list.
Perhaps a buffer-unsigned-indices-only compiler directive.
>
>(However I think that it is possible to write your code using unsigneds so that you use unsigned everywhere
instead of signed, and then this comes automatically...)
>
>I don't care too much about constants, they're not likely to be used in performance critical code I think.
>
>Dag Sverre Seljebotn

(Continue reading)

headers

Dag Sverre Seljebotn | 17 Aug 10:06

Re: [Cython] Boundchecking question

Sorry about all the posts, but I just now realized what you are saying....

well:
- I write an algorithm where I don't care about speed and use negative indices
- someone else takes it and turns off bounds checking as it doesn't raise any indexerrors, so "why not"?
- poof!

I think this would be very obscure. The recipe people would tend to follow seems to be "run with bounds
checking on, if all the tests pass then you can turn it off". This would break that way of working.

I vote for a new compiler directive to do this, and then a new higher-level directive including both this and
bounds checking. Alternatively, a buffer option allow_negative which is set to True by default.

Dag Sverre Seljebotn
-----Original Message-----
From: Robert Bradshaw <robertwb@...>
Date: Sunday, Aug 17, 2008 6:55 am
Subject: [Cython] Boundchecking question
To: Cython-dev <cython-dev@...>Reply-To: cython-dev@...

I've been playing with the (very cool!) buffer stuff Dag did getting  
>ready for the SciPy conference. I've seen a 20% increase in speed not  
>adjusting for negative indices, but making sure the indices are  
>unsigned is a pain (especially if there is arithmetic involved). One  
>proptosal that has been brought up is to make positive integer  
>constants unsigned, which could lead to complications elsewhere and  
>would still require care. Another proposal that I'd like to throw out  
>there is to have negative index realigning part of bounds checking,  
>i.e. negative indices are not checked for if bounds checking is off.
>

(Continue reading)

headers

Robert Bradshaw | 17 Aug 10:15

Re: [Cython] Boundchecking question

On Aug 17, 2008, at 1:08 AM, Dag Sverre Seljebotn wrote:

> Sorry about all the posts, but I just now realized what you are  
> saying....
>
> well:
> - I write an algorithm where I don't care about speed and use  
> negative indices
> - someone else takes it and turns off bounds checking as it doesn't  
> raise any indexerrors, so "why not"?
> - poof!
>
> I think this would be very obscure. The recipe people would tend to  
> follow seems to be "run with bounds checking on, if all the tests  
> pass then you can turn it off". This would break that way of working.

Yep, certainly.

> I vote for a new compiler directive to do this, and then a new  
> higher-level directive including both this and bounds checking.  
> Alternatively, a buffer option allow_negative which is set to True  
> by default.

My conclusion too. I still think we should put the option in a  
buffers namespace. "Flat is better than nested." vs "Namespaces are  
one honking great idea -- let's do more of those!" But the pragma  
doesn't turn of bounds checking for, other objects, e.g. tuples and  
lists (which could be nice to do).

- Robert

(Continue reading)

headers

Dag Sverre Seljebotn | 17 Aug 10:14

Re: [Cython] Boundchecking question

On boundscheck, I'm thinking that it means "make the assumption that this code will not raise an
IndexError". That's it.

(And I think it should apply to lists and tuples as well if possible.

(One could add a more fine-grained buffer_bounds_check too then, of course. Or "boundscheck = all",
"boundscheck=None", "boundscheck = list,buffer"). But let's leave that for now, we can be backwards
compatible later.

Dag Sverre Seljebotn
-----Original Message-----
From: Robert Bradshaw <robertwb@...>
Date: Sunday, Aug 17, 2008 10:11 am
Subject: Re: [Cython] Boundchecking question
To: cython-dev@...: cython-dev@...

On Aug 17, 2008, at 12:23 AM, Dag Sverre Seljebotn wrote:
>
>> I'm not sure what you mean -- a negative bound is only checked for  
> once per dimension. I.e. Positive ints are only checked for  
> negativity once per dim.
>
>> (Remember that one must also check for the negative bound, i.e. -n,  
> but this is only done for negative numbers).
>
>I am talking about the case where bounds checking is turned off, and  
>"once per dimension" is relatively expensive. Even when it predicts  
>correctly it still does the test. I've got some code using 2D buffers  
>in the inner loop. Here's the timings:
>

(Continue reading)