Dlaczego Haskell (GHC) jest tak szybki?

Haskell (z GHCkompilatorem) jest znacznie szybszy, niż można się spodziewać . Używana poprawnie, może być zbliżona do języków niskiego poziomu. (Ulubioną rzeczą dla Haskellerów jest próba uzyskania do 5% C (lub nawet pokonania go, ale to oznacza, że ​​używasz nieefektywnego programu C, ponieważ GHC kompiluje Haskell do C).) Moje pytanie brzmi, dlaczego?

Haskell jest deklaratywny i oparty na rachunku lambda. Architektura maszyn jest wyraźnie niezbędna, ponieważ z grubsza opiera się na maszynach Turinga. Rzeczywiście, Haskell nie ma nawet określonej kolejności oceny. Ponadto zamiast zajmować się typami danych maszynowych, cały czas tworzysz algebraiczne typy danych.

Najdziwniejsze są jednak funkcje wyższego rzędu. Można by pomyśleć, że tworzenie funkcji w locie i rozrzucanie ich spowoduje spowolnienie programu. Ale korzystanie z funkcji wyższego rzędu sprawia, że ​​Haskell jest szybszy. Rzeczywiście wydaje się, że aby zoptymalizować kod Haskell, musisz uczynić go bardziej eleganckim i abstrakcyjnym, a nie bardziej maszynowym. Żadna z bardziej zaawansowanych funkcji Haskella nie wydaje się nawet wpływać na jego wydajność, jeśli go nie poprawią.

Przepraszam, jeśli to zabrzmi bzdura, ale oto moje pytanie: Dlaczego Haskell (skompilowany z GHC) jest tak szybki, biorąc pod uwagę jego abstrakcyjny charakter i różnice w stosunku do fizycznych maszyn?

Uwaga: Powodem, dla którego mówię, że C i inne języki rozkazujące są nieco podobne do Maszyn Turinga (ale nie w takim stopniu, w jakim Haskell jest podobny do Lambda Calculus) jest to, że w języku rozkazującym masz skończoną liczbę stanów (aka numer linii) , wraz z taśmą (suwakiem), dzięki czemu stan i bieżąca taśma określają, co zrobić z taśmą. Zobacz wpis w Wikipedii, Ekwiwalenty maszyn Turinga , aby przejść z maszyn Turinga do komputerów.

Zgadzam się z Dietrich Epp: to połączenie kilku rzeczy, które sprawiają, że GHC jest szybki.

Przede wszystkim Haskell ma bardzo wysoki poziom. Dzięki temu kompilator może przeprowadzać agresywne optymalizacje bez przerywania kodu.

Pomyśl o SQL. Teraz, kiedy piszę SELECToświadczenie, może to wyglądać na pętlę rozkazującą, ale tak nie jest . Może się wydawać, że zapętla się we wszystkich wierszach w tej tabeli, próbując znaleźć ten, który pasuje do określonych warunków, ale tak naprawdę „kompilator” (silnik DB) może zamiast tego wyszukiwać indeks - który ma zupełnie inną charakterystykę wydajności. Ponieważ jednak SQL jest tak wysoki, „kompilator” może zastępować całkowicie różne algorytmy, stosować wiele procesorów lub kanałów we / wy lub całe serwery w sposób transparentny i więcej.

Myślę, że Haskell jest taki sam. Może ci się wydawać , że poprosiłeś Haskella o zamapowanie listy danych wejściowych na drugą listę, przefiltrowanie drugiej listy do trzeciej listy, a następnie policz, ile wynikło wyników. Ale nie widziałeś, aby GHC stosowało za kulisami reguły przepisywania fuzji strumienia, przekształcając całość w pojedynczą ciasną pętlę kodu maszynowego, która wykonuje całe zadanie w jednym przejściu danych bez alokacji - coś, co być żmudnym, podatnym na błędy i niemożliwym do utrzymania pisaniem ręcznie. Jest to naprawdę możliwe tylko z powodu braku szczegółów niskiego poziomu w kodzie.

Innym sposobem spojrzenia na to może być… dlaczego Haskell nie miałby być szybki? Co to robi, że powinno spowolnić?

To nie jest interpretowany język, taki jak Perl czy JavaScript. To nawet nie jest system maszyn wirtualnych, takich jak Java czy C #. Kompiluje się aż do natywnego kodu maszynowego, więc nie ma narzutu.

