Kompleksitas waktu dari kompiler

54

Saya tertarik pada kompleksitas waktu dari kompiler. Jelas ini adalah pertanyaan yang sangat rumit karena ada banyak kompiler, opsi kompiler dan variabel yang perlu dipertimbangkan. Secara khusus, saya tertarik pada LLVM tetapi akan tertarik pada pemikiran orang atau tempat untuk memulai penelitian. Google yang cukup tampaknya membawa sedikit ke cahaya.

Dugaan saya adalah bahwa ada beberapa langkah optimasi yang eksponensial, tetapi hanya berdampak kecil pada waktu aktual. Misalnya, eksponensial berdasarkan angka adalah argumen dari suatu fungsi.

Dari atas kepala saya, saya akan mengatakan bahwa menghasilkan pohon AST akan linier. Generasi IR akan membutuhkan melangkah melalui pohon sambil mencari nilai dalam tabel yang terus tumbuh, jadi $O(n^2)$ atau $O(n\log n)$ . Pembuatan dan penautan kode akan menjadi jenis operasi yang serupa. Karena itu, tebakan saya adalah $O(n^2)$ , jika kita menghapus variabel eksponensial yang tidak tumbuh secara realistis.

Tapi aku bisa salah total. Apakah ada yang punya pemikiran tentang itu?

compilers luar biasa
sumber

7

Anda harus berhati-hati ketika mengklaim sesuatu "eksponensial", "linear",

O (n^{2})

$O(n^2)$ , atau

O (n \log n)

$O(n \log n)$ . Setidaknya bagi saya, sama sekali tidak jelas bagaimana Anda mengukur input Anda (Eksponensial dalam apa? Apa

n

$n$ berdiri?)

Juho

2

Ketika Anda mengatakan LLVM, apakah maksud Anda Dentang? LLVM adalah proyek besar dengan beberapa sub proyek penyusun yang berbeda sehingga agak ambigu.

Nate CK

5

Untuk C # itu setidaknya eksponensial untuk masalah kasus terburuk (Anda dapat menyandikan NP menyelesaikan masalah SAT di C #). Ini bukan hanya optimasi, itu diperlukan untuk memilih kelebihan fungsi yang benar. Untuk bahasa seperti C ++ itu tidak bisa dipastikan, karena templat sudah selesai.

CodesInChaos

2

@Aneane Aku tidak mengerti maksudmu. Instansiasi template terjadi selama kompilasi. Anda dapat menyandikan masalah sulit ke dalam template dengan cara yang memaksa kompiler untuk menyelesaikan masalah itu untuk menghasilkan output yang benar. Anda dapat mempertimbangkan kompiler sebagai juru bahasa turing bahasa pemrograman templat lengkap.

CodesInChaos

3

Resolusi C # overload cukup rumit ketika Anda menggabungkan beberapa kelebihan beban dengan ekspresi lambda. Anda dapat menggunakannya untuk menyandikan rumus boolean sedemikian rupa, yang menentukan apakah ada kelebihan beban yang berlaku membutuhkan masalah NP-complete 3SAT. Untuk benar-benar mengkompilasi masalah, kompiler harus benar-benar menemukan solusi untuk formula itu, yang bahkan mungkin lebih sulit. Eric Lippert berbicara tentang itu secara rinci dalam posting blognya Ekspresi Lambda vs Metode Anonim, Bagian Lima

CodesInChaos

50

Buku terbaik untuk menjawab pertanyaan Anda mungkin adalah: Cooper dan Torczon, "Engineering a Compiler," 2003. Jika Anda memiliki akses ke perpustakaan universitas, Anda harus dapat meminjam salinannya.

Dalam kompiler produksi seperti llvm atau gcc, para desainer berusaha keras untuk menjaga semua algoritma di bawah ini $O(n^2)$ dimana $n$ adalah ukuran input. Untuk beberapa analisis untuk fase "optimisasi" ini berarti Anda perlu menggunakan heuristik daripada menghasilkan kode yang benar-benar optimal.

