O que a JVM tem que sacrificar a fim de implementar a otimização de chamada de cauda?

Question

As pessoas dizem que a implementação Clojure é excelente para além da limitação de não ter nenhuma cauda chamada optimização - uma limitação da JVM não a implementação Clojure.

http://lambda-the-ultimate.org/node/2547

Tem sido dito que para implementar TCO em Python sacrificaria

• pilha-trace despejos, e
• depuração regularidade.

Explique-me o que o grande negócio com otimização de chamada de cauda e porque Python precisa dele

Será que os mesmos sacrifícios têm que ser feitos para uma implementação JVM de TCO? Será que qualquer outra coisa tem que ser sacrificado?

Answer 1

Enquanto diferente (em que as instruções il já existia) É interessante notar o esforço adicional do .Net equipe JIT 64 bit tinha que passar a respeitar todas as chamadas de cauda.

Eu chamo, nomeadamente, o comentário:

O lado negativo é claro é que, se você tem de depurar ou código de perfil otimizado, estar preparado para lidar com pilhas de chamadas que parecem que estão faltando alguns frames.

Eu acho que é altamente improvável que a JVM pode evitar isso também.

Tendo em conta que, em circunstâncias em que a otimização de chamada de cauda foi solicitado, o JIT deve assumir que é necessário para evitar um estouro de pilha isso não é algo que só pode ser desligado em compilações de depuração. Eles não são muito uso para depuração se falhar antes de chegar à parte interessante. O 'otimização' é na verdade é uma característica permanente e um problema para rastreamentos de pilha afetadas por ela.

É importante ressaltar que qualquer otimização que evita a criação de um quadro de pilha real quando a fazer uma operação que o programador descreve conceitualmente / entende como sendo uma operação de pilha (chamar uma função, por exemplo) será inerentemente causa uma desconexão entre o que é apresentado para o usuário quando a depuração / fornecendo o rastreamento de pilha e realidade.
Isto é inevitável que o código que descreve a operação torna-se mais e mais em separado dos mecânica da máquina de estado de executar a operação.

Answer 2

O trabalho é andamento agora para adicionar chamadas de cauda para a JVM. Há uma href="http://wikis.sun.com/display/mlvm/TailCalls" rel="nofollow noreferrer"> página falar sobre alguns detalhes.

Answer 3

Sim, é geralmente o caso que a implementação TCO vai evitar que fiquem vestígios pilha completa. Isto é inevitável, porque todo o ponto de TCO é evitar a criação de quadros de pilha adicionais.

Também vale a pena interessante notar que Clojure tem um-não-stack consumindo recurso "recorrência" para contornar esta limitação nas versões atuais da JVM.

Exemplo:

(defn triangle [n accumulator] 
  (if 
    (<= n 0)  
      accumulator
      (recur (dec n) (+ n accumulator))))

(triangle 1000000 0)

=> 500000500000     (note stack does not explode here!)