Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

Speed-up for loops

 
 
Michael Kreim
Guest
Posts: n/a
 
      09-02-2010
Hi,

I was comparing the speed of a simple loop program between Matlab and
Python.

My Codes:
$ cat addition.py
imax = 1000000000
a = 0
for i in xrange(imax):
a = a + 10
print a

$ cat addition.m
imax = 1e9;
a = 0;
for i=0:imax-1
a = a + 10;
end
disp(a);
exit;

The results look like this:
$ /usr/bin/time --verbose python addition.py
10000000000
Command being timed: "python addition.py"
User time (seconds): 107.30
System time (seconds): 0.08
Percent of CPU this job got: 97%
Elapsed (wall clock) time (h:mm:ss or m:ss): 1:50.09
[...]

$ /usr/bin/time --verbose matlab -nodesktop -nosplash -r "addition"
[...]
1.0000e+10
Command being timed: "matlab -nodesktop -nosplash -r addition"
User time (seconds): 7.65
System time (seconds): 0.18
Percent of CPU this job got: 94%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:08.25
[...]

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

Are there any ways to speed up the for/xrange loop?
Or do I have to live with the fact that Matlab beats Python in this example?

Thanks a lot for your answers.

With best regards,

Michael
 
Reply With Quote
 
 
 
 
Peter Otten
Guest
Posts: n/a
 
      09-02-2010
Michael Kreim wrote:

> I was comparing the speed of a simple loop program between Matlab and
> Python.
>
> My Codes:
> $ cat addition.py
> imax = 1000000000
> a = 0
> for i in xrange(imax):
> a = a + 10
> print a


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


Move it into a function; this turns a and i into local variables.

def f():
imax = 1000000000
a = 0
for i in xrange(imax):
a = a + 10
print a
f()

> Or do I have to live with the fact that Matlab beats Python in this
> example?


I think so.
 
Reply With Quote
 
 
 
 
Michael Kreim
Guest
Posts: n/a
 
      09-02-2010
Peter Otten wrote:
> Move it into a function; this turns a and i into local variables.
>
> def f():
> imax = 1000000000
> a = 0
> for i in xrange(imax):
> a = a + 10
> print a
> f()


Wow. It is still slower than Matlab, but your suggestion speeds up the
code by ca 50%.
But I do not understand why the change of a global to a local variable
gives such a big difference.


$ cat addition.py
imax = 1000000000
a = 0
for i in xrange(imax):
a = a + 10
print a

$ cat additionOtten.py
def f():
imax = 1000000000
a = 0
for i in xrange(imax):
a = a + 10
print a
f()

$ /usr/bin/time --verbose python addition.py
10000000000
Command being timed: "python addition.py"
User time (seconds): 110.52
System time (seconds): 0.01
Percent of CPU this job got: 98%
Elapsed (wall clock) time (h:mm:ss or m:ss): 1:52.76
[...]

$ /usr/bin/time --verbose python additionOtten.py
10000000000
Command being timed: "python additionOtten.py"
User time (seconds): 56.38
System time (seconds): 0.00
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:56.64
[...]
 
Reply With Quote
 
Peter Otten
Guest
Posts: n/a
 
      09-02-2010
Michael Kreim wrote:

> Peter Otten wrote:
>> Move it into a function; this turns a and i into local variables.
>>
>> def f():
>> imax = 1000000000
>> a = 0
>> for i in xrange(imax):
>> a = a + 10
>> print a
>> f()

>
> Wow. It is still slower than Matlab, but your suggestion speeds up the
> code by ca 50%.
> But I do not understand why the change of a global to a local variable
> gives such a big difference.


Basically the local namespace is a C array where accessing an item is just
pointer arithmetic while the global namespace is a Python dictionary.

There may be optimisations for the latter. If you can read C have a look at
the LOAD/STORE_FAST and LOAD/STORE_GLOBAL implementations for the gory
details:

http://svn.python.org/view/python/tr....c?view=markup

Peter

 
Reply With Quote
 
Hrvoje Niksic
Guest
Posts: n/a
 
      09-02-2010
Michael Kreim <(E-Mail Removed)> writes:

> Are there any ways to speed up the for/xrange loop?
> Or do I have to live with the fact that Matlab beats Python in this
> example?


To a point, yes. However, there are things you can do to make your
Python code go faster. One has been pointed out by Peter.

Another is that Python treats numbers as regular heap objects, so
creating a bunch of unneeded integers by xrange slows things down
(despite allocation of integer objects being heavily optimized). For
this reason, you may want to change xrange(1000000000) to
itertools.repeat(None, 1000000000).

$ python -m timeit -s 'from itertools import repeat' 'for _ in repeat(None, 100000): pass'
1000 loops, best of 3: 1.71 msec per loop
$ python -m timeit -s 'from itertools import repeat' 'for _ in xrange(100000): pass'
100 loops, best of 3: 2.43 msec per loop
 
Reply With Quote
 
Nobody
Guest
Posts: n/a
 
      09-02-2010
On Thu, 02 Sep 2010 12:02:40 +0200, Michael Kreim wrote:

