Velocity Reviews > Speed-up for loops

# 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:
imax = 1000000000
a = 0
for i in xrange(imax):
a = a + 10
print a

imax = 1e9;
a = 0;
for i=0:imax-1
a = a + 10;
end
disp(a);
exit;

The results look like this:
10000000000
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?

With best regards,

Michael

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:
> 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.

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.

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

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

10000000000
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
[...]

10000000000
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
[...]

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
details:

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

Peter

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

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.

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
__________________________________________________ ____________________

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

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:
> 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

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