Złożoność czasowa kompilatora

54

Interesuje mnie złożoność czasowa kompilatora. Oczywiście jest to bardzo skomplikowane pytanie, ponieważ istnieje wiele kompilatorów, opcji kompilatora i zmiennych do rozważenia. W szczególności interesuję się LLVM, ale interesują mnie wszelkie przemyślenia i miejsca rozpoczęcia badań. Całkiem google wydaje się niewiele rozjaśniać.

Domyślam się, że istnieją pewne kroki optymalizacji, które są wykładnicze, ale mają niewielki wpływ na rzeczywisty czas. Np. Wykładnicza zależna od liczby jest argumentem funkcji.

Z góry mojej głowy powiedziałbym, że generowanie drzewa AST byłoby liniowe. Generowanie IR wymagałoby przejścia przez drzewo podczas wyszukiwania wartości w ciągle rosnących tabelach, więc lub . Generowanie kodu i łączenie byłoby podobnym rodzajem operacji. Dlatego domyślam się , gdybyśmy usunęli wykładnicze zmiennych, które nie rosną realistycznie. $O(n^2)$ $O(n\log n)$ $O(n^2)$

Mogę się jednak całkowicie mylić. Czy ktoś ma coś na ten temat?

compilers superbriggs
źródło

7

Musisz uważać, gdy twierdzisz, że cokolwiek jest „wykładnicze”, „liniowe”, lub . Przynajmniej dla mnie wcale nie jest oczywiste, jak mierzysz swój wkład (wykładniczy w czym? Co oznacza ?)

O (n^{2})

$O(n^2)$

O (n \log n)

$O(n \log n)$

n

$n$

Juho

2

Kiedy mówisz LLVM, masz na myśli Clanga? LLVM to duży projekt z kilkoma różnymi podprojektami kompilatora, więc jest nieco niejednoznaczny.

Nate CK,

5

Dla C # jest co najmniej wykładniczy w przypadku najgorszych problemów (możesz zakodować NP pełny problem SAT w C #). Nie jest to tylko optymalizacja, jest wymagana do wyboru prawidłowego przeciążenia funkcji. Dla języka takiego jak C ++ będzie nierozstrzygalny, ponieważ szablony są w toku.

CodesInChaos

2

@Zane Nie rozumiem, o co ci chodzi. Tworzenie instancji szablonu odbywa się podczas kompilacji. Trudne problemy można zakodować w szablonach w sposób, który zmusza kompilator do rozwiązania tego problemu w celu uzyskania prawidłowego wyniku. Można uznać kompilator za interpreter pełnego języka programowania szablonów Turinga.

CodesInChaos

3

Rozdzielczość przeciążenia w C # jest dość trudna, gdy łączysz wiele przeciążeń z wyrażeniami lambda. Można go użyć do zakodowania formuły boolowskiej w taki sposób, że ustalenie, czy występuje odpowiednie przeciążenie, wymaga problemu NP-complete 3SAT. Aby faktycznie skompilować problem, kompilator musi znaleźć rozwiązanie dla tej formuły, co może być nawet trudniejsze. Eric Lippert mówi o tym szczegółowo w swoim blogu Lambda Expressions vs. Anonymous Methods, Part Five

CodesInChaos

50

Najlepszą książką, w której można odpowiedzieć na twoje pytanie, byłyby prawdopodobnie: Cooper i Torczon, „Engineering a Compiler”, 2003. Jeśli masz dostęp do biblioteki uniwersyteckiej, powinieneś być w stanie pożyczyć kopię.

W kompilatorze produkcyjnym, takim jak llvm lub gcc, projektanci dokładają wszelkich starań, aby wszystkie algorytmy pozostawały poniżej gdzie jest rozmiarem danych wejściowych. W przypadku niektórych analiz dla faz „optymalizacji” oznacza to, że należy użyć heurystyki zamiast tworzyć naprawdę optymalny kod. $O(n^2)$ $n$

Lexer jest skończoną maszyną stanu, więc w wielkości wejściowej (w znakach) i wytwarza strumień tokenów który jest przekazywany do parsera. $O(n)$ $O(n)$

