Czy dynamiczny język, taki jak Ruby / Python, może osiągnąć wydajność podobną do C / C ++?


64

Zastanawiam się, czy można zbudować kompilatory dla dynamicznych języków, takich jak Ruby, aby mieć podobną i porównywalną wydajność do C / C ++? Z tego, co rozumiem na temat kompilatorów, weźmy na przykład Ruby, kompilowanie kodu Ruby nigdy nie będzie wydajne, ponieważ sposób, w jaki Ruby obsługuje odbicie, funkcje takie jak automatyczna konwersja typów z liczb całkowitych na duże liczby całkowite oraz brak pisania statycznego sprawia, że ​​budowanie wydajnego kompilatora dla Ruby niezwykle trudne.

Czy można zbudować kompilator, który może kompilować Ruby lub inne dynamiczne języki do pliku binarnego, który działa bardzo blisko C / C ++? Czy istnieje fundamentalny powód, dla którego kompilatory JIT, takie jak PyPy / Rubinius, ostatecznie lub nigdy nie będą pasować do C / C ++ pod względem wydajności?

Uwaga: Rozumiem, że „wydajność” może być niejasna, więc aby to wyjaśnić, miałem na myśli, że jeśli możesz zrobić X w C / C ++ z wydajnością Y, czy możesz zrobić X w Ruby / Python z wydajnością zbliżoną do Y? Gdzie X to wszystko, od sterowników urządzeń i kodu systemu operacyjnego, po aplikacje internetowe.


1
Czy możesz przeredagować pytanie, aby zachęcić do odpowiedzi popartych odpowiednimi dowodami w stosunku do innych?
Raphael

@Raphael Poszedłem i zredagowałem. Wydaje mi się, że moja edycja zasadniczo nie zmienia znaczenia pytania, ale czyni go mniej zachęcającym do wyrażania opinii.
Gilles

1
W szczególności uważam, że musisz naprawić jeden (lub kilka) konkretnych mierników wydajności. Runtime? Wykorzystanie przestrzeni? Zużycie energii? Czas programisty? Zwrot inwestycji? Zwróć też uwagę na to pytanie dotyczące naszej meta, które dotyczy tego pytania (a raczej jego odpowiedzi).
Raphael

To pytanie jest typowym inicjatorem wojen religijnych. Jak widać z odpowiedzi, mamy jedną, choć bardzo cywilizowaną.
Andrej Bauer

Istnieją dynamiczne języki pozwalające na opcjonalne adnotacje typu (np. Clojure). Z tego, co wiem, wydajność związana z funkcjami z adnotacjami typu jest równoważna z tym, kiedy język zostałby wpisany statycznie.
Pedro Morte Rolo

Odpowiedzi:


68

Wszystkim, którzy powiedzieli „tak”, zaoferuję kontrapunkt, że odpowiedź brzmi „nie” z założenia . Języki te nigdy nie będą w stanie dopasować wydajności języków skompilowanych statycznie.

Kos zaoferował (bardzo prawidłowy) punkt, w którym dynamiczne języki mają więcej informacji o systemie w czasie wykonywania, które można wykorzystać do optymalizacji kodu.

Istnieje jednak druga strona medalu: należy śledzić te dodatkowe informacje. W nowoczesnych architekturach jest to zabójca wydajności.

William Edwards oferuje ładny przegląd argumentu .

W szczególności wspomniane przez Kos optymalizacje nie mogą być stosowane poza bardzo ograniczonym zakresem, chyba że drastycznie ograniczysz moc ekspresji swoich języków, jak wspomniał Devin. Jest to oczywiście opłacalny kompromis, ale ze względu na dyskusję powstaje język statyczny , a nie dynamiczny. Te języki różnią się zasadniczo od Python lub Ruby, ponieważ większość ludzi je rozumie.

William przytacza kilka interesujących slajdów IBM :

  • Każda zmienna może być dynamicznie wpisywana: potrzebujesz sprawdzania typu
  • Każda instrukcja może potencjalnie generować wyjątki z powodu niedopasowania typu i tak dalej: Potrzebujesz sprawdzania wyjątków
  • Każde pole i symbol można dodawać, usuwać i zmieniać w czasie wykonywania: Potrzebujesz kontroli dostępu
  • Typ każdego obiektu i jego hierarchię klas można zmienić w czasie wykonywania: Konieczne jest sprawdzenie hierarchii klas

Niektóre z tych kontroli można wyeliminować po analizie (uwaga: ta analiza wymaga również czasu - w czasie wykonywania).

Ponadto Kos twierdzi, że języki dynamiczne mogą nawet przewyższyć wydajność C ++. JIT może rzeczywiście analizować zachowanie programu i zastosować odpowiednie optymalizacje.

Ale kompilatory C ++ mogą zrobić to samo! Nowoczesne kompilatory oferują tak zwaną optymalizację sterowaną profilem, która, jeśli otrzyma odpowiednie dane wejściowe, może modelować zachowanie środowiska wykonawczego programu i zastosować te same optymalizacje, które zastosowałby JIT.

Oczywiście wszystko zależy od istnienia realistycznych danych treningowych, a ponadto program nie może dostosować swoich charakterystyk wykonawczych, jeśli wzorzec użytkowania zmieni się w połowie cyklu. JIT teoretycznie sobie z tym poradzą. Byłbym zainteresowany, aby zobaczyć, jak to wygląda w praktyce, ponieważ w celu przełączenia optymalizacji JIT musiałby stale zbierać dane o użytkowaniu, co ponownie spowalnia wykonanie.

Podsumowując, nie jestem przekonany, że optymalizacje w punkcie startowym środowiska uruchomieniowego przeważają nad kosztem śledzenia informacji o środowisku wykonawczym w długim okresie , w porównaniu do analizy statycznej i optymalizacji.


2
@Raphael To „wada” kompilatora. W szczególności, czy javackiedykolwiek była przeprowadzana optymalizacja profilowa? Nie, o ile mi wiadomo. Zasadniczo nie ma sensu, aby kompilator języka JIT był dobrze zoptymalizowany, ponieważ JIT może sobie z tym poradzić (a przynajmniej w ten sposób więcej języków korzysta z tego wysiłku). Tak więc (co zrozumiałe) javacoptymalizator nigdy nie wkładał wiele wysiłku , o ile wiem (w przypadku języków .NET jest to zdecydowanie prawda).
Konrad Rudolph