Lexer adalah mesin negara yang terbatas, jadi $O(n)$ dalam ukuran input (dalam karakter) dan menghasilkan aliran $O(n)$ token yang diteruskan ke parser.

Untuk banyak kompiler untuk banyak bahasa parser adalah LALR (1) dan dengan demikian memproses token stream dalam waktu $O(n)$ dalam jumlah token input. Selama parsing Anda biasanya harus melacak tabel simbol, tetapi, untuk banyak bahasa, itu dapat ditangani dengan tumpukan tabel hash ("kamus"). Setiap akses kamus adalah $O(1)$ , tetapi Anda kadang-kadang harus berjalan di tumpukan untuk mencari simbol. Kedalaman tumpukan adalah $O(s)$ dimana $s$ adalah kedalaman ruang lingkup. (Jadi dalam bahasa mirip-C, berapa banyak lapisan kurung kurawal yang ada di dalam Anda.)

Kemudian pohon parse biasanya "diratakan" ke dalam grafik aliran kontrol. Node dari grafik aliran kontrol mungkin berupa instruksi 3-alamat (mirip dengan bahasa rakitan RISC), dan ukuran grafik aliran kontrol biasanya akan linier dalam ukuran pohon parse.

Kemudian serangkaian langkah-langkah eliminasi redundansi biasanya diterapkan (eliminasi subekspresi umum, gerakan kode invarian loop, propagasi konstan, ...). (Ini sering disebut "optimisasi" walaupun jarang ada yang optimal tentang hasilnya, tujuan sebenarnya adalah untuk meningkatkan kode sebanyak mungkin dalam batasan waktu dan ruang yang telah kita tempatkan pada kompiler.) Setiap langkah eliminasi redundansi akan biasanya memerlukan bukti dari beberapa fakta tentang grafik aliran kontrol. Bukti-bukti ini biasanya dilakukan dengan menggunakan analisis aliran data . Sebagian besar analisis aliran data dirancang sehingga akan menyatu $O(d)$ melewati grafik aliran di mana $d$ adalah (secara kasar) kedalaman sarang loop dan melewati grafik aliran membutuhkan waktu $O(n)$ dimana $n$ adalah jumlah instruksi 3-alamat.

Untuk optimasi yang lebih canggih, Anda mungkin ingin melakukan analisis yang lebih canggih. Pada titik ini Anda mulai mengalami pengorbanan. Anda ingin algoritma analisis Anda mengambil kurang dari $O(n^2)$ waktu dalam ukuran diagram alir seluruh program, tetapi ini berarti Anda perlu melakukannya tanpa informasi (dan program meningkatkan transformasi) yang mungkin mahal untuk dibuktikan. Contoh klasik dari hal ini adalah analisis alias, di mana untuk pasangan memori menulis Anda ingin membuktikan bahwa keduanya menulis tidak pernah dapat menargetkan lokasi memori yang sama. (Anda mungkin ingin melakukan analisis alias untuk melihat apakah Anda dapat memindahkan satu instruksi di atas yang lain.) Tetapi untuk mendapatkan informasi yang akurat tentang alias, Anda mungkin perlu menganalisis setiap jalur kontrol yang mungkin melalui program, yang eksponensial dalam jumlah cabang. dalam program (dan dengan demikian eksponensial dalam jumlah node dalam grafik aliran kontrol.)

Selanjutnya Anda masuk ke alokasi register. Alokasi register dapat dirumuskan sebagai masalah pewarnaan grafik, dan pewarnaan grafik dengan jumlah warna minimal dikenal sebagai NP-Hard. Jadi kebanyakan kompiler menggunakan semacam heuristik serakah dikombinasikan dengan tumpahan register dengan tujuan mengurangi jumlah tumpahan register sebaik mungkin dalam batas waktu yang wajar.

