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

Is there any reason for Python being so slow?

Yes.

But what does it matter? You've created 100,000 xrange objects. Why? What does that matter? What is your real question on performance? What algorithm do you actually have that's actually too slow?

---

for i in xrange(0,100000): # Creates one xrange object
    for j in xrange(0,100000): # Creates a fresh xrange object each time through the loop

Answer 2

A good compiler would optimise away the loop.

Assuming the loop isn't optimised away, I'd expect Python to be something like 100 times slower than the C version

Answer 3

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 4

for i in xrange(0, 10000):
    for j in xrange(0, 10000):
        pass

or

for i in xrange(0, 100000000):
    pass

Python 2.6.5 - Time taken : 8.50866484642

PyPy 1.3 - Time taken : 1.55999398232

reason of slow work not in creation of xrange objects

Answer 5

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).

Answer 6

gcc 4.2 with the -O1 flag or higher optimize away the loop and the program takes 1 milli second to execute. This benchmark is not very representative as it is very far from any real world use. You're doing a nested loop for a reason, and you never leave it empty. Python doesn't optimize away the loop, although I see no technical reason why it couldn't.

Python is slower than C because it's further from the machine language. xrange is a nice abstraction but it adds a heavy layer of machine code compared to a simple C loop.

C source:

int main( void ){
        int i, j;
        for (i=0;i<100000;i++){
                for (j=0;j<100000;j++){
                        continue;
                }
        }
        return 0;
}