1
@Raphael Kluczowym słowem jest: może. Nie pokazuje tego w żaden sposób. To wszystko, co chciałem powiedzieć. W poprzednich akapitach podałem powody (ale brak dowodu) mojego założenia.
Konrad Rudolph

1
@Ben Nie przeczę, że to skomplikowane. To tylko intuicja. W końcu śledzenie wszystkich tych informacji w środowisku wykonawczym jest kosztowne. Nie przekonuje mnie twoje zdanie na temat IO. Jeśli jest to przewidywalne (= typowy przypadek użycia), to PGO może to przewidzieć. Jeśli jest to fałszywe, nie jestem przekonany, że JIT może go zoptymalizować. Może raz na jakiś czas, z czystego szczęścia. Ale niezawodnie? …
Konrad Rudolph

2
@Konrad: Twoja intuicja jest fałszywa. Nie chodzi o różnicowanie w czasie wykonywania, chodzi o nieprzewidywalność w czasie kompilacji . Ulubieniec dla JIT vs optymalizacja statyczna nie polega na tym, że zachowanie programu zmienia się w czasie wykonywania jako „zbyt szybkie” do profilowania, lecz wtedy, gdy zachowanie programu jest łatwe do zoptymalizowania w każdym uruchomieniu programu, ale zmienia się gwałtownie pomiędzy biegnie. Optymalizator statyczny będzie zazwyczaj musiał zoptymalizować tylko dla jednego zestawu warunków, podczas gdy JIT optymalizuje każdy przebieg osobno, dla warunków, które występują w tym przebiegu.
Ben

3
Uwaga: ten wątek z komentarzem przekształca się w mini czat. Jeśli chcesz kontynuować tę dyskusję, zaproś ją na czat. Komentarze powinny być użyte do ulepszenia oryginalnego postu. Proszę przerwać tę rozmowę tutaj. Dzięki.
Robert Cartaino

20

jeśli możesz zrobić X w C / C ++ z wydajnością Y, czy możesz zrobić X w Ruby / Python z wydajnością zbliżoną do Y?

Tak. Weźmy jako przykład PyPy. Jest to zbiór kodu Pythona, który wykonuje interpretację zbliżoną do C (nie tak blisko, ale też nie aż tak daleko). Dokonuje tego, przeprowadzając analizę całego programu w kodzie źródłowym, aby przypisać każdej zmiennej typ statyczny (szczegółowe informacje znajdują się w dokumentach Annotator i Rtyper ), a następnie, po uzbrojeniu w te same informacje o typie, co C, można wykonać to samo rodzaje optymalizacji. Przynajmniej w teorii.

Kompromis oczywiście polega na tym, że RPython akceptuje tylko podzbiór kodu Pythona i ogólnie, nawet jeśli to ograniczenie zostanie zniesione, tylko podzbiór kodu Pythona może sobie poradzić: podzbiór, który można analizować i nadać typy statyczne.

Jeśli wystarczająco ograniczysz Python, możesz zbudować optymalizatory, które będą mogły skorzystać z ograniczonego podzbioru i skompilować go do wydajnego kodu. To naprawdę nie jest interesująca korzyść, w rzeczywistości jest dobrze znana. Ale głównym celem używania Pythona (lub Ruby) było przede wszystkim to, że chcieliśmy zastosować ciekawe funkcje, które być może nie analizują dobrze i dają dobrą wydajność! Ciekawe pytanie brzmi ...

Ponadto, czy kompilatory JIT, takie jak PyPy / Rubinius, kiedykolwiek będą pasować do C / C ++ pod względem wydajności?

Nie

Rozumiem przez to: pewnie, że w miarę gromadzenia się kodu można uzyskać wystarczającą ilość informacji o pisaniu i wystarczającą liczbę punktów aktywnych do skompilowania całego kodu aż do kodu maszynowego. I może uda nam się uzyskać lepszą wydajność niż C dla jakiegoś kodu. Nie sądzę, żeby to było bardzo kontrowersyjne. Ale wciąż musi się „rozgrzać”, a wydajność jest nieco mniej przewidywalna i nie będzie tak dobra jak C lub C ++ dla niektórych zadań, które wymagają konsekwentnie i przewidywalnie wysokiej wydajności.

Istniejące dane dotyczące wydajności dla języka Java, które zawierają zarówno więcej informacji o typie niż Python lub Ruby, jak i lepiej rozwinięty kompilator JIT niż Python lub Ruby, nadal nie są zgodne z C / C ++. Jest jednak na tym samym boisku.


1
„Oczywiście kompromis polega na tym, że tylko podzbiór kodu w Pythonie jest akceptowany, a raczej tylko podzbiór kodu w Pythonie może sobie poradzić: podzbiór, który można analizować i nadać mu typy statyczne”. To nie jest całkiem dokładne. Kompilator RPython może w ogóle zaakceptować tylko podzbiór. Kompilacja do RPython do racjonalnie wydajnego C działa tylko dlatego, że trudno kompilowane części Pythona nigdy nie występują w programach RPython; to nie tylko to, że jeśli wystąpią, nie zostaną zoptymalizowane. Jest to skompilowany interpreter, który obsługuje cały Python.
Ben

1
O JIT: widziałem więcej niż jeden test porównawczy, w którym Java zdeklasowała kilka odmian C (++). Tylko C ++ ze wzmocnieniem wydaje się być niezawodny. W takim przypadku zastanawiam się nad wydajnością przypadającą na programistę, ale to już inny temat.
Raphael

@Ben: gdy już masz RPython, tworzenie kompilatora / interpretera jest trywialne, gdy wraca do korzystania z interpretera CPython, gdy kompilator RPython zawiedzie, dlatego „tylko podzbiór kodu Python może zrobić dobrze: ...” jest całkowicie dokładny.
Lie Ryan