Akhirnya Anda masuk ke pembuatan kode. Pembuatan kode biasanya dilakukan maksimal-blok dasar pada saat di mana blok dasar adalah seperangkat node grafik aliran kontrol terhubung linear dengan entri tunggal dan keluar tunggal. Ini dapat dirumuskan ulang sebagai grafik yang mencakup masalah di mana grafik yang Anda coba untuk tutupi adalah grafik ketergantungan dari set instruksi 3-alamat di blok dasar, dan Anda mencoba untuk menutup dengan satu set grafik yang mewakili mesin yang tersedia instruksi. Masalah ini bersifat eksponensial dalam ukuran blok dasar terbesar (yang pada prinsipnya dapat menjadi urutan yang sama dengan ukuran seluruh program), jadi ini lagi biasanya dilakukan dengan heuristik di mana hanya sebagian kecil dari penutup yang mungkin. diperiksa.

Logika Pengembaraan
sumber

4

Ketiga! Secara kebetulan, banyak masalah yang coba diselesaikan oleh penyusun (mis. Alokasi register) adalah NP-hard, tetapi yang lain secara formal tidak dapat diputuskan. Misalkan, misalnya, Anda memiliki panggilan p () diikuti oleh panggilan q (). Jika p adalah fungsi murni, maka Anda dapat dengan aman menyusun ulang panggilan selama p () tidak berulang tanpa henti. Membuktikan ini membutuhkan pemecahan masalah penghentian. Seperti halnya masalah NP-hard, penulis kompiler dapat melakukan upaya sebanyak atau sesedikit mungkin dalam mendekati solusi yang layak.

Nama samaran

4

Oh, satu hal lagi: Ada beberapa jenis sistem yang digunakan saat ini yang secara teori sangat kompleks. Inferensi tipe Hindley-Milner dikenal dengan bahasa DEXPTIME-complete, dan bahasa seperti ML harus mengimplementasikannya dengan benar. Namun, run time dalam praktiknya linier karena a) kasus patologis tidak pernah muncul dalam program dunia nyata, dan b) programmer dunia nyata cenderung memasukkan anotasi jenis, jika hanya untuk mendapatkan pesan kesalahan yang lebih baik.

Nama samaran

1

Jawaban yang bagus, satu-satunya hal yang tampaknya hilang adalah bagian sederhana dari penjelasan, dijabarkan dalam istilah sederhana: Menyusun program dapat dilakukan dalam O (n). Mengoptimalkan program sebelum kompilasi, seperti yang dilakukan kompiler modern, adalah tugas yang praktis tidak terbatas. Waktu yang sebenarnya diperlukan tidak diatur oleh batas tugas yang melekat, tetapi oleh kebutuhan praktis untuk kompiler untuk menyelesaikan pada titik tertentu sebelum orang bosan menunggu. Itu selalu kompromi.

aaaaaaaaaaaa

@ Nama samaran, fakta bahwa berkali-kali kompiler harus menyelesaikan masalah penghentian (atau masalah NP yang sangat buruk) adalah salah satu alasan standar memberikan kelonggaran penulis kompiler dalam mengasumsikan perilaku tidak terdefinisi tidak terjadi (seperti loop tak terbatas dan semacamnya). ).

vonbrand

15

Sebenarnya, beberapa bahasa (seperti C ++, Lisp, dan D) adalah Turing-complete pada waktu kompilasi, jadi kompilasi mereka tidak dapat diputuskan secara umum. Untuk C ++, ini karena instantiasi templat rekursif. Untuk Lisp dan D, Anda dapat mengeksekusi hampir semua kode pada waktu kompilasi, sehingga Anda dapat membuang kompilator ke dalam infinite loop jika Anda mau.

Demi
sumber

3

Sistem Haskell (dengan ekstensi) dan Scala juga lengkap-Turing, yang berarti bahwa pemeriksaan tipe mungkin memerlukan waktu yang tidak terbatas. Scala sekarang juga memiliki makro lengkap Turing di atasnya.

Jörg W Mittag

5

Dari pengalaman saya yang sebenarnya dengan kompiler C #, saya dapat mengatakan bahwa untuk program tertentu ukuran biner keluaran tumbuh secara eksponensial sehubungan dengan ukuran sumber input (ini sebenarnya diperlukan oleh spesifikasi C # dan tidak dapat dikurangi), jadi kompleksitas waktu harus setidaknya eksponensial juga.