W przeciwieństwie do języków OO [Java, C #, JavaScript…], Haskell ma pełny typ kasowania [jak C, C ++, Pascal…]. Wszystkie sprawdzanie typów odbywa się tylko w czasie kompilacji. Nie ma więc sprawdzania typu w czasie wykonywania, aby spowolnić. (W tym przypadku nie sprawdza się zerowych wskaźników. Na przykład w Javie JVM musi sprawdzić zerowe wskaźniki i zgłosić wyjątek, jeśli je uszanujesz. Haskell nie musi się tym przejmować).

Mówisz, że powolne jest „tworzenie funkcji w locie”, ale jeśli spojrzysz bardzo uważnie, tak naprawdę nie robisz tego. Może to wyglądać tak jak ty, ale tak nie jest. Jeśli powiesz (+5), cóż, jest to zakodowane na stałe w kodzie źródłowym. Nie można go zmienić w czasie wykonywania. Więc to nie jest tak naprawdę funkcja dynamiczna. Nawet funkcje curry naprawdę zapisują parametry w bloku danych. Cały kod wykonywalny faktycznie istnieje w czasie kompilacji; nie ma interpretacji w czasie wykonywania. (W przeciwieństwie do niektórych innych języków, które mają „funkcję ewaluacji”).

Pomyśl o Pascalu. Jest stary i nikt tak naprawdę go nie używa, ale nikt nie narzekałby, że Pascal jest wolny . Jest wiele rzeczy, których można nie lubić, ale powolność tak naprawdę nie jest jedną z nich. Haskell tak naprawdę nie robi tyle, co różni się od Pascala, poza zbieraniem pamięci zamiast ręcznego zarządzania pamięcią. Niezmienne dane pozwalają na kilka optymalizacji silnika GC [które leniwe oceny nieco komplikują].

Myślę, że chodzi o to, że Haskell wygląda na zaawansowanego, wyrafinowanego i na wysokim poziomie, i wszyscy myślą: „och, to jest naprawdę potężne, musi być niesamowicie wolne! ” Ale tak nie jest. A przynajmniej nie jest tak, jak można się spodziewać. Tak, ma niesamowity system pisania. Ale wiesz co? To wszystko dzieje się w czasie kompilacji. Z biegiem czasu już go nie ma. Tak, pozwala konstruować skomplikowane narzędzia ADT z wierszem kodu. Ale wiesz co? ADT tylko zwykły zwykły C unionna structsekundę. Nic więcej.

Prawdziwym zabójcą jest leniwa ocena. Gdy dobrze opanujesz ścisłość / lenistwo swojego kodu, możesz pisać głupio szybki kod, który jest nadal elegancki i piękny. Ale jeśli źle to zrobisz, twój program będzie tysiące razy wolniejszy i naprawdę nie jest oczywiste, dlaczego tak się dzieje.

Na przykład napisałem prosty, trywialny program do zliczania, ile razy każdy bajt pojawia się w pliku. W przypadku pliku wejściowego o wielkości 25 KB uruchomienie programu zajęło 20 minut i połknęło 6 gigabajtów pamięci RAM! To absurdalne !! Ale potem zdałem sobie sprawę, na czym polega problem, dodałem pojedynczy wzór huku, a czas pracy spadł do 0,02 sekundy .

Tutaj Haskell idzie nieoczekiwanie powoli. Przyzwyczajenie się do tego zajmuje trochę czasu. Ale z czasem łatwiej jest pisać naprawdę szybki kod.

Co sprawia, że ​​Haskell jest tak szybki? Czystość. Typy statyczne. Lenistwo. Ale przede wszystkim będąc wystarczająco wysokim poziomem, aby kompilator mógł radykalnie zmienić implementację bez naruszania oczekiwań twojego kodu.

Ale myślę, że to tylko moja opinia ...

Przez długi czas uważano, że języki funkcjonalne nie mogą być szybkie - a zwłaszcza leniwe języki funkcjonalne. Stało się tak, ponieważ ich wczesne wdrożenia zostały w istocie zinterpretowane, a nie autentycznie skompilowane.

Pojawiła się druga fala projektów opartych na redukcji wykresów i otworzyła możliwość znacznie bardziej wydajnej kompilacji. Simon Peyton Jones napisał o tych badaniach w swoich dwóch książkach Wdrażanie funkcjonalnych języków programowania i Wdrażanie języków funkcjonalnych: samouczek (pierwszy z rozdziałami Wadlera i Hancocka, a drugi napisany z Davidem Lesterem). (Lennart Augustsson poinformował mnie również, że jedną z kluczowych motywów poprzedniej książki było opisanie sposobu, w jaki jego kompilator LML, który nie był szeroko komentowany, osiągnął kompilację).

Kluczowym pojęciem przy podejściach do redukcji wykresów, takich jak opisane w tych pracach, jest to, że nie myślimy o programie jako o sekwencji instrukcji, ale o wykresie zależności, który jest oceniany przez szereg lokalnych redukcji. Drugim kluczowym wnioskiem jest to, że ocena takiego wykresu nie musi być interpretowana, ale sam wykres można zbudować z kodu . W szczególności możemy przedstawić węzeł wykresu nie jako „wartość lub„ kod operacji ”i wartości, na których ma działać”, ale zamiast tego jako funkcję, która po wywołaniu zwraca żądaną wartość. Przy pierwszym wywołaniu pyta podwęzły o ich wartości, a następnie działa na nich, a następnie zastępuje się nową instrukcją, która mówi tylko: „zwróć wynik.

Jest to opisane w późniejszym artykule, który wyjaśnia podstawy działania GHC do dziś (choć modulo wiele różnych poprawek): „Wdrażanie leniwych języków funkcjonalnych na standardowym sprzęcie: bezgwiezdna maszyna bez tagów”. . Obecny model wykonania dla GHC jest udokumentowany bardziej szczegółowo na Wiki GHC .

Zatem wgląd jest taki, że ścisłe rozróżnienie „danych” i „kodu”, które uważamy za „fundamentalne” w działaniu maszyn, nie jest tym, jak muszą działać, ale jest narzucone przez nasze kompilatory. Możemy więc to wyrzucić i mieć kod (kompilator), który generuje kod samomodyfikujący (plik wykonywalny) i wszystko może działać całkiem nieźle.

Okazuje się zatem, że choć architektura maszyn jest w pewnym sensie imperatywna, języki mogą się do nich mapować w bardzo zaskakujący sposób, który nie wygląda jak konwencjonalna kontrola przepływu w stylu C, a jeśli uważamy, że jest wystarczająco niski, może to być również wydajny.

Do tego dochodzi wiele innych optymalizacji, w szczególności związanych z czystością, ponieważ pozwala to na większy zakres „bezpiecznych” przekształceń. Kiedy i jak zastosować te przekształcenia, aby poprawiały sytuację, a nie gorzej, jest oczywiście kwestią empiryczną, a przy tym i wielu innych drobnych wyborach lata pracy zostały poświęcone zarówno pracy teoretycznej, jak i praktycznej analizie porównawczej. To oczywiście także odgrywa pewną rolę. Artykuł, który stanowi dobry przykład tego rodzaju badań, brzmi: „ Robienie szybkiego curry: Push / Enter vs. Eval / Apply dla języków wyższego rzędu”.

Na koniec należy zauważyć, że ten model nadal wprowadza koszty ogólne z powodu pośrednich. Można tego uniknąć w przypadkach, w których wiemy, że „bezpieczne” jest robienie rzeczy ściśle, a tym samym unikanie pośrednich wykresów. Mechanizmy wywodzące się ze ścisłości / popytu są ponownie szczegółowo opisane na GHC Wiki .

Cóż, tutaj jest wiele do skomentowania. Postaram się odpowiedzieć jak najwięcej.

Używana poprawnie, może być zbliżona do języków niskiego poziomu.

Z mojego doświadczenia wynika, że ​​zwykle w wielu przypadkach można uzyskać dwukrotność wydajności Rdza. Ale są też (szerokie) przypadki użycia, w których wydajność jest niska w porównaniu do języków niskiego poziomu.

a nawet go pobić, ale to oznacza, że ​​używasz nieefektywnego programu C, ponieważ GHC kompiluje Haskell do C)

To nie do końca poprawne. Haskell kompiluje się do C-- (podzbiór C), który jest następnie kompilowany przez natywny generator kodu do złożenia. Generator kodu rodzimego zwykle generuje szybszy kod niż kompilator C, ponieważ może zastosować pewne optymalizacje, których nie potrafi zwykły kompilator C.

Architektura maszyn jest wyraźnie niezbędna, ponieważ z grubsza opiera się na maszynach Turinga.

To nie jest dobry sposób, aby o tym pomyśleć, szczególnie, że nowoczesne procesory będą oceniać instrukcje w porządku i być może jednocześnie.

Rzeczywiście, Haskell nie ma nawet określonej kolejności oceny.

Faktycznie, Haskell jest niejawnie definiowania kolejności oceny.

Ponadto zamiast zajmować się typami danych maszynowych, cały czas tworzysz algebraiczne typy danych.

Odpowiadają w wielu przypadkach, pod warunkiem, że masz wystarczająco zaawansowany kompilator.

Można by pomyśleć, że tworzenie funkcji w locie i rozrzucanie ich spowoduje spowolnienie programu.

Haskell jest skompilowany, więc funkcje wyższego rzędu nie są tworzone w locie.

wydaje się optymalizować kod Haskell, musisz uczynić go bardziej eleganckim i abstrakcyjnym, a nie bardziej maszynowym.

Ogólnie rzecz biorąc, uczynienie kodu bardziej „maszynowym” jest nieproduktywnym sposobem na zwiększenie wydajności w Haskell. Ale uczynienie go bardziej abstrakcyjnym nie zawsze jest dobrym pomysłem. Co jest dobrym pomysłem jest za pomocą wspólnych struktur danych i funkcji, które zostały mocno zoptymalizowany (takich jak połączonych listach).

f x = [x]i f = puresą dokładnie takie same na przykład w Haskell. Dobry kompilator nie zapewniłby lepszej wydajności w pierwszym przypadku.

Dlaczego Haskell (skompilowany z GHC) jest tak szybki, biorąc pod uwagę jego abstrakcyjny charakter i różnice w stosunku do fizycznych maszyn?

Krótka odpowiedź brzmi „ponieważ została zaprojektowana właśnie do tego”. GHC używa bezgwiezdnej maszyny Tagless G (STG). Możesz przeczytać artykuł na ten temat tutaj (jest dość złożony). GHC robi również wiele innych rzeczy, takich jak analiza ścisłości i optymistyczna ocena .

Powodem, dla którego mówię, że C i inne języki rozkazujące są nieco podobne do Maszyn Turinga (ale nie w takim stopniu, w jakim Haskell jest podobny do rachunku Lambda Calculus), jest to, że w języku rozkazującym masz skończoną liczbę stanów (aka numer linii), wraz za pomocą taśmy (pamięci RAM), dzięki czemu stan i bieżąca taśma określają, co zrobić z taśmą.

Czy zatem chodzi o zamieszanie, że ta zmienność powinna prowadzić do spowolnienia kodu? Lenistwo Haskella w rzeczywistości oznacza, że ​​zmienność nie ma większego znaczenia, niż myślisz, że jest, a ponadto jest na wysokim poziomie, więc kompilator może zastosować wiele optymalizacji. W związku z tym modyfikacja rekordu w miejscu rzadko będzie wolniejsza niż w języku takim jak C.

Dlaczego Haskell (GHC) jest tak szybki?

Coś musiało się radykalnie zmienić, odkąd ostatnio mierzyłem wydajność Haskella. Na przykład:

• Test porównawczy przetwarzania plików RRD, w którym autor stwierdził, że opracowanie Haskella trwało dłużej i działa wolniej (1020 s) niż Go (130 s) i OCaml (67 s), tj. 15 razy wolniej niż OCaml.
• Prosty słownik odniesienia pokazał Haskell działa ~ 10x wolniej niż F #.
• Ray Tracer Porównanie Język jest kolejnym przykładem, gdzie Haskell był wolniejszy niż C ++, Java, a nawet OCaml i Lisp.
• Równolegle rodzajowy QuickSort Haskell 55% mniejsza niż F # i wymaga znacznie więcej kodu.

Co się zmieniło? Zauważam, że ani pytanie, ani żadna z jego aktualnych odpowiedzi nie odnoszą się do jakichkolwiek weryfikowalnych testów porównawczych, a nawet kodu.

Ulubioną rzeczą dla Haskellerów jest próba uzyskania w granicach 5% C

Czy masz jakieś odniesienia do weryfikowalnych wyników, z których ktokolwiek kiedykolwiek się zbliżył?