9
@Raphael Wielokrotnie pokazano, że dobrze napisany kod C ++ przewyższa Javę. Jest to „dobrze napisana” część, która jest nieco trudniejsza do zdobycia w C ++, więc na wielu ławkach widać wyniki, w których Java przewyższa C ++. C ++ jest zatem droższy, ale gdy potrzebna jest ścisła kontrola pamięci i metalowy piasek, C / C ++ jest tym, do czego się zwracasz. W szczególności C jest tylko asemblerem ac / p.
TC1

7
Porównanie maksymalnej wydajności innych języków z językami takimi jak C / C ++ jest swego rodzaju ćwiczeniem daremności, ponieważ można wstawiać asembler bezpośrednio w ramach specyfikacji języka. Wszystko, co może zrobić maszyna, uruchamiając program napisany w dowolnym języku, w najgorszym wypadku można powielić, pisząc asembler ze śladu wykonanych instrukcji. O wiele bardziej interesująca byłaby, jak sugeruje @Raphael we wcześniejszym komentarzu, wydajność na wysiłek programistyczny (roboczogodziny, wiersze kodu itp.).
Patrick87

18

Krótka odpowiedź brzmi: nie wiemy , zapytaj ponownie za 100 lat. (Być może nadal nie będziemy wiedzieć; być może nigdy się nie dowiemy.)

Teoretycznie jest to możliwe. Weź wszystkie napisane programy, ręcznie przetłumacz je na najbardziej wydajny kod maszynowy i napisz interpreter, który mapuje kody źródłowe na kody maszynowe. Jest to możliwe, ponieważ kiedykolwiek napisano tylko skończoną liczbę programów (a gdy więcej programów zostanie napisanych, nie przestawaj tłumaczeń ręcznych). Jest to oczywiście całkowicie idiotyczne pod względem praktycznym.

Z drugiej strony teoretycznie języki wysokiego poziomu mogą osiągnąć wydajność kodu maszynowego, ale go nie przekroczą. Jest to nadal bardzo teoretyczne, ponieważ w praktyce bardzo rzadko uciekamy się do pisania kodu maszynowego. Ten argument nie dotyczy porównywania języków wyższego poziomu: nie oznacza, że ​​C musi być bardziej wydajny niż Python, tylko ten kod maszynowy nie może być gorszy niż Python.

Z drugiej strony, na czysto eksperymentalnych warunkach, widzimy, że w większości przypadków interpretowane języki wysokiego poziomu osiągają gorsze wyniki niż skompilowane języki niskiego poziomu. Mamy tendencję do pisania kodu, który nie jest wrażliwy na czas, w językach wysokiego poziomu i krytycznych czasowo wewnętrznych pętli w asemblerze, z językami takimi jak C i Python pomiędzy nimi. Chociaż nie mam żadnych statystyk, które mogłyby to potwierdzić, myślę, że w większości przypadków jest to najlepsza decyzja.

Istnieją jednak niekwestionowane przypadki, w których języki wysokiego poziomu pokonują kod, który można realistycznie napisać: środowiska programowania specjalnego przeznaczenia. Programy takie jak Matlab i Mathematica są często znacznie lepsze w rozwiązywaniu niektórych problemów matematycznych niż to, co potrafią napisać zwykli śmiertelnicy. Funkcje biblioteki mogły być napisane w C lub C ++ (co jest paliwem do obozu „języki niskiego poziomu są bardziej wydajne”), ale to nie moja sprawa, jeśli piszę kod Mathematica, biblioteka to czarna skrzynka.

Czy teoretycznie jest możliwe, że Python zbliży się, a może nawet, do optymalnej wydajności niż C? Jak widać powyżej, tak, ale dzisiaj jesteśmy bardzo daleko od tego. Z drugiej strony, kompilatory poczyniły duży postęp w ciągu ostatnich dziesięcioleci i postęp ten nie zwalnia.

Języki wysokiego poziomu powodują, że więcej rzeczy jest zautomatyzowanych, więc mają więcej pracy do wykonania, a zatem są mniej wydajne. Z drugiej strony mają one zwykle więcej informacji semantycznych, więc łatwiej jest dostrzec optymalizacje (jeśli piszesz kompilator Haskell, nie musisz się martwić, że inny wątek zmodyfikuje zmienną pod twoim nosem). Jednym z kilku wysiłków zmierzających do porównania jabłek i pomarańczy w różnych językach programowania jest gra Computer Language Benchmark Game (wcześniej znana jako strzelanka). Fortran błyszczy w zadaniach numerycznych; ale jeśli chodzi o manipulowanie danymi strukturalnymi lub komutacją szybkich wątków, F # i Scala mają się dobrze. Nie bierz tych wyników za ewangelię: wiele z tego, co mierzą, to to, jak dobry był autor programu testowego w każdym języku.

Argumentem przemawiającym za językami wysokiego poziomu jest to, że wydajność w nowoczesnych systemach nie jest tak silnie skorelowana z liczbą wykonywanych instrukcji, a tym bardziej z czasem. Języki niskiego poziomu są odpowiednie dla prostych maszyn sekwencyjnych. Jeśli język wysokiego poziomu wykonuje dwukrotnie więcej instrukcji, ale bardziej inteligentnie korzysta z pamięci podręcznej, dzięki czemu pomija o połowę mniej pamięci podręcznej, może wygrać.

Na platformach serwerowych i stacjonarnych procesory prawie osiągnęły płaskowyż, w którym nie przyspieszają (platformy mobilne też się tam dostają); faworyzuje to języki, w których równoległość jest łatwa do wykorzystania. Wiele procesorów spędza większość czasu na oczekiwaniu na odpowiedź We / Wy; czas spędzony na obliczeniach ma niewielkie znaczenie w porównaniu z ilością operacji we / wy, a język, który pozwala programiście zminimalizować komunikację, jest korzystny.

Podsumowując, podczas gdy języki wysokiego poziomu zaczynają się od kary, mają więcej miejsca na ulepszenia. Jak blisko mogą się zbliżyć? Zapytaj ponownie za 100 lat.

