Jak język, którego kompilator napisany jest w C, może być kiedykolwiek szybszy niż C?

Patrząc na stronę Julii , możesz zobaczyć testy porównawcze kilku języków w kilku algorytmach (czasy pokazane poniżej). W jaki sposób język z kompilatorem napisanym pierwotnie w C może przewyższyć kod C?

Rysunek: czasy testu porównawczego w stosunku do C (im mniejsze, tym lepsza wydajność C = 1,0).

Nie ma koniecznej zależności między implementacją kompilatora a jego wydajnością. Mógłbyś napisać kompilator w języku takim jak Python lub Ruby, którego najczęstsze implementacje są bardzo wolne, a ten kompilator mógłby wypisać wysoce zoptymalizowany kod maszynowy, który byłby w stanie przewyższyć C. Sam kompilator długo by działał, ponieważ jegokod jest napisany w wolnym języku. (Mówiąc dokładniej, napisane w języku z powolną implementacją. Języki nie są z natury szybkie ani powolne, jak zauważa Raphael w komentarzu. Rozwijam ten pomysł poniżej.) Skompilowany program byłby tak szybki jak jego dozwolona własna implementacja - moglibyśmy napisać w Pythonie kompilator, który generuje ten sam kod maszynowy co kompilator Fortran, a nasze skompilowane programy byłyby tak szybkie jak Fortran, nawet jeśli skompilowanie ich zajęłoby dużo czasu.

To inna historia, jeśli mówimy o tłumaczu. Tłumacze muszą działać, gdy uruchomiony jest program, który interpretują, więc istnieje związek między językiem, w którym tłumacz jest wdrożony, a wydajnością interpretowanego kodu. Potrzeba sprytnej optymalizacji środowiska wykonawczego, aby język interpretowany działał szybciej niż język, w którym interpreter jest zaimplementowany, a ostateczna wydajność może zależeć od tego, jak podatny jest kawałek tego rodzaju optymalizacji. Wiele języków, takich jak Java i C #, używa środowisk wykonawczych z modelem hybrydowym, który łączy niektóre zalety tłumaczy z niektórymi zaletami kompilatorów.

Jako konkretny przykład przyjrzyjmy się bliżej Pythonowi. Python ma kilka implementacji. Najpopularniejszym jest CPython, interpreter kodu bajtowego napisany w C. Istnieje również PyPy, który jest napisany w specjalnym dialekcie Pythona o nazwie RPython i który wykorzystuje hybrydowy model kompilacji podobny do JVM. PyPy jest znacznie szybszy niż CPython w większości testów; używa różnego rodzaju niesamowitych sztuczek, aby zoptymalizować kod w czasie wykonywania. Jednak język Python, w którym działa PyPy, jest dokładnie tym samym językiem, w którym działa CPython, z wyjątkiem kilku różnic, które nie wpływają na wydajność.

Załóżmy, że napisaliśmy kompilator w języku Python dla Fortran. Nasz kompilator wytwarza ten sam kod maszynowy co GFortran. Teraz kompilujemy program Fortran. Możemy uruchomić nasz kompilator na CPython lub możemy uruchomić go na PyPy, ponieważ jest napisany w Pythonie i obie te implementacje działają w tym samym języku Python. Przekonamy się, że jeśli uruchomimy nasz kompilator na CPython, następnie uruchomimy go na PyPy, a następnie skompilujemy to samo źródło Fortran z GFortran, otrzymamy dokładnie ten sam kod maszynowy trzy razy, więc skompilowany program zawsze będzie działał z mniej więcej taką samą prędkością. Czas potrzebny na wyprodukowanie tego skompilowanego programu będzie jednak inny. CPython najprawdopodobniej potrwa dłużej niż PyPy, a PyPy najprawdopodobniej potrwa dłużej niż GFortran, mimo że wszystkie z nich wyprowadzą ten sam kod maszynowy na końcu.

Po zeskanowaniu tabeli porównawczej witryny Julia wygląda na to, że żaden z języków działających na interpreterach (Python, R, Matlab / Octave, JavaScript) nie ma żadnych testów porównawczych, w których pokonują C. Jest to generalnie zgodne z tym, czego się spodziewałbym, chociaż mogłem sobie wyobrazić kod napisany za pomocą wysoce zoptymalizowanej biblioteki Numpy Pythona (napisanej w C i Fortran), pokonując niektóre możliwe implementacje C podobnego kodu. Języki, które są równe lub lepsze niż C są kompilowane (Fortran, Julia ) lub przy użyciu modelu hybrydowego z częściową kompilacją (Java i prawdopodobnie LuaJIT). PyPy korzysta również z modelu hybrydowego, więc jest całkiem możliwe, że gdybyśmy uruchomili ten sam kod Pythona na PyPy zamiast CPython, faktycznie widzielibyśmy go jako C w niektórych testach porównawczych.

