Why is python much slower than node.js when recursing

Question

I wrote a simple fibonacci testing program to compare the performance of node.js and python. It turns out that python took 5 seconds to finish the calculation, and node.js ended for 200 ms. Why does python work so bad in 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

In fact, it is not possible to set up such a benchmark and get results useful enough to create complete speed statements; benchmarking is extremely complex, and in some cases, battery life can even partially separate parts of your test because they understand that there is a faster way to do what you say you want to do.

However, in the end, you are not comparing Python with node.js, you are comparing their interpreters: CPython with V8. Python and Javascript have similar language features that affect performance (garbage collection, dynamic types, even heap allocation of integers, which I think?), So when you run this test, it really is a shootout between translators.

And in this context, although such tests, as a rule, have no value, the question “Why is V8 faster than CPython for this kind of thing” has a kind of answer: because of the JIT compiler .

So, if you want a direct comparison, try running your Python code on PyPy, which is a Python interpreter with JIT. Or try running Javascript code at runtime without JIT. However, at this point, you will probably find that benchmarking is too complex and too complex to use a script like this to judge which language is faster.

Answer 2

Node uses the JIT compiler, which is designed to notify when the same block of code is run many times with the same input types and compiles its native code. It is possible that Node even notices that it is a pure function and an embedding of some results, but by the very nature of such a compiler it is difficult to say from the outside.

CPython is a naive interpreter and will do exactly what you tell it. However, there is an attempt to write a Python JIT (written in Python, not less) called PyPy , and as you can see, the results obtained in this way 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 the memoized fibonacci function in Python, you will 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 can 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); 

There seems to be no performance improvement on the javascript side, which usually indicates that some kind of memoization mechanism already exists.

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

Answer 4

I would write this as a comment, but since I do not have enough points for this yet, I added another answer.

Pypy was mentioned as a series of answers / comments, and now this is a couple of years later than the date of the original question, and I thought that I would give an update for the latest versions of CPython and pypy by 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, 11/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 a little over 9 times faster than CPython in this micro-control. It still looks like node.js will be faster.

Greetings, Tim.