Jakie ograniczenia JVM nakłada na optymalizację wezwania ogona

Clojure nie wykonuje optymalizacji ogona na własną rękę: jeśli masz funkcję rekurencji ogona i chcesz ją zoptymalizować, musisz użyć specjalnej formy recur. Podobnie, jeśli masz dwie wzajemnie rekurencyjne funkcje, możesz je zoptymalizować tylko za pomocą trampoline.

Kompilator Scala jest w stanie wykonać TCO dla funkcji rekurencyjnej, ale nie dla dwóch wzajemnie rekurencyjnych funkcji.

Ilekroć czytałem o tych ograniczeniach, zawsze przypisywano im pewne ograniczenia właściwe dla modelu JVM. Prawie nic nie wiem o kompilatorach, ale to mnie trochę zastanawia. Pozwól mi wziąć przykład z Programming Scala. Tutaj funkcja

def approximate(guess: Double): Double =
  if (isGoodEnough(guess)) guess
  else approximate(improve(guess))

jest przetłumaczone na

0: aload_0
1: astore_3
2: aload_0
3: dload_1
4: invokevirtual #24; //Method isGoodEnough:(D)Z
7: ifeq
10: dload_1
11: dreturn
12: aload_0
13: dload_1
14: invokevirtual #27; //Method improve:(D)D
17: dstore_1
18: goto 2

Tak więc na poziomie kodu bajtowego wystarczy goto. W tym przypadku kompilator wykonuje ciężką pracę.

Jakie narzędzie bazowej maszyny wirtualnej pozwoliłoby kompilatorowi łatwiej obsługiwać TCO?

Na marginesie, nie spodziewałbym się, że rzeczywiste maszyny będą znacznie mądrzejsze niż JVM. Mimo to wiele języków kompilujących się do kodu natywnego, takich jak Haskell, nie wydaje się mieć problemów z optymalizacją wywołań ogonowych (no cóż, Haskell może czasami mieć z powodu lenistwa, ale to już inna kwestia).

Teraz niewiele wiem o Clojure, a niewiele o Scali, ale spróbuję.

Po pierwsze, musimy rozróżnić między WEWNĘTRZNYMI ogonami i ODWRÓCENIE ogona. Rekurencję ogona można raczej łatwo przekształcić w pętlę. W przypadku wezwań ogonów jest to znacznie trudniejsze w ogólnym przypadku. Musisz wiedzieć, jak się nazywa, ale z polimorfizmem i / lub pierwszorzędnymi funkcjami rzadko o tym wiesz, więc kompilator nie może wiedzieć, jak zastąpić wywołanie. Tylko w czasie wykonywania znasz kod docelowy i możesz tam przejść bez przydzielania kolejnej ramki stosu. Na przykład poniższy fragment ma wywołanie ogonowe i nie wymaga miejsca na stosie, gdy jest odpowiednio zoptymalizowany (w tym TCO), ale nie można go wyeliminować podczas kompilacji dla JVM:

function forward(obj: Callable<int, int>, arg: int) =
    let arg1 <- arg + 1 in obj.call(arg1)

Chociaż jest to tylko odrobinę nieefektywne, istnieją całe style programowania (takie jak Continuation Passing Style lub CPS), które mają mnóstwo wywołań ogonowych i rzadko wracają. Wykonanie tego bez pełnego TCO oznacza, że ​​możesz uruchomić tylko małe fragmenty kodu, zanim zabraknie miejsca na stosie.

Jakie narzędzie bazowej maszyny wirtualnej pozwoliłoby kompilatorowi łatwiej obsługiwać TCO?

Instrukcja ogona, na przykład w maszynie wirtualnej Lua 5.1. Twój przykład nie jest już prostszy. Mój staje się mniej więcej taki:

push arg
push 1
add
load obj
tailcall Callable.call
// implicit return; stack frame was recycled

Na marginesie, nie spodziewałbym się, że rzeczywiste maszyny będą znacznie mądrzejsze od JVM.

Masz rację, nie są. W rzeczywistości są mniej inteligentne i dlatego nawet nie wiedzą (dużo) o takich rzeczach, jak ramki stosu. Właśnie dlatego można wyciągać sztuczki, takie jak ponowne wykorzystywanie przestrzeni stosu i przeskakiwanie do kodu bez wypychania adresu zwrotnego.

Clojure może przeprowadzić automatyczną optymalizację rekurencji ogona w pętle: z pewnością jest to możliwe na JVM, jak udowadnia Scala.

