Czy kompilatory takie jak Javac automatycznie wykrywają czyste funkcje i je równolegle?

Wiadomo, że czyste funkcje ułatwiają parellelizację. Co takiego jest w programowaniu funkcjonalnym, które sprawia, że jest ono z natury przystosowane do wykonywania równoległego?

Czy kompilatory takie jak Javac są wystarczająco inteligentne, aby wykryć, kiedy metoda jest czystą funkcją? Zawsze można zaimplementować klasy, które implementują funkcjonalne interfejsy, takie jak Function , ale mają skutki uboczne.

functional-programming

— Naveen
źródło

Pytanie dotyczy nie tylko tego, czy kompilator może wiedzieć, czy funkcja jest czysta, ale także czy może inteligentnie zaplanować równoległe wykonywanie funkcji czystych. Nie wystarczy wystrzelić nowy wątek dla każdego: jest to nieefektywne. GHC (Haskell) radzi sobie z tym za pomocą lenistwa i „zielonych nici”; Byłbym szczerze zaskoczony, gdyby nawet jakiś nieczysty język próbował, biorąc pod uwagę dodatkową trudność upewnienia się, że czyste wątki zostały poprawnie zaplanowane w odniesieniu do głównego nieczystego wątku.

— Ryan Reich,

@RyanReich, czy są jakieś korzyści wynikające z używania programowania funkcjonalnego w nieczystym języku funkcjonalnym, takim jak Java? czy korzyści z programowania funkcjonalnego są czysto funkcjonalne, takie jak modułowość?

— Naveen

@RyanReich GHC zajmuje się tym problemem, prosząc programistę o adnotację, gdy chce równoległości. Czystość oznacza, że adnotacje te nigdy nie zmieniają semantyki, a jedynie wydajność. (Istnieją również mechanizmy współbieżności, które mogą powodować paralelizm, ale jest to inny kocioł ryb.)

— Derek Elkins opuścił SE

@Naveen Istnieją inne zalety czystych funkcji w zakresie optymalizacji oprócz równoległości, takie jak większa swoboda zmiany kolejności kodu, zapamiętywanie i wspólna eliminacja podwyrażeń. Mogę się mylić, ale wątpię, czy javac próbuje wykryć czystość, ponieważ prawdopodobnie jest to dość rzadkie w kodzie idiomatycznym i nieco trudne dla wszystkich oprócz najbardziej trywialnych przypadków. Na przykład musisz wiedzieć, że nie będzie żadnych NullPointerExceptions. Korzyści wynikające z optymalizacji opartych na tym są również prawdopodobnie niewielkie w przypadku typowych aplikacji Java.

— Derek Elkins opuścił SE

javac to kompilator Java, który pobiera kod źródłowy Java i generuje pliki klas kodu bajtów Java. Jest dość ograniczony co do tego, co może (i powinien) zrobić. Nie ma swobody ani niezbędnych mechanizmów leżących u podstaw wprowadzenia równoległości do pliku klasy bajtów kodu.

— Erik Eidt

Odpowiedzi:

są kompilatorami takimi jak Javac, wystarczająco inteligentnymi, by wykryć, kiedy metoda jest czystą funkcją.

To nie jest kwestia „wystarczająco inteligentna”. Nazywa się to analizą czystości i jest niemożliwe do udowodnienia w ogólnym przypadku: jest to równoważne z rozwiązaniem problemu zatrzymania.

Teraz, oczywiście, optymalizatory robią rzeczy niemożliwe do udowodnienia przez cały czas, „niemożliwe do udowodnienia w ogólnym przypadku” nie oznacza, że nigdy nie działa, to tylko oznacza, że nie może działać we wszystkich przypadkach. Istnieją więc algorytmy do sprawdzania, czy funkcja jest czysta, czy nie, po prostu częściej wynikiem jest „Nie wiem”, co oznacza, że ze względów bezpieczeństwa i poprawności należy założyć że ta konkretna funkcja może być nieczysta.

I nawet w przypadkach, gdy to robi pracę, algorytmy są skomplikowane i kosztowne.

To jest problem nr 1: działa tylko w szczególnych przypadkach .

