Re: Speed-up for loops

Discussion in 'Python' started by Tim Wintle, Sep 2, 2010.

  1. Tim Wintle

    Tim Wintle Guest

    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.
     
    Tim Wintle, Sep 2, 2010
    #1
    1. Advertising

  2. Tim Wintle

    Carl Banks Guest

    On Sep 2, 5:55 am, Tim Wintle <> 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
     
    Carl Banks, Sep 2, 2010
    #2
    1. Advertising

  3. 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
     
    Ulrich Eckhardt, Sep 3, 2010
    #3
  4. 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
     
    Stefan Behnel, Sep 3, 2010
    #4
  5. Ulrich Eckhardt <> 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.
     
    Hrvoje Niksic, Sep 3, 2010
    #5
  6. Tim Wintle

    Tim Wintle Guest

    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
     
    Tim Wintle, Sep 3, 2010
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ham

    I need speed Mr .Net....speed

    Ham, Oct 28, 2004, in forum: ASP .Net
    Replies:
    6
    Views:
    2,371
    Antony Baula
    Oct 29, 2004
  2. efiedler
    Replies:
    1
    Views:
    2,129
    Tim Ward
    Oct 9, 2003
  3. Michael Kreim

    Speed-up for loops

    Michael Kreim, Sep 2, 2010, in forum: Python
    Replies:
    12
    Views:
    2,198
    Stefan Behnel
    Sep 5, 2010
  4. David Cournapeau

    Re: Speed-up for loops

    David Cournapeau, Sep 5, 2010, in forum: Python
    Replies:
    19
    Views:
    717
    BartC
    Sep 8, 2010
  5. Me
    Replies:
    2
    Views:
    263
Loading...

Share This Page