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

[Chris Mellon]

On 9/2/07, Diez B. Roggisch <deets at nospam.web.de> wrote:
> Wildemar Wildenburger schrieb:
> > Martin v. Löwis wrote:
> >>>> (2) it is a interpretation language
> >>> Not quite. It's compiled to byte-code - just like Java (would you call
> >>> Java an 'interpreted language' ?)
> >>
> >> Python is not implemented like Java. In Java (at least in HotSpot),
> >> the byte code is further compiled to machine code before execution;
> >> in Python, the byte code is interpreted.
> >>
> > OK, good. Naive question now comming to mind: Why doesn't Python do the
> > latter as well?
>
> because of the dynamic nature of it. Java is statically typed, so the
> JIT can heavily optimize.
>
> OTH psyco IS a JIT-compiler to optimize certain calculations which are
> mostly of a numerical nature. But this can't be done to the extend it is
> possible in java.
>

Original code: 3 min, 9 seconds
Original code with psyco: 30.28 seconds
Original code, compiled with Pyrex: 1min 39 seconds (moves the for loops into C)
Same, with a,b,c declared with cdef int: 20 seconds (uses c pow()
instead of going through Python).
Same, with the for..xrange loops rewritten to use C integer loops: 13
seconds (saves xrange use, but since the python loop was already gone,
not too much savings).

With a small amount of work, you should be able to implement the C
algorithm in Pyrex (or even just use the C algorithm, in a wrapper
that converts the return value to an int) and get the same speed as
the C version + a constant marshalling factor.

Adding pysco took all of 20 seconds (half that because I needed to
move the module scope code into a function), and re-writing with pyrex
took a minute or two. So, as a demonstration of numeric optmization,
both of them can give you quite good rewards with minimal effort.