Problem nr 2: Biblioteki . Aby funkcja była czysta, może ona zawsze wywoływać tylko funkcje czyste (i te funkcje mogą wywoływać tylko funkcje czyste itd.). Javac oczywiście wie tylko o Javie i wie tylko o kodzie, który widzi. Tak więc, jeśli twoja funkcja wywołuje funkcję w innej jednostce kompilacyjnej, nie możesz wiedzieć, czy jest czysta, czy nie. Jeśli wywołuje funkcję napisaną w innym języku, nie możesz tego wiedzieć. Jeśli wywołuje funkcję w bibliotece, która może nawet nie zostać jeszcze zainstalowana, nie możesz tego wiedzieć. I tak dalej.

Działa to tylko wtedy, gdy masz analizę całego programu, gdy cały program jest napisany w tym samym języku i wszystko jest kompilowane za jednym razem. Nie możesz używać żadnych bibliotek.

Problem nr 3: Planowanie . Po ustaleniu, które części są czyste, nadal musisz zaplanować je dla oddzielnych wątków. Albo nie. Uruchamianie i zatrzymywanie wątków jest bardzo kosztowne (szczególnie w Javie). Nawet jeśli utrzymujesz pulę wątków i nie uruchamiasz ich ani nie zatrzymujesz, przełączanie kontekstu wątków jest również drogie. Musisz mieć pewność, że obliczenia będą działały znacznie dłużej niż czas potrzebny na zaplanowanie i zmianę kontekstu, w przeciwnym razie stracisz wydajność, a nie ją zyskasz.

Jak zapewne już się domyślacie, ustalenie, jak długo potrwa obliczenie, jest ogólnie niemożliwe (nie możemy nawet ustalić, czy zajmie to skończoną ilość czasu, nie mówiąc już o tym, ile czasu), a także trudne i kosztowne, nawet w specjalny przypadek.

Na bok: Javac i optymalizacje . Zauważ, że większość implementacji javac w rzeczywistości nie wykonuje wielu optymalizacji. całkowicie go zoptymalizuj, z wyjątkiem tego, że nie może wykonywać wstawiania ponad granicami wątków, a zatem funkcja, którą można całkowicie zoptymalizować, jest teraz niepotrzebnie wykonywana.Na przykład implementacja javac przez Oracle polega na bazowym silniku wykonawczym w celu optymalizacji . Prowadzi to do kolejnego zestawu problemów: powiedzmy, javac zdecydował, że określona funkcja jest czysta i wystarczająco droga, więc kompiluje ją do wykonania na innym wątku. Następnie pojawia się optymalizator platformy (na przykład kompilator HotSpot C2 JIT) i optymalizuje całą funkcję. Teraz masz pusty wątek, który nic nie robi. Albo wyobraź sobie, że javac postanawia zaplanować funkcję w innym wątku, a optymalizator platformy mógłby to zrobić

Tak więc robienie czegoś takiego ma sens tylko wtedy, gdy masz jeden kompilator, który wykonuje większość optymalizacji za jednym razem, aby kompilator wiedział i mógł wykorzystać wszystkie różne optymalizacje na różnych poziomach i ich interakcje między sobą.

Należy zauważyć, że, na przykład, kompilator JIT HotSpot C2 rzeczywiście ma wykonać pewne auto wektoryzacji, który jest również formą auto-zrównoleglenia.

— Jörg W Mittag
źródło

Cóż, w zależności od twojej definicji „czystej funkcji”, użycie nieczystych funkcji w implementacji może być dozwolone.

— Deduplicator

@Deduplicator Cóż, w zależności od definicji definition, stosując odmienne definitionod purityjest prawdopodobnie niejasne

— kot

Twój problem nr 2 jest w większości unieważniony przez fakt, że praktycznie wszystkie optymalizacje są wykonywane przez JIT (oczywiście o tym wiesz, ale go ignorujesz). Podobnie problem nr 3 zostaje częściowo unieważniony, ponieważ JIT w dużej mierze opiera się na statystykach zebranych przez tłumacza. Szczególnie nie zgadzam się z „Nie możesz używać żadnych bibliotek”, ponieważ ratuje nas deoptimizacja. Zgadzam się, że dodatkowa złożoność byłaby problemem.

— maaartinus

@maaartinus: Poza tym tylko sam koniec mojej odpowiedzi jest specyficzny dla javaca. I specjalnie zrobić wzmiankę, na przykład, że „ta działa tylko, gdy masz analizę całego programu, kiedy cały program został napisany w tym samym języku, a wszystko jest kompilowany na raz w jednym zamachem.” Dotyczy to oczywiście C2: dotyczy tylko jednego języka (kod bajtowy JVM) i ma dostęp do całego programu naraz.

— Jörg W Mittag

