Desempenho: recursão vs. iteração em Javascript

24

Li recentemente alguns artigos (por exemplo, http://dailyjs.com/2012/09/14/functional-programming/ ) sobre os aspectos funcionais do Javascript e a relação entre Scheme e Javascript (o último foi influenciado pelo primeiro, que é uma linguagem funcional, enquanto os aspectos OO são herdados do Self, que é uma linguagem baseada em prototipagem).

No entanto, minha pergunta é mais específica: eu queria saber se existem métricas sobre o desempenho da recursão versus iteração em Javascript.

Eu sei que em algumas linguagens (onde por iteração de design funciona melhor) a diferença é mínima porque o intérprete / compilador converte recursão em iteração, no entanto, acho que provavelmente esse não é o caso do Javascript, pois é, pelo menos parcialmente, um funcional língua.

javascript functional-programming recursion mastazi
fonte
3
Faça seu próprio teste e descubra imediatamente em jsperf.com
TehShrike 18/12/12
com a recompensa e uma resposta mencionando o TCO. Parece que o ES6 especifica o TCO, mas até agora ninguém o implementa se acreditarmos em kangax.github.io/compat-table/es6 Estou perdendo alguma coisa?
Matthias Kauer

Respostas:

28

O JavaScript não executa a otimização da recursão da cauda ; portanto, se a sua recursão for muito profunda, você poderá obter um estouro da pilha de chamadas. A iteração não tem esses problemas. Se você acha que vai recorrer muito e realmente precisa de recursão (por exemplo, para preencher), substitua a recursão por sua própria pilha.

O desempenho da recursão é provavelmente pior do que o desempenho da iteração, porque chamadas e retornos de função exigem preservação e restauração do estado, enquanto a iteração simplesmente salta para outro ponto em uma função.

Triang3l
fonte
Apenas imaginando ... Eu vi um pouco de código em que uma matriz vazia é criada e o site da função recursiva é atribuído a uma posição na matriz e, em seguida, o valor armazenado na matriz é retornado. É isso que você quer dizer com "substituir a recursão por sua própria pilha"? Por exemplo: var stack = []; var factorial = function(n) { if(n === 0) { return 1 } else { stack[n-1] = n * factorial(n - 1); return stack[n-1]; } }
mastazi
@mastazi: Não, isso fará uma pilha de chamadas inútil junto com a interna. Eu quis dizer algo como o preenchimento de fila baseado na fila da Wikipedia .
precisa saber é o seguinte
Vale a pena notar que uma linguagem não executa o TCO, mas uma implementação pode. A maneira que as pessoas otimizar meios JS que talvez TCO poderia aparecer em algumas implementações
Daniel Gratzer
11
@mastazi Substitua a elsefunção nessa por else if (stack[n-1]) { return stack[n-1]; } elsee você terá memorização . Quem escreveu esse código fatorial teve uma implementação incompleta (e provavelmente deveria ter usado em stack[n]todos os lugares, em vez de stack[n-1]).
Izkata
Obrigado @Izkata, costumo fazer esse tipo de otimização, mas até hoje não sabia o nome. Eu deveria ter estudado CS em vez de TI ;-)
mastazi
20

Atualização : desde o ES2015, o JavaScript tem TCO ; portanto, parte do argumento abaixo não permanece mais.

Embora o Javascript não tenha otimização de chamada final, a recursão geralmente é o melhor caminho a percorrer. E sinceramente, exceto em casos extremos, você não terá estouros de pilha de chamadas.

O desempenho é algo a ser lembrado, mas também a otimização prematura. Se você acha que a recursão é mais elegante que a iteração, faça isso. Se esse for o seu gargalo (o que talvez nunca seja), você poderá substituí-lo por uma iteração feia. Mas na maioria das vezes, o gargalo está nas manipulações do DOM ou, geralmente, na E / S, não no próprio código.

A recursão é sempre mais elegante 1 .

1 : Opinião pessoal.

