Warum unterstützt die JVM die Tail-Call-Optimierung immer noch nicht?

95

Zwei Jahre nach der Optimierung des JVM-Prevent-Tail-Call scheint es eine Prototyp- Implementierung zu geben, und MLVM listet die Funktion seit einiger Zeit als "Proto 80%" auf.

Gibt es kein aktives Interesse von Sun / Oracle an der Unterstützung von Tail Calls oder ist es nur so, dass Tail Calls "[...] auf jeder [...] Feature-Prioritätsliste den zweiten Platz einnehmen ", wie in der JVM erwähnt Sprachgipfel ?

Es würde mich sehr interessieren, wenn jemand einen MLVM-Build getestet hat und einige Eindrücke davon teilen könnte, wie gut er funktioniert (wenn überhaupt).

Update: Beachten Sie, dass einige VMs wie Avian ordnungsgemäße Tail-Calls ohne Probleme unterstützen.

soc
quelle
14
Mit dem gemeldeten Exodus von Sun-Leuten von Oracle würde ich nicht erwarten, dass eines der aktuellen Projekte fortgesetzt wird, es sei denn, dies wird ausdrücklich von Oracle gesagt :(
Thorbjørn Ravn Andersen
16
Beachten Sie, dass Ihre akzeptierte Antwort völlig falsch ist. Es gibt keinen grundsätzlichen Konflikt zwischen Tail-Call-Optimierung und OOP, und natürlich haben einige Sprachen wie OCaml und F # sowohl OOP als auch TCO.
JD
2
Das Aufrufen der Sprachen OCaml und F # OOP ist in erster Linie ein schlechter Witz. Aber ja, OOP und TCO haben nicht viel gemeinsam, außer der Tatsache, dass die Laufzeit überprüfen muss, ob die zu optimierende Methode nicht an anderer Stelle überschrieben / untergeordnet wird.
soc
5
+1 Aus einem C-Hintergrund stammend, habe ich immer angenommen, dass TCO in jeder modernen JVM eine Selbstverständlichkeit ist. Es ist mir nie in den
Sinn gekommen
2
@soc: "außer der Tatsache, dass die Laufzeit überprüfen muss, ob die zu optimierende Methode nicht überschrieben / woanders untergeordnet wird". Ihre "Tatsache" ist völliger Unsinn.
JD

Antworten:

32

Diagnose von Java-Code: Die Verbesserung der Leistung Ihres Java-Codes ( alt ) erklärt, warum die JVM die Tail-Call-Optimierung nicht unterstützt.

Obwohl bekannt ist, wie eine schwanzrekursive Funktion automatisch in eine einfache Schleife umgewandelt wird, erfordert die Java-Spezifikation nicht, dass diese Umwandlung durchgeführt wird. Vermutlich ist ein Grund dafür nicht, dass die Transformation im Allgemeinen nicht statisch in einer objektorientierten Sprache durchgeführt werden kann. Stattdessen muss die Transformation von der Schwanzrekursionsfunktion zur einfachen Schleife dynamisch von einem JIT-Compiler durchgeführt werden.

Es gibt dann ein Beispiel für Java-Code, der sich nicht transformieren lässt.

Wie das Beispiel in Listing 3 zeigt, können wir nicht erwarten, dass statische Compiler eine Transformation der Schwanzrekursion in Java-Code durchführen, während die Semantik der Sprache erhalten bleibt. Stattdessen müssen wir uns auf die dynamische Kompilierung durch die JIT verlassen. Abhängig von der JVM kann die JIT dies tun oder nicht.

Dann gibt es einen Test, mit dem Sie herausfinden können, ob Ihre JIT dies tut.

Da es sich um ein IBM Papier handelt, enthält es natürlich einen Stecker:

Ich habe dieses Programm mit einigen Java SDKs ausgeführt, und die Ergebnisse waren überraschend. Die Ausführung auf Suns Hotspot JVM für Version 1.3 zeigt, dass Hotspot die Transformation nicht durchführt. Bei den Standardeinstellungen ist der Stapelspeicher auf meinem Computer in weniger als einer Sekunde erschöpft. Auf der anderen Seite schnurrt IBMs JVM für Version 1.3 problemlos, was darauf hinweist, dass der Code auf diese Weise transformiert wird.

Emory
quelle
62
FWIW, Tail Calls handeln nicht nur von selbstrekursiven Funktionen, wie er impliziert. Tail-Aufrufe sind alle Funktionsaufrufe, die in der Tail-Position angezeigt werden. Sie müssen keine Aufrufe an sich selbst sein und sie müssen keine Aufrufe an statisch bekannte Orte sein (z. B. können sie virtuelle Methodenaufrufe sein). Das Problem, das er beschreibt, ist kein Problem, wenn die Tail-Call-Optimierung im allgemeinen Fall ordnungsgemäß durchgeführt wird und sein Beispiel daher perfekt in objektorientierten Sprachen funktioniert, die Tail-Calls unterstützen (z. B. OCaml und F #).
JD
3
"muss dynamisch von einem JIT-Compiler ausgeführt werden", was bedeutet, dass dies von der JVM selbst und nicht vom Java-Compiler ausgeführt werden muss. Aber das OP fragt nach der JVM.
Raedwald
11
"Im Allgemeinen kann die Transformation nicht statisch in einer objektorientierten Sprache durchgeführt werden." Dies ist natürlich ein Zitat, aber jedes Mal, wenn ich eine solche Ausrede sehe, möchte ich nach Zahlen fragen - denn ich wäre nicht überrascht, wenn sie in der Praxis in den meisten Fällen zur Kompilierungszeit festgelegt werden könnten.
Greenoldman
5
Der Link zum zitierten Artikel ist jetzt fehlerhaft, obwohl Google ihn zwischengespeichert hat. Noch wichtiger ist, dass die Argumentation des Autors fehlerhaft ist. Das angegebene Beispiel könnte durch statische und nicht nur dynamische Kompilierung optimiert werden , wenn nur der Compiler eine instanceofPrüfung einfügt , um festzustellen, ob thises sich um ein ExampleObjekt handelt (und nicht um eine Unterklasse von Example).
Alex D
4
Verlinken
Sie
30

Ein Grund, den ich in der Vergangenheit gesehen habe, um TCO nicht in Java zu implementieren (und es wird als schwierig angesehen), ist, dass das Berechtigungsmodell in der JVM stapelempfindlich ist und daher Tail-Calls die Sicherheitsaspekte berücksichtigen müssen.

Ich glaube, Clements und Felleisen [1] [2] haben gezeigt, dass dies kein Hindernis ist, und ich bin mir ziemlich sicher, dass der in der Frage erwähnte MLVM-Patch dies auch behandelt.

Mir ist klar, dass dies Ihre Frage nicht beantwortet. nur interessante Informationen hinzufügen.

  1. http://www.ccs.neu.edu/scheme/pubs/esop2003-cf.pdf
  2. http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf
Alex Miller
quelle
1
+1. Hören Sie Fragen / Antworten am Ende dieser Präsentation von Brian Goetz youtube.com/watch?v=2y5Pv4yN0b0&t=3739
mcoolive
15

Vielleicht wissen Sie das bereits, aber die Funktion ist nicht so trivial, wie es sich anhört, da die Java-Sprache den Stack-Trace tatsächlich dem Programmierer zur Verfügung stellt.

Betrachten Sie das folgende Programm:

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());
    }
}

