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

[Steven D'Aprano]

On Sun, 02 Sep 2007 21:00:45 +0200, Wildemar Wildenburger wrote:

> 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?
> 
> /W

There is no single version of Java, and the reference interpretation runs 
on a virtual machine just like Python. Today there are virtual machine 
implementations of Java, native compilers, and Just In Time compilers for 
Java, including HotSpot mentioned by Martin, but Java the language was 
originally defined to run on a VM.

See, for example, here: http://schmidt.devlib.org/java/compilers.html

There are costs to native compilation, the biggest one of course being 
the initial investment in time and effort in creating the native 
compiler. Sun and other commercial companies have invested a lot of money 
in Java, and I don't think the money invested in Python has come even 
close. Consequently, any work into JIT compilation for Java has been done 
by volunteers.

Nevertheless, we have Psyco, which is a JIT compiler of sorts; work also 
continues on PyPy (Python implemented in Python) which, it is hoped, will 
lead to faster Python implementations.

Part of the reason that native compilation for Python is hard is that 
Python's dynamic object model makes it very difficult to apply the same 
sorts of compiler optimizations that C and Java allow. Comparatively 
little of the work done by Python can be safely pushed from run time to 
compile time, so it is unlikely that the average Python application will 
ever run as fast as the equivalent C code -- although that ignores the 
question of what "the equivalent C code" could possibly mean. (If the C 
code includes all the dynamic high-level features of Python, it too would 
surely run as slowly as Python, and if it didn't, it can hardly be said 
to be equivalent.) Nevertheless, by using something like Psyco parts of 
your Python code can run at virtually the same speed as C.

A big question mark in my mind is Lisp, which according to aficionados is 
just as dynamic as Python, but has native compilers that generate code 
running as fast as highly optimized C. I'm not qualified to judge whether 
the lessons learnt from Lisp can be applied to Python, but in any case 
Lisp is an old, old language -- only Fortran is older. The amount of 
development effort and money put into Lisp dwarfs that put into Python by 
possibly a hundred or more.

So... if you'd like to see Python run as fast as C or Lisp, and you have 
a few tens of millions of dollars spare to invest in development, I think 
the Python Software Foundation would love to hear from you.



-- 
Steven.