Uwaga końcowa: często nie dokonuje się porównania między najbardziej wydajnym programem, który można napisać w języku A i tym samym w języku B, ani między najskuteczniejszym programem, jaki kiedykolwiek napisano w każdym języku, ale między najskuteczniejszym programem, który można napisać przez człowieka w określonym czasie w każdym języku. Wprowadza to element, którego nie można analizować matematycznie, nawet w zasadzie. W praktyce oznacza to często, że najlepsza wydajność to kompromis między tym, ile kodu niskiego poziomu trzeba napisać, aby osiągnąć cele wydajności, a tym, ile kodu niskiego poziomu trzeba napisać, aby dotrzymać dat wydania.


Myślę, że rozróżnienie między wysokim a niskim poziomem jest niewłaściwe. C ++ może być (bardzo) wysoki poziom. Jednak nowoczesny C ++ wysokiego poziomu nie musi (niekoniecznie) osiągać gorszych wyników niż odpowiednik niskiego poziomu - wręcz przeciwnie. C ++ i jego biblioteki zostały starannie zaprojektowane, aby oferować abstrakcje wysokiego poziomu bez obniżania wydajności. To samo dotyczy przykładu Haskell: jego abstrakcje na wysokim poziomie często włączają, a nie zapobiegają optymalizacjom. Pierwotne rozróżnienie między językami dynamicznymi a językami statycznymi ma w tym względzie większy sens.
Konrad Rudolph

@KonradRudolph Masz rację, w tym poziomie niskiego / wysokiego poziomu jest nieco arbitralne rozróżnienie. Ale języki dynamiczne kontra statyczne też nie wychwytują wszystkiego; JIT może wyeliminować dużą różnicę. Zasadniczo znane teoretyczne odpowiedzi na to pytanie są trywialne i bezużyteczne, a praktyczna odpowiedź brzmi „to zależy”.
Gilles

Cóż, myślę, że pytanie brzmi: „jak dobry może być JIT, a jeśli prześcigną kompilację statyczną, czy statycznie skompilowane języki również mogą na tym skorzystać?” Przynajmniej tak rozumiem pytanie, kiedy weźmiemy pod uwagę JIT. I tak, zgadzam się z twoją oceną, ale z pewnością możemy uzyskać pewne domysły, które wykraczają poza „to zależy”. ;-)
Konrad Rudolph

@KonradRudolph Gdybym chciał zgadywać, zapytałbym o inżynierii oprogramowania .
Gilles

1
Strzelanina językowa jest niestety budzącym wątpliwości źródłem ilościowych testów porównawczych: nie akceptują one wszystkich programów tylko tych uznanych za typowe dla danego języka. Jest to trudny i bardzo subiektywny wymóg; oznacza to, że nie można zakładać, że implementacja rzutów karnych jest właściwie dobra (aw praktyce niektóre implementacje mają oczywiście odrzucone lepsze alternatywy). Z drugiej strony; są to znaki mikrodruku, a niektóre implementacje wykorzystują nietypowe techniki, których nigdy nie wzięto by pod uwagę w bardziej normalnym scenariuszu, tylko po to, aby uzyskać wydajność. Więc: to gra, niezbyt wiarygodne źródło danych.
Eamon Nerbonne

10

Podstawowa różnica pomiędzy ++ rachunku C x = a + boraz sprawozdania Python x = a + bjest to, że C / C ++ kompilator może powiedzieć z tym stwierdzeniem (i trochę dodatkowych informacji, że ma łatwo dostępne o typach x, ai b) właśnie maszyna kod musi być wykonywany . Podczas gdy, aby powiedzieć, jakie operacje ma wykonać instrukcja Python, musisz rozwiązać problem zatrzymania.

W języku C ta instrukcja po prostu skompiluje się do jednego z kilku rodzajów dodawania maszyn (a kompilator C wie, który). W C ++ może się kompilować w ten sposób lub może wywoływać funkcję wywoływania statycznie znanej funkcji lub (w najgorszym przypadku) może być zmuszona do kompilacji do wirtualnego wyszukiwania i wywoływania metod, ale nawet to ma dość niewielki narzut kodu maszynowego. Co ważniejsze, kompilator C ++ może stwierdzić na podstawie statycznie znanych typów, czy może wyemitować pojedynczą operację szybkiego dodawania, czy też musi użyć jednej z wolniejszych opcji.

W Pythonie, kompilator może teoretycznie zrobić prawie tak dobre, jeśli wiedział, że ai bobaj ints. Istnieje pewne dodatkowe obciążenie związane z boksem, ale jeśli typy byłyby statycznie znane, prawdopodobnie można by się tego również pozbyć (wciąż przedstawiając interfejs, że liczby całkowite są obiektami z metodami, hierarchią superklas itp.). Problem polega na tym, że kompilator Pythona nie możewiedz o tym, ponieważ klasy są definiowane w czasie wykonywania, mogą być modyfikowane w czasie wykonywania, a nawet moduły, które definiują i importują, są rozwiązywane w czasie wykonywania (a nawet, które instrukcje importowania są wykonywane, zależą od rzeczy, które można poznać tylko w czasie wykonywania). Tak więc kompilator Pythona musiałby wiedzieć, jaki kod został wykonany (tj. Rozwiązać problem zatrzymania), aby wiedzieć, co zrobi skompilowana instrukcja.

Tak więc nawet przy najbardziej wyrafinowanych analizach, które są teoretycznie możliwe , po prostu nie można wiele powiedzieć o tym, co dana instrukcja Python zrobi z wyprzedzeniem. Oznacza to, że nawet jeśli zaimplementowany zostałby wyrafinowany kompilator Pythona, prawie we wszystkich przypadkach nadal musiałby emitować kod maszynowy zgodny z protokołem wyszukiwania słownika Python, aby określić klasę obiektu i znaleźć metody (przechodząc przez MRO hierarchii klas, który może również zmieniać się dynamicznie w czasie wykonywania, a więc trudno go skompilować do prostej wirtualnej tabeli metod) i zasadniczo robić to, co robią (powolni) tłumacze. Dlatego tak naprawdę nie ma wyrafinowanych kompilatorów optymalizujących dla języków dynamicznych. Nie jest to tylko trudne do stworzenia, maksymalna możliwa wypłata nie jest

