Why did JS solve the recursion problem much faster than Python/Lua?

Question

Python

There is problem 14 from the Euler project.
The essence of the problem is the following repeating sequence defined for the set of natural numbers:
n → n/2 (n - even)
n → 3n + 1 (n - odd)
Which initial element less than a million generates the longest sequence?
The solution of the problem is recursive. As part of the channel https://www.youtube.com/watch?v=mHbgWHqeBp0 (yes, the quality is still terrible) I made a performance comparison in solving this problem in Python / LUA (I will not give the code, it is approximately the same as JS)

console.time('coll');
function getCollatz(number, iterations=1){
    if (number===1){
        return iterations
    } else if (number % 2 === 0){
        return getCollatz(Math.floor(number/2), iterations+1)
    } else {
        return getCollatz(3*number+1, iterations+1)
    }
}

let a = 0;
let x = 0;
let y = 0

for (let i = 1; i< 1000001; i++){
    let current_iter = getCollatz(i);
    if (current_iter>a){
        a = current_iter;
        x = i
    }
    y++
}
console.timeEnd('coll')
console.log(x)

The numbers came out like this:

1. Python: 59 sec
   
2. Lua: 17 sec
   

No surprises for me yet, but JS on NodeJS did it in 2 seconds!!!!
Actually the question is why?
PS All 3 tests on the same machine

Answer 1

dig here
https://benchmarksgame-team.pages.debian.net/bench...
and don't mess around with garbage anymore
, there are tests where an asynchronous python is faster than a node, etc., etc.
everything is too multifactorial to make generalizations of the form N faster / slower than M
, it is enough to know the order of speed
JS and Python languages ​​\u200b\u200bof the same level and order

Answer 2

Once upon a time, a friend discovered that the implementation of calculating Fibonacci numbers through recursion in Java is faster than its counterpart in C. He was not only surprised by this, but also studied the issue. It turned out that gcc did push si in every function call; push di; and at the end of pop si; pop di; although the si and di registers were not used in any way in the compiled code. This gave some microscopic, but still time costs.
Any specific test is specific, it shows not how fast this or that language works (more precisely, its specific implementation), but what kind of time spent on a specific task turned out in this implementation. In a different task, in a different implementation of the same language, it's just that even on different hardware, a different result can be obtained.

Answer 3

Synthetic benchmarks almost always lie, because those who write them rarely know all the compared technologies thoroughly and are unlikely to be able to reduce the task to similar conditions. As a rule, similar conditions come out only when all possible optimizations are disabled, because optimizations work differently for different technologies.
As already mentioned above, you didn’t translate the Python code in vain, perhaps experts in this PL would offer a more optimal solution.
According to the js version, I can say that v8 is very good at optimizing tail recursion. And in this example, instead of an expensive recursion, a cheaper loop will work for you. I can surprise you, rewrite your solution in C right as it is and compile without optimizations - js + v8 will be faster

Answer 4

Dear author, try this variant (Python 3.8) on your computer. The result will surprise you.

import time
import sys
from functools import lru_cache


@lru_cache(5000000)
def calc(number: int) -> int:

    if number == 1:
        return 0
    elif number % 2 == 0:
        iterations = calc(number//2)+1
    else:
        iterations = calc(3*number+1)+1

    return iterations


if __name__ == '__main__':

    sys.setrecursionlimit(2000)
    start = time.process_time()
    max_num, num = 0, 0

    for i in range(1, 1000000+1):
        if (cur_num := calc(i)) > max_num:
            max_num, num = cur_num, i

    print('n =', num, 'iterations =', max_num+1, 'time =', time.process_time()-start, 'sec')

If you change the decorator to
it will be even a little faster.