Por que a JVM ainda não oferece suporte à otimização de chamada final?

95

Dois anos após as otimizações de faz-the-jvm-prevent-tail-call-call , parece haver uma implementação de protótipo e o MLVM listou o recurso como "proto 80%" há algum tempo.

Não há interesse ativo da parte da Sun / Oracle em apoiar chamadas finais ou apenas que as chamadas finais estão "[...] fadadas a ficar em segundo lugar em cada lista de prioridade de recursos [...]", conforme mencionado na JVM Language Summit ?

Eu estaria realmente interessado se alguém testou uma compilação de MLVM e pudesse compartilhar algumas impressões de como ela funciona bem (se funcionar).

Atualização: Observe que algumas VMs, como a Avian, oferecem suporte a chamadas de cauda adequadas sem problemas.

soc
fonte
14
Com o êxodo relatado de pessoas da Sun da Oracle, eu não esperaria que qualquer um dos projetos atuais continuasse, a menos que explicitamente dito da Oracle :(
Thorbjørn Ravn Andersen
16
Observe que sua resposta aceita está completamente errada. Não há conflito fundamental entre a otimização de chamada final e OOP e, é claro, várias linguagens como OCaml e F # têm OOP e TCO.
JD
2
Bem, chamar as línguas OCaml e F # OOP é uma piada de mau gosto em primeiro lugar. Mas sim, OOP e TCO não têm muito em comum, exceto o fato de que o tempo de execução deve verificar se o método sendo otimizado não foi sobrescrito / subclassificado em outro lugar.
soc
5
+1 Vindo de uma experiência C, sempre presumi que o TCO era um dado em qualquer JVM moderno. Nunca me ocorreu verificar e, quando o fiz, os resultados foram surpreendentes ...
thkala
2
@soc: "exceto o fato de que o tempo de execução deve verificar se o método sendo otimizado não foi sobrescrito / subclassificado em outro lugar". Seu "fato" é um absurdo completo.
JD

Respostas:

32

Diagnosticando Código Java: Melhorando o Desempenho de Seu Código Java ( alt ) explica por que a JVM não oferece suporte à otimização de chamada final.

Mas embora seja bem conhecido como transformar automaticamente uma função recursiva de cauda em um loop simples, a especificação Java não exige que essa transformação seja feita. Presumivelmente, um motivo pelo qual não é um requisito é que, em geral, a transformação não pode ser feita estaticamente em uma linguagem orientada a objetos. Em vez disso, a transformação da função recursiva de cauda em loop simples deve ser feita dinamicamente por um compilador JIT.

Em seguida, dá um exemplo de código Java que não se transforma.

Portanto, como mostra o exemplo da Listagem 3, não podemos esperar que os compiladores estáticos realizem a transformação da recursão final no código Java enquanto preservam a semântica da linguagem. Em vez disso, devemos contar com a compilação dinâmica pelo JIT. Dependendo do JVM, o JIT pode ou não fazer isso.

Em seguida, ele fornece um teste que você pode usar para descobrir se seu JIT faz isso.

Naturalmente, como este é um artigo da IBM, inclui um plugue:

Eu executei este programa com alguns SDKs Java e os resultados foram surpreendentes. Executar no Hotspot JVM da Sun para a versão 1.3 revela que o Hotspot não realiza a transformação. Nas configurações padrão, o espaço da pilha se esgota em menos de um segundo na minha máquina. Por outro lado, a JVM da IBM para a versão 1.3 ronrona sem problemas, indicando que ela transforma o código dessa maneira.

emory
fonte
62
FWIW, as chamadas finais não são apenas sobre funções auto-recursivas, como ele sugere. Chamadas posteriores são quaisquer chamadas de função que aparecem na posição final. Eles não precisam ser chamadas para self e não precisam ser chamadas para locais estaticamente conhecidos (por exemplo, podem ser chamadas de método virtual). O problema que ele descreve não é um problema se a otimização da chamada final for feita corretamente no caso geral e, conseqüentemente, seu exemplo funciona perfeitamente em linguagens orientadas a objetos que suportam chamadas finais (por exemplo, OCaml e F #).
JD
3
"deve ser feito dinamicamente por um compilador JIT", o que significa que deve ser feito pelo próprio JVM em vez do compilador Java. Mas o OP está perguntando sobre a JVM.
Raedwald,
11
"em geral, a transformação não pode ser feita estaticamente em uma linguagem orientada a objetos." Claro que é uma citação, mas sempre que vejo tal desculpa gostaria de perguntar sobre os números - porque não ficaria surpreendido se na prática na maioria dos casos pudesse ser estabelecido em tempo de compilação.
greenoldman
5
O link para o artigo citado está quebrado, embora o Google o tenha armazenado em cache. Mais importante ainda, o raciocínio do autor é falho. O exemplo dado poderia ser otimizado por chamada final, usando compilação estática e não apenas dinâmica, se apenas o compilador inserisse uma instanceofverificação para ver se thisé um Exampleobjeto (em vez de uma subclasse de Example).
Alex D
4
basta acessar
Suvitruf - Andrei Apanasik
30

Um motivo que vi no passado para não implementar o TCO (e isso é visto como difícil) em Java é que o modelo de permissão na JVM é sensível à pilha e, portanto, as chamadas finais devem lidar com os aspectos de segurança.

Acredito que Clements e Felleisen [1] [2] demonstraram que isso não é um obstáculo e tenho quase certeza de que o patch MLVM mencionado na pergunta também lida com isso.

Sei que isso não responde à sua pergunta; apenas adicionando informações interessantes.

  1. http://www.ccs.neu.edu/scheme/pubs/esop2003-cf.pdf
  2. http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf
Alex Miller
fonte
1
+1. Ouça as perguntas / respostas no final desta apresentação de Brian Goetz youtube.com/watch?v=2y5Pv4yN0b0&t=3739
mcoolive
15

Talvez você já saiba disso, mas o recurso não é tão trivial quanto pode parecer, já que a linguagem Java realmente expõe o rastreamento da pilha para o programador.

Considere o seguinte programa:

public class Test {

    public static String f() {
        String s = Math.random() > .5 ? f() : g();
        return s;
    }

    public static String g() {
        if (Math.random() > .9) {
            StackTraceElement[] ste = new Throwable().getStackTrace();
            return ste[ste.length / 2].getMethodName();
        }
        return f();
    }

    public static void main(String[] args) {
        System.out.println(f());
    }
}

Mesmo que isso tenha uma "chamada de cauda", pode não ser otimizado. (Se for otimizado, ainda requer a manutenção de toda a pilha de chamadas, uma vez que a semântica do programa depende disso.)

Basicamente, isso significa que é difícil suportar isso enquanto ainda é compatível com versões anteriores.

aioobe
fonte
17
Encontrou o erro em seu pensamento: "requer a contabilidade de toda a pilha de chamadas, uma vez que a semântica do programa depende disso". :-) É como as novas "Exceções suprimidas". Programas que dependem dessas coisas estão fadados ao fracasso. Na minha opinião, o comportamento do programa é absolutamente correto: jogar fora os stack frames é o objetivo das chamadas finais.
soc,
4
@Marco, mas praticamente qualquer método pode lançar uma exceção, a partir da qual toda a pilha de chamadas estará disponível, certo? Além disso, você não pode decidir com antecedência quais métodos chamarão indiretamente gneste caso ... pense em polimorfismo e reflexão, por exemplo.
aioobe
2
É um efeito colateral causado pela adição de ARM no Java 7. É um exemplo de que você não pode confiar nas coisas que mostrou acima.
soc
6
"o fato de que a linguagem expõe a pilha de chamadas torna difícil implementar isso": a linguagem exige que o rastreamento de pilha retornado por getStackTrace()de um método x()que o código-fonte mostra ser chamado de um método y()também mostra que x()foi chamado y()? Porque se há alguma liberdade, não há problema real.
Raedwald,
8
É apenas uma questão de formular as especificações de um único método, de "fornece todos os frames da pilha" a "fornece todos os frames da pilha ativos, deixando de fora os obsoletos por chamadas finais". Além disso, pode-se torná-lo uma opção de linha de comando ou uma propriedade do sistema, quer a chamada final seja respeitada.
Ingo
12

Java é a linguagem menos funcional que você poderia imaginar (bem, OK, talvez não !), Mas isso seria uma grande vantagem para linguagens JVM, como Scala , que são.

Minhas observações são que tornar a JVM uma plataforma para outras linguagens nunca pareceu estar no topo da lista de prioridades da Sun e, agora, da Oracle, acho.

oxbow_lakes
fonte
16
@ Thorbjørn - escrevi um programa para prever se um determinado programa pararia em um período finito de tempo. Demorei muito !
oxbow_lakes 01 de
3
Os primeiros BASICs que usei não tinham funções, mas sim GOSUB e RETURN. Também não acho que LOLCODE seja muito funcional (e você pode interpretar isso em dois sentidos).
David Thornley,
1
@David, funcional! = Tem funções.
Thorbjørn Ravn Andersen,
2
@ Thorbjørn Ravn Andersen: Não, mas é uma espécie de pré-requisito, não acha?
David Thornley,
3
"tornar a JVM uma plataforma para outras linguagens nunca pareceu estar no topo da lista de prioridades da Sun". Eles se esforçaram consideravelmente mais para tornar a JVM uma plataforma para linguagens dinâmicas do que para linguagens funcionais.
JD