Pyrex list/array

[Jim Lewis]

I'm trying to move a function into pyrex for speed. The python side
needs to pass a list to the pyrex function. Do I need to convert to
array or something so pyrex can generate tight code? I'm not clear how
to do this.

[John Machin]

Re: Pyrex list/array

On 4/06/2006 4:56 AM, Jim Lewis wrote:[color=blue]
> I'm trying to move a function into pyrex for speed.[/color]

You probably didn't expect the Inquisition; nobody does. But here it is,
nice red uniforms and all:

1. What is your speed requirement and how far short of that are you at
the moment?
2. Are you sure there is no Python or third-party module that does what
you want?
3. Is your algorithm the best possible?
4. Is your Python implementation of that algorithm the best possible?
Have you exposed it to the critical gaze of the speed-freaks in this
newsgroup?
5. Does your architecture support psyco? If so, have you tried that and
what were the results?
[color=blue]
> The python side
> needs to pass a list to the pyrex function. Do I need to convert to
> array or something so pyrex can generate tight code? I'm not clear how
> to do this.
>[/color]

The question might be better asked on the Pyrex mailing list.

You don't need to convert a list to a C array, and it may not even be
possible, depending on what type(s) of data you have in the list.

Almost any Python code is also valid Pyrex code. For a start, just
compile your function with Pyrex and compare the speed. What you do next
is going to depend very much on what operations you are performing on
the list and the objects it contains. Watch out for Python built-ins
like range, xrange, ord, chr, abs, bool, int(a_number), float(a_number) ,
divmod, max/min (two_numeric_ar gs). In almost all cases you get cheap
wins by replacing use of these by simple C-like code -- provided of
course you are absolutely sure you know what types you are dealing with.

HTH,
John

[Jim Lewis]

Re: Pyrex list/array

Thanks for your comments.
[color=blue]
> You probably didn't expect the Inquisition...[/color]

Correct ;-)
[color=blue]
> 1. What is your speed requirement and how far short of that are you at the moment?[/color]

~10 times faster.
[color=blue]
> 2. Are you sure there is no Python or third-party module that does what you want?[/color]

Yes.
[color=blue]
> 3. Is your algorithm the best possible?[/color]

I think so although of course one can never be certain.
[color=blue]
> 4. Is your Python implementation of that algorithm the best possible? Have you exposed it to the critical gaze of the speed-freaks in this newsgroup?[/color]

Thanks for the good suggestion but I want to try pyrex first.
[color=blue]
> 5. Does your architecture support psyco? If so, have you tried that and what were the results?[/color]

Already using psyco.
[color=blue]
> The question might be better asked on the Pyrex mailing list.[/color]

I did not find it - where is it?
[color=blue]
> Almost any Python code is also valid Pyrex code. For a start, just compile your function with Pyrex and compare the speed.[/color]

It's slower.
[color=blue]
> What you do next is going to depend very much on what operations you are performing on the list and the objects it contains.[/color]

Simple list of ints. Comparing sections of lists between each other.

[skip@pobox.com]

Re: Pyrex list/array

[color=blue][color=green]
>> 5. Does your architecture support psyco? If so, have you tried that
>> and what were the results?[/color][/color]

Jim> Already using psyco.

Is it substantially faster with psyco than without? If psyco is performing
its magic on the critical section of code already, you are going to lose
that when switching to Pyrex.

Skip

[Jim Lewis]

Re: Pyrex list/array

> Is it substantially faster with psyco than without? If psyco is performing[color=blue]
> its magic on the critical section of code already, you are going to lose
> that when switching to Pyrex.[/color]

Yes but from what I read Pyrex can be a lot faster than psyco under the
right circumstances.

[skip@pobox.com]

Re: Pyrex list/array

[color=blue][color=green]
>> Is it substantially faster with psyco than without? If psyco is
>> performing its magic on the critical section of code already, you are
>> going to lose that when switching to Pyrex.[/color][/color]

