Apakah kompiler menggunakan multithreading untuk waktu kompilasi yang lebih cepat?

16

Jika saya ingat kursus kompiler saya dengan benar, kompiler tipikal memiliki garis besar yang disederhanakan berikut:

  • Penganalisa leksikal memindai (atau memanggil beberapa fungsi pemindaian) kode sumber karakter-demi-karakter
  • String karakter input diperiksa terhadap kamus leksem untuk validitas
  • Jika leksemanya valid, itu kemudian diklasifikasikan sebagai token yang sesuai dengannya
  • Parser memvalidasi sintaks kombinasi token; token-to-token .

Apakah secara teori layak untuk membagi kode sumber menjadi empat (atau penyebut apa pun) dan multithread proses pemindaian dan penguraian? Apakah ada kompiler yang menggunakan multithreading?

8 proton
sumber
1
@RobertHarvey Jawaban teratas tautan pertama menulis, "tetapi kompilernya sendiri masih berurutan tunggal." Jadi itu tidak?
8proton
Saya sarankan Anda membaca sisa jawaban, terutama yang ini , dan tautan kedua yang saya posting.
Robert Harvey
2
@RobertHarvey Tautan kedua yang Anda poskan, dari pemahaman saya tentang apa yang dikatakannya, berbicara tentang kompiler yang menghasilkan versi multithreaded dari aplikasi kompilasi Anda. Ini bukan tentang kompiler itu sendiri. Terima kasih atas sumber daya yang Anda bagikan dan meluangkan waktu untuk merespons.
8proton

Jawaban:

29

Proyek perangkat lunak besar biasanya terdiri dari banyak unit kompilasi yang dapat dikompilasi secara relatif independen, sehingga kompilasi sering diparalelkan pada granularitas yang sangat kasar dengan memanggil kompiler beberapa kali secara paralel. Ini terjadi pada tingkat proses OS dan dikoordinasikan oleh sistem build daripada compiler yang tepat. Saya menyadari ini bukan apa yang Anda minta tetapi itu adalah hal yang paling dekat dengan paralelisasi di kebanyakan penyusun.

Mengapa demikian? Nah, banyak pekerjaan yang dilakukan kompiler tidak mudah paralel:

  • Anda tidak bisa hanya membagi input menjadi beberapa bongkahan dan lex mereka secara mandiri. Untuk kesederhanaan Anda ingin membagi pada batas lexme (sehingga tidak ada utas yang dimulai di tengah lexme), tetapi menentukan batas lexme berpotensi membutuhkan banyak konteks. Misalnya, ketika Anda melompat di tengah file, Anda harus memastikan Anda tidak melompat ke string literal. Tetapi untuk memeriksanya, pada dasarnya Anda harus melihat setiap karakter yang datang sebelumnya, yang hampir sama banyaknya dengan bekerja sama dengan memulai saja. Selain itu, lexing jarang menjadi penghambat dalam kompiler untuk bahasa modern.
  • Parsing bahkan lebih sulit untuk diparalelkan. Semua masalah pemisahan teks input untuk lexing berlaku lebih banyak lagi untuk memisahkan token untuk penguraian --- misalnya, menentukan di mana fungsi dimulai pada dasarnya sama sulitnya dengan mem-parsing isi fungsi untuk memulai. Meskipun mungkin ada beberapa cara untuk mengatasi hal ini, mereka mungkin akan menjadi kompleks secara tidak proporsional untuk keuntungan kecil. Parsing juga bukan hambatan terbesar.
  • Setelah diuraikan, biasanya Anda perlu melakukan resolusi nama, tetapi ini mengarah ke jaring hubungan yang sangat luas. Untuk menyelesaikan panggilan metode di sini, Anda mungkin harus menyelesaikan impor dalam modul ini, tetapi yang mengharuskan Anda menyelesaikan nama-nama di unit kompilasi lain , dll. Sama untuk inferensi jenis jika bahasa Anda memilikinya.

Setelah ini, itu menjadi sedikit lebih mudah. Pengecekan tipe dan optimisasi dan pembuatan kode mungkin, pada prinsipnya, diparalelkan pada fungsi granularity. Saya masih tahu sedikit jika ada kompiler melakukan ini, mungkin karena melakukan tugas apa pun sebesar ini cukup menantang. Anda juga harus mempertimbangkan bahwa sebagian besar proyek perangkat lunak besar mengandung begitu banyak unit kompilasi sehingga pendekatan "run a bunch of compilers in parallel" sepenuhnya memadai untuk membuat semua core Anda tetap sibuk (dan dalam beberapa kasus, bahkan seluruh server farm). Plus, dalam tugas-tugas kompilasi besar disk I / O dapat menjadi hambatan sebanyak pekerjaan kompilasi yang sebenarnya.

Semua yang dikatakan, saya tahu kompiler yang memparalelkan pekerjaan pembuatan kode dan optimasi. Kompiler Rust dapat membagi pekerjaan back-end (LLVM, yang sebenarnya mencakup optimasi kode yang secara tradisional dianggap "menengah-akhir") di antara beberapa utas. Ini disebut "unit kode-gen". Berbeda dengan kemungkinan paralelisasi lain yang dibahas di atas, ini ekonomis karena:

  1. Bahasa ini memiliki unit kompilasi yang agak besar (dibandingkan dengan, katakanlah, C atau Java), jadi mungkin ada lebih sedikit unit kompilasi dalam penerbangan daripada Anda memiliki core.
  2. Bagian yang diparalelkan biasanya membutuhkan sebagian besar waktu kompilasi.
  3. Pekerjaan backend, untuk sebagian besar, paralel memalukan - hanya mengoptimalkan dan menerjemahkan ke kode mesin setiap fungsi secara mandiri. Tentu saja ada optimasi antar-prosedural, dan unit codegen menghambatnya dan dengan demikian berdampak pada kinerja, tetapi tidak ada masalah semantik.

sumber
2

Kompilasi adalah masalah "paralel yang memalukan".

Tidak ada yang peduli tentang waktu untuk mengkompilasi satu file. Orang-orang peduli tentang waktu mengkompilasi 1000 file. Dan untuk 1000 file, setiap inti prosesor dapat dengan senang hati mengkompilasi satu file pada satu waktu, membuat semua core benar-benar sibuk.

Kiat: "make" menggunakan banyak inti jika Anda memberinya opsi baris perintah yang benar. Tanpa itu akan mengkompilasi satu file setelah yang lain pada sistem 16 inti. Yang berarti Anda dapat membuatnya kompilasi 16 kali lebih cepat dengan perubahan satu baris ke opsi build Anda.

gnasher729
sumber