Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Re: Speed-up for loops

Reply
Thread Tools

Re: Speed-up for loops

 
 
Tim Wintle
Guest
Posts: n/a
 
      09-02-2010
On Thu, 2010-09-02 at 12:02 +0200, Michael Kreim wrote:
> Hi,
>
> I was comparing the speed of a simple loop program between Matlab and
> Python.


> Unfortunately my Python Code was much slower and I do not understand why.


The main reason is that, under the hood, cpython does something like
this (in psudo-code)

itterator = xrange(imax)
while 1:
next_attribute = itterator.next
try:
i = next_attribute()
except:
break
a = a + 10

where C (and I'm assuming matlab) does this:

while 1:
i = i + 1
if (i > imax):
break
a = a + 10

And the function call in the python is fairly expensive on it's own.
Plus it has to do all the standard interpreter stuff for memory
management and deciding when to give up the GIL etc.

> Are there any ways to speed up the for/xrange loop?


leaving it in python, no. (well, "range" is faster in 2.x, but once you
get some cache misses due to increased memory usage it's much slower)

avoiding iteration by using list comprehensions can help a lot though as
it avoids most of the function calls.

If you really need to optimise it then you can convert that module to
cython by adding a cdef, and then compile it:

cdef int i
for i in xrange(imax):
a = a + 10
print a

or you can write it in C it'll run a lot faster.


 
Reply With Quote
 
 
 
 
Carl Banks
Guest
Posts: n/a
 
      09-02-2010
On Sep 2, 5:55*am, Tim Wintle <(E-Mail Removed)> wrote:
> On Thu, 2010-09-02 at 12:02 +0200, Michael Kreim wrote:
> > Hi,

>
> > I was comparing the speed of a simple loop program between Matlab and
> > Python.
> > Unfortunately my Python Code was much slower and I do not understand why.

>
> The main reason is that, under the hood, cpython does something like
> this (in psudo-code)
>
> itterator = xrange(imax)
> while 1:
> * next_attribute = itterator.next
> * try:
> * * i = next_attribute()
> * except:
> * * break
> * a = a + 10
>
> where C (and I'm assuming matlab) does this:
>
> while 1:
> * i = i + 1
> * if (i > imax):
> * * break
> * a = a + 10


Not really. Someone already posted timings of the while-loop version
in Python and it's much slower than the for loop. The iterator stuff
is a minor overhead.

The real reason is simple and boring: many languages optimize loops
like this, Python doesn't.

Matlab has a hundred paid engineers who's job is to optimize it, and
its focus is mathematics, so of course they're going to pull out every
stop to get simple loops like the above as fast as possible.


> And the function call in the python is fairly expensive on it's own.
> Plus it has to do all the standard interpreter stuff for memory
> management and deciding when to give up the GIL etc.


Matlab has all that stuff too (it's memory management is much, much
worse than Python's, in fact, but memory management usually doesn't
play into tight loop timings).


> > Are there any ways to speed up the for/xrange loop?

>
> leaving it in python, no. (well, "range" is faster in 2.x, but once you
> get some cache misses due to increased memory usage it's much slower)
>
> avoiding iteration by using list comprehensions can help a lot though as
> it avoids most of the function calls.


List comprehensions use iteration and don't avoid function calls
relative to equivalent for-loops. I think the main reason they're a
little faster is they can use tighter bytecode.

> If you really need to optimise it then you can convert that module to
> cython by adding a cdef, and then compile it:
>
> cdef int i
> for i in xrange(imax):
> * * *a = a + 10
> print a
>
> or you can write it in C it'll run a lot faster.


numpy is terrific when you can use it, and I've found that it can do a
lot more than most people expect. The hard part is figuring out how.

In particular, numpy will trounce Matlab's performance for large
amounts of data, because of the aforementioned memory management
problem.


Carl Banks
 
Reply With Quote
 
 
 
 
Ulrich Eckhardt
Guest
Posts: n/a
 
      09-03-2010
Tim Wintle wrote:
> [..] under the hood, cpython does something like this (in psudo-code)
>
> itterator = xrange(imax)
> while 1:
> next_attribute = itterator.next
> try:
> i = next_attribute()
> except:
> break
> a = a + 10


There is one thing that strikes me here: The code claims that each iteration
there is a lookup of the 'next' field in the iterator. I would expect that
this is looked up once before the loop only.

Can you confirm that or am I misinterpreting your intention here?

Uli

--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932

 
Reply With Quote
 
Stefan Behnel
Guest
Posts: n/a
 
      09-03-2010
Ulrich Eckhardt, 03.09.2010 08:52:
> Tim Wintle wrote:
>> [..] under the hood, cpython does something like this (in psudo-code)
>>
>> itterator = xrange(imax)
>> while 1:
>> next_attribute = itterator.next
>> try:
>> i = next_attribute()
>> except:
>> break
>> a = a + 10

>
> There is one thing that strikes me here: The code claims that each iteration
> there is a lookup of the 'next' field in the iterator. I would expect that
> this is looked up once before the loop only.
>
> Can you confirm that or am I misinterpreting your intention here?


It needs to do that. Nothing keeps you from redefining "next" in each call.
That's even a well known way to implement state machines.

However, as usual, the details are a bit different in CPython, which has a
C level slot for the "next" method. So the lookup isn't as heavy as it looks.

Stefan

 
Reply With Quote
 
Hrvoje Niksic
Guest
Posts: n/a
 
      09-03-2010
Ulrich Eckhardt <(E-Mail Removed)> writes:

> Tim Wintle wrote:
>> [..] under the hood, cpython does something like this (in psudo-code)
>>
>> itterator = xrange(imax)
>> while 1:
>> next_attribute = itterator.next
>> try:
>> i = next_attribute()
>> except:
>> break
>> a = a + 10

>
> There is one thing that strikes me here: The code claims that each
> iteration there is a lookup of the 'next' field in the iterator. I
> would expect that this is looked up once before the loop only.


It is looked up every time, but the lookup is efficient because "next"
is one of the special methods that have a slot in the C struct that
defines a Python type. A closer code would be something like:

next_function = iterator->ob_type->tp_next;

....which is as fast as it gets. CPython implements this in
Python/ceval.c, just look for FOR_ITER.
 
Reply With Quote
 
Tim Wintle
Guest
Posts: n/a
 
      09-03-2010
On Fri, 2010-09-03 at 08:52 +0200, Ulrich Eckhardt wrote:
> Tim Wintle wrote:
> > [..] under the hood, cpython does something like this (in psudo-code)
> >
> > itterator = xrange(imax)
> > while 1:
> > next_attribute = itterator.next
> > try:
> > i = next_attribute()
> > except:
> > break
> > a = a + 10

>
> There is one thing that strikes me here: The code claims that each iteration
> there is a lookup of the 'next' field in the iterator. I would expect that
> this is looked up once before the loop only.
>
> Can you confirm that or am I misinterpreting your intention here?


As Stefan and Hrvoje have posted, there is a lookup - but in 2.4 and
above it's straight off the C structure and compiled efficiently.

(I've been looking at 2.3's source recently and had forgotten the
optimisation)

Tim



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Multiple For Loops? pinod01@sympatico.ca VHDL 1 02-22-2006 03:10 PM
Etherchannel disabled = spanning tree loops... traust Cisco 0 02-21-2006 05:34 PM
Loops with loops using html-template Me Perl Misc 2 01-12-2006 05:07 PM
Perl loops should use break, not last Jeremy Morton Perl 1 01-30-2005 10:50 PM
to many FOR loops? eismaus4 VHDL 1 04-27-2004 02:54 PM



Advertisments