CODEWITHSUNDEEP
pythonnode.js
gleery
gleery

Reputation: 241

Why python is much slower than node.js on recursion

I've wrote a simple fibonacci test program to compare the performance of node.js and python. It turns out python took 5s to finish the computation, while node.js ends in 200ms Why does python perform so poor on this case?

python

import time

beg = time.clock()
def fib(n):
    if n <=2:
        return 1
    return fib(n-2) + fib(n-1)

var = fib(35)

end = time.clock()
print var
print end - beg

node.js

var beg = new Date().getTime();

function fib(n)
{
    if (n <= 2)
        return 1;

    return fib(n-2) + fib(n-1);
}

var f = fib(35);
var end = new Date().getTime();

console.log(f);
console.log(end - beg);

Upvotes: 9

Views: 9056

Answers (5)

Nicolas Gu&#233;rinet
Nicolas Gu&#233;rinet

Reputation: 2236

There is a way to speed up Cpython on recursion by using lru_cache() decorator. Then, the result will come faster than NodeJS. find more information about recursion and lru_cache() in the links below.

https://realpython.com/lru-cache-python/#using-lru_cache-to-implement-an-lru-cache-in-python

https://realpython.com/python-thinking-recursively/

from functools import lru_cache
import time
beg = time.time()

@lru_cache()
def fib(n):     
    if n <=2:        
        return 1 
    return fib(n-2) + fib(n-1)  
var = fib(35)  
end = time.time() 
print (var)
print (end - beg)

C:\Users\steps\Desktop>python dot.py 
9227465
0.0

Upvotes: -2

timfoden
timfoden

Reputation: 443

I would have written this as a comment, but as I don't as yet have enough points to do so, I've added another answer.

As a number of the answers/comments have mentioned pypy, and it's now a couple of years later than the date of the original question, and I thought I'd give an update for recent versions of CPython and pypy running the python code from the question:

Windows 7 64-bit, Intel Xeon E5-1607 3GHz.

U:>python --version
Python 2.7.5

U:>python fib.py
9227465
3.54921930198

U:>pypy --version
Python 2.7.3 (2cec7296d7fb, Nov 12 2013, 13:24:40)
[PyPy 2.2.0 with MSC v.1500 32 bit]

U:>pypy fib.py
9227465
0.385597246386

So at this point in time pypy is just over 9 times faster than CPython in this micro benchmark. It still looks like node.js would be faster.

Cheers, Tim.

Upvotes: 2

Andrew Gorcester
Andrew Gorcester

Reputation: 19983

It is not really possible to set up a contrived benchmark like this and get results useful enough to make blanket statements about speed; benchmarking is extremely complex and in some cases runtimes can even factor out parts of your benchmark entirely because they realize there's a faster way to do what you tell it you want to do.

However, the bottom line is that you're not comparing Python to node.js, you're comparing their interpreters: CPython to V8. Python and Javascript have similar language features that affect performance (garbage collection, dynamic types, even heap allocation of integers I think?) so when you run this benchmark, it's really a shootout between interpreters.

And in that context, even though benchmarks like this generally aren't of value, the question "Why is V8 faster than CPython on this kind of thing" does kind of have an answer: it's because of the JIT compiler.

So if you want a straight-up comparison, try running your Python code on PyPy, which is a Python interpreter with a JIT. Or try running your Javascript code on a runtime with no JIT. At that point, however, you will probably find that benchmarking is too hard and too complex to use to use a script like this to make a judgement about which language is faster.

Upvotes: 15

Eevee
Eevee

Reputation: 48594

Node uses a JIT compiler, which is designed to notice when the same block of code is run many times with the same types of input and compile it to machine code. It's possible that Node is even noticing this is a pure function and inlining some of the results, but by the very nature of such a compiler it's kind of hard to tell from the outside.

CPython is a naïve interpreter and will do exactly what you tell it. There is, however, an attempt underway to write a Python JIT (written in Python, no less) called PyPy, and as you can see, the results thusfar are promising:

$ time python2 fib.py
9227465
python2 fib.py  2.90s user 0.01s system 99% cpu 2.907 total
$ time pypy fib.py
9227465
pypy fib.py  1.73s user 0.03s system 96% cpu 1.816 total

Upvotes: 9

Benjamin Toueg
Benjamin Toueg

Reputation: 10877

If you use a memoized fibonacci function in Python, you'll see that it becomes much faster:

import time

beg = time.clock()

def memoize(f):
    cache = {}
    def decorated_function(*args):
        if args in cache:
            return cache[args]
        else:
            cache[args] = f(*args)
            return cache[args]
    return decorated_function

@memoize
def fib(n):
    if n <=2:
        return 1
    return fib(n-2) + fib(n-1)

var = fib(35)

end = time.clock()
print(var)
print(end - beg)

You could do the same in javascript:

function memoize( fn ) {
    return function () {
        var args = Array.prototype.slice.call(arguments),
            hash = "",
            i = args.length;
        currentArg = null;
        while (i--) {
            currentArg = args[i];
            hash += (currentArg === Object(currentArg)) ?
            JSON.stringify(currentArg) : currentArg;
            fn.memoize || (fn.memoize = {});
        }
        return (hash in fn.memoize) ? fn.memoize[hash] :
        fn.memoize[hash] = fn.apply(this, args);
    };
}

var beg = new Date().getTime();

function fib(n)
{
    if (n <= 2)
        return 1;

    return fib(n-2) + fib(n-1);
}

var f = memoize(fib)(35);
var end = new Date().getTime();

console.log(f);
console.log(end - beg);

It looks like there is no performance improvement on the javascript side, which tends to show that there already is some kind of memoization mechanism built-in here.

Credits : http://ujihisa.blogspot.fr/2010/11/memoized-recursive-fibonacci-in-python.html, http://addyosmani.com/blog/faster-javascript-memoization/

Upvotes: 6

Related Questions