W wielu kompilatorach dla wielu języków analizatorem jest LALR (1), a zatem przetwarza strumień tokenów w czasie w liczbie tokenów wejściowych. Podczas parsowania zwykle musisz śledzić tabelę symboli, ale w wielu językach można to obsłużyć za pomocą stosu tabel skrótów („słowniki”). Każdy dostęp do słownika to , ale czasami może być konieczne przejście stosu w celu wyszukania symbolu. Głębokość stosu wynosi gdzie jest głębokością zagnieżdżenia zakresów. (Więc w językach podobnych do C, ile warstw nawiasów klamrowych jesteś w środku.) $O(n)$ $O(1)$ $O(s)$ $s$

Następnie parsowane drzewo jest zwykle „spłaszczane” do grafu kontrolnego. Węzły wykresu przepływu sterowania mogą być instrukcjami 3-adresowymi (podobnymi do języka asemblera RISC), a rozmiar wykresu przepływu sterowania będzie zwykle liniowy w stosunku do wielkości drzewa analizy.

Następnie zwykle stosuje się szereg etapów eliminacji redundancji (wspólna eliminacja podwyrażenia, ruch kodu niezmiennika w pętli, ciągła propagacja, ...). (Jest to często nazywane „optymalizacją”, chociaż rzadko jest coś optymalnego w wyniku, prawdziwym celem jest poprawienie kodu w jak największym stopniu w ramach ograniczeń czasowych i przestrzennych, które nałożyliśmy na kompilator.) Każdy krok eliminacji nadmiarowości będzie zazwyczaj wymagają dowodów potwierdzających niektóre fakty dotyczące grafu kontrolnego. Te dowody są zwykle wykonywane przy użyciu analizy przepływu danych . Większość analiz przepływu danych zaprojektowano tak, aby zbiegały się w przebiegach nad wykresem przepływu, gdzie jest (z grubsza) głębokością zagnieżdżenia pętli, a przejście przez wykres przepływu zajmuje czas $O(d)$ $d$ $O(n)$ gdzie jest liczbą instrukcji 3-adresowych. $n$

Aby uzyskać bardziej wyrafinowane optymalizacje, możesz przeprowadzić bardziej wyrafinowane analizy. W tym momencie zaczynasz wpadać na kompromisy. Chcesz, aby algorytmy analizy zajmowały znacznie mniej niż $O(n^2)$ czas wielkości wykresu przepływu całego programu, ale oznacza to, że musisz obejść się bez informacji (i usprawnień transformacji programu), których udowodnienie może być kosztowne. Klasycznym przykładem tego jest analiza aliasów, w której dla niektórych zapisów pamięci chciałbyś udowodnić, że te dwa zapisy nigdy nie mogą być kierowane na to samo miejsce w pamięci. (Możesz przeprowadzić analizę aliasu, aby sprawdzić, czy możesz przenieść jedną instrukcję nad drugą.) Ale aby uzyskać dokładne informacje na temat aliasów, może być konieczne przeanalizowanie każdej możliwej ścieżki sterowania przez program, która jest wykładnicza pod względem liczby rozgałęzień w programie (a zatem wykładniczo w liczbie węzłów na grafie przepływu sterowania).

Następnie przejdziesz do alokacji rejestru. Przydział rejestru można sformułować jako problem polegający na zabarwieniu wykresu, a kolorowanie wykresu przy minimalnej liczbie kolorów jest znane jako NP-Hard. Dlatego większość kompilatorów używa pewnego rodzaju chciwej heurystyki w połączeniu z rozlewaniem rejestrów w celu jak najlepszego ograniczenia liczby wycieków rejestrów w rozsądnych ramach czasowych.