Tugas resolusi kelebihan beban umum di C # dikenal sebagai NP-hard (dan kompleksitas implementasi aktual setidaknya eksponensial).

Pemrosesan komentar dokumentasi XML dalam sumber C # juga memerlukan evaluasi ekspresi XPath 1.0 yang sewenang-wenang pada waktu kompilasi, yang juga eksponensial, AFAIK.

Vladimir Reshetnikov
sumber

Apa yang membuat binari C # meledak seperti itu? Kedengarannya seperti bug bahasa bagi saya ...

vonbrand

1

Begitulah cara tipe generik dikodekan dalam metadata. 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

Ukurlah dengan basis kode yang realistis, seperti seperangkat proyek sumber terbuka. Jika Anda memplot hasilnya sebagai (codeSize, finishTime), maka Anda dapat memplot grafik tersebut. Jika data Anda f (x) = y adalah O (n), maka memplot g = f (x) / x akan memberi Anda garis lurus setelah data mulai menjadi besar.

Plot f (x) / x, f (x) / lg (x), f (x) / (x * lg (x)), f (x) / (x * x), dll. Grafik akan menyelam off ke nol, naikkan tanpa batas, atau ratakan. Gagasan ini berguna untuk situasi seperti mengukur waktu memasukkan mulai dari database kosong (yaitu: untuk mencari 'kebocoran kinerja' dalam jangka waktu yang lama.).

rampok
sumber

1

Pengukuran empiris waktu berjalan tidak membangun kompleksitas komputasi. Pertama, kompleksitas komputasi paling umum diungkapkan dalam hal waktu berjalan terburuk. Kedua, bahkan jika Anda ingin mengukur semacam kasus rata-rata, Anda harus memastikan bahwa input Anda "rata-rata" dalam arti itu.

David Richerby

Yah yakin itu hanya perkiraan. Tetapi tes empiris sederhana dengan banyak data nyata (setiap komit untuk sekelompok repositori git) mungkin mengalahkan model yang cermat. Bagaimanapun, jika suatu fungsi benar-benar O (n ^ 3) dan Anda memplot f (n) / (n n n), Anda harus mendapatkan garis yang berisik dengan kemiringan kira-kira nol. Jika Anda merencanakan hanya O (n ^ 3) / (n * n), Anda akan melihatnya naik secara linear. Sangat jelas jika Anda melebih-lebihkan dan menonton garis dengan cepat menyelam ke nol.

Rob

1

Misalnya, quicksort berjalan dalam waktu

Θ (n \log n)

$\Theta(n\log n)$ pada sebagian besar input data tetapi beberapa implementasi miliki

Θ (n^{2})

$\Theta(n^2)$ waktu berjalan dalam kasus terburuk (biasanya, pada input yang sudah diurutkan). Namun, jika Anda hanya merencanakan waktu berjalan, Anda akan lebih cenderung berlari ke sana

Θ (n \log n)

$\Theta(n\log n)$ kasus dari

Θ (n^{2})

$\Theta(n^2)$ yang

David Richerby

Saya setuju bahwa itu yang perlu Anda ketahui jika Anda khawatir mendapatkan penolakan layanan dari penyerang memberi Anda input buruk, melakukan beberapa penguraian input kritis real-time. Fungsi sebenarnya yang mengukur waktu kompilasi akan sangat bising, dan kasus yang kita pedulikan akan berada dalam repositori kode nyata.

Rob

1

Tidak. Pertanyaannya menanyakan kompleksitas waktu dari masalah tersebut. Itu biasanya ditafsirkan sebagai waktu berjalan terburuk, yang dengan tegas bukan waktu berjalan pada kode dalam repositori. Tes yang Anda usulkan memberikan pegangan yang masuk akal pada berapa lama Anda mungkin mengharapkan kompiler untuk mengambil sepotong kode, yang merupakan hal yang baik dan berguna untuk diketahui. Tetapi mereka hampir tidak memberi tahu Anda tentang kompleksitas komputasional dari masalah tersebut.

David Richerby

Kompleksitas waktu dari kompiler

Jawaban: