为什么python在递归上比node.js慢得多

Question

我编写了一个简单的fibonacci测试程序来比较node.js和python的性能。 结果python花了5秒完成计算，而node.js在200毫秒内结束 为什么python在这种情况下表现如此糟糕？

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

建立这样一个人为的基准并得到足够有用的结果来对速度进行全面的说明是不可能的；基准测试是非常复杂的，在某些情况下，运行时甚至可以完全将基准的一部分分解出来，因为它们意识到有一种更快的方法来完成你告诉它你想做的事情。

但是，归根结底，您不是在比较Python和node.js，而是在比较它们的解释器：CPython和V8。Python和Javascript有类似的语言特性，它们会影响性能（垃圾收集、动态类型，甚至我认为是整数的堆分配？）所以当你运行这个基准测试时，它实际上是一个解释程序之间的交火。

在这种情况下，尽管像这样的基准通常没有价值，但问题“为什么V8在这种情况下比CPython快”确实有一个答案：这是因为JIT编译器。

因此，如果您想直接比较，可以尝试在PyPy上运行您的Python代码，PyPy是一个带有JIT的Python解释器。或者尝试在没有JIT的运行时运行Javascript代码。然而，在这一点上，您可能会发现基准测试太难，太复杂，无法使用这样的脚本来判断哪种语言更快。

Answer 2

Node使用一个JIT compiler，它被设计用来注意同一代码块在同一类型的输入下运行多次，并将其编译为机器代码。Node甚至可能注意到这是一个纯函数并内联了一些结果，但是根据这种编译器的本质，很难从外部分辨出来。

CPython是一个天真的翻译，会按照你说的做。不过，目前正在尝试编写一个名为PyPy的Python JIT（用Python编写，同样如此），正如您所看到的，thusfar的结果很有希望：

$ 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

如果您在Python中使用一个带记忆的fibonacci函数，您将看到它变得更快：

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)

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

看起来javascript方面没有性能改进，这往往表明这里已经内置了某种记忆机制。

学分：http://ujihisa.blogspot.fr/2010/11/memoized-recursive-fibonacci-in-python.html，http://addyosmani.com/blog/faster-javascript-memoization/