Florian Margaine
fonte
3
Concordo que a recursão é mais elegante e a elegância é importante, pois é legível e fácil de manter (isso é subjetivo, mas, na minha opinião, a recursão é muito fácil de ler e, portanto, sustentável). No entanto, às vezes o desempenho é importante; você pode apoiar a afirmação de que a recursão é o melhor caminho a seguir, mesmo em termos de desempenho?
mastazi
3
@mastazi, como disse na minha resposta, duvido que a recursão seja o seu gargalo. Na maioria das vezes, é a manipulação do DOM ou, geralmente, a E / S. E não se esqueça que a otimização prematura é a raiz de todos os males;)
Florian Margaine 18/12/12
+1 na manipulação de DOM sendo um gargalo na maioria das vezes! Lembro-me de uma entrevista muito interessante para Yehuda Katz (Ember.js) sobre isso.
mastazi
11
@mike A definição de "prematuro" é "madura ou madura antes da hora certa". Se você sabe que fazer algo recursivamente causará um excesso de pilha, não será prematuro. No entanto, se você assumir por um capricho (sem dados reais), é prematuro.
Zirak
2
Com o Javascript, você não sabe quanto pilha o programa terá disponível. Você pode ter uma pilha pequena no IE6 ou uma pilha grande no FireFox. Os algoritmos recursivos raramente têm uma profundidade fixa, a menos que você faça um loop recursivo no estilo Scheme. Simplesmente não parece que a recursão não baseada em loop se encaixe para evitar otimizações prematuras.
mike30
7

Eu também estava curioso sobre esse desempenho em javascript, então fiz alguns experimentos (embora em uma versão mais antiga do nó). Escrevi uma calculadora fatorial recursivamente versus iterações e a executei algumas vezes localmente. O resultado parecia bastante inclinado para a recursão com um imposto (esperado).

Código: https://github.com/j03m/trickyQuestions/blob/master/factorial.js

Result:
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:557
Time:126
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:519
Time:120
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:541
Time:123
j03m-MacBook-Air:trickyQuestions j03m$ node --version
v0.8.22
Dr.HappyPants
fonte
Você pode tentar fazer isso "use strict";e ver se isso faz diferença. (Ele produzirá jumps em vez da sequência de chamadas padrão)
Burdock
11
Em uma versão recente do nó (6.9.1), obtive resultados extremamente semelhantes. Há um pouco de imposto sobre recursão, mas considero um caso extremo - a diferença de 400ms para 1.000.000 de loops é 0,0025 ms por loop. Se você está fazendo 1.000.000 de loops, é algo a ter em mente.
Kelz
6

Conforme solicitação do OP, eu irei entrar em contato (sem me fazer de bobo, espero: P)

Acho que todos concordamos que a recursão é apenas uma maneira mais elegante de codificar. Se bem feito, pode resultar em código mais sustentável, o que é IMHO tão importante (se não mais) que reduzir 0,0001ms.

No que diz respeito ao argumento de que o JS não executa a otimização de chamada de cauda: isso não é mais verdade, o uso do modo estrito do ECMA5 permite o TCO. Era algo que eu não estava muito feliz há um tempo, mas pelo menos agora eu sei por que arguments.calleelança erros no modo estrito. Conheço o link acima para um relatório de bug, mas o bug está definido como WONTFIX. Além disso, o TCO padrão está chegando: ECMA6 (dezembro de 2013).

Instintivamente, e mantendo a natureza funcional do JS, eu diria que a recursão é o estilo de codificação mais eficiente em 99,99% do tempo. No entanto, Florian Margaine tem razão quando diz que é provável que o gargalo seja encontrado em outro lugar. Se você está manipulando o DOM, provavelmente está mais concentrado em escrever seu código da maneira mais sustentável possível. A API do DOM é o que é: lenta.

Eu acho que é quase impossível oferecer uma resposta definitiva sobre qual é a opção mais rápida. Ultimamente, muitos jspref que eu vi mostram que o mecanismo V8 do Chrome é ridiculamente rápido em algumas tarefas, que são 4x mais lentas no SpiderMonkey da FF e vice-versa. Os mecanismos JS modernos têm todos os tipos de truques nas mangas para otimizar seu código. Não sou especialista, mas sinto que a V8, por exemplo, é altamente otimizada para fechamentos (e recursão), enquanto o mecanismo JScript da MS não é. O SpiderMonkey costuma ter um desempenho melhor quando o DOM está envolvido ...

Em resumo: eu diria que técnica terá melhor desempenho, como sempre em JS, é quase impossível de prever.

Elias Van Ootegem
fonte
3

Sem o modo estrito, o desempenho da iteração geralmente é um pouco mais rápido que a recursão ( além de fazer com que o JIT faça mais trabalho ). A otimização da recursão da cauda elimina essencialmente qualquer diferença perceptível porque transforma toda a sequência de chamadas em um salto.

Exemplo: Jsperf

Sugiro me preocupar muito mais com a clareza e a simplicidade do código quando se trata de escolher entre recursão e iteração.

Bardana
fonte