Jak maszyna zbudowana przez człowieka może być silniejsza od człowieka? To jest dokładnie to samo pytanie.

Odpowiedź jest taka, że ​​wyjście kompilatora zależy od algorytmów zaimplementowanych przez ten kompilator, a nie od języka używanego do jego implementacji. Możesz napisać naprawdę wolny, nieefektywny kompilator, który wytwarza bardzo wydajny kod. W kompilatorze nie ma nic specjalnego: to tylko program, który pobiera dane wejściowe i generuje dane wyjściowe.

Chcę zwrócić uwagę na wspólne założenie, które moim zdaniem jest błędne do tego stopnia, że ​​szkodzi przy wyborze narzędzi do pracy.

Nie ma czegoś takiego jak wolny lub szybki język. ¹

W drodze do procesora, który faktycznie coś robi, jest wiele kroków².

1. Co najmniej jeden programista z określonymi zestawami umiejętności.
2. (Formalny) język, w którym programują („kod źródłowy”).
3. Biblioteki, których używają.
4. Coś, co tłumaczy kod źródłowy na kod maszynowy (kompilatory, interpretatory).
5. Ogólna architektura sprzętowa, np. Liczba jednostek przetwarzających i układ hierarchii pamięci.
6. System operacyjny zarządzający sprzętem.
7. Optymalizacje procesora.

Każdy element przyczynia się do rzeczywistego czasu wykonywania, który można zmierzyć, czasem w dużym stopniu. Różne „języki” koncentrują się na różnych rzeczach3.

Podam tylko kilka przykładów.

• 1 vs 2-4 : przeciętny programista C prawdopodobnie wygeneruje znacznie gorszy kod niż przeciętny programista Java, zarówno pod względem poprawności, jak i wydajności. Jest tak, ponieważ programista ma więcej obowiązków w C.

• 1/4 vs 7 : w języku niskiego poziomu, takim jak C, możesz być w stanie wykorzystać niektóre funkcje procesora jako programista . W językach wyższego poziomu może to zrobić tylko kompilator / tłumacz, tylko jeśli znają docelowy procesor.

• 1/4 vs 5 : czy chcesz lub musisz kontrolować układ pamięci, aby jak najlepiej wykorzystać dostępną architekturę pamięci? Niektóre języki dają ci kontrolę nad tym, niektóre nie.

• 2/4 vs 3 : Sam interpretowany Python jest strasznie wolny, ale istnieją popularne powiązania z wysoce zoptymalizowanymi, natywnie skompilowanymi bibliotekami do obliczeń naukowych. Więc robienie pewnych rzeczy w Pythonie jest w końcu szybkie , jeśli większość pracy jest wykonywana przez te biblioteki.

• 2 vs 4 : Standardowy interpreter języka Ruby jest dość wolny. Z drugiej strony JRuby może być bardzo szybki. To jest ten sam język jest szybki przy użyciu innego kompilatora / interpretera.

• 1/2 vs 4 : Za pomocą optymalizacji kompilatora prosty kod można przełożyć na bardzo wydajny kod maszynowy.

Najważniejsze jest to, że znaleziony przez ciebie test porównawczy nie ma większego sensu, przynajmniej nie po sprowadzeniu do tabeli, którą zawierasz. Nawet jeśli interesuje Cię tylko czas pracy, musisz określić cały łańcuch od programisty do procesora; zamiana dowolnego elementu może radykalnie zmienić wyniki.

Żeby było jasne, to odpowiada na pytanie, ponieważ pokazuje, że język, w którym kompilator (krok 4) jest napisany, jest tylko jednym elementem układanki i prawdopodobnie wcale nie jest istotny (patrz inne odpowiedzi).

1. Z pewnością istnieją funkcje językowe, które są droższe do wdrożenia niż inne. Ale istnienie funkcji nie oznacza, że ​​musisz z nich korzystać, a droga funkcja może zaoszczędzić na korzystaniu z wielu tańszych, a tym samym ostatecznie się opłacić. (Mają inne zalety, których nie można zmierzyć w czasie wykonywania).
2. Pomijam poziom algorytmu, ponieważ nie zawsze ma on zastosowanie i jest w większości niezależny od używanego języka programowania. Należy pamiętać, że różne algorytmy lepiej nadają się na przykład na inny sprzęt.