Zauważ, że to nie jest oparte na tym, co kod jest robić, to na podstawie tego, co kod mógłby robić. Nawet kod Pythona, który jest prostą serią liczb całkowitych operacji arytmetycznych, musi zostać skompilowany tak, jakby mógł wywoływać dowolne operacje klasowe. Języki statyczne mają większe ograniczenia dotyczące możliwości działania kodu, w związku z czym ich kompilatory mogą przyjmować więcej założeń.

Kompilatory JIT zyskują na tym, czekając, aż środowisko wykonawcze skompiluje / zoptymalizuje. To pozwala im emitować kod, który działa na co kod jest robić raczej niż to, co można było zrobić. Z tego powodu kompilatory JIT mają znacznie większą potencjalną korzyść dla języków dynamicznych niż dla języków statycznych; dla bardziej statycznych języków większość tego, co chciałby wiedzieć optymalizator, można poznać z wyprzedzeniem, więc równie dobrze możesz go zoptymalizować, pozostawiając mniej kompilatora JIT.

Istnieją różne kompilatory JIT dla języków dynamicznych, które twierdzą, że osiągają prędkości wykonania porównywalne z kompilowanymi i zoptymalizowanymi C / C ++. Istnieją nawet optymalizacje, które mogą być wykonywane przez kompilator JIT, których nie można wykonać za pomocą kompilatora z wyprzedzeniem dla dowolnego języka, więc teoretycznie kompilacja JIT (dla niektórych programów) może pewnego dnia przewyższyć najlepszy możliwy kompilator statyczny. Ale jak słusznie zauważył Devin, właściwości kompilacji JIT (tylko „hotspoty” są szybkie i dopiero po okresie rozgrzewki) oznaczają, że języki dynamiczne skompilowane w JIT raczej nie będą odpowiednie dla wszystkich możliwych aplikacji, nawet jeśli staną się tak szybkie lub szybsze niż języki skompilowane statycznie.


1
To teraz dwa głosy negatywne bez komentarzy. Z radością powitałbym sugestie, jak poprawić tę odpowiedź!
Ben

Nie przegłosowałem, ale nie masz racji co do „potrzeby rozwiązania problemu zatrzymania”. W wielu okolicznościach wykazano, że kod w dynamicznych językach można skompilować do optymalnego kodu docelowego, natomiast o
ile

@mikera Przykro mi, ale nie, jesteś w błędzie. Nikt nigdy nie wdrożył kompilatora (w tym sensie, że rozumiemy, że GCC jest kompilatorem) dla całkowicie ogólnego języka Python lub innych dynamicznych języków. Każdy taki system działa tylko dla podzbioru języka lub tylko dla niektórych programów, lub czasami emituje kod, który jest w zasadzie tłumaczem zawierającym program zakodowany na stałe. Jeśli chcesz, napiszę program w języku Python zawierający wiersz, w foo = x + yktórym przewidywanie zachowania operatora dodawania w czasie kompilacji zależy od rozwiązania problemu zatrzymania.
Ben

Mam rację i myślę, że nie rozumiesz. Powiedziałem „w wielu okolicznościach”. Nie powiedziałem „we wszystkich możliwych okolicznościach”. To, czy potrafisz skonstruować wymyślony przykład związany z problemem zatrzymania, jest w dużej mierze nieistotne w prawdziwym świecie. FWIW, możesz również skonstruować podobny przykład dla C ++, aby i tak niczego nie udowodnić. W każdym razie nie przyszedłem tutaj, aby wdać się w kłótnię, aby zasugerować poprawę odpowiedzi. Zdecyduj sie.
mikera

@mikea Myślę, że możesz nie rozumieć. Aby skompilować x + ydo wydajnych operacji dodawania komputera, musisz wiedzieć w czasie kompilacji, czy tak jest. Przez cały czas , nie tylko przez jakiś czas. W przypadku języków dynamicznych prawie nigdy nie jest to możliwe przy realistycznych programach, mimo że rozsądna heurystyka przez większość czasu wydaje się słuszna. Kompilacja wymaga gwarancji czasu kompilacji . Mówiąc o tym, że „w wielu okolicznościach” wcale nie odnosisz się do mojej odpowiedzi.
Ben

9

Szybki wskaźnik wskazujący najgorszy scenariusz dla języków dynamicznych:

Analiza Perla nie jest obliczalna

W rezultacie (pełnego) Perla nigdy nie można skompilować statycznie.


Ogólnie, jak zawsze, zależy. Jestem pewien, że jeśli spróbujesz emulować funkcje dynamiczne w języku kompilowanym statycznie, dobrze przemyślani tłumacze lub (częściowo) skompilowane warianty mogą zbliżyć się lub podważyć wydajność języków kompilowanych statycznie.

Inną kwestią, o której należy pamiętać, jest to, że języki dynamiczne rozwiązują inny problem niż C. C jest zaledwie przyjemną składnią asemblera, podczas gdy języki dynamiczne oferują bogate abstrakcje. Wydajność środowiska wykonawczego często nie jest najważniejsza: na przykład czas wprowadzenia produktu na rynek zależy od tego, czy programiści będą w stanie napisać złożone systemy wysokiej jakości w krótkich ramach czasowych. Rozszerzalność bez ponownej kompilacji, na przykład za pomocą wtyczek, to kolejna popularna funkcja. Który język preferujesz w tych przypadkach?


5

Próbując udzielić bardziej obiektywnej odpowiedzi naukowej na to pytanie, argumentuję w następujący sposób. Język dynamiczny wymaga tłumacza lub środowiska wykonawczego do podejmowania decyzji w czasie wykonywania. Ten interpreter lub środowisko wykonawcze jest programem komputerowym i jako taki został napisany w pewnym języku programowania, statycznym lub dynamicznym.

Jeśli interpreter / środowisko wykonawcze zostało napisane w języku statycznym, wówczas można napisać program w tym języku statycznym, który (a) pełni tę samą funkcję co program dynamiczny, który interpretuje i (b) wykonuje co najmniej równie dobrze. Mamy nadzieję, że jest to oczywiste, ponieważ dostarczenie dokładnego dowodu tych roszczeń wymagałoby dodatkowego (prawdopodobnie znacznego) wysiłku.

