Dlaczego kompilatory nie wstawiają wszystkiego? [Zamknięte]

13

Czasami kompilatory wywołują funkcje wbudowane. Oznacza to, że przenoszą kod wywoływanej funkcji do funkcji wywołującej. To sprawia, że ​​rzeczy są nieco szybsze, ponieważ nie ma potrzeby pchania i pop-upowania na stosie wywołań i poza nim.

Więc moje pytanie brzmi: dlaczego kompilatory nie uwzględniają wszystkiego? Zakładam, że dzięki temu plik wykonywalny byłby znacznie szybszy.

Jedynym powodem, dla którego mogę wymyślić, jest znacznie większy plik wykonywalny, ale czy to naprawdę ma znaczenie w dzisiejszych czasach z setkami GB pamięci? Czy poprawa wydajności nie jest tego warta?

Czy jest jakiś inny powód, dla którego kompilatory nie tylko wstawiają wszystkich wywołań funkcji?

Aviv Cohn
źródło
18
IDK o tobie, ale nie mam setek GB pamięci tylko leżących wokół.
Ampt
2
Isn't the improved performance worth it?W przypadku metody, która uruchomi pętlę 100 razy i zniszczy niektóre poważne liczby, narzut związany z przenoszeniem 2 lub 3 argumentów do rejestrów procesora jest niczym.
Doval
5
Jesteś zbyt ogólny, czy „kompilatory” oznaczają „wszystkie kompilatory” i czy „wszystko” oznacza naprawdę „wszystko”? Wtedy odpowiedź jest prosta, są sytuacje, w których po prostu nie można wstawić. Przychodzi mi na myśl rekursja.
Otávio Décio
17
Lokalizacja pamięci podręcznej jest o wiele ważniejsza niż narzut niewielkich wywołań funkcji.
SK-logic
3
Czy poprawa wydajności naprawdę ma znaczenie w dzisiejszych czasach przy setkach GFLOPS mocy obliczeniowej?
mouviciel

Odpowiedzi:

22

Po pierwsze zauważ, że jednym z głównych efektów inline jest to, że umożliwia on dalszą optymalizację w witrynie połączenia.

Na twoje pytanie: są rzeczy trudne, a nawet niemożliwe do wstawienia:

  • dynamicznie połączone biblioteki

  • funkcje określane dynamicznie (dynamiczne wysyłanie, wywoływane przez wskaźniki funkcji)

  • funkcje rekurencyjne (puszka rekurencyjna)

  • funkcje, dla których nie masz kodu (ale optymalizacja czasu łącza pozwala na to dla niektórych z nich)

Inlining ma więc nie tylko korzystne skutki:

  • większy plik wykonywalny oznacza więcej miejsca na dysku i dłuższy czas ładowania

  • większy plik wykonywalny oznacza wzrost ciśnienia pamięci podręcznej (należy pamiętać, że wprowadzenie wystarczająco małych funkcji, takich jak proste programy pobierające, może zmniejszyć rozmiar pliku wykonywalnego i ciśnienie pamięci podręcznej)

I wreszcie, dla funkcji, których wykonanie zajmuje nietrudny czas, zysk po prostu nie jest wart bólu.

AProgrammer
źródło
3
niektóre rekurencyjne wywołania mogą być wstawiane (wywołania ogonowe), ale wszystkie mogą zostać przekształcone w iterację, jeśli opcjonalnie dodasz jawny stos
maniak zapadkowy
@ratchetfreak, możesz także przekształcić niektóre nie rekurencyjne wywołanie w tail one. Ale to dla mnie w dziedzinie „trudnej” (szczególnie gdy masz funkcje współrekurencyjne lub musisz dynamicznie określać, gdzie przeskoczyć, aby zasymulować zwrot), ale to nie jest niemożliwe (po prostu wdrożyłeś ramy kontynuacji i biorąc pod uwagę, że teraźniejszość staje się łatwiejsza).
AProgrammer
11

Głównym ograniczeniem jest polimorfizm środowiska uruchomieniowego. Jeśli podczas pisania ma miejsce dynamiczna wysyłka, foo.bar()nie można wstawić wywołania metody. To wyjaśnia, dlaczego kompilatory nie uwzględniają wszystkiego.

Nie można również łatwo wprowadzić połączeń rekurencyjnych.

Inliniowanie między modułami jest również trudne do wykonania ze względów technicznych (przyrostowa rekompilacja byłaby niemożliwa np.)

Jednak kompilatory wykonują wiele czynności.

Simon Bergot
źródło
3
Wprowadzanie za pomocą wirtualnej wysyłki jest bardzo trudne, ale nie niemożliwe. Niektóre kompilatory C ++ są w stanie to zrobić w określonych okolicznościach.
bstamour
2
... a także niektóre kompilatory JIT (devirtualizacja).
Frank
@bstamour Dowolny na wpół przyzwoity kompilator dowolnego języka z odpowiednią optymalizacją wywoła statycznie, tj. dewirtualizuje, wywołanie metody deklarowanej wirtualnej na obiekcie, którego typ dynamiczny można poznać w czasie kompilacji. Może to ułatwić wprowadzanie, jeśli faza dewializacji występuje przed (lub inną) fazą wprowadzania. Ale to jest banalne. Czy miałeś na myśli coś jeszcze? Nie rozumiem, w jaki sposób można osiągnąć rzeczywiste „Inlining poprzez wirtualną wysyłkę”. Aby inline, trzeba znać typ statycznej - czyli devirtualise - więc istnienie środków inline nie jest żaden wirtualny sklep
underscore_d
9

Po pierwsze, nie zawsze można wstawić, np. Funkcje rekurencyjne mogą nie zawsze być niewzruszalne (ale można wstawić program zawierający definicję rekurencyjną factz tylko drukowaniem fact(8)).

Wówczas inklinowanie nie zawsze jest korzystne. Jeśli kompilator wstawia się tak bardzo, że kod wynikowy jest wystarczająco duży, aby jego gorące części nie pasowały np. Do pamięci podręcznej instrukcji L1, może to być znacznie wolniejsze niż wersja bez wstawiania (która z łatwością mieściłaby się w pamięci podręcznej L1) ... Ponadto ostatnie procesory bardzo szybko wykonują CALLinstrukcje maszynowe (przynajmniej do znanej lokalizacji, tj. Bezpośredniego połączenia, a nie wskaźnika przez wskaźnik).

Wreszcie pełne wprowadzenie wymaga całej analizy programu. Może to nie być możliwe (lub jest zbyt kosztowne). Z C lub C ++ skompilowanym przez GCC (a także z Clang / LLVM ) musisz włączyć optymalizację czasu łącza (poprzez kompilację i połączenie z np. g++ -flto -O2), Co zajmuje sporo czasu kompilacji.

Basile Starynkevitch
źródło
1
Dla przypomnienia, LLVM / Clang (i kilka innych kompilatorów) obsługuje również optymalizację czasu łącza .
Ty
Wiem to; LTO istniało w poprzednim wieku (IIRC, przynajmniej w niektórych zastrzeżonych kompilatorach MIPS).
Basile Starynkevitch
7

Choć może się to wydawać zaskakujące, wprowadzenie wszystkiego niekoniecznie skraca czas wykonania. Zwiększony rozmiar kodu może utrudniać procesorowi przechowywanie całego kodu jednocześnie w pamięci podręcznej. Brak pamięci podręcznej w kodzie staje się bardziej prawdopodobny, a brak pamięci podręcznej jest drogi. Jest to znacznie gorsze, jeśli potencjalnie wbudowane funkcje są duże.

Od czasu do czasu zauważyłem znaczną poprawę wydajności, biorąc duże fragmenty kodu oznaczone jako „wbudowane” z plików nagłówkowych, umieszczając je w kodzie źródłowym, więc kod jest tylko w jednym miejscu, a nie w każdej witrynie wywołującej. Następnie pamięć podręczna procesora jest lepiej wykorzystywana, a Ty masz także lepszy czas kompilacji ...

Tom Tanner
źródło
wydaje się to jedynie powtórzeniem punktów poczynionych i wyjaśnionych we wcześniejszej odpowiedzi, która została opublikowana godzinę temu
gnat
1
Jakie skrytki? L1? L2? L3? Który jest ważniejszy?
Peter Mortensen
1

Wstawienie wszystkiego nie oznaczałoby tylko zwiększonego zużycia pamięci dyskowej, ale także zwiększonego zużycia pamięci wewnętrznej, co nie jest tak obfite. Pamiętaj, że kod opiera się również na pamięci w segmencie kodu; jeśli funkcja jest wywoływana z 10000 miejsc (powiedzmy te ze standardowych bibliotek w dość dużym projekcie), to kod tej funkcji zajmuje 10000 razy więcej pamięci wewnętrznej.

Innym powodem mogą być kompilatory JIT; jeśli wszystko jest w linii, nie ma gorących punktów do dynamicznej kompilacji.

m3th0dman
źródło
1

Po pierwsze, istnieją proste przykłady, w których wprowadzenie wszystkiego bardzo źle się sprawdzi. Rozważ ten prosty kod C:

void f1 (void) { printf ("Hello, world\n"); }
void f2 (void) { f1 (); f1 (); f1 (); f1 (); }
void f3 (void) { f2 (); f2 (); f2 (); f2 (); }
...
void f99 (void) { f98 (); f98 (); f98 (); f98 (); }

Zgadnij, co będzie dla ciebie najważniejsze.

Następnie przyjmij założenie, że wbudowanie przyspieszy. Tak jest czasami, ale nie zawsze. Jednym z powodów jest to, że kod pasujący do pamięci podręcznej instrukcji działa o wiele szybciej. Jeśli wywołam funkcję z 10 miejsc, zawsze uruchamiam kod z pamięci podręcznej instrukcji. Jeśli jest wstawiony, kopie są wszędzie i działają o wiele wolniej.

Istnieją inne problemy: Inlining tworzy ogromne funkcje. Ogromne funkcje są znacznie trudniejsze do optymalizacji. Osiągnąłem znaczny wzrost kodu krytycznego pod względem wydajności, ukrywając funkcje w osobnym pliku, aby zapobiec wbudowaniu ich w kompilator. W rezultacie wygenerowany kod dla tych funkcji był znacznie lepszy, gdy były ukryte.

BTW. Nie mam „setek GB pamięci”. Mój komputer nie ma nawet „setek GB miejsca na dysku twardym”. A jeśli moja aplikacja zawiera „setki GB pamięci”, załadowanie aplikacji do pamięci zajęłoby 20 minut.

gnasher729
źródło