3. Celowo nie wybieram tutaj różnych wskaźników sukcesu: wydajności czasu pracy, wydajności pamięci, czasu programisty, bezpieczeństwa, bezpieczeństwa, (do udowodnienia?) Poprawności, wsparcia narzędziowego, niezależności od platformy, ...

   Porównywanie języków z jedną miarą, mimo że zostały one zaprojektowane do zupełnie innych celów, jest ogromnym błędem.

Jest jedna zapomniana rzecz dotycząca optymalizacji.

Odbyła się długa debata o tym, że fortran przewyższa C. Rozbijając zniekształconą debatę: ten sam kod został napisany w C i fortran (jak sądzili testerzy), a wydajność została przetestowana na podstawie tych samych danych. Problem polega na tym, że te języki się różnią, C pozwala na aliasing wskaźników, podczas gdy fortran nie.

Więc kody nie były takie same, nie było __restrict w plikach testowanych w C, co dało różnice, po przepisaniu plików w celu poinformowania kompilatora, że ​​może zoptymalizować wskaźniki, środowiska uruchomieniowe stają się podobne.

Chodzi o to, że niektóre techniki optymalizacji są łatwiejsze (lub zaczynają być legalne) w nowo utworzonym języku.

$X$

Po drugie, VM może przeprowadzić test ciśnienia podczas pracy, dzięki czemu może pobrać kod pod ciśnieniem i zoptymalizować go, a nawet wstępnie go wyliczyć podczas działania. Z góry skompilowany program C nie oczekuje, gdzie jest presja lub (przez większość czasu) istnieją ogólne wersje plików wykonywalnych dla ogólnej rodziny maszyn.

W tym teście jest również JS, cóż, są szybsze maszyny wirtualne niż V8, a także działa szybciej niż C w niektórych testach.

Sprawdziłem to, a w kompilatorach C dostępne były unikalne techniki optymalizacji.

Kompilator C musiałby wykonać statyczną analizę całego kodu naraz, przejść na daną platformę i obejść problemy z wyrównaniem pamięci.

Maszyna wirtualna po prostu dokonała transliteracji części kodu w celu zoptymalizowania złożenia i uruchomienia go.

O Julii - kiedy sprawdziłem, że działa na kodzie AST, na przykład GCC pominęło ten krok i dopiero niedawno zacząłem pobierać z tego informacje. To plus inne ograniczenia i techniki maszyn wirtualnych mogą nieco wyjaśnić.

Przykład: weźmy prostą pętlę, która pobiera początkowy punkt końcowy ze zmiennych i ładuje część zmiennych do obliczeń znanych w czasie wykonywania.

Kompilator C generuje zmienne ładujące z rejestrów.
Ale w czasie wykonywania te zmienne są znane i traktowane jako stałe poprzez wykonanie.
Zamiast więc ładować zmienne z rejestrów (i nie wykonywać buforowania, ponieważ może się zmieniać, a od analizy statycznej nie jest jasne), są one traktowane w pełni jak stałe i są składane, propagowane.

Poprzednie odpowiedzi podają prawie wyjaśnienie, choć głównie z pragmatycznego punktu widzenia, ponieważ pytanie ma sens , co doskonale wyjaśnia odpowiedź Raphaela .

Dodając do tej odpowiedzi, należy zauważyć, że w dzisiejszych czasach kompilatory C są napisane w C. Oczywiście, jak zauważył Raphael, ich wydajność i wydajność mogą zależeć między innymi od procesora, na którym działa. Ale zależy to również od optymalizacji przeprowadzonej przez kompilator. Jeśli napiszesz w C lepszy kompilator optymalizujący dla C (który następnie skompilujesz ze starym, aby móc go uruchomić), otrzymasz nowy kompilator, który sprawia, że ​​C jest szybszym językiem niż wcześniej. Więc, co jest szybkość C? Zauważ, że możesz nawet skompilować nowy kompilator sam ze sobą, jako drugi przebieg, dzięki czemu kompiluje się bardziej wydajnie, choć nadal daje ten sam kod obiektowy. Twierdzenie o pełnym zatrudnieniu pokazuje, że nie jest to koniec takich ulepszeń (dzięki Rafaelowi za wskaźnik).

Myślę jednak, że warto sformalizować tę kwestię, ponieważ bardzo dobrze ilustrują niektóre podstawowe pojęcia, a szczególnie denotacyjne i operacyjne spojrzenie na rzeczy.

Co to jest kompilator?

$C_{S\to T}$$C$$\mathcal C_{S\to T}$$P_{:S}$$\mathcal P$ $S$$P_{:T}$ $T$$\mathcal P$