Wreszcie możesz przejść do generowania kodu. Generowanie kodu jest zwykle wykonywane jako maksymalny blok podstawowy w czasie, gdy blok podstawowy jest zestawem liniowo połączonych węzłów grafowych sterowania przepływem z jednym wejściem i jednym wyjściem. Można to przeformułować jako wykres obejmujący problem, w którym wykres, który próbujesz pokryć, jest wykresem zależności zestawu instrukcji 3-adresowych w bloku podstawowym, a próbujesz pokryć się zestawem wykresów reprezentujących dostępną maszynę instrukcje. Ten problem ma wykładniczy rozmiar największego bloku podstawowego (który w zasadzie może być tego samego rzędu co rozmiar całego programu), więc znów dzieje się tak zwykle z heurystyką, gdzie tylko niewielka część możliwych pokryć jest badany.

Wędrująca logika
źródło

4

Trzeci! Nawiasem mówiąc, wiele problemów, które kompilatory próbują rozwiązać (np. Alokacja rejestru), jest trudnych do NP, ale inne są formalnie nierozstrzygalne. Załóżmy na przykład, że masz wywołanie p (), a następnie wywołanie q (). Jeśli p jest czystą funkcją, możesz bezpiecznie zmienić kolejność wywołań, o ile p () nie zapętla się w nieskończoność. Udowodnienie tego wymaga rozwiązania problemu zatrzymania. Podobnie jak w przypadku problemów związanych z NP-trudnością, autor kompilatora może włożyć tyle wysiłku w tak mało, jak to możliwe.

pseudonim

4

Aha, jeszcze jedno: w użyciu są obecnie systemy typów, które są bardzo złożone w teorii. Wnioskowanie o typie Hindleya-Milnera jest znane dla DEXPTIME-complete, a języki podobne do ML muszą poprawnie go implementować. Jednak czas działania jest w praktyce liniowy, ponieważ a) przypadki patologiczne nigdy nie pojawiają się w programach w świecie rzeczywistym, oraz b) programiści w świecie rzeczywistym zwykle umieszczają adnotacje typu, choćby po to, aby uzyskać lepsze komunikaty o błędach.

pseudonim

1

Świetna odpowiedź, jedyne, co wydaje się brakować, to prosta część objaśnienia, wyrażona w prostych słowach: Kompilacja programu może być wykonana w O (n). Optymalizacja programu przed kompilacją, tak jak zrobiłby to każdy współczesny kompilator, jest praktycznie nieograniczona. Czas, jaki faktycznie zajmuje, nie jest związany z żadną nieodłączną granicą zadania, ale raczej z praktycznej potrzeby ukończenia kompilatora w pewnym momencie, zanim ludzie będą zmęczeni czekaniem. To zawsze kompromis.

aaaaaaaaaaaa

@Pseudonim, fakt, że wiele razy kompilator musiałby rozwiązać problem zatrzymania (lub bardzo nieprzyjemne trudne problemy NP) jest jednym z powodów, dla których standardy dają autorowi kompilatora swobodę zakładania, że niezdefiniowane zachowanie się nie wydarzy (np. Nieskończone pętle i takie ).

vonbrand

15

W rzeczywistości niektóre języki (takie jak C ++, Lisp i D) są kompletne w czasie kompilacji Turinga, więc ich kompilacja jest w ogóle nierozstrzygalna. W przypadku C ++ wynika to z rekurencyjnej instancji szablonu. W przypadku Lisp i D możesz wykonać prawie dowolny kod w czasie kompilacji, więc możesz wrzucić kompilator do nieskończonej pętli, jeśli chcesz.

Demi
źródło

3

Systemy Haskell (z rozszerzeniami) i Scala są również pełne Turinga, co oznacza, że sprawdzenie typu może zająć nieskończenie dużo czasu. Scala ma teraz również na wierzchu makra Turinga.

Jörg W Mittag

5

Z mojego doświadczenia z kompilatorem C # mogę powiedzieć, że w przypadku niektórych programów rozmiar wyjściowego pliku binarnego rośnie wykładniczo w stosunku do wielkości źródła wejściowego (jest to faktycznie wymagane przez specyfikację C # i nie można go zmniejszyć), więc złożoność czasu musi być co najmniej wykładniczy.

Ogólne zadanie rozwiązywania przeciążenia w języku C # jest znane jako trudne dla NP (a rzeczywista złożoność implementacji jest co najmniej wykładnicza).

