Czy kompilatory wykorzystują wielowątkowość w celu skrócenia czasu kompilacji?

Jeśli dobrze pamiętam kurs mojego kompilatora, typowy kompilator ma następujący uproszczony zarys:

• Analizator leksykalny skanuje (lub wywołuje funkcję skanowania) kod źródłowy znak po znaku
• Ciąg znaków wejściowych jest sprawdzany pod kątem poprawności ze słownikiem leksemów
• Jeśli leksem jest ważny, jest on następnie klasyfikowany jako token, któremu odpowiada
• Analizator składni sprawdza składnię kombinacji tokenów; token po tokenie .

Czy teoretycznie wykonalne jest podzielenie kodu źródłowego na ćwiartki (lub jakikolwiek inny mianownik) i wielowątkowość procesu skanowania i analizy? Czy istnieją kompilatory wykorzystujące wielowątkowość?

Duże projekty oprogramowania zwykle składają się z wielu jednostek kompilacji, które można kompilować stosunkowo niezależnie, dlatego kompilacja jest często równoległa z bardzo zgrubną szczegółowością poprzez kilkakrotne wywoływanie kompilatora. Dzieje się tak na poziomie procesów systemu operacyjnego i jest koordynowane przez system kompilacji, a nie przez kompilator. Zdaję sobie sprawę, że nie o to pytałeś, ale jest to najbardziej zbliżona do równoległości w większości kompilatorów.

Dlaczego? Cóż, większość pracy wykonywanej przez kompilatory nie daje się łatwo zrównoleglać:

• Nie możesz tak po prostu podzielić danych wejściowych na kilka części i leksować je niezależnie. Dla uproszczenia chciałbyś podzielić granice leksemu (aby żaden wątek nie zaczynał się w środku leksemu), ale określenie granic leksemu potencjalnie wymaga dużego kontekstu. Na przykład, kiedy przeskakujesz w środku pliku, musisz upewnić się, że nie wskoczyłeś do literału łańcuchowego. Ale żeby to sprawdzić, musisz przyjrzeć się zasadniczo każdej postaci, która pojawiła się wcześniej, co jest prawie tak samo ciężkie, jak po prostu leksykanie jej na początek. Poza tym leksykon rzadko bywa wąskim gardłem w kompilatorach dla współczesnych języków.
• Analiza jest jeszcze trudniejsza do zrównoleglenia. Wszystkie problemy związane z dzieleniem tekstu wejściowego do leksykacji dotyczą jeszcze bardziej podziału tokenów do parsowania --- np. Ustalenie, gdzie zaczyna się funkcja, jest w zasadzie tak trudne, jak parsowanie zawartości funkcji na początek. Chociaż mogą istnieć sposoby na obejście tego, prawdopodobnie będą one nieproporcjonalnie skomplikowane z powodu niewielkiej korzyści. Parsowanie też nie jest największym wąskim gardłem.
• Po przeanalizowaniu zwykle trzeba wykonać rozpoznawanie nazw, ale prowadzi to do ogromnej przeplatanej sieci relacji. Aby rozwiązać wywołanie metody tutaj, być może trzeba najpierw rozwiązać importowanie w tym module, ale wymagają one rozpoznania nazw w innej jednostce kompilacji itp. To samo w przypadku wnioskowania o typie, jeśli ma to język.

Po tym jest nieco łatwiej. Sprawdzanie i optymalizacja typów oraz generowanie kodu mogą być w zasadzie zrównoleglone przy ziarnistości funkcji. Wciąż wiem o kilku, jeśli w ogóle to robią kompilatory, być może dlatego, że wykonywanie tak dużych zadań jednocześnie jest dość trudne. Trzeba także wziąć pod uwagę, że większość dużych projektów oprogramowania zawiera tak wiele jednostek kompilacyjnych, że podejście „uruchom kilka kompilatorów równolegle” jest całkowicie wystarczające, aby utrzymać wszystkie rdzenie (a w niektórych przypadkach nawet całą farmę serwerów). Ponadto w przypadku dużych zadań kompilacji dyskowe operacje we / wy mogą stanowić tak samo wąskie gardło, jak faktyczna praca kompilacji.

To powiedziawszy, znam kompilator, który równolegle pracuje nad generowaniem i optymalizacją kodu. Kompilator Rust może dzielić pracę zaplecza (LLVM, która faktycznie obejmuje optymalizacje kodu, które tradycyjnie uważa się za „środkowy koniec”) na kilka wątków. Nazywa się to „jednostkami genów kodu”. W przeciwieństwie do innych możliwości równoległości omówionych powyżej, jest to ekonomiczne, ponieważ:

1. Język ma dość duże jednostki kompilacji (w porównaniu, powiedzmy, C lub Java), więc w locie może być mniej jednostek kompilacji niż w przypadku rdzeni.
2. Część, która jest równoległa, zwykle zajmuje ogromną większość czasu kompilacji.
3. Praca z backendem jest w większości krępująco równoległa - wystarczy zoptymalizować i przetłumaczyć na kod maszynowy każdą funkcję niezależnie. Istnieją oczywiście optymalizacje między procedurami, a jednostki codegen utrudniają je, a tym samym wpływają na wydajność, ale nie ma żadnych problemów semantycznych.

Kompilacja to problem „żenująco równoległy”.

Nikt nie dba o czas na skompilowanie jednego pliku. Ludziom zależy na czasie kompilacji 1000 plików. A dla 1000 plików każdy rdzeń procesora może z przyjemnością skompilować jeden plik na raz, utrzymując wszystkie rdzenie całkowicie zajęte.

Wskazówka: „make” używa wielu rdzeni, jeśli dasz mu właściwą opcję wiersza poleceń. Bez tego kompiluje jeden plik po drugim w systemie 16-rdzeniowym. Co oznacza, że ​​możesz go skompilować 16 razy szybciej, zmieniając opcje wiersza o jedną linię.