@ JörgWMittag Wiem, że OP pyta o javac, ale założę się, że zakładają, że javac jest odpowiedzialny za optymalizację. I że prawie nie wiedzą, że jest C2. Nie mówię, że twoja odpowiedź jest zła. Po prostu pozwolenie javacowi na jakąkolwiek optymalizację (z wyjątkiem drobiazgów takich jak używanie StringBuilder) nie ma sensu, więc odrzuciłbym to i po prostu zakładam, że OP pisze javac, ale oznacza Hotspot. Twój problem nr 2 jest całkiem dobrym powodem, aby nie optymalizować niczego w javac.

— maaartinus

W głosowanej odpowiedzi nie odnotowano jednej rzeczy. Synchroniczna komunikacja między wątkami jest niezwykle droga. Jeśli funkcja może być wykonywana z prędkością wielu milionów wywołań na sekundę, w rzeczywistości bardziej cię boli, aby ją zrównoleglić, niż pozostawić ją taką, jaka jest.

Najszybsza forma synchronicznej komunikacji między wątkami, wykorzystująca zajęte pętle ze zmiennymi atomowymi, jest niestety nieefektywna energetycznie. Jeśli musisz zastosować zmienne warunkowe w celu oszczędzania energii, wydajność komunikacji między wątkami ucierpi.

Tak więc kompilator nie tylko musi ustalić, czy funkcja jest czysta, ale musiałby także oszacować czas wykonania funkcji, aby zobaczyć, czy równoległość jest wygraną netto. Musiałby także wybierać między zajętymi pętlami za pomocą zmiennych atomowych lub zmiennych warunkowych. I musiałby tworzyć nici za twoimi plecami.

Dynamiczne tworzenie wątków jest nawet wolniejsze niż stosowanie zmiennych warunkowych. Kompilator musiałby więc skonfigurować pewną liczbę już uruchomionych wątków.

Odpowiedź na twoje pytanie brzmi: nie , kompilatory nie są wystarczająco „inteligentne”, aby automatycznie zrównoleglać czyste funkcje, szczególnie w świecie Java. Są sprytni, nie automatycznie je równolegle!

— juhist
źródło

„ Są inteligentne przez nie auto parallelizing ich! ” : To idzie zbyt daleko. Chociaż prawdą jest, że tworzenie paraleli w każdym możliwym punkcie tylko dla samej siebie byłoby zasadniczo nieefektywne, inteligentny kompilator zidentyfikowałby praktyczną strategię paralelizacji. Myślę, że większość ludzi to rozumie, więc kiedy mówimy o automatycznej równoległości, mamy na myśli automatyczną równoległość.

— Nat

@Nat: Śmiesznie za mocno. Wymagałoby to zidentyfikowania czystych funkcji w skali wykonawczej 100s milisekund, a oczekiwanie, że kompilator uzyska jakiekolwiek pojęcie o czasie wykonywania pętli, które nie mają stałych w swoich iteracjach (a przypadki, których nie chcesz) jest niemądre.

— Joshua,

Zgadzam się - komentarz @ Nat sugeruje, że paralelizacja niekoniecznie oznacza wiele wątków, co jest prawdą. JIT może na przykład wstawiać wiele wywołań do czystej funkcji i przeplatać instrukcje CPU w niektórych przypadkach. Na przykład, jeśli oba wywołania metody pobierają stałą, można ją pobrać raz i przechowywać w rejestrze procesora dla obu instancji używanej metody. Nowoczesne procesory to bestie z licznymi rejestrami ogólnego przeznaczenia i specjalistycznymi instrukcjami, które mogą być bardzo pomocne przy optymalizacji kodu.

@Joshua: Kompilator JIT jest o wiele prostszy. Kompilator JIT może również stwierdzić, że funkcja może nie być czysta, ale jak dotąd żadne wywołanie nie wywoływało nieczystego zachowania.

— gnasher729,

Zgadzam się z @Joshua. Mam trudny do zrównoleglenia algorytm w pracy. Próbowałem ręcznie zrównoleglić go, nawet dokonując uproszczeń przybliżających (a tym samym modyfikując algorytm), i za każdym razem zawiodłem. Nawet program mówiący o tym, czy możliwe jest zrównoleglenie czegoś, jest niezwykle trudny, nawet jeśli byłoby to znacznie prostsze niż faktyczne zrównoleglenie. Pamiętaj, że mówimy o kompletnych językach programowania Turinga.

— juhist