Obwohl dies einen "Tail-Call" hat, kann es nicht optimiert werden. (Wenn es wird optimiert, es bedarf noch der Buchführung des gesamten Call-Stack , da die Semantik des Programms beruht darauf.)

Grundsätzlich bedeutet dies, dass es schwierig ist, dies zu unterstützen, während es dennoch abwärtskompatibel ist.

aioobe
quelle
17
Finden Sie den Fehler in Ihrem Gedanken: "Erfordert die Buchhaltung des gesamten Aufrufstapels, da die Semantik des Programms davon abhängt". :-) Es ist wie bei den neuen "unterdrückten Ausnahmen". Programme, die sich auf solche Dinge verlassen, müssen brechen. Meiner Meinung nach ist das Verhalten des Programms absolut korrekt: Das Wegwerfen von Stack-Frames ist das, worum es bei Tail-Aufrufen geht.
Soc
4
@Marco, aber fast jede Methode könnte eine Ausnahme auslösen, von der der gesamte Call-Stack verfügbar sein muss, oder? Außerdem können Sie nicht im Voraus entscheiden, welche Methoden gin diesem Fall indirekt aufgerufen werden. Denken Sie beispielsweise an Polymorphismus und Reflexion.
Aioobe
2
Dies ist ein Nebeneffekt, der durch das Hinzufügen von ARM in Java 7 verursacht wird. Dies ist ein Beispiel dafür, dass Sie sich nicht auf die oben gezeigten Dinge verlassen können.
Soc
6
"Die Tatsache, dass die Sprache den Aufrufstapel verfügbar macht, macht es schwierig, dies zu implementieren": Erfordert die Sprache, dass die getStackTrace()von einer Methode x(), die der Quellcode anzeigt , zurückgegebene Stapelverfolgung von einer Methode aufgerufen wird, y()zeigt dies auchx() aus aufgerufen wurde y()? Denn wenn es etwas Freiheit gibt, gibt es kein wirkliches Problem.
Raedwald
8
Dies ist lediglich eine Frage der Formulierung der Spezifikation einer einzelnen Methode, von "gibt Ihnen alle Stapelrahmen" bis "gibt Ihnen alle aktiven Stapelrahmen, wobei diejenigen weggelassen werden, die durch Endaufrufe veraltet sind". Darüber hinaus könnte man es zu einem Befehlszeilenschalter oder einer Systemeigenschaft machen, ob der Tail-Call berücksichtigt wird.
Ingo
12

Java ist die am wenigsten funktionierende Sprache, die Sie sich vorstellen können (na gut, vielleicht auch nicht !), Aber dies wäre ein großer Vorteil für JVM-Sprachen wie Scala .

Meine Beobachtungen sind, dass die Herstellung der JVM zu einer Plattform für andere Sprachen für Sun und ich für Oracle nie ganz oben auf der Prioritätenliste zu stehen schien.

oxbow_lakes
quelle
16
@ Thorbjørn - Ich habe ein Programm geschrieben, um vorherzusagen, ob ein bestimmtes Programm in einer begrenzten Zeitspanne anhalten würde. Ich habe ewig gebraucht !
oxbow_lakes
3
Die ersten BASICs, die ich verwendet habe, hatten keine Funktionen, sondern GOSUB und RETURN. Ich denke auch nicht, dass LOLCODE sehr funktional ist (und das kann man in zweierlei Hinsicht verstehen).
David Thornley
1
@ David, funktional! = Hat Funktionen.
Thorbjørn Ravn Andersen
2
@ Thorbjørn Ravn Andersen: Nein, aber es ist eine Art Voraussetzung, nicht wahr?
David Thornley
3
"Die JVM zu einer Plattform für andere Sprachen zu machen, schien für Sun nie ganz oben auf der Prioritätenliste zu stehen." Sie haben erheblich mehr Anstrengungen unternommen, um die JVM zu einer Plattform für dynamische Sprachen zu machen, als für funktionale Sprachen.
JD