$\mathcal C_{S\to T}$$C_{S\to T}$$\{(P_{:S},P_{:T})\mid P_S\in S \wedge P_T\in T\}$

$\mathcal C_{S\to T}$$P_S$$P_T$$\mathcal P$

$P_{:T}$$P_{:S}$$\mathcal C_{S\to T}$

Udoskonalając argument, prawdopodobnie chcemy, aby kompilator miał dobrą wydajność, aby tłumaczenie mogło być wykonane w rozsądnym czasie. Wydajność programu kompilatora ma więc znaczenie dla użytkowników, ale nie ma wpływu na semantykę. Mówię o wydajności, ponieważ teoretyczna złożoność niektórych kompilatorów może być znacznie wyższa, niż można by się spodziewać.

O ładowaniu

Zilustruje to rozróżnienie i pokaże praktyczne zastosowanie.

$S$$I_S$$C_{S\to T\,:S}$$S$$C_{S\to T\,:S}$$I_S$$P_{:S}$$P_{:T}$$S$$T$

$C_{S\to T\,:S}$$S$$C_{S\to T\,:T}$$T$$T$$T$

Zgodnie z twierdzeniem Bluma o przyspieszeniu istnieją programy, które napisane i działające na najszybszej kombinacji komputer / kompilator będą działały wolniej niż program dla tego samego na pierwszym komputerze z uruchomioną interpretacją języka BASIC. Po prostu nie ma „najszybszego języka”. Wszystko, co możesz powiedzieć, to to, że jeśli napiszesz ten sam algorytm w kilku językach (implementacje; jak wspomniano, istnieje wiele różnych kompilatorów C, a nawet natknąłem się na dość sprawnego interpretera C), będzie on działał szybciej lub wolniej w każdym .

Nie może istnieć hierarchia „zawsze wolniejsza”. Jest to zjawisko, o którym wszyscy biegli w kilku językach są świadomi: każdy język programowania został zaprojektowany dla określonego rodzaju aplikacji, a częściej używane implementacje zostały pięknie zoptymalizowane dla tego typu programów. Jestem prawie pewien, że np. Program do wygłupiania się z ciągami napisanymi w Perlu prawdopodobnie pobije ten sam algorytm napisany w C, podczas gdy program chrupiący duże tablice liczb całkowitych w C będzie szybszy niż Perl.

Wróćmy do pierwotnego wiersza: „Jak język, którego kompilator napisany jest w C, może być szybszy niż C?” Myślę, że to naprawdę znaczyło: jak program napisany w Julii, którego rdzeń jest napisany w C, może być szybszy niż program napisany w C? W szczególności, w jaki sposób program „mandel” napisany w Julii może działać w 87% czasu wykonania równoważnego programu „mandel” napisanego w C?

Traktat Babou jest jedyną jak dotąd poprawną odpowiedzią na to pytanie. Wszystkie pozostałe odpowiedzi jak dotąd odpowiadają mniej więcej na inne pytania. Problem z tekstem Babou polega na tym, że opis teoretyczny „Co to jest kompilator” o długości wielu akapitów jest napisany w taki sposób, że oryginalny plakat prawdopodobnie będzie miał problemy ze zrozumieniem. Każdy, kto pojmie pojęcia, o których mowa w słowach „semantyczny”, „denotacyjnie”, „realizacyjny”, „obliczalny” i tak dalej, zna już odpowiedź na pytanie.

Prostszą odpowiedzią jest to, że ani kod C, ani kod Julii, nie jest bezpośrednio wykonywalny przez maszynę. Oba muszą zostać przetłumaczone, a ten proces tłumaczenia wprowadza wiele sposobów, w których wykonywalny kod maszynowy może być wolniejszy lub szybszy, ale nadal daje ten sam efekt końcowy. Zarówno C, jak i Julia wykonują kompilację, co oznacza serię tłumaczeń na inną formę. Zwykle plik tekstowy czytelny dla człowieka jest tłumaczony na jakąś wewnętrzną reprezentację, a następnie zapisywany jako sekwencja instrukcji, które komputer może bezpośrednio zrozumieć. W przypadku niektórych języków jest to coś więcej, a Julia jest jednym z nich - ma kompilator „JIT”, co oznacza, że ​​cały proces tłumaczenia nie musi odbywać się od razu dla całego programu. Ale wynikiem końcowym dla dowolnego języka jest kod maszynowy, który nie wymaga dalszego tłumaczenia, kod, który można wysłać bezpośrednio do procesora, aby coś zrobić. W końcu TO jest „obliczenie” i istnieje więcej niż jeden sposób, aby powiedzieć procesorowi CPU, w jaki sposób uzyskać pożądaną odpowiedź.

