Nested loop comparison in Python,Java and C

Question

The following code in python takes very long to run. (I couldn't wait until the program ended, though my friend told me for him it took 20 minutes.)

But the equivalent code in Java runs in approximately 8 seconds and in C it takes 45 seconds.

I expected Python to be slow but not this much, and in case of C which I expected to be faster than Java was actually slower. Is the JVM using some loop unrolling technique to achieve this speed? Is there any reason for Python being so slow?

import time
st=time.time()
for i in xrange(0,100000):
    for j in xrange(0,100000):
        continue;
print "Time taken : ",time.time()-st

Answer 1

Your test is not measuring anything meaningful.

A language's performance in the real world has little to do with how quickly it executes a tight loop.

Frankly, I'm intrigued that C and Java took as long as they did; I would have expected both of their compilers to realize that there was nothing happening inside the inner loop, and have optimized both of them away into nonexistence (and 0 seconds).

Python, on the other hand, is still interpreted (I could be wrong about this). In any case, it looks like the outer loop is needing to construct 100,000 xrange objects on which to run the empty inner loop, and that's unlikely to be optimized away.

So all you're really measuring is various compilers' ability to see through the fact that no real computing work is being done.

Answer 2

The lesson is: Performance is never what you expect. Therefore, always measure, never believe.

Some reasons why you might see these numbers (and from the first sentence, some of these might be completely wrong):

C is compiled for an "i586" processor (also called Pentium). That CPU was sold from 1993 to about 2000. Have you seen one lately? Guess not. So the C code isn't really optimized for what your CPU can do (or to put it another way around: Today's CPUs try very hard to be a fast Pentium CPU). Java, OTOH, is compiled for your CPU as the code is loaded. It can pull some tricks that C simply can't. The price is that the C program starts in 15ms while the Java program needs 4 Seconds.

Python has no JIT (just in time compiler), yet. All code is converted into bytecode which is then interpreted. This means the loop above is turned into a dozen bytecode instructions which are then interpreted by a C program. That just takes time. Python is not meant for huge loops, it's meant for smart algorithms which you simply can't express in any other language (at least not with the same amount of code and readability).

So just as it doesn't make sense to go shopping with a 18t truck (you can transport anything but you won't find a space to park it), chose your programming language according to the problem you need to solve. It has to be small&fast? C. Just fast? Java. Flexible? Python. Flexible&Fast: Python with a helper library in C (like NumPy).