Performance question about math operations

[Bengt Richter]

On Mon, 1 Jul 2002 23:00:30 -0700 (PDT), "Andrew P. Lentvorski" <bsder at mail.allcaps.org> wrote:

>I have a VLSI layout editor written in Python.  At its core, it has to
>redraw a lot of polygons.  This requires a lot of coordinate conversion
>mathematics.  Essentially the following loop:
>
>#! /usr/bin/env python
>
>def main():
>    i = 0
>
>    while i < 1000000:
>        i = i + 1
>
>        (1-678)*3.589
>        -((1-456)*3.589)
>
>if __name__=="__main__":
>    main()
>
Note that there is no constant expression folding in Python, so you
are actually doing all the operations you are specifying.

And there is no automatic hoisting of constant stuff out of the loop,
so pre-compute and store constants outside the loop where you can.

It's hard to say without actual code. There is a trick you could use
to fold constant expressions, e.g.,

Say you wanted to translate a list of coordinates:
 >>> coordlist = [(1,2),(3,4),(5,6)]

Say you _know_ these are constant for a particular translation
 >>> k1=5; k2=10

Then
 >>> exec 'newlist = [(x+%s,y+%s) for x,y in coordlist]' % (k1*20+10,k2*10)
 >>> newlist
 [(111, 102), (113, 104), (115, 106)]

The trick was that what got compiled and executed was first evaluated as
 >>> 'newlist = [(x+%s,y+%s) for x,y in coordlist]' % (k1*20+10,k2*10)

which produced the code
 'newlist = [(x+110,y+100) for x,y in coordlist]'

which has simple constants instead of expressions and lookups during the list comprehension.
This would only be worth while on really long lists of coordinates, depending on how complex
your constant expressions are.

I'm sure you can see how to generalize the above to (x*%s+%s, y*%s+%s) with appropriate
expressions for the four constant values to get any desired rotation/scaling/translation.

However, you may want to consider what the array module might do for you (maybe in
combination with the above trick), or you could look for some graphics software that
may match what you're doing.

>Now, I understand that looping in Python has overhead.  It turns out that
>the loop without the math operations takes about .5 seconds.  Fine.
>However, each line of math operations adds .75 seconds to the total loop
>time for a total run time of about 2 seconds.  This is with -O enabled
>(even though it doesn't seem to have any effect).
>
>This same loop in C++ (with classes, indirection, copy contruction, etc)
>takes about .05 seconds.
>
>That's about a factor of 30 (1.5 / .05) difference even if I cancel out
>the loop overhead.  I could handle factor of 2 or 4, but 30 seems a bit
>high.
>
>What is eating all that time?  And can I do anything about it?
>
Again, hard to say without actual code ;-)

Regards,
Bengt Richter