Można sobie wyobrazić język programowania, który ma zarówno operator „plus”, jak i „zwielokrotnienie”, oraz inny język, który ma tylko „plus”. Jeśli twoje obliczenia wymagają mnożenia, jeden język będzie „wolniejszy”, ponieważ oczywiście procesor może zrobić oba bezpośrednio, ale jeśli nie masz możliwości wyrażenia potrzeby pomnożenia 5 * 5, musisz napisać „5 + 5 + 5 + 5 + 5 ”. Ta ostatnia zajmie więcej czasu, aby dojść do tej samej odpowiedzi. Przypuszczalnie coś takiego dzieje się z Julią; być może język pozwala programiście określić pożądany cel obliczenia zestawu Mandelbrota w sposób, którego nie można bezpośrednio wyrazić w C.

Procesor zastosowany w teście został wymieniony jako procesor Xeon E7-8850 2,00 GHz. Benchmark C wykorzystał kompilator gcc 4.8.2 do wygenerowania instrukcji dla tego procesora, a Julia korzysta ze struktury kompilatora LLVM. Możliwe, że backend gcc (część, która wytwarza kod maszynowy dla konkretnej architektury procesora) nie jest tak zaawansowany jak backend LLVM. To może mieć wpływ na wydajność. Dzieje się też wiele innych rzeczy - kompilator może „zoptymalizować”, być może wydając instrukcje w innej kolejności niż określona przez programistę, a nawet nie robiąc żadnych rzeczy, jeśli może przeanalizować kod i stwierdzić, że nie są wymagane, aby uzyskać właściwą odpowiedź. A programista mógł napisać część programu C w sposób, który spowalnia go, ale nie „

Wszystko to można powiedzieć: istnieje wiele sposobów pisania kodu maszynowego w celu obliczenia zestawu Mandelbrota, a używany język ma znaczący wpływ na sposób pisania tego kodu maszynowego. Im więcej rozumiesz na temat kompilacji, zestawów instrukcji, pamięci podręcznych itd., Tym lepiej będziesz przygotowany do uzyskania pożądanych rezultatów. Główną zaletą wyników testu cytowanych dla Julii jest to, że żaden język ani narzędzie nie jest najlepsze we wszystkim. W rzeczywistości najlepszym współczynnikiem prędkości na całym wykresie była Java!

Szybkość skompilowanego programu zależy od dwóch rzeczy:

1. Charakterystyka wydajności maszyny ją wykonującej
2. Zawartość pliku wykonywalnego

Język, w którym napisany jest kompilator, nie ma znaczenia dla (1). Na przykład kompilator Java można napisać w języku C, Java lub Python, ale we wszystkich przypadkach „maszyną” wykonującą program jest JVM.

Język, w którym napisany jest kompilator, nie ma znaczenia dla (2). Na przykład nie ma powodu, dla którego kompilator C napisany w Pythonie nie może wypisać dokładnie tego samego pliku wykonywalnego co kompilator C napisany w C lub Javie.

Spróbuję zaoferować krótszą odpowiedź.

Sedno pytania leży w definicji „prędkości” języka .

Większość, jeśli nie wszystkie testy porównania prędkości nie sprawdzają maksymalnej możliwej prędkości. Zamiast tego piszą mały program w języku, który chcą przetestować, aby rozwiązać problem. Podczas pisania programu programiści używają tego, co zakładają * jako najlepszej praktyki i konwencji języka w czasie testu. Następnie mierzą prędkość, z jaką program został wykonany.

* Założenia są czasami błędne.

Kod napisany w języku X, którego kompilator jest napisany w C, może przewyższać kod napisany w C, pod warunkiem, że kompilator C nie zapewnia optymalnej optymalizacji w porównaniu z językiem X. Jeśli utrzymamy optymalizację poza dyskusją, to czy kompilator X mógłby wygenerować lepiej kod obiektowy niż wygenerowany przez kompilator C, a następnie kod napisany w X może wygrać wyścig.

Ale jeśli język X jest językiem interpretowanym, a interpreter jest napisany w C, i jeśli założymy, że interpreter języka X i kodu napisanego w C jest kompilowany przez ten sam kompilator C, to w żaden sposób kod napisany w X nie będzie lepszy niż kod napisane w C, pod warunkiem, że obie implementacje stosują ten sam algorytm i wykorzystują równoważne struktury danych.