为什么Python在递归方面比Node.js慢得多

Question

我写了一个简单的斐波那契测试程序，用来比较node.js和python的性能。 结果发现python需要5秒才能完成计算，而node.js只需要200毫秒。 为什么在这个案例中，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);

- gleery

---

你正在比较实现：CPython和Node.js。语言比较将是Python（实现包括CPython，PyPy，IronPython和Jython）与JavaScript（实现包括SpiderMonkey，V8和Chakra）的比较。 - Chris Morgan

这个问题引发了一些非常有启发性的答案。感谢大家。 - itsafire

Answer 1

很难通过设定类似的基准测试来获取有用的结果，以便对速度进行一般性的陈述；基准测试非常复杂，有些情况下运行时甚至会将你基准测试的某些部分排除在外，因为它们意识到存在更快的方式来执行你所要求的操作。

然而，归根结底，你并不是在比较Python和node.js，而是在比较它们的解释器：CPython和V8。Python和Javascript具有影响性能的相似语言特性（垃圾收集、动态类型，甚至包括整数的堆分配），所以当你运行这个基准测试时，实际上是在比较解释器。

在这个背景下，虽然这样的基准测试通常没有价值，但问题“为什么V8在这种情况下比CPython更快”确实有一个答案：这是由于JIT编译器。

因此，如果你想要一个直接的比较，请尝试在PyPy上运行Python代码，这是一个带有JIT的Python解释器。或者尝试在没有JIT的运行时上运行JavaScript代码。不过，在那时，你可能会发现基准测试过于困难和复杂，不能使用这样的脚本来判断哪种语言更快。

- Andrew Gorcester

---

但是Python通常是CPython，即使有一些合理的原因（JIT编译/内存），它仍然比较慢。我已经进行了基准测试，初步迹象表明，标准的node.js比标准的Python快约10倍。在某些情况下，对于大型循环，Python（Cpython）比所有其他主流语言都慢一个数量级... - D.L

Answer 2

Node使用JIT编译器，旨在注意到相同的代码块多次以相同类型的输入运行，并将其编译为机器代码。可能Node甚至注意到这是一个纯函数，并内联一些结果，但由于这种编译器的本质，很难从外部看出来。

CPython是一个天真的解释器，会完全按照您的指示执行。然而，目前正在进行一项尝试，编写一个Python JIT（甚至用Python编写），称为PyPy，如您所见，迄今为止的结果很有前途：

$ 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

- Eevee

Answer 3

如果你在Python中使用一个记忆化的斐波那契函数，你会发现它变得更快了：

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/

- Benjamin Toueg

---

这是一份测试程序，不是为了实际应用而写的，我有意这样编写。 - gleery

在记忆化下同时运行这两个测试可以给出一些线索，说明正在发生什么。 - Benjamin Toueg

这个问题涉及到递归函数在两种环境（Python和Node.js）中的性能，但是你的答案优化了算法。 - MajidTaheri

提示是JavaScript可能使用JIT，这是@eevee确认的。 - Benjamin Toueg

Answer 4

我本来想把这个作为评论来写的，但由于我还没有足够的积分，所以我添加了另一个答案。

由于一些回答/评论提到了pypy，而现在距离原始问题的日期已经过去了几年，我想为最近版本的CPython和pypy提供更新，运行来自问题的Python代码。

Windows 7 64位，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

因此，在这个微基准测试中，pypy比CPython快了9倍。看起来node.js会更快。

祝好，Tim。

- timfoden

Answer 5

有一种方法可以通过使用lru_cache()装饰器来加速Cpython的递归。然后，结果将比NodeJS更快地出现。在下面的链接中找到有关递归和lru_cache()的更多信息。

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

- Nicolas Guérinet