Jim> Yes but from what I read Pyrex can be a lot faster than psyco under
Jim> the right circumstances.

I'm sure that's true. That also means under the wrong circumstances it
might not. ;-) Can you post the code that's running too slowly?

Also, note that psyco learned some new tricks at the recent NeedForSpeed
sprint. You might want to check out the latest version from Subversion and
give it a whirl.

Skip

[John Machin]

Re: Pyrex list/array

On 4/06/2006 7:59 PM, Jim Lewis wrote:[color=blue]
> Thanks for your comments.
>[color=green]
>> You probably didn't expect the Inquisition...[/color]
>
> Correct ;-)[/color]

Nobody does :-)
[color=blue]
>[color=green]
>> The question might be better asked on the Pyrex mailing list.[/color]
>
> I did not find it - where is it?[/color]

Evidently somewhere near the Hall of the Mountain King. A reference to
it is cunningly concealed in the last place one would think of finding
it: under the heading "Mailing List" on the Pyrex home page :-) Here:
http://lists.copyleft.no/mailman/listinfo/pyrex ... get in quick before
the pirate moves it again.
[color=blue]
>[color=green]
>> Almost any Python code is also valid Pyrex code. For a start, just compile your function with Pyrex and compare the speed.[/color]
>
> It's slower.
>[color=green]
>> What you do next is going to depend very much on what operations you are performing on the list and the objects it contains.[/color]
>
> Simple list of ints. Comparing sections of lists between each other.[/color]

Do you mean alist[x:x+n] == alist[y:y+n] ?
If so, that's creating two new lists each of size n, and then comparing
those two lists. I doubt that psyco would recognize that it didn't need
to copy the two slices. The first step might be to write functions to
compare without copying, e.g.:

def py_slices_cmp_e q(py_list, start1, start2, size):
"""Return 1 if py_list[start1+size] == py_list[start2+size]
else 0"""
offset = start2 - start1
for i in xrange(start1, start1+size):
if py_list[i] != py_list[i+offset]:
return 0
return 1

See what psyco makes of that.
Then turn that into a cdef function for Pyrex.

If that's still not fast enough, then you might be in for some harder work:

Allocate memory for a C array, unpack your list into it, write
comparison functions c_slices_cmp_* that operate on your array of ints.
There should be no Python stuff in there, only C constructs. You can
even use memcmp() for the cmp_eq function.

Which brings us back to your original question "Do I need to convert to
array or something so pyrex can generate tight code?" ...
1. Some of the above may help you to determine whether you need to.
2. Without any knowledge of the size of your list or what you are doing,
we can't help you much more on whether you need to.
3. AFAICT, Pyrex doesn't do much in the way of optimisation, leaving
that up to the C compiler. Generating tight code would depend more on
you replacing appropriately-chosen Pythonisms with C-isms.

As for *how* to make your C array, something like this:

cdef extern from "Python.h":
void PyMem_Free(void *p)
void* PyMem_Malloc(in t n) except NULL
# untested -- compiles OK :-)
cdef int * int_array_from_ list(object ilist):
cdef int n, i
cdef int * arrayp
n = len(ilist)
arrayp = <int *>PyMem_Malloc( n * sizeof(int))
for i from 0 <= i < n:
arrayp[i] = ilist[i]
return &arrayp[0]

Hoping some of this helps,
John

[Jim Lewis]

Re: Pyrex list/array

> cunningly concealed in the last place one would think of finding it: under the heading "Mailing List" on the Pyrex home page :-)

Hmmm - maybe I should try the scroll bar occassionally ;-)
[color=blue]
> Do you mean alist[x:x+n] == alist[y:y+n] ?[/color]

OK, probably you an Skip are right - let's see if I missed something at
the Python level.

There are essentially two differences from your snip above. I am trying
to compute n and there are multiple (under 10) lists. Size of lists are
typically under 100 ints.
[color=blue]
> ...See what psyco makes of that.[/color]

I'm doing a similar straightforward loop approach but it's too slow.

Jim