Why is this loop heavy code so slow in Python? Possible Project Euler spoilers

[Mark Dickinson]

On Sep 2, 7:51 am, jwrweather... at gmail.com wrote:
> The resulting executable takes 0.24 seconds to run. I'm not expecting
> a scripting language to run faster than native code, but I was
> surprised at how much slower it was in this case. Any ideas as to what
> is causing python so much trouble in the above code?

Below is some code and some timings that show that Python is spending
at least 1/3 of its time computing the squares: a*a, b*b and c*c. So
to explain why Python is so much slower than C, it should be enough to
explain what's going on with these multiplications.  Here's my attempt
at an explanation:

To compute a*a, Python has to do the following, all at run-time

(1) Find the type of a.
(2) Look up the corresponding multiplication method for this type.
(3) (In the multiplication method): find the type of the right-hand
side, in this case a again.
(4) Having established that both arguments are ints, worry about
whether the result is going to overflow (in which case a long needs to
be returned).
(5) Do the multiplication.
(6) Allocate a new Python integer to hold the result, and return it.

The C code only has to do step (5), and this boils down to a single
machine instruction.

Mark

Code and timings: (Python 2.5.1/G4.)

def test():
    solutions = [0] * 1000
    for a in xrange(1, 1000):
        for b in xrange(1, 1000 - a):
            for c in xrange(1, 1000 - a - b):
                if a*a + b*b == c*c:
                    solutions[a+b+c] += 1
    return solutions

def test2():
    solutions = [0] * 1000
    squares = [x*x for x in xrange(1000)]
    for a in xrange(1, 1000):
        for b in xrange(1, 1000 - a):
            for c in xrange(1, 1000 - a - b):
                if squares[a] + squares[b] == squares[c]:
                    solutions[a+b+c] += 1
    return solutions


>>> from profile import run
>>> run("l = test(); l2 = test2()")
         5 function calls in 299.984 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall
filename:lineno(function)
        1    0.010    0.010    0.010    0.010 :0(setprofile)
        1    0.000    0.000  299.973  299.973 <string>:1(<module>)
        1    0.000    0.000  299.984  299.984 profile:0(l = test(); l2
= test2())
        0    0.000             0.000          profile:0(profiler)
        1  182.262  182.262  182.262  182.262 test.py:1(test)
        1  117.711  117.711  117.711  117.711 test.py:10(test2)