W rzeczywistości była to decyzja projektowa, aby tego nie robić - musisz jawnie użyć recurspecjalnego formularza, jeśli chcesz tę funkcję. Zobacz wątek pocztowy Re: Dlaczego nie ma optymalizacji połączeń ogonowych w grupie Google Clojure.

W obecnej JVM jedyne, co jest niemożliwe, to optymalizacja wywołania ogonowego między różnymi funkcjami (wzajemna rekurencja). Nie jest to szczególnie skomplikowane do wdrożenia (inne języki, takie jak Scheme, miały tę funkcję od samego początku), ale wymagałoby to zmiany specyfikacji JVM. Na przykład musisz zmienić zasady dotyczące zachowania pełnego stosu wywołań funkcji.

Przyszła iteracja JVM prawdopodobnie uzyska tę możliwość, chociaż prawdopodobnie jako opcję, aby zachować zachowanie kompatybilności wstecznej dla starego kodu. Powiedz, Podgląd funkcji w Geeknizer wymienia to dla Java 9:

Dodawanie wezwań do ogona i kontynuacji ...

^{Oczywiście przyszłe plany działania zawsze mogą ulec zmianie.}

Jak się okazuje, i tak nie jest to nic wielkiego. W ciągu ponad 2 lat kodowania Clojure mam nigdy nie się z sytuacją, w której brak TCO był problemem. Głównymi tego przyczynami są:

• Możesz już uzyskać szybką rekursję ogona dla 99% typowych przypadków z recurpętlą lub pętlą. Przypadek wzajemnej rekurencji ogona jest rzadki w normalnym kodzie
• Nawet gdy potrzebujesz wzajemnej rekurencji, często głębokość rekurencji jest na tyle płytka, że ​​i tak możesz to zrobić na stosie bez TCO. TCO to w końcu tylko „optymalizacja” ...
• W bardzo rzadkich przypadkach, gdy potrzebujesz jakiejś formy wzajemnej rekurencji nie pochłaniającej stosów, istnieje wiele innych alternatyw, które mogą osiągnąć ten sam cel: leniwe sekwencje, trampoliny itp.

Na marginesie, nie spodziewałbym się, że rzeczywiste maszyny będą znacznie mądrzejsze od JVM.

Nie chodzi o bycie mądrzejszym, ale o bycie innym. Do niedawna JVM był zaprojektowany i zoptymalizowany wyłącznie dla jednego języka (oczywiście Java), który ma bardzo ścisłą pamięć i modele wywoływania.

Nie tylko nie było żadnych gotowskaźników ani wskaźników, nie było nawet sposobu, aby wywołać funkcję „gołą” (która nie była metodą zdefiniowaną w klasie).

Koncepcyjnie, podczas atakowania JVM, autor kompilatora musi zapytać „jak mogę wyrazić tę koncepcję w kategoriach Java?”. I oczywiście nie ma możliwości wyrażenia całkowitego kosztu posiadania w Javie.

Pamiętaj, że nie są one postrzegane jako awarie JVM, ponieważ nie są potrzebne w Javie. Gdy tylko Java będzie potrzebować takich funkcji, jest dodawana do JVM.

Dopiero niedawno władze Java zaczęły poważnie traktować JVM jako platformę dla języków innych niż Java, więc już uzyskało wsparcie dla funkcji, które nie mają odpowiednika w Javie. Najbardziej znanym jest pisanie dynamiczne, które jest już w JVM, ale nie w Javie.

Tak więc na poziomie kodu bajtowego wystarczy goto. W tym przypadku kompilator wykonuje ciężką pracę.

Czy zauważyłeś, że adres metody zaczyna się od 0? Że wszystkie metody zbiorów zaczynają się od 0? JVM nie pozwala wyskoczyć poza metodę.

Nie mam pojęcia, co by się stało z odgałęzieniem z przesunięciem poza metodą, które zostało załadowane przez java - być może zostanie przechwycony przez weryfikator kodu bajtowego, może wygeneruje wyjątek, a może faktycznie wyskoczy poza metodę.

Problem polega oczywiście na tym, że tak naprawdę nie można zagwarantować, gdzie będą inne metody tej samej klasy, a tym bardziej metody innych klas. Wątpię, aby JVM udzielał jakichkolwiek gwarancji co do miejsca załadowania metod, ale chętnie bym go poprawił.