Why python is much slower than node.js on recursion

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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/