javascript - Why simple factorial algorithms in JS are much faster than in Python or R? -

why javascript being more faster in computation?

i've been making tests 4 simple factorial algorithms: recursion, tail recursion, while loop , for loop. i've made tests in r, python, , javascript.

i measured time took each algorithm compute 150 factorial, 5000 times. r used system.time(replicate()). python used time.clock(), resource module, , timeit module. javascript used console.time(), date().getmilliseconds(), , date().gettime(), running script using node via terminal.

this never intended compare running times between languages, see form (recursive, tail recursive, loop, or while loop) faster languages i'm learning. performance of javascript algorithms caught attention, though.

you can see 4 different factorial algorithms , measurement implementations here:

r factorial algorithms , performance.

python factorial algorithms , performance.

javascript factorial algorithms , performance.

on following examples, f stands for loop, w stands while loop.

the results r are:

running time of different factorial algorithm implementations, in seconds. compute 150 factorial 5000 times:  factorialrecursive()  user  system elapsed  0.044   0.001   0.045   factorialtailrecursive()  user  system elapsed  3.409   0.012   3.429   factorialiterw()  user  system elapsed  2.481   0.006   2.488   factorialiterf()  user  system elapsed  0.868   0.002   0.874  

the results python are:

running time of different factorial algorithm implementations. uses timeit module, resource module, , custom performance function.  compute 150 factorial 5000 times:  factorial_recursive() timeit:          0.891448974609 custom:          0.87 resource user:   0.870953 resource system: 0.001843  factorial_tail_recursive() timeit:          1.02211785316 custom:          1.02 resource user:   1.018795 resource system: 0.00131  factorial_iter_w() timeit:          0.686491012573 custom:          0.68 resource user:   0.687408 resource system: 0.001749  factorial_iter_f() timeit:          0.563406944275 custom:          0.57 resource user:   0.569383 resource system: 0.001423 

the results javascript are:

running time of different factorial algorithm implementations. uses console.time(), date().gettime() , date().getmilliseconds()  compute 150 factorial 5000 times:  factorialrecursive(): 30ms using date().gettime(): 19ms using date().getmilliseconds(): 19ms  factorialtailrecursive(): 44ms using date().gettime(): 44ms using date().getmilliseconds(): 43ms  factorialiterw(): 4ms using date().gettime(): 3ms using date().getmilliseconds(): 3ms  factorialiterf(): 4ms using date().gettime(): 4ms using date().getmilliseconds(): 3ms 

if understand correctly, there no way measure cpu time in javascript using js code, , methods used above measure wall clock time.

the wall clock time measurements of javascript faster python or r implementations.

for example, wall clock running time of factorial algorithm using loop: r: 0.874s python: 0.57 s javascript: 0.004s

why javascript being more faster in computation?

in detail can speak r, here 2ct. maybe can analyze happens in other languages , come conclusions.

first of all, however, r version of factorialrecursive not recursive: call r's factorial (n - 1) uses $\gamma$ function.

here benchmarking results including factorial via gamma function , more rish (vectorized) way of expressing iterative calculation:

> factorialcumprod <- function(n) cumprod (seq_len (n))[n]  > microbenchmark(factorial(150),                   factorialrecursive(150), factorialtailrecursive(150),                   factorialiterf(150), factorialiterw(150), factorialcumprod (150),                  times = 5000) unit: microseconds                         expr     min      lq   median       uq       max neval               factorial(150)   1.258   2.026   2.2360   2.5850    55.386  5000      factorialrecursive(150) 273.014 281.325 285.0265 301.2310  2699.336  5000  factorialtailrecursive(150) 291.732 301.858 306.4690 323.9295  4958.803  5000          factorialiterf(150)  71.728  74.941  76.1290  78.7830  2894.819  5000          factorialiterw(150) 218.118 225.102 228.0360 238.3020 78845.045  5000        factorialcumprod(150)   3.493   4.959   5.3790   5.9375    65.444  5000 

microbenchmark randomizes order of function calls. make difference compared executing blocks of same function call.

i guess can learn here need take account design decisions developers of language/language implementation when choose algorithm.

r known slow @ recursion. find simple function call without doing return constant costs 750 ns, 150 function calls in account half time of recursive algorithms. directly calling gamma (150 + 1) instead of doing indirectly factorial (150) yields similar difference. if want know more why so, you'll have ask r core team.

the loops spend amazing amount of overhead on checking things. give impression:

> (i in 1 : 3) { +    cat (i ," ") +    <- 10 +    cat (i ,"\n") + } 1  10  2  10  3  10  

i think saving work speedup in vectorized functions comes from.

the difference between while , for iterative versions comes fact n : 1 in for loop vectorized. taking step further, i.e. using cumprod function r provides cumulative products considerably speeds calculations: we're within factor of 2 - 3 compared r's base implementation $\gamma$ function (you may argue cheating because cumprod has c function behind - r interpreter written in c, distinctions bit blurred here).

i think paying heavily here safety checks r has , has have tailored interactive use. see "why python code run faster in function?" related issues in python.

take home message 1: both recursion , explict loops in r sensible option if computation in each function call/inside loop complicated enough overhead doesn't matter.

take home message 2: knowing math can tremendously: r's factorial has constant run time (about 1.8 μs on laptop):

take home message 3: however, speed-up matter @ all? factorials, not: graph goes on whole range of x result can held double. computations both functions not take more ca. 5 μs. "worst" function in 500 μs. if had large numbers of factorials calculate, you'd use look-up table: vector of 170 elements isn't big. factorialcumprod calculates whole thing within 5 μs you.
if happen need factorials of larger numbers calculations, should try hard reformulate problem - i'd anyways expect numeric trouble right behind corner (even if can use big integers - in r there packages gmp , rmpfr)

---

ps: in case wondering fibonacci numbers cannot replaced convenient cumprod or cumsum call, see these blog posts recursive , iterative calculation (the worst algorithm in world?) , closed form calculation (computing fibonacci numbers using binet’s formula)