Dlaczego rekursja w javascript jest tak powolna?

Question

Właśnie prowadził ten wzorzec na jsperf: https://jsperf.com/mapping1

starałem się sprawdzić, czy mapa, która mogłaby pokonać wykorzystywane rekursji funkcji Array.prototype mapy. Moja zaginęła. Potwornie. Czy ktoś może wyjaśnić, dlaczego?

map = function(f, xs) { 
    if (xs.length === 0) {return []} 
    return [f(head(xs))].concat(map(f, tail(xs))) 
} 

// head() and tail() do exactly what you would expect. I wish there was a way to programmatically fork lists in js... 

Answer 1

Oto realizacja fasterMap rekurencyjnie, ale bez concat, to 20x szybciej niż mapie i tylko 1.5x wolniej niż rodzimej Array.map:

var Cx = function(){ 
    this.map = function (f, xs) { 
     if (xs.length === 0) {return []} 
     return [f(head(xs))].concat(arguments.callee(f, tail(xs))) 
    } 

    this.fasterMap = function(f, xs, i) { 
     i = i || 0; 
     if (xs.length === 0 || i > xs.length - 1) {return []} 
     xs[i] = f(xs[i]) 
     arguments.callee(f, xs, i + 1) 
     return xs 
    } 

    this.arrMap = function (f, xs) { 
     return xs.map(f) 
    } 
} 

function head(arr){return arr[0]} 
function tail(arr){return arr.slice(1)} 

function add1(x){return x + 1} 

function rep(n,f){ 
    for(var i = 0; i < n; i++) 
     f(i) 
} 

var cx = new Cx() 

;[9,99,999].forEach(function(n){ 
    var test = [] 
    rep(n,function(i){test.push(i + 1)}) 

    ;['map','fasterMap','arrMap'].forEach(function(mapType){ 
     var mapFn = function(){return cx[mapType](add1,test)} 
     if(n < 10) 
      console.log(' ' + mapType,mapFn()) 
     else{ 
      console.time(' ' + mapType + ' ' + n) 
      rep(1000,mapFn) 
      console.timeEnd(' ' + mapType + ' ' + n) 
     } 
    }) 
}) 

Oto wyniki testów na Cloud9 IDE:

map [ 2, 3, 4, 5, 6, 7, 8, 9, 10 ]                                                      
fasterMap [ 2, 3, 4, 5, 6, 7, 8, 9, 10 ]                                                    
arrMap [ 3, 4, 5, 6, 7, 8, 9, 10, 11 ]                                                     

map 99: 45ms                                                           
fasterMap 99: 8ms                                                          
arrMap 99: 7ms                                                           

map 999: 2227ms                                                          
fasterMap 999: 102ms                                                         
arrMap 999: 85ms 

Więc odpowiedź jest concat sprawia, że ​​funkcja mapy jest wolna.