> I was comparing the speed of a simple loop program between Matlab and
> Python.


> imax = 1000000000
> a = 0
> for i in xrange(imax):
> a = a + 10
> print a


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


Sure; the above can be reduced to just:

print imax * 10


More seriously, if you're comparing against Matlab, you should look at
NumPy. If there's a reasonably direct approach using NumPy, it will be
much quicker than a Python "for" loop (in a sense, NumPy is a library of
useful "for" loops implemented in C).

Even a fairly indirect NumPy approach is often quicker than pure Python.

 
Reply With Quote
 
Philip Bloom
Guest
Posts: n/a
 
      09-02-2010
Uh.

Try:
Imax=1000000000
a=0
i=0
While(i<imax):
a= a+10
i=i+1
print a

I suspect you will find it is way faster than using range or xrange for
large numbers and map far more closely in the final result to what you
are doing on matlab's side. At least last I checked, xrange and range
both involve iterating through an array, which is much slower in all
cases than just doing an int vs int compare (which is what your matlab
is doing).

-----Original Message-----
From: python-list-bounces+pbloom=(E-Mail Removed)
[mailtoython-list-bounces+pbloom=(E-Mail Removed)] On Behalf Of
Nobody
Sent: Thursday, September 02, 2010 9:05 AM
To: http://www.velocityreviews.com/forums/(E-Mail Removed)
Subject: Re: Speed-up for loops

On Thu, 02 Sep 2010 12:02:40 +0200, Michael Kreim wrote:

> I was comparing the speed of a simple loop program between Matlab and
> Python.


> imax = 1000000000
> a = 0
> for i in xrange(imax):
> a = a + 10
> print a


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


Sure; the above can be reduced to just:

print imax * 10


More seriously, if you're comparing against Matlab, you should look at
NumPy. If there's a reasonably direct approach using NumPy, it will be
much quicker than a Python "for" loop (in a sense, NumPy is a library of
useful "for" loops implemented in C).

Even a fairly indirect NumPy approach is often quicker than pure Python.

--
http://mail.python.org/mailman/listinfo/python-list

__________________________________________________ ____________________
This email has been scanned by the MessageLabs
__________________________________________________ ____________________

__________________________________________________ ____________________
This email has been scanned by the MessageLabs
__________________________________________________ ____________________
 
Reply With Quote
 
Peter Otten
Guest
Posts: n/a
 
      09-02-2010
Philip Bloom wrote:

> Uh.


> Try:
> Imax=1000000000
> a=0
> i=0
> While(i<imax):
> a= a+10
> i=i+1
> print a


> I suspect you will find it is way faster than using range or xrange for
> large numbers and map far more closely in the final result to what you
> are doing on matlab's side. At least last I checked, xrange and range
> both involve iterating through an array, which is much slower in all
> cases than just doing an int vs int compare (which is what your matlab
> is doing).


How did you check?

$ python -m timeit "for i in xrange(1000000): pass"
10 loops, best of 3: 47.5 msec per loop
$ python -m timeit "i = 0" "while i < 1000000: i += 1"
10 loops, best of 3: 152 msec per loop
$

So an empty while loop takes about three times as long as the equivalent for
loop. Also:

"""
class xrange(object)
| xrange([start,] stop[, step]) -> xrange object
|
| Like range(), but instead of returning a list, returns an object that
| generates the numbers in the range on demand. For looping, this is
| slightly faster than range() and more memory efficient.
"""

Peter
 
Reply With Quote
 
BartC
Guest
Posts: n/a
 
      09-03-2010
"Michael Kreim" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...

> I was comparing the speed of a simple loop program between Matlab and
> Python.
>
> My Codes:
> $ cat addition.py
> imax = 1000000000
> a = 0
> for i in xrange(imax):
> a = a + 10
> print a


> Unfortunately my Python Code was much slower and I do not understand why.
>
> Are there any ways to speed up the for/xrange loop?
> Or do I have to live with the fact that Matlab beats Python in this
> example?


I'm not sure the Python developers were interested in getting fast loops.

For-loops which iterate between two numbers are amongst the easiest things
to make fast in a language. Yet originally you had to use:

for i in range(N):

which (if I understood correctly) actually created a list of N objects,
populated it with the values 0, 1, 2...N-1 (presumably using a more sensible
loop), then iterated between the values of the list!

So Python had the distinction of being one of the slowest languages in which
to do nothing (ie. running an empty loop).

--
Bartc

 
Reply With Quote
 
Stefan Behnel
Guest
Posts: n/a
 
      09-03-2010
BartC, 03.09.2010 22:17:
> for i in range(N):
>
> which (if I understood correctly) actually created a list of N objects,
> populated it with the values 0, 1, 2...N-1 (presumably using a more
> sensible loop), then iterated between the values of the list!


I guess what applies here is "special cases aren't special enough to break
the rules". The performance is good enough in most cases, it only hurts
when the range is large and the loop body is small in comparison, such as
in the most obvious stupid benchmarks.

Also, xrange() is a pretty old addition the the language and now replaces
range() in Python 3.

Stefan

 
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