Zakładając, że te twierdzenia są prawdziwe, jedynym wyjściem jest wymaganie, aby tłumacz / środowisko wykonawcze również było napisane w języku dynamicznym. Jednak natrafiamy na ten sam problem, co wcześniej: jeśli interpreter jest dynamiczny, wymaga interpretera / środowiska wykonawczego, który również musi być napisany w języku programowania, dynamicznym lub statycznym.

O ile nie założymy, że instancja tłumacza jest zdolna do interpretacji samego siebie w czasie wykonywania (mam nadzieję, że jest to oczywiście absurdalne), jedynym sposobem na pokonanie języków statycznych jest interpretacja każdej instancji tłumacza przez osobną instancję tłumacza; prowadzi to albo do nieskończonego regresu (mam nadzieję, że to jest oczywiste absurdalne), albo do zamkniętej pętli tłumaczy (mam nadzieję, że jest to również oczywiste absurdalne).

Wydaje się zatem, że nawet teoretycznie języki dynamiczne nie mogą działać lepiej niż języki statyczne. Podczas korzystania z modeli realistycznych komputerów wydaje się to jeszcze bardziej prawdopodobne; w końcu maszyna może wykonywać tylko sekwencje instrukcji maszyny, a wszystkie sekwencje instrukcji maszyny mogą być kompilowane statycznie.

W praktyce dopasowanie wydajności języka dynamicznego do języka statycznego może wymagać ponownego wdrożenia interpretera / środowiska wykonawczego w języku statycznym; jednak to, co możesz zrobić, to sedno i sedno tego argumentu. To pytanie z kurczaka i jaja i pod warunkiem, że zgadzasz się z niepotwierdzonymi (choć moim zdaniem głównie oczywistymi) założeniami podanymi powyżej, możemy faktycznie na nie odpowiedzieć; musimy skinąć głową statycznym, a nie dynamicznym językom.

Innym sposobem udzielenia odpowiedzi na pytanie, w świetle tej dyskusji, jest: w przechowywanym programie model sterowania = danych w obliczeniach, który leży u podstaw współczesnego przetwarzania, rozróżnienie między kompilacją statyczną a dynamiczną jest fałszywą dychotomią; statycznie skompilowane języki muszą mieć możliwość generowania i wykonywania dowolnego kodu w czasie wykonywania. Jest to zasadniczo związane z uniwersalnym obliczeniem.


Czytając to ponownie, nie sądzę, że to prawda. Kompilacja JIT łamie twój argument. Nawet najprostszy kod, np. main(args) { for ( i=0; i<1000000; i++ ) { if ( args[0] == "1" ) {...} else {...} }Można znacznie przyspieszyć, gdy argsznana jest wartość (zakładając, że nigdy się nie zmienia, co możemy potwierdzić). Kompilator statyczny nie może nigdy utworzyć kodu, który porzuca porównanie. (Oczywiście w tym przykładzie po prostu wyciągasz ifz pętli. Ale sprawa może być bardziej skomplikowana.)
Raphael

@Raphael myślę JIT prawdopodobnie sprawia, że mój argument. Programy dokonujące kompilacji JIT (np. JVM) są zwykle programami kompilowanymi statycznie. Jeśli statycznie skompilowany program JIT mógłby uruchomić skrypt szybciej niż jakiś inny program statyczny mógłby wykonać tę samą pracę, wystarczy „spakować” skrypt za pomocą kompilatora JIT i nazwać ten pakiet kompilacją statyczną. Musi to działać przynajmniej tak samo, jak JIT działający na osobnym programie dynamicznym, co przeczy argumentowi, że JIT musi działać lepiej.
Patrick87

Hm, to tak jakby powiedzieć, że dołączenie skryptu Ruby do jego interpretera daje statycznie skompilowany program. Nie zgadzam się (ponieważ usuwa wszystkie różnice językowe w tym zakresie), ale jest to kwestia semantyki, a nie pojęć. Koncepcyjnie, dostosowanie programu w czasie wykonywania (JIT) może prowadzić do optymalizacji, których nie można wykonać w czasie kompilacji (kompilator statyczny), i o to mi chodzi.
Raphael

@Raphael To, że nie ma znaczącego rozróżnienia, jest w pewnym sensie odpowiedzią: każda próba sztywnego sklasyfikowania niektórych języków jako statycznych, a zatem cierpiących na ograniczenia wydajności, kończy się niepowodzeniem z tego właśnie powodu: nie ma istotnej różnicy między opakowaniem jednostkowym (Ruby , skrypt) pakiet i program C. Jeśli (Ruby, skrypt) może sprawić, że maszyna wykona prawidłową sekwencję instrukcji, aby skutecznie rozwiązać dany problem, to może sprytnie spreparowany program w języku C.
Patrick87

Ale można określić różnicę. Jeden wariant wysyła podany kod do procesora bez zmian (C), drugi kompiluje się w czasie wykonywania (Ruby, Java, ...). Pierwszy z nich rozumiemy przez „kompilację statyczną”, podczas gdy ten drugi to „kompilacja just in time” (która umożliwia optymalizacje zależne od danych).
Raphael

4

Czy potrafisz budować kompilatory dla dynamicznych języków, takich jak Ruby, aby mieć podobną i porównywalną wydajność do C / C ++?

Myślę, że odpowiedź brzmi „tak” . Wierzę również, że mogą nawet przewyższyć obecną architekturę C / C ++ pod względem wydajności (nawet jeśli nieznacznie).

Powód jest prosty: w czasie wykonywania jest więcej informacji niż w czasie kompilacji.

Typy dynamiczne są tylko niewielką przeszkodą: jeśli funkcja jest zawsze lub prawie zawsze wykonywana z tymi samymi typami argumentów, optymalizator JIT może wygenerować gałąź i kod maszynowy dla tego konkretnego przypadku. I można zrobić o wiele więcej.

Zobacz Dynamic Languages ​​Strike Back , przemówienie Steve'a Yegge z Google (gdzieś wierzę, że jest też wersja wideo). Wspomina o konkretnych technikach optymalizacji JIT z V8. Inspirujące!

Nie mogę się doczekać tego, co będziemy mieć w ciągu najbliższych 5 lat!


2
Uwielbiam optymizm.
Dave Clarke

Uważam, że w przemówieniu Steve'a pojawiła się bardzo konkretna krytyka nieścisłości. Wyślę je, gdy je znajdę.
Konrad Rudolph

1
@DaveClarke to mnie utrzymuje :)
Kos

2

Ludzie, którzy najwyraźniej uważają, że jest to teoretycznie możliwe, lub w dalekiej przyszłości, całkowicie się mylę. Chodzi o to, że dynamiczne języki zapewniają i narzucają zupełnie inny styl programowania. W rzeczywistości różnica jest dwojaka, nawet jeśli oba aspekty są ze sobą powiązane:

  • Symbole (zmienne, a raczej wszelkiego rodzaju powiązania danych identyfikacyjnych <->) nie są wpisywane.
  • Struktury (dane, wszystko, co żyje w środowisku wykonawczym) są również nietypowane według typów ich elementów.

Drugi punkt zapewnia ogólność za darmo. Zauważ, że tutaj struktury są elementami złożonymi, kolekcjami, ale także samymi typami, a nawet (!) Procedurami wszelkiego rodzaju (funkcje, akcje, operacje) ... Możemy pisać struktury według ich typów elementów, ale ze względu na pierwszy punkt i tak sprawdzenie nastąpi w czasie wykonywania. Moglibyśmy wpisywać symbole i nadal mieć uporządkowane te, które nie są wpisywane zgodnie z typami elementów (tablica abyłaby po prostu typowana jako tablica, a nie tablica liczb całkowitych), ale nawet te kilka nie jest prawdziwe w języku dynamicznym ( amoże również zawierać ciąg).

L. , tj. Rodzajem fikcyjnej maszyny, lub pełną biblioteką uruchomieniową. A następnie programuj (bezpośrednio w C) używając tylko modelu, bez zwykłych funkcji C. Oznacza to posiadanie:

  • ElementL.L. w modelu)
  • ElementL.
  • wszystkie struktury (ponownie, w tym procedury modelu) otrzymują tylko elementy

Jest dla mnie jasne, że to tylko ogromna kara za perf; i nawet nie dotykam wszystkich konsekwencji (niezliczonej liczby testów uruchomieniowych wszelkiego rodzaju niezbędnych do zapewnienia wrażliwości programu) dobrze opisanych w innych postach.


+1 Bardzo interesujące. Czy przeczytałeś moją odpowiedź? Twoje i moje myślenie wydają się podobne, chociaż twoja odpowiedź zawiera więcej szczegółów i ciekawą perspektywę.
Patrick87

Języki dynamiczne nie muszą być rozpakowane. Wdrożenie modelu języka dynamicznego w C poważnie ogranicza możliwości optymalizacji; utrudnia to kompilatorowi rozpoznanie optymalizacji wysokiego poziomu (np. niezmienne dane) i zmusza niektóre podstawowe operacje (np. wywołania funkcji) do przejścia przez C. To, co opisujesz, nie jest daleko od interpretera kodu bajtowego, z dekodowaniem kodu bajtowego wstępnie oszacowane; natywne kompilatory zwykle działają znacznie lepiej, wątpię, aby dekodowanie kodu bajtowego mogło uzasadnić różnicę.
Gilles

@ Patrick87: masz rację, nasze myślenie wydaje się bardzo podobne (nie czytałem wcześniej, przepraszam, moja refleksja pochodzi z obecnie implementacji dyn lang w C).
spir.

@Gilles: Raczej zgadzam się co do tego, że „... nie trzeba rozpakowywać”, jeśli masz na myśli brak wpisywania statycznego . Ale nie tak sądzą ludzie o dyn langs w ogóle. Osobiście uważam, że ogólność (w ogólnym znaczeniu podanym w powyższej odpowiedzi) jest cechą o wiele potężniejszą i znacznie trudniejszą do życia bez niej. Możemy łatwo znaleźć sposoby radzenia sobie z typami statycznymi, poszerzając nasze myślenie o tym, jak można zdefiniować dany (pozornie polimorficzny) typ, lub nadając większą elastyczność instancjom bezpośrednio.
spir.

1

Nie miałem czasu na szczegółowe przeczytanie wszystkich odpowiedzi ... ale byłem rozbawiony.

Podobne kontrowersje pojawiły się w latach sześćdziesiątych i wczesnych siedemdziesiątych (historia informatyki często się powtarza): można skompilować języki wysokiego poziomu w celu wytworzenia kodu tak wydajnego jak kod maszynowy, cóż, powiedzmy kod asemblacyjny, wytworzony ręcznie przez programistę. Wszyscy wiedzą, że programista jest znacznie mądrzejszy niż jakikolwiek program i może zaproponować bardzo inteligentną optymalizację (myśląc właściwie o tym, co nazywa się teraz optymalizacją wizjera). To oczywiście ironia z mojej strony.

Pojawiła się nawet koncepcja rozszerzenia kodu: stosunek wielkości kodu wygenerowanego przez kompilator do wielkości kodu dla tego samego programu wyprodukowanego przez dobrego programistę (tak jakby było ich zbyt wiele :-). Oczywiście chodziło o to, aby stosunek ten był zawsze większy niż 1. Językami tamtych czasów byli Cobol i Fortran 4 lub Algol 60 dla intelektualistów. Myślę, że Lisp nie był brany pod uwagę.

Cóż, pojawiły się pogłoski, że ktoś opracował kompilator, który czasami może uzyskać współczynnik rozszerzenia 1 ... dopóki nie stała się regułą, że skompilowany kod jest znacznie lepszy niż kod pisany ręcznie (i również bardziej niezawodny). W tamtych czasach ludzie martwili się rozmiarem kodu (małe wspomnienia), ale to samo dotyczy szybkości lub zużycia energii. Nie będę przedstawiał powodów.

Dziwne cechy, dynamiczne cechy języka nie mają znaczenia. Liczy się sposób, w jaki są używane, czy są używane. Wydajność, niezależnie od jednostki (rozmiar kodu, prędkość, energia, ...) często zależy od bardzo małych części programów. Dlatego istnieje spora szansa, że ​​urządzenia, które dają ekspresyjną moc, tak naprawdę nie przeszkadzają. Przy dobrej praktyce programowania zaawansowane urządzenia są wykorzystywane tylko w zdyscyplinowany sposób, aby wyobrazić sobie nowe struktury (to była lekcja seplenienia).

Fakt, że język nie ma pisania statycznego, nigdy nie oznacza, że ​​programy napisane w tym języku nie są wpisywane statycznie. Z drugiej strony może się zdarzyć, że system typów używany przez program nie jest jeszcze wystarczająco sformalizowany, aby istniał teraz moduł sprawdzania typu.

W dyskusji pojawiło się kilka odniesień do analizy najgorszego przypadku („problem zatrzymania”, parsowanie PERL). Jednak analiza najgorszego przypadku jest w większości nieistotna. Liczy się to, co dzieje się w większości przypadków lub w użytecznych przypadkach ... jakkolwiek zdefiniowane, zrozumiane lub doświadczone. Oto kolejna historia, bezpośrednio związana z optymalizacją programu. Miało to miejsce dawno temu na dużym uniwersytecie w Teksasie, pomiędzy doktorantem i jego doradcą (który został później wybrany w jednej z akademii krajowych). O ile pamiętam, student nalegał na przestudiowanie problemu z analizą / optymalizacją, który doradca okazał się nieuleczalny. Wkrótce przestali mówić. Ale uczeń miał rację: problem był na tyle praktyczny, że w większości praktycznych przypadków rozprawa, którą stworzył, stała się pracą referencyjną.

Aby dodatkowo skomentować stwierdzenie, że Perl parsing is not computablecokolwiek rozumie się przez to zdanie, istnieje podobny problem z ML, który jest niezwykle dobrze sformalizowanym językiem.Type checking complexity in ML is a double exponential in the lenght of the program.Jest to bardzo precyzyjny i formalny wynik w najgorszym przypadku złożoności ... co nie ma znaczenia. Afaik, użytkownicy ML nadal czekają na praktyczny program, który rozbije moduł sprawdzania typu.

W wielu przypadkach, tak jak wcześniej, ludzki czas i kompetencje są rzadsze niż moc obliczeniowa.

Prawdziwym problemem w przyszłości będzie ewolucja naszych języków w celu zintegrowania nowej wiedzy, nowych form programowania, bez konieczności przepisywania całego nadal używanego oprogramowania.

Jeśli spojrzysz na matematykę, jest to bardzo duży zasób wiedzy. Języki używane do jej wyrażania, notacje i pojęcia ewoluowały na przestrzeni wieków. Łatwo jest pisać stare twierdzenia z nowymi koncepcjami. Dostosowujemy główne dowody, ale nie zawracamy sobie głowy wieloma wynikami.

Ale w przypadku programowania może być konieczne przepisanie wszystkich odbitek próbnych od zera (programy są próbkami). Może być tak, że tak naprawdę potrzebujemy bardzo wysokiego poziomu i rozwijalnych języków programowania. Projektanci optymalizatorów chętnie podążą za nimi.


0

Kilka uwag:

  • Nie wszystkie języki wysokiego poziomu są dynamiczne. Haskell ma bardzo wysoki poziom, ale jest w pełni statyczny. Nawet systemy programowania języków, takie jak Rust, Nim i D, potrafią wyrażać abstrakcje wysokiego poziomu zwięźle i skutecznie. W rzeczywistości mogą być tak zwięzłe jak języki dynamiczne.

  • Istnieją wysoce zoptymalizowane kompilatory z wyprzedzeniem dla języków dynamicznych. Dobre wdrożenia Lisp osiągają połowę prędkości odpowiadającej C.

  • Kompilacja JIT może być tutaj dużą wygraną. CloudFlare Web Application Firewall generuje kod Lua, który jest wykonywany przez LuaJIT. LuaJIT mocno optymalizuje faktycznie wykonane ścieżki wykonywania (zwykle ścieżki nieatakowe), w wyniku czego kod działa znacznie szybciej niż kod generowany przez statyczny kompilator przy rzeczywistym obciążeniu. W przeciwieństwie do statycznego kompilatora z optymalizacją sterowaną profilem, LuaJIT dostosowuje się do zmian ścieżek wykonywania w czasie wykonywania.

  • Decydująca jest także dezimtymizacja . Zamiast kodu skompilowanego w JIT, który musi sprawdzać, czy klasa jest ładowana małpowo, czynność małpowania powoduje zawieszenie w systemie wykonawczym, który odrzuca kod maszynowy zależny od starej definicji.


Jak to jest odpowiedź? Cóż, punkt trzy może, jeśli dodasz referencje.
Raphael

Jestem bardzo sceptycznie nastawiony do twierdzenia, że ​​PGO nie może dorównać wydajności LuaJIT dla kodu aplikacji WWW przy typowym obciążeniu.
Konrad Rudolph

@KonradRudolph Kluczową zaletą JIT jest to, że JIT dostosowuje kod, gdy różne ścieżki stają się gorące.
Demi

@Demetri Wiem to. Ale bardzo trudno jest oszacować, czy jest to zaleta - zobacz moją odpowiedź i komentarz do dyskusji. W skrócie: chociaż JIT może dostosowywać się do zmian w użyciu, musi także śledzić rzeczy w czasie wykonywania, co pociąga za sobą narzut. Próg rentowności jest intuicyjny tylko w przypadku częstych zmian w zachowaniu. W przypadku aplikacji internetowych prawdopodobnie istnieje tylko jeden (lub bardzo nieliczny) wzorzec użytkowania, dla którego opłaca się optymalizacja, więc minimalny wzrost wydajności dzięki możliwości dostosowania nie równoważy obciążenia związanego z ciągłym profilowaniem.
Konrad Rudolph
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.