Dlaczego maszyna JVM nadal nie obsługuje optymalizacji połączeń końcowych?

95

Wydaje się, że dwa lata po optymalizacji jvm -zapobiega-ogonowi-wywołania , pojawiła się prototypowa implementacja i MLVM od jakiegoś czasu określa tę funkcję jako „proto 80%”.

Czy po stronie Sun / Oracle nie ma aktywnego zainteresowania wspieraniem wywołań końcowych, czy po prostu wywołania końcowe mają „[...] zająć drugie miejsce na każdej liście priorytetów funkcji [...]”, jak wspomniano na JVM Szczyt językowy ?

Byłbym bardzo zainteresowany, gdyby ktoś przetestował kompilację MLVM i mógł podzielić się wrażeniami z tego, jak dobrze działa (jeśli w ogóle).

Aktualizacja: Zwróć uwagę, że niektóre maszyny wirtualne, takie jak Avian, obsługują prawidłowe wywołania końcowe bez żadnych problemów.

soc
źródło
14
Po zgłoszonym exodusie ludzi Sun z Oracle, nie spodziewałbym się, że którykolwiek z obecnych projektów będzie kontynuowany, chyba że zostanie to wyraźnie powiedziane przez Oracle :(
Thorbjørn Ravn Andersen
16
Zwróć uwagę, że Twoja zaakceptowana odpowiedź jest całkowicie błędna. Nie ma fundamentalnego konfliktu między optymalizacją wywołań końcowych a OOP i oczywiście kilka języków, takich jak OCaml i F #, ma zarówno OOP, jak i TCO.
JD
2
Cóż, wywoływanie języków OCaml i F # OOP to po pierwsze kiepski żart. Ale tak, OOP i TCO nie mają wiele wspólnego, z wyjątkiem faktu, że środowisko wykonawcze musi sprawdzić, czy optymalizowana metoda nie jest nadpisana / podklasowana gdzie indziej.
soc
5
+1 Pochodząc z C, zawsze zakładałem, że całkowity koszt posiadania jest dany w każdej nowoczesnej JVM. Nigdy nie przyszło mi do głowy, żeby sprawdzić, a kiedy to zrobiłem, wyniki były zaskakujące ...
thkala
2
@soc: "z wyjątkiem faktu, że środowisko wykonawcze musi sprawdzić, czy optymalizowana metoda nie jest nadpisana / podklasa w innym miejscu". Twój „fakt” to kompletny nonsens.
JD

Odpowiedzi:

32

Diagnozowanie kodu Java: zwiększanie wydajności kodu Java ( alt ) wyjaśnia, dlaczego maszyna JVM nie obsługuje optymalizacji wywołań końcowych.

Ale chociaż dobrze wiadomo, jak automatycznie przekształcić funkcję rekurencyjną ogonową w prostą pętlę, specyfikacja Java nie wymaga wykonania tej transformacji. Przypuszczalnie jednym z powodów, dla których nie jest to wymagane, jest to, że generalnie transformacja nie może być wykonana statycznie w języku zorientowanym obiektowo. Zamiast tego transformacja z rekurencyjnej funkcji ogonowej do prostej pętli musi być wykonywana dynamicznie przez kompilator JIT.

Następnie podaje przykład kodu Java, który nie zostanie przekształcony.

Tak więc, jak pokazuje przykład z Listingu 3, nie możemy oczekiwać, że statyczne kompilatory wykonają transformację rekurencji ogona w kodzie Javy, zachowując semantykę języka. Zamiast tego musimy polegać na dynamicznej kompilacji przez JIT. W zależności od JVM zespół JIT może to zrobić lub nie.

Następnie daje test, którego możesz użyć, aby dowiedzieć się, czy Twój JIT to robi.

Oczywiście, ponieważ jest to papier IBM, zawiera wtyczkę:

Uruchomiłem ten program z kilkoma pakietami Java SDK i wyniki były zaskakujące. Uruchomienie na maszynie wirtualnej Hotspot firmy Sun w wersji 1.3 ujawnia, że ​​Hotspot nie wykonuje transformacji. Przy ustawieniach domyślnych miejsce na stosie wyczerpuje się na moim komputerze w mniej niż sekundę. Z drugiej strony JVM IBM dla wersji 1.3 mruczy bez problemu, wskazując, że dokonuje transformacji kodu w ten sposób.

emory
źródło
62
FWIW, wywołania ogonowe to nie tylko funkcje samorekurencyjne, jak sugeruje. Wywołania końcowe to wszelkie wywołania funkcji, które pojawiają się w pozycji ogona. Nie muszą to być wywołania do siebie i nie muszą to być wywołania do znanych statycznie lokalizacji (np. Mogą to być wywołania metod wirtualnych). Problem, który opisuje, nie stanowi problemu, jeśli optymalizacja wywołań ogonowych jest wykonywana poprawnie w ogólnym przypadku, a zatem jego przykład działa doskonale w językach obiektowych, które obsługują wywołania ogonowe (np. OCaml i F #).
JD
3
„musi być wykonywane dynamicznie przez kompilator JIT”, co oznacza, że ​​musi to być wykonywane przez samą maszynę JVM, a nie przez kompilator Javy. Ale OP pyta o JVM.
Raedwald
11
„Ogólnie rzecz biorąc, transformacja nie może być wykonana statycznie w języku zorientowanym obiektowo”. To oczywiście cytat, ale za każdym razem, gdy widzę taką wymówkę, chciałbym zapytać o liczby - bo nie zdziwiłbym się, gdyby w praktyce w większości przypadków udało się to ustalić w czasie kompilacji.
greenoldman
5
Link do cytowanego artykułu jest teraz uszkodzony, chociaż Google zapisuje go w pamięci podręcznej. Co ważniejsze, rozumowanie autora jest błędne. Podany przykład mógłby być zoptymalizowany pod kątem wywołań ogonowych, przy użyciu statycznej, a nie tylko dynamicznej kompilacji, gdyby tylko kompilator wstawił instanceofsprawdzenie, czy thisjest Exampleobiektem (a nie podklasą Example).
Alex D
4
wystarczy link do webarchive web.archive.org/web/20120506085636/http://www.ibm.com/…
Suvitruf - Andrei Apanasik
30

Jednym z powodów, dla których widziałem w przeszłości, że nie implementowałem TCO (i jest to postrzegane jako trudne) w Javie, jest to, że model uprawnień w JVM jest wrażliwy na stos, a zatem wywołania końcowe muszą obsługiwać aspekty bezpieczeństwa.

Uważam, że Clements i Felleisen [1] [2] wykazali, że nie jest to przeszkodą i jestem prawie pewien, że łatka MLVM wspomniana w pytaniu również sobie z tym radzi.

Zdaję sobie sprawę, że to nie odpowiada na twoje pytanie; po prostu dodając interesujące informacje.

  1. http://www.ccs.neu.edu/scheme/pubs/esop2003-cf.pdf
  2. http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf
Alex Miller
źródło
1
+1. Posłuchaj pytań / odpowiedzi pod koniec tej prezentacji Briana Goetza youtube.com/watch?v=2y5Pv4yN0b0&t=3739
mcoolive
15

Być może już to wiesz, ale funkcja nie jest tak trywialna, jak mogłoby się wydawać, ponieważ język Java w rzeczywistości udostępnia programiście ślad stosu.

Rozważ następujący program:

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

Nawet jeśli ma to wywołanie ogonowe, może nie zostać zoptymalizowane. (Jeśli jest zoptymalizowany, nadal wymaga prowadzenia księgowości całego stosu wywołań, ponieważ opiera się na nim semantyka programu).

Zasadniczo oznacza to, że trudno jest to wspierać, będąc nadal kompatybilnym wstecz.

aioobe
źródło
17
Znalazłem błąd w twojej myśli: „wymaga prowadzenia księgowości całego stosu wywołań, ponieważ semantyka programu na nim opiera się”. :-) To jak nowe „stłumione wyjątki”. Programy opierające się na takich rzeczach są skazane na niepowodzenie. Moim zdaniem zachowanie programu jest absolutnie poprawne: odrzucanie ramek stosu jest tym, o co chodzi w wywołaniach tail.
soc
4
@Marco, ale prawie każda metoda może zgłosić wyjątek, z którego cały stos wywołań będzie dostępny, prawda? Poza tym nie możesz z góry zdecydować, które metody będą pośrednio wywoływać gw tym przypadku ... pomyśl na przykład o polimorfizmie i refleksji.
aioobe,
2
Jest to efekt uboczny spowodowany dodaniem ARM w Javie 7. To przykład, że nie możesz polegać na takich rzeczach, które pokazałeś powyżej.
soc
6
„fakt, że język ujawnia stos wywołań utrudnia implementację tego”: czy język wymaga, aby ślad stosu zwracany przez getStackTrace()metodę, x()którą pokazuje kod źródłowy, był wywoływany z metody, y()pokazuje również, że x()została wywołana z y()? Ponieważ jest jakaś wolność, nie ma prawdziwego problemu.
Raedwald
8
To tylko kwestia sformułowania specyfikacji pojedynczej metody, od „daje wszystkie ramki stosu” do „daje wszystkie aktywne ramki stosu, pomijając te przestarzałe przez wywołania ogonowe”. Co więcej, można by uczynić z niego przełącznik wiersza poleceń lub właściwość systemową, czy honorowane jest wywołanie końcowe.
Ingo
12

Java jest najmniej funkcjonalnym językiem, jaki można sobie wyobrazić (no dobra, może nie !), Ale byłaby to wielka zaleta w przypadku języków JVM, takich jak Scala .

Z moich obserwacji wynika, że ​​uczynienie z JVM platformy dla innych języków nigdy nie wydawało się być na szczycie listy priorytetów dla Sun, a teraz chyba dla Oracle.

oxbow_lakes
źródło
16
@ Thorbjørn - napisałem program, aby przewidzieć, czy dany program zatrzyma się w skończonym czasie. Zajęło mi to wieki !
oxbow_lakes
3
Pierwsze BASIC-y, których użyłem, nie miały funkcji, ale raczej GOSUB i RETURN. Nie sądzę, żeby LOLCODE był bardzo funkcjonalny (i można to przyjąć na dwa sposoby).
David Thornley
1
@David, funkcjonalny! = Ma funkcje.
Thorbjørn Ravn Andersen
2
@ Thorbjørn Ravn Andersen: Nie, ale jest to warunek wstępny, nie powiedziałbyś?
David Thornley
3
„uczynienie z JVM platformy dla innych języków nigdy nie wydawało się być na szczycie listy priorytetów firmy Sun”. Włożyli znacznie więcej wysiłku w uczynienie JVM platformą dla języków dynamicznych niż dla języków funkcjonalnych.
JD