Przetwarzanie komentarzy do dokumentacji XML w źródłach w języku C # wymaga również oceny dowolnych wyrażeń XPath 1.0 w czasie kompilacji, czyli również wykładniczo, AFAIK.

Vladimir Reshetnikov
źródło

Co powoduje wysadzenie binariów C # w ten sposób? Brzmi dla mnie jak błąd językowy ...

vonbrand,

1

Jest to sposób, w jaki typy ogólne są kodowane w metadanych. class X<A,B,C,D,E> { class Y : X<Y,Y,Y,Y,Y> { Y.Y.Y.Y.Y.Y.Y.Y.Y y; } }

Vladimir Reshetnikov

-2

Zmierz go za pomocą realistycznych baz kodu, takich jak zestaw projektów open source. Jeśli wydrukujesz wyniki jako (codeSize, finishTime), możesz wykreślić te wykresy. Jeśli twoje dane f (x) = y to O (n), to wykreślenie g = f (x) / x powinno dać ci linię prostą po tym, jak dane zaczną się powiększać.

Wykres f (x) / x, f (x) / lg (x), f (x) / (x * lg (x)), f (x) / (x * x) itp. Wykres zanurkuje wyzerować, zwiększyć bez ograniczeń lub spłaszczyć. Pomysł ten przydaje się w sytuacjach takich jak pomiar czasu wstawiania zaczynając od pustej bazy danych (np. W celu znalezienia „przecieku wydajności” przez długi okres.).

Obrabować
źródło

1

Empiryczny pomiar czasów działania nie określa złożoności obliczeniowej. Po pierwsze, złożoność obliczeniowa jest najczęściej wyrażana jako najgorszy czas działania. Po drugie, nawet jeśli chcesz zmierzyć jakiś przeciętny przypadek, musisz ustalić, że twoje dane wejściowe są w tym sensie „średnie”.

David Richerby,

Cóż, na pewno jest to tylko szacunek. Ale proste testy empiryczne z dużą ilością prawdziwych danych (każde zatwierdzenie dla kilku repozytoriów git) mogą równie dobrze przebić ostrożny model. W każdym razie, jeśli funkcją jest rzeczywiście O (n ^ 3) i narysujesz wykres f (n) / (n n n), powinieneś otrzymać zaszumioną linię o nachyleniu z grubsza zero. Jeśli narysujesz tylko O (n ^ 3) / (n * n), zobaczysz, że rośnie liniowo. To naprawdę oczywiste, jeśli przeceniasz i obserwujesz, jak linia szybko zanurkuje do zera.

Rob

1

Nie. Na przykład Quicksort działa w czasie na większości danych wejściowych, ale niektóre implementacje mają czas działania w najgorszym przypadku (zwykle na danych wejściowych, które są już posortowane). Jeśli jednak po prostu wykreślisz czas działania, znacznie bardziej prawdopodobne jest, że napotkasz przypadki niż przypadki .

Θ (n \log n)

$\Theta(n\log n)$

Θ (n^{2})

$\Theta(n^2)$

Θ (n \log n)

$\Theta(n\log n)$

Θ (n^{2})

$\Theta(n^2)$

David Richerby

Zgadzam się, że to jest to, co musisz wiedzieć, jeśli martwisz się uzyskaniem odmowy usługi od atakującego, który daje ci złe dane wejściowe, dokonując krytycznej analizy danych wejściowych w czasie rzeczywistym. Prawdziwa funkcja mierząca czasy kompilacji będzie bardzo hałaśliwa, a przypadek, na którym nam zależy, będzie w prawdziwych repozytoriach kodu.

Rob

1

Nie. Pytanie dotyczy złożoności problemu w czasie. Jest to zwykle interpretowane jako najgorszy czas działania, który zdecydowanie nie jest czasem działania kodu w repozytoriach. Testy, które proponujesz, dają rozsądny wpływ na to, jak długo możesz oczekiwać, że kompilator przyjmie dany fragment kodu, co jest dobrą i przydatną rzeczą, którą należy wiedzieć. Ale prawie nic nie mówią o złożoności obliczeniowej problemu.

David Richerby,

Złożoność czasowa kompilatora

Odpowiedzi: