Bisakah bahasa dinamis seperti Ruby / Python mencapai kinerja C / C ++?

64

Saya bertanya-tanya apakah mungkin untuk membangun kompiler untuk bahasa dinamis seperti Ruby untuk memiliki kinerja yang mirip dan sebanding dengan C / C ++? Dari apa yang saya pahami tentang kompiler, ambil Ruby misalnya, kompilasi kode Ruby tidak pernah bisa efisien karena cara Ruby menangani refleksi, fitur seperti konversi tipe otomatis dari integer ke integer besar, dan kurangnya pengetikan statis membuat pembuatan kompiler efisien untuk Ruby sangat sulit.

Apakah mungkin untuk membangun kompiler yang dapat mengkompilasi Ruby atau bahasa dinamis lainnya ke biner yang berkinerja sangat dekat dengan C / C ++? Apakah ada alasan mendasar mengapa kompiler JIT, seperti PyPy / Rubinius akhirnya atau tidak akan pernah cocok dengan C / C ++ dalam kinerja?

Catatan: Saya mengerti bahwa "kinerja" tidak jelas, jadi untuk menjernihkannya, maksud saya, jika Anda dapat melakukan X di C / C ++ dengan kinerja Y, dapatkah Anda melakukan X di Ruby / Python dengan kinerja yang dekat dengan Y? Di mana X adalah segalanya, mulai dari driver perangkat dan kode OS, hingga aplikasi web.

Ichiro
sumber
1
Bisakah Anda mengulangi pertanyaan itu sehingga mendorong jawaban yang didukung oleh bukti yang tepat atas orang lain?
Raphael
@ Raphael Saya telah pergi ke depan dan mengedit. Saya pikir hasil edit saya tidak secara mendasar mengubah makna pertanyaan, tetapi membuatnya kurang mengundang opini.
Gilles 'SO- stop being evil'
1
Secara khusus, saya pikir Anda perlu memperbaiki satu (atau beberapa) ukuran kinerja nyata. Runtime? Penggunaan ruang? Penggunaan energi? Waktu pengembang? Pengembalian investasi? Perhatikan juga pertanyaan ini pada meta kami yang menyangkut pertanyaan ini (atau lebih tepatnya jawabannya).
Raphael
Pertanyaan ini adalah penggagas khas perang agama. Dan seperti yang bisa kita lihat dari jawaban, kita punya satu, meskipun sangat beradab.
Andrej Bauer
Ada bahasa dinamis yang memungkinkan anotasi jenis opsional (misalnya: Clojure). Dari apa yang saya ketahui, kinerja yang terkait dengan fungsi-fungsi beranotasi sama dengan ketika suatu bahasa diketik secara statis.
Pedro Morte Rolo

Jawaban:

68

Kepada semua yang mengatakan "ya" saya akan menawarkan poin tandingan bahwa jawabannya adalah "tidak", menurut desain . Bahasa-bahasa itu tidak akan pernah bisa menyamai kinerja bahasa yang dikompilasi secara statis.

Kos menawarkan titik (sangat valid) bahwa bahasa dinamis memiliki informasi lebih lanjut tentang sistem saat runtime yang dapat digunakan untuk mengoptimalkan kode.

Namun, ada sisi lain dari koin: informasi tambahan ini perlu dicatat. Pada arsitektur modern, ini adalah pembunuh kinerja.

William Edwards menawarkan ikhtisar argumen yang bagus .

Secara khusus, optimisasi yang disebutkan oleh Kos tidak dapat diterapkan di luar cakupan yang sangat terbatas kecuali jika Anda membatasi kekuatan ekspresif bahasa Anda secara drastis, seperti yang disebutkan oleh Devin. Ini tentu saja merupakan trade-off yang layak tetapi demi diskusi, Anda kemudian berakhir dengan bahasa statis , bukan yang dinamis. Bahasa-bahasa tersebut berbeda secara mendasar dari Python atau Ruby karena kebanyakan orang akan memahaminya.

William mengutip beberapa slide IBM yang menarik :

  • Setiap variabel dapat diketik secara dinamis: Memerlukan pemeriksaan jenis
  • Setiap pernyataan berpotensi menyebabkan pengecualian karena jenis ketidakcocokan dan sebagainya: Perlu pemeriksaan pengecualian
  • Setiap bidang dan simbol dapat ditambahkan, dihapus, dan diubah saat runtime: Perlu pemeriksaan akses
  • Jenis setiap objek dan hierarki kelasnya dapat diubah saat runtime: Memerlukan pemeriksaan hierarki kelas

Beberapa pemeriksaan tersebut dapat dihilangkan setelah analisis (NB: analisis ini juga membutuhkan waktu - saat runtime).

Lebih lanjut, Kos berpendapat bahwa bahasa dinamis bahkan dapat melampaui kinerja C ++. JIT memang dapat menganalisis perilaku program dan menerapkan optimisasi yang sesuai.

Tetapi kompiler C ++ dapat melakukan hal yang sama! Kompiler modern menawarkan apa yang disebut optimasi dipandu profil yang, jika mereka diberi input yang sesuai, dapat memodelkan perilaku runtime program dan menerapkan optimisasi yang sama dengan yang akan diterapkan JIT.

Tentu saja, ini semua bergantung pada keberadaan data pelatihan yang realistis dan lebih jauh lagi program tidak dapat mengadaptasi karakteristik runtime-nya jika pola penggunaan berubah saat dijalankan. Secara teoritis JIT dapat menangani hal ini. Saya akan tertarik untuk melihat bagaimana tarif ini dalam praktik, karena, untuk mengubah optimisasi, JIT akan terus-menerus harus mengumpulkan data penggunaan yang sekali lagi memperlambat eksekusi.

Singkatnya, saya tidak yakin bahwa optimisasi hot-spot runtime lebih besar daripada overhead pelacakan informasi runtime dalam jangka panjang , dibandingkan dengan analisis statis dan optimisasi.

Konrad Rudolph
sumber
2
@ Raphael Itu "kekurangan" dari kompiler itu. Secara khusus, javacpernahkah optimasi yang dipandu profil? Tidak sejauh yang saya ketahui. Secara umum tidak masuk akal untuk membuat kompiler dari bahasa JITted dengan baik dalam mengoptimalkan karena JIT dapat mengatasinya (dan paling tidak, dengan cara ini lebih banyak bahasa mendapat keuntungan dari upaya). Jadi (dapat dimengerti) tidak pernah ada banyak upaya untuk javacoptimizer, sejauh yang saya tahu (untuk bahasa .NET ini benar-benar benar).
Konrad Rudolph
1
@ Raphael Kata kuncinya adalah: mungkin. Itu tidak menunjukkannya. Hanya itu yang ingin saya katakan. Saya telah memberikan alasan (tetapi tidak ada bukti) untuk asumsi saya di paragraf sebelumnya.
Konrad Rudolph
1
@ Aku tidak menyangkal itu rumit. Ini hanyalah sebuah intuisi. Melacak semua informasi itu pada saat runtime memerlukan biaya. Saya tidak yakin dengan poin Anda tentang IO. Jika ini dapat diprediksi (= kasus penggunaan khas), maka PGO dapat memprediksinya. Jika palsu, saya tidak yakin JIT bisa mengoptimalkannya juga. Mungkin sesekali, karena keberuntungan. Namun andal? …
Konrad Rudolph
2
@ Konrad: Intuisi Anda salah. Ini bukan tentang variasi saat runtime, ini tentang ketidakpastian pada waktu kompilasi . Titik manis untuk JIT vs optimisasi statis tidak ketika perilaku program berubah saat runtime "terlalu cepat" untuk membuat profil, itu ketika perilaku program mudah dioptimalkan dalam setiap menjalankan program individu, tetapi bervariasi antara berjalan. Pengoptimal statis umumnya harus mengoptimalkan hanya untuk satu set kondisi, sedangkan JIT mengoptimalkan setiap proses secara terpisah, untuk kondisi yang terjadi dalam proses tersebut.
Ben
3
Perhatikan: Utas komentar ini berkembang menjadi ruang obrolan mini. Jika Anda ingin melanjutkan diskusi ini, bawa ke obrolan. Komentar harus digunakan untuk meningkatkan pos asli. Harap hentikan percakapan ini di sini. Terima kasih.
Robert Cartaino
20

jika Anda dapat melakukan X dalam C / C ++ dengan kinerja Y, dapatkah Anda melakukan X dalam Ruby / Python dengan kinerja yang dekat dengan Y?

Iya. Ambil, sebagai contoh, PyPy. Ini adalah kumpulan kode Python yang melakukan dekat dengan C dalam melakukan interpretasi (tidak terlalu dekat, tetapi tidak terlalu jauh). Itu melakukan ini dengan melakukan analisis program penuh pada kode sumber untuk menetapkan setiap variabel tipe statis (lihat dokumen Annotator dan Rtyper untuk perincian), dan kemudian, setelah dipersenjatai dengan informasi tipe yang sama yang Anda berikan C, ia dapat melakukan hal yang sama macam optimasi. Setidaknya secara teori.

Pengorbanannya tentu saja adalah bahwa hanya sebagian dari kode Python yang diterima oleh RPython, dan secara umum, bahkan jika pembatasan itu dicabut, hanya sebagian dari kode Python yang dapat melakukannya dengan baik: subset yang dapat dianalisis dan diberikan tipe statis.

Jika Anda cukup membatasi Python, pengoptimal dapat dibangun yang dapat memanfaatkan subset terbatas dan mengkompilasinya ke kode efisien. Ini sebenarnya bukan manfaat yang menarik, bahkan sudah terkenal. Tetapi inti dari menggunakan Python (atau Ruby) di tempat pertama adalah bahwa kami ingin menggunakan fitur menarik yang mungkin tidak menganalisis dengan baik dan menghasilkan kinerja yang baik! Jadi pertanyaan yang menarik sebenarnya ...

Selain itu, akankah kompiler JIT, seperti PyPy / Rubinius akan cocok dengan C / C ++ dalam kinerja?

Tidak

Maksud saya: tentu, mungkin ketika kode berjalan menumpuk Anda bisa mendapatkan cukup informasi pengetikan dan cukup hotspot untuk mengkompilasi semua kode sampai ke kode mesin. Dan mungkin kita bisa mendapatkan ini berkinerja lebih baik daripada C untuk beberapa kode. Saya tidak berpikir itu sangat kontroversial. Tapi itu masih harus "pemanasan", dan kinerja masih sedikit kurang dapat diprediksi, dan itu tidak akan sebaik C atau C ++ untuk tugas-tugas tertentu yang membutuhkan kinerja tinggi secara konsisten dan dapat diprediksi.

Data kinerja yang ada untuk Java, yang memiliki lebih banyak tipe informasi daripada Python atau Ruby, dan kompiler JIT yang lebih baik daripada Python atau Ruby, masih tidak cocok dengan C / C ++. Namun, di stadion baseball yang sama.

Devin Jeanpierre
sumber
1
"Pengorbanannya tentu saja adalah hanya sebagian dari kode Python yang diterima, atau lebih tepatnya, hanya sebagian dari kode Python yang dapat melakukannya dengan baik: subset yang dapat dianalisis dan diberikan tipe statis." Ini tidak terlalu akurat. Hanya subset yang dapat diterima sama sekali oleh kompiler RPython. Mengkompilasi ke RPython ke C yang efisien secara efisien hanya bekerja secara tepat karena bagian-bagian Python yang sulit dikompilasi dijamin tidak akan pernah muncul dalam program RPython; itu bukan hanya bahwa jika terjadi mereka tidak akan dioptimalkan. Ini adalah juru bahasa yang dikompilasi yang menangani semua Python.
Ben
1
Tentang JIT: Saya telah melihat lebih dari satu patokan di mana Java mengungguli beberapa rasa C (++). Hanya C ++ dengan peningkatan yang tampaknya tetap unggul. Dalam hal ini, saya bertanya-tanya tentang kinerja per waktu pengembang, tetapi itu adalah topik lain.
Raphael
@Ben: setelah Anda memiliki RPython, mudah untuk membuat kompiler / juru bahasa yang kembali menggunakan juru bahasa CPython ketika kompiler RPython gagal, oleh karena itu "hanya sebagian dari kode Python yang dapat melakukannya dengan baik: ..." benar-benar akurat.
Lie Ryan
9
@ Raphael Telah ditunjukkan berkali-kali bahwa kode C ++ yang ditulis dengan baik mengungguli Java. Ini adalah bagian "ditulis dengan baik" yang sedikit lebih sulit untuk masuk ke C ++, jadi di banyak bangku Anda melihat hasil bahwa Java mengungguli C ++. Karena itu, C ++ lebih mahal, tetapi ketika kontrol mem ketat dan grit logam diperlukan, C / C ++ itulah yang Anda pilih. C khususnya hanya assembler ac / p.
TC1
7
Membandingkan kinerja maksimal bahasa lain dengan bahasa seperti C / C ++ adalah semacam latihan yang sia-sia, karena Anda dapat langsung merakit perakitan sebagai bagian dari spesifikasi bahasa. Apa pun yang dapat dilakukan oleh mesin untuk menjalankan program yang ditulis dalam bahasa apa pun, paling buruk Anda dapat menggandakannya dengan menulis rakitan dari jejak instruksi yang dieksekusi. Metrik yang jauh lebih menarik adalah, seperti yang disarankan @Raphael dalam komentar sebelumnya, kinerja per upaya pengembangan (jam kerja, baris kode, dll.).
Patrick87
18

Jawaban singkatnya adalah: kita tidak tahu , tanyakan lagi dalam 100 tahun. (Kita mungkin masih belum tahu; mungkin kita tidak akan pernah tahu.)

Secara teori, ini mungkin. Ambil semua program yang pernah ditulis, terjemahkan secara manual ke kode mesin yang paling efisien, dan tulis juru bahasa yang memetakan kode sumber ke kode mesin. Ini dimungkinkan karena hanya sejumlah program terbatas yang pernah ditulis (dan semakin banyak program ditulis, pertahankan terjemahan manual). Ini juga, tentu saja, benar-benar bodoh dalam hal praktis.

Kemudian lagi, secara teori, bahasa tingkat tinggi mungkin dapat mencapai kinerja kode mesin, tetapi mereka tidak akan melampaui itu. Ini masih sangat teoretis, karena secara praktis, kami sangat jarang menggunakan kode mesin. Argumen ini tidak berlaku untuk membandingkan bahasa tingkat yang lebih tinggi: itu tidak menyiratkan bahwa C harus lebih efisien daripada Python, hanya bahwa kode mesin tidak dapat melakukan lebih buruk daripada Python.

Berasal dari sisi lain, dengan istilah yang murni eksperimental, kita dapat melihat bahwa sebagian besar waktu , bahasa tingkat tinggi yang ditafsirkan berkinerja lebih buruk daripada bahasa tingkat rendah yang dikompilasi. Kita cenderung menulis kode non-waktu-sensitif dalam bahasa tingkat tinggi dan loop dalam waktu kritis dalam perakitan, dengan bahasa seperti C dan Python termasuk di antaranya. Meskipun saya tidak memiliki statistik untuk mendukung ini, saya pikir ini memang keputusan terbaik dalam banyak kasus.

Namun, ada contoh yang tidak terbantahkan di mana bahasa tingkat tinggi mengalahkan kode yang akan ditulis secara realistis: lingkungan pemrograman tujuan khusus. Program seperti Matlab dan Mathematica seringkali jauh lebih baik dalam memecahkan beberapa jenis masalah matematika daripada apa yang bisa ditulis oleh manusia biasa. Fungsi pustaka mungkin ditulis dalam C atau C ++ (yang merupakan bahan bakar untuk kamp “bahasa tingkat rendah lebih efisien”), tetapi itu bukan urusan saya jika saya menulis kode Mathematica, perpustakaan adalah kotak hitam.

Apakah secara teori dimungkinkan bahwa Python akan mendapatkan sedekat, atau mungkin bahkan lebih dekat, ke kinerja optimal daripada C? Seperti yang terlihat di atas, ya, tapi kami sangat jauh dari itu hari ini. Kemudian lagi, kompiler telah membuat banyak kemajuan dalam beberapa dekade terakhir, dan kemajuan itu tidak melambat.

Bahasa tingkat tinggi cenderung membuat lebih banyak hal otomatis, sehingga mereka memiliki lebih banyak pekerjaan untuk dilakukan, dan dengan demikian cenderung kurang efisien. Di sisi lain, mereka cenderung memiliki lebih banyak informasi semantik, sehingga lebih mudah untuk menemukan optimasi (jika Anda menulis kompilator Haskell, Anda tidak perlu khawatir bahwa utas lain akan memodifikasi variabel di bawah hidung Anda). Salah satu dari beberapa upaya untuk membandingkan apel dan jeruk dengan bahasa pemrograman yang berbeda adalah Computer Benchmark Game (sebelumnya dikenal sebagai baku tembak). Fortran cenderung bersinar pada tugas-tugas numerik; tetapi ketika harus memanipulasi data terstruktur atau pergantian utas tingkat tinggi, F # dan Scala melakukannya dengan baik. Jangan menganggap hasil ini sebagai Injil: banyak dari apa yang mereka ukur adalah seberapa baik penulis program pengujian dalam setiap bahasa.

Argumen yang mendukung bahasa tingkat tinggi adalah bahwa kinerja pada sistem modern tidak begitu berkorelasi kuat dengan jumlah instruksi yang dieksekusi, dan kurang dari waktu ke waktu. Bahasa tingkat rendah cocok untuk mesin sekuensial sederhana. Jika bahasa tingkat tinggi mengeksekusi instruksi dua kali lebih banyak, tetapi mengelola untuk menggunakan cache lebih cerdas sehingga hanya setengah dari cache yang terlewat, itu mungkin akan menjadi pemenang.

Pada platform server dan desktop, CPU hampir mencapai puncak di mana mereka tidak mendapatkan yang lebih cepat (platform mobile juga ada di sana); ini mendukung bahasa di mana paralelisme mudah dieksploitasi. Banyak prosesor menghabiskan sebagian besar waktu mereka menunggu tanggapan I / O; waktu yang dihabiskan dalam perhitungan sedikit dibandingkan dengan jumlah I / O, dan bahasa yang memungkinkan pemrogram untuk meminimalkan komunikasi adalah menguntungkan.

Secara keseluruhan, sementara bahasa tingkat tinggi dimulai dengan penalti, mereka memiliki lebih banyak ruang untuk perbaikan. Seberapa dekat mereka? Tanyakan lagi dalam 100 tahun.

Catatan akhir: seringkali, perbandingannya bukan antara program yang paling efisien yang dapat ditulis dalam bahasa A dan sama dalam bahasa B, atau antara program paling efisien yang pernah ditulis dalam setiap bahasa, tetapi antara program paling efisien yang dapat ditulis oleh manusia dalam jumlah waktu tertentu dalam setiap bahasa. Ini memperkenalkan elemen yang tidak dapat dianalisis secara matematis, bahkan secara prinsip. Dalam istilah praktis, ini sering berarti bahwa kinerja terbaik adalah kompromi antara seberapa banyak kode tingkat rendah yang Anda perlu tulis untuk memenuhi sasaran kinerja dan berapa banyak kode tingkat rendah yang Anda miliki waktu untuk menulis untuk memenuhi tanggal rilis.

Gilles 'SANGAT berhenti menjadi jahat'
sumber
Saya pikir perbedaan antara level tinggi dan level rendah adalah yang salah. C ++ dapat (sangat) tingkat tinggi. Namun C ++ tingkat tinggi yang modern tidak (tentu) berkinerja lebih buruk daripada yang setara dengan level rendah - justru sebaliknya. C ++ dan perpustakaannya dirancang dengan hati-hati untuk menawarkan abstraksi tingkat tinggi tanpa penalti kinerja. Hal yang sama berlaku untuk contoh Haskell Anda: abstraksi tingkat tinggi sering kali memungkinkan daripada mencegah optimisasi. Perbedaan asli antara bahasa dinamis dan bahasa statis lebih masuk akal dalam hal ini.
Konrad Rudolph
@KonradRudolph Anda benar, dalam level rendah / level tinggi adalah perbedaan yang agak sewenang-wenang. Tetapi bahasa dinamis vs statis tidak menangkap semuanya juga; sebuah JIT dapat menghilangkan banyak perbedaan. Pada dasarnya, jawaban teoretis yang diketahui untuk pertanyaan ini sepele dan tidak berguna, dan jawaban praktisnya adalah "itu tergantung".
Gilles 'SO- stop being evil'
Kalau begitu, saya pikir pertanyaannya hanya menjadi “seberapa bagus JIT menjadi, dan jika mereka menyalip kompilasi statis, dapatkah bahasa yang dikompilasi secara statis juga mendapat untung dari mereka?” Setidaknya itulah bagaimana saya memahami pertanyaan begitu kita mempertimbangkan JIT. Dan ya, saya setuju dengan penilaian Anda, tetapi tentu saja kami bisa mendapatkan beberapa tebakan yang melampaui "tergantung". ;-)
Konrad Rudolph
@KonradRudolph Jika saya ingin menebak, saya akan bertanya tentang Rekayasa Perangkat Lunak .
Gilles 'SANGAT berhenti menjadi jahat'
1
Sayangnya, shootout bahasa adalah sumber yang dipertanyakan untuk tolok ukur kuantitatif: mereka tidak menerima semua program hanya yang dianggap khas bahasa. Ini adalah persyaratan yang rumit dan sangat subyektif; itu berarti Anda tidak dapat berasumsi bahwa implementasi baku tembak sebenarnya ada gunanya (dan dalam praktiknya, beberapa implementasi jelas-jelas telah menolak alternatif yang unggul). Di sisi lain; ini adalah microbenchmark dan beberapa implementasi menggunakan teknik yang tidak biasa yang tidak akan pernah Anda pertimbangkan dalam skenario yang lebih normal hanya untuk memenangkan kinerja. Jadi: ini permainan, bukan sumber data yang sangat andal.
Eamon Nerbonne
10

Perbedaan mendasar antara C ++ pernyataan x = a + bdan pernyataan Python x = a + badalah bahwa C / C ++ compiler tahu dari pernyataan ini (dan sedikit tambahan informasi bahwa ia memiliki tersedia tentang jenis x, adan b) tepat apa kode mesin harus dijalankan . Sedangkan untuk mengetahui operasi apa yang akan dilakukan pernyataan Python, Anda harus menyelesaikan Masalah Pemutusan.

Dalam C pernyataan itu pada dasarnya akan dikompilasi ke salah satu dari beberapa jenis penambahan mesin (dan kompiler C tahu yang mana). Dalam C ++ mungkin mengkompilasi seperti itu, atau mungkin mengkompilasi untuk memanggil fungsi yang dikenal secara statis, atau (kasus terburuk) mungkin harus dikompilasi ke metode pencarian dan panggilan metode virtual, tetapi bahkan ini memiliki overhead kode mesin yang cukup kecil. Lebih penting lagi, kompiler C ++ dapat mengetahui dari jenis yang diketahui secara statis yang terlibat apakah ia dapat memancarkan satu operasi penambahan cepat atau apakah ia perlu menggunakan salah satu opsi yang lebih lambat.

Dalam Python, sebuah kompiler secara teoritis dapat melakukan hampir sebaik itu jika tahu itu adan bkeduanya ints. Ada beberapa overhead tinju tambahan, tetapi jika jenisnya diketahui secara statis Anda mungkin bisa menyingkirkannya juga (sambil tetap menampilkan antarmuka yang bilangan bulat adalah objek dengan metode, hierarki kelas-super, dll). Masalahnya adalah kompiler untuk Python tidak bisaketahui hal ini, karena kelas didefinisikan pada saat runtime, dapat dimodifikasi pada saat runtime, dan bahkan modul yang melakukan pendefinisian dan pengimporan diselesaikan pada saat runtime (dan bahkan pernyataan impor mana yang dijalankan tergantung pada hal-hal yang hanya dapat diketahui saat runtime). Jadi kompiler Python harus tahu kode apa yang telah dieksekusi (yaitu menyelesaikan Masalah Berhenti) untuk mengetahui apa pernyataan yang dikompilasi akan dilakukan.

Jadi, bahkan dengan analisis paling canggih yang secara teori dimungkinkan , Anda tidak bisa memberi tahu banyak tentang apa yang akan dilakukan pernyataan Python sebelumnya. Ini berarti bahwa bahkan jika kompiler Python canggih diimplementasikan, itu dalam hampir semua kasus masih harus memancarkan kode mesin yang mengikuti protokol pencarian kamus Python untuk menentukan kelas objek dan menemukan metode (melintasi MRO dari hirarki kelas, yang juga dapat berubah secara dinamis saat runtime dan sulit untuk dikompilasi ke tabel metode virtual sederhana), dan pada dasarnya melakukan apa yang dilakukan oleh penerjemah (lambat). Inilah sebabnya mengapa sebenarnya tidak ada kompiler pengoptimal yang canggih untuk bahasa dinamis. Ini tidak hanya sulit untuk membuat satu, hasil maksimal yang mungkin bukan

Catatan bahwa ini tidak didasarkan pada apa kode yang melakukan, hal ini didasarkan pada apa kode bisa melakukan. Bahkan kode Python yang merupakan rangkaian sederhana dari operasi aritmatika integer harus dikompilasi seolah-olah ia dapat memanggil operasi kelas sewenang-wenang. Bahasa statis memiliki batasan lebih besar pada kemungkinan untuk apa yang bisa dilakukan kode, dan akibatnya kompiler mereka dapat membuat lebih banyak asumsi.

Kompiler JIT mendapatkan keuntungan ini dengan menunggu sampai runtime untuk mengkompilasi / mengoptimalkan. Hal ini memungkinkan mereka memancarkan kode yang bekerja untuk apa kode yang melakukan daripada apa yang bisa melakukan. Dan karena kompiler JIT ini memiliki potensi hasil yang lebih besar untuk bahasa dinamis daripada bahasa statis; untuk bahasa yang lebih statis, apa yang ingin diketahui oleh pengoptimal dapat diketahui sebelumnya, jadi sebaiknya Anda mengoptimalkannya, sehingga menyisakan sedikit bagi kompiler JIT untuk melakukannya.

Ada berbagai kompiler JIT untuk bahasa dinamis yang mengklaim untuk mencapai kecepatan eksekusi yang sebanding dengan C / C ++ yang disusun dan dioptimalkan. Bahkan ada optimisasi yang dapat dilakukan oleh kompiler JIT yang tidak dapat dilakukan oleh kompiler sebelumnya untuk bahasa apa pun, jadi kompilasi JIT secara teoritis (untuk beberapa program) suatu hari bisa mengungguli kompiler statis terbaik. Tetapi seperti yang ditunjukkan oleh Devin dengan tepat, properti dari kompilasi JIT (hanya "hotspot" yang cepat, dan hanya setelah periode pemanasan) berarti bahwa bahasa dinamis yang dikompilasi dengan JIT tidak akan pernah cocok untuk semua aplikasi yang mungkin, bahkan jika mereka menjadi lebih cepat atau lebih cepat daripada bahasa yang dikompilasi secara statis pada umumnya.

Ben
sumber
1
Itu sekarang dua suara tanpa komentar. Saya akan menyambut saran untuk bagaimana meningkatkan jawaban ini!
Ben
Saya tidak mengundurkan diri, tetapi Anda salah tentang "perlu menyelesaikan masalah penghentian". Telah dibuktikan dalam banyak keadaan bahwa kode dalam bahasa dinamis dapat dikompilasi menjadi kode target optimal, sedangkan setahu saya tidak ada demonstrasi ini yang menyertakan solusi untuk masalah penghentian :-)
mikera
@ Mikera Maaf, tapi tidak, Anda salah. Tidak ada yang pernah mengimplementasikan kompiler (dalam pengertian bahwa kami memahami bahwa GCC adalah kompiler) untuk Python yang sepenuhnya umum , atau bahasa dinamis lainnya. Setiap sistem seperti itu hanya berfungsi untuk sebagian bahasa, atau hanya program tertentu, atau terkadang memancarkan kode yang pada dasarnya adalah juru bahasa yang berisi program yang dikodekan keras. Jika Anda mau, saya akan menulis Anda sebuah program Python yang berisi baris di foo = x + ymana memprediksi perilaku operator tambahan pada waktu kompilasi tergantung pada penyelesaian masalah penghentian.
Ben
Saya benar dan saya pikir Anda tidak mengerti intinya. Saya berkata "dalam banyak situasi". Saya tidak mengatakan "dalam semua keadaan yang memungkinkan". Apakah Anda dapat membuat contoh yang dibuat-buat yang terkait dengan masalah penghentian sebagian besar tidak relevan di dunia nyata. FWIW, Anda juga bisa membuat contoh serupa untuk C ++ sehingga Anda tidak akan membuktikan apa pun. Bagaimanapun, saya tidak datang ke sini untuk berdebat, hanya untuk menyarankan perbaikan pada jawaban Anda. Ambil atau tinggalkan.
mikera
@mikea Saya pikir Anda mungkin kehilangan intinya. Untuk mengkompilasi x + yke operasi penambahan mesin yang efisien, Anda harus tahu pada waktu kompilasi apakah itu atau tidak. Setiap saat , bukan hanya sebagian waktu. Untuk bahasa dinamis ini hampir tidak pernah mungkin dengan program yang realistis, meskipun heuristik yang masuk akal akan menebak sebagian besar waktu. Kompilasi membutuhkan jaminan waktu kompilasi . Jadi dengan berbicara tentang "dalam banyak situasi" Anda sebenarnya tidak menanggapi jawaban saya sama sekali.
Ben
9

Hanya penunjuk cepat yang menguraikan skenario terburuk untuk bahasa dinamis:

Perl parsing tidak dapat dihitung

Akibatnya, Perl (penuh) tidak akan pernah dapat dikompilasi secara statis.


Secara umum, seperti biasa, itu tergantung. Saya yakin bahwa jika Anda mencoba meniru fitur dinamis dalam bahasa yang dikompilasi secara statis, interpreter yang disusun dengan baik atau (sebagian) varian yang dikompilasi dapat mendekati atau melemahkan kinerja bahasa yang dikompilasi secara statis.

Hal lain yang perlu diingat adalah bahwa bahasa dinamis memecahkan masalah lain daripada C. C tidak lebih dari sintaksis yang bagus untuk assembler sementara bahasa dinamis menawarkan abstraksi yang kaya. Kinerja Runtime seringkali bukan perhatian utama: waktu-ke-pasar, misalnya, tergantung pada pengembang Anda yang mampu menulis sistem yang rumit dan berkualitas tinggi dalam jangka waktu yang singkat. Ekstensibilitas tanpa kompilasi ulang, misalnya dengan plugin, adalah fitur populer lainnya. Bahasa apa yang Anda sukai dalam hal ini?

Raphael
sumber
5

Dalam upaya menawarkan jawaban ilmiah yang lebih obyektif terhadap pertanyaan ini, saya berpendapat sebagai berikut. Bahasa yang dinamis membutuhkan penerjemah, atau runtime, untuk membuat keputusan pada saat run time. Penerjemah ini, atau runtime, adalah program komputer dan, dengan demikian, ditulis dalam beberapa bahasa pemrograman, baik statis atau dinamis.

Jika interpreter / runtime ditulis dalam bahasa statis, maka seseorang dapat menulis sebuah program dalam bahasa statis itu yang (a) melakukan fungsi yang sama dengan program dinamis yang ditafsirkannya dan (b) melakukan setidaknya juga. Mudah-mudahan, ini terbukti dengan sendirinya, karena untuk memberikan bukti yang kuat tentang klaim ini akan membutuhkan upaya tambahan (mungkin cukup besar).

Dengan menganggap klaim ini benar, satu-satunya jalan keluar adalah mewajibkan penerjemah / runtime ditulis dalam bahasa yang dinamis juga. Namun, kami mengalami masalah yang sama seperti sebelumnya: jika penerjemahnya dinamis, ia membutuhkan juru bahasa / runtime, yang juga harus ditulis dalam bahasa pemrograman, dinamis atau statis.

Kecuali Anda berasumsi bahwa sebuah instance dari juru bahasa mampu menafsirkan dirinya sendiri pada saat runtime (saya harap ini jelas tidak masuk akal), satu-satunya cara untuk mengalahkan bahasa statis adalah untuk setiap contoh juru bahasa untuk ditafsirkan oleh contoh juru bahasa yang berbeda; ini mengarah pada kemunduran tanpa batas (saya harap ini jelas tidak masuk akal) atau loop tertutup dari penafsir (saya harap ini juga jelas absurd).

Tampaknya, kemudian, bahwa bahkan dalam teori, bahasa dinamis dapat melakukan tidak lebih baik daripada bahasa statis, secara umum. Saat menggunakan model komputer yang realistis, tampaknya bahkan lebih masuk akal; Lagi pula, sebuah mesin hanya dapat menjalankan urutan instruksi mesin, dan semua urutan instruksi mesin dapat dikompilasi secara statis.

Dalam praktiknya, mencocokkan kinerja bahasa dinamis dengan bahasa statis dapat memerlukan penerapan kembali juru bahasa / runtime dalam bahasa statis; Namun, Anda dapat melakukan itu sama sekali adalah inti dan pokok dari argumen ini. Ini pertanyaan ayam dan telur dan, asalkan Anda setuju dengan asumsi yang belum terbukti (meskipun, menurut saya, sebagian besar terbukti sendiri) yang dibuat di atas, kita sebenarnya bisa menjawabnya; kita harus memberi anggukan pada bahasa statis, bukan dinamis.

Cara lain untuk menjawab pertanyaan, dalam terang diskusi ini, adalah ini: dalam program tersimpan, control = model data komputasi yang terletak di jantung komputasi modern, perbedaan antara kompilasi statis dan dinamis adalah dikotomi yang salah; bahasa yang dikompilasi secara statis harus memiliki cara menghasilkan dan mengeksekusi kode arbitrer pada saat run time. Ini pada dasarnya terkait dengan perhitungan universal.

Patrick87
sumber
Membaca ulang ini, saya rasa itu tidak benar. Kompilasi JIT mematahkan argumen Anda. Bahkan kode yang paling sederhana, mis. main(args) { for ( i=0; i<1000000; i++ ) { if ( args[0] == "1" ) {...} else {...} }Dapat secara signifikan dipercepat begitu nilai argsdiketahui (dengan asumsi itu tidak pernah berubah, yang mungkin bisa kita nyatakan). Kompiler statis tidak dapat membuat kode yang pernah dibandingkan. (Tentu saja, dalam contoh itu Anda hanya menarik ifkeluar dari loop. Tapi masalahnya mungkin lebih berbelit-belit.)
Raphael
@ Raphael Saya pikir JIT mungkin membuat argumen saya. Program yang melakukan kompilasi JIT (misalnya, JVM) biasanya adalah program yang dikompilasi secara statis. Jika program JIT yang dikompilasi secara statis dapat menjalankan skrip lebih cepat daripada beberapa program statis lainnya dapat melakukan pekerjaan yang sama, cukup "bundel" skrip dengan kompiler JIT, dan panggil bundel itu program yang dikompilasi secara statis. Ini harus melakukan setidaknya seperti halnya JIT yang beroperasi pada program dinamis yang terpisah, yang bertentangan dengan argumen apa pun yang harus dilakukan JIT dengan lebih baik.
Patrick87
Hm, itu seperti mengatakan bundling naskah Ruby dengan penerjemahnya memberi Anda program yang dikompilasi secara statis. Saya tidak setuju (karena menghapus semua perbedaan bahasa dalam hal ini), tapi itu masalah semantik, bukan konsep. Secara konseptual, mengadaptasi program saat runtime (JIT) dapat melakukan optimisasi yang tidak dapat Anda lakukan pada waktu kompilasi (penyusun statis), dan itulah poin saya.
Raphael
@Raphael Bahwa tidak ada perbedaan yang berarti adalah semacam jawaban: setiap upaya untuk secara kaku mengklasifikasikan beberapa bahasa sebagai statis, dan karenanya mengalami keterbatasan kinerja, gagal karena alasan ini: tidak ada perbedaan yang meyakinkan antara yang dipaketkan (Ruby) , skrip) bundel dan program C. Jika (Ruby, script) dapat membuat mesin mengeksekusi urutan instruksi yang tepat untuk secara efisien menyelesaikan masalah yang diberikan, maka bisa juga program C yang dibuat dengan cerdik.
Patrick87
Tetapi Anda dapat menentukan perbedaannya. Satu varian mengirimkan kode yang ada ke prosesor tidak berubah (C), kompilasi lainnya saat runtime (Ruby, Java, ...). Yang pertama adalah apa yang kami maksud dengan "kompilasi statis" sedangkan yang terakhir adalah "kompilasi tepat waktu" (yang memungkinkan optimisasi yang bergantung pada data).
Raphael
4

Bisakah Anda membuat kompiler untuk bahasa dinamis seperti Ruby untuk memiliki kinerja yang mirip dan sebanding dengan C / C ++?

Saya pikir jawabannya "ya" . Saya juga percaya bahwa mereka bahkan dapat melampaui arsitektur C / C ++ saat ini dalam hal efisiensi (bahkan jika sedikit).

Alasannya sederhana: Ada lebih banyak informasi dalam run-time daripada di compile-time.

Tipe dinamis hanya sedikit kendala: Jika suatu fungsi selalu atau hampir selalu dieksekusi dengan tipe argumen yang sama, maka pengoptimal JIT dapat menghasilkan cabang dan kode mesin untuk kasus tertentu. Dan ada banyak lagi yang bisa dilakukan.

Lihat Dynamic Languages ​​Strike Back , pidato oleh Steve Yegge dari Google (ada juga versi video di suatu tempat yang saya percaya). Dia menyebutkan beberapa teknik optimisasi JIT konkret dari V8. Menginspirasi!

Saya menantikan apa yang akan kita miliki dalam 5 tahun ke depan!

Kos
sumber
2
Saya suka optimisme.
Dave Clarke
Saya percaya ada beberapa kritik yang sangat spesifik tentang ketidakakuratan dalam pembicaraan Steve. Saya akan mempostingnya ketika saya menemukannya.
Konrad Rudolph
1
@ DaveClarke itulah yang membuat saya tetap berjalan :)
Kos
2

Orang-orang yang tampaknya berpikir ini secara teori mungkin, atau jauh di masa depan, sepenuhnya salah menurut pendapat saya. Intinya terletak pada kenyataan bahwa bahasa dinamis menyediakan dan memaksakan gaya pemrograman yang sama sekali berbeda. Sebenarnya, perbedaannya ada dua, bahkan jika kedua aspek tersebut saling terkait:

  • Simbol (vars, atau lebih tepatnya id <-> binding datum dari semua jenis) tidak diketik.
  • Struktur (data, semua yang hidup saat runtime) juga tidak diketik berdasarkan jenis elemennya.

Poin kedua memberikan kedermawanan secara gratis. Perhatikan bahwa struktur di sini adalah elemen komposit, koleksi, tetapi juga mengetik sendiri, dan bahkan (!) Rutinitas dari semua jenis (fungsi, tindakan, operasi) ... Kita bisa mengetik struktur berdasarkan tipe elemen mereka, tetapi karena titik pertama cek akan terjadi saat runtime. Kita dapat mengetik simbol dan masih memiliki yang terstruktur tanpa mengetik sesuai dengan jenis elemen mereka (array ahanya akan diketik sebagai array bukan sebagai array int), tetapi bahkan beberapa ini tidak benar dalam bahasa yang dinamis ( abisa juga mengandung Sebuah benang).

L

  • ElementLL
  • semua simbol adalah tipe itu Element, mereka dapat menampung elemen apa punL
  • semua struktur (sekali lagi, termasuk rutinitas model) hanya menerima Elemen

Jelas bagi saya bahwa ini hanya penalti perf besar; dan saya bahkan tidak menyentuh semua konsekuensi (segudang pemeriksaan runtime dari semua jenis yang diperlukan untuk memastikan sensibilitas program) dijelaskan dengan baik dalam posting lain.

roh
sumber
+1 Sangat menarik. Sudahkah Anda membaca jawaban saya? Pemikiran Anda dan saya tampak serupa, meskipun jawaban Anda memang memberikan lebih banyak detail dan perspektif yang menarik.
Patrick87
Bahasa dinamis tidak harus di-untyped. Menerapkan model bahasa dinamis di C sangat membatasi kemungkinan optimisasi; itu membuat sangat sulit bagi kompiler untuk mengenali optimasi tingkat tinggi (misalnya data yang tidak dapat diubah), dan memaksa beberapa operasi mendasar (mis. pemanggilan fungsi) untuk melalui C. Apa yang Anda gambarkan tidak jauh dari penerjemah bytecode, dengan decode bytecode dinilai sebelumnya; kompiler asli cenderung berkinerja lebih baik, saya ragu bahwa decode bytecode dapat membenarkan perbedaannya.
Gilles 'SO- berhenti menjadi jahat'
@ Patrick87: Anda benar, garis pemikiran kami tampak sangat mirip (belum pernah membaca sebelumnya, maaf, refleksi saya berasal dari penerapan dyn lang di C saat ini).
spir
@Gilles: Saya agak setuju tentang "... tidak harus di-untyped", jika Anda maksudnya tidak diketik secara statis . Tapi ini bukan apa yang orang pikirkan tentang dyn secara umum, kurasa. Saya pribadi menganggap kedermawanan (dalam pengertian umum yang diberikan dalam jawaban di atas) fitur yang jauh lebih kuat dan jauh lebih sulit untuk hidup tanpanya. Kita dapat dengan mudah menemukan cara untuk melakukan dengan tipe statis dengan memperluas pemikiran kita tentang bagaimana tipe yang diberikan (tampaknya polimorfik) dapat didefinisikan, atau dengan memberikan lebih banyak fleksibilitas untuk instance secara langsung.
spir
1

Saya tidak punya waktu untuk membaca semua jawaban secara terperinci ... tetapi saya merasa geli.

Ada kontroversi serupa pada tahun enam puluhan dan awal tujuh puluhan (sejarah ilmu komputer sering terulang): dapatkah bahasa tingkat tinggi dikompilasi untuk menghasilkan kode seefisien kode mesin, yah, misalnya kode perakitan, diproduksi secara manual oleh seorang programmer. Semua orang tahu seorang programmer jauh lebih pintar daripada program apa pun dan dapat menghasilkan optimasi yang sangat cerdas (berpikir sebagian besar dari apa yang sekarang disebut optimasi lubang intip). Ini tentu saja ironi bagi saya.

Bahkan ada konsep perluasan kode: rasio ukuran kode yang dihasilkan oleh kompiler dengan ukuran kode untuk program yang sama yang dihasilkan oleh programmer yang baik (seolah-olah ada terlalu banyak :-). Tentu saja idenya adalah bahwa rasio ini selalu lebih besar dari 1. Bahasa pada waktu itu adalah Cobol dan Fortran 4, atau Algol 60 untuk para intelektual. Saya percaya Lisp tidak dipertimbangkan.

Yah ada beberapa rumor bahwa seseorang telah menghasilkan kompiler yang kadang-kadang bisa mendapatkan rasio ekspansi 1 ... sampai itu menjadi aturan bahwa kompilasi kode jauh lebih baik daripada kode tulisan tangan (dan lebih dapat diandalkan juga). Orang-orang khawatir tentang ukuran kode pada masa itu (kenangan kecil) tetapi hal yang sama berlaku untuk kecepatan, atau konsumsi energi. Saya tidak akan membahas alasannya.

Fitur aneh, fitur dinamis suatu bahasa tidak masalah. Yang penting adalah bagaimana mereka digunakan, apakah mereka digunakan. Kinerja, dalam unit apa pun (ukuran kode, kecepatan, energi, ...) seringkali bergantung pada bagian-bagian yang sangat kecil dari program. Oleh karena itu ada peluang bagus bahwa fasilitas yang memberikan daya ekspresif tidak akan menghalangi. Dengan praktik pemrograman yang baik, fasilitas canggih hanya digunakan dengan cara yang disiplin, untuk membayangkan struktur baru (itu adalah pelajaran pelat).

Fakta bahwa suatu bahasa tidak memiliki pengetikan statis tidak pernah berarti bahwa program yang ditulis dalam bahasa tersebut tidak diketik secara statis. Di sisi lain, mungkin jenis sistem yang digunakan suatu program belum diformalkan secara memadai untuk pemeriksa tipe yang ada sekarang.

Telah ada, dalam diskusi, beberapa referensi untuk analisis kasus terburuk ("masalah terputus-putus", pengurai PERL). Tetapi analisis kasus terburuk sebagian besar tidak relevan. Yang penting adalah apa yang terjadi dalam kebanyakan kasus atau dalam kasus yang bermanfaat ... namun didefinisikan atau dipahami atau dialami. Di sinilah cerita lain, langsung terkait dengan optimasi program. Itu terjadi sejak lama di sebuah universitas besar di Texas, antara seorang mahasiswa PhD dan penasihatnya (yang kemudian terpilih di salah satu akademi nasional). Seingat saya, siswa itu bersikeras mempelajari masalah analisis / optimisasi yang menurut penasihatnya tidak bisa diatasi. Segera mereka tidak lagi berbicara. Tetapi siswa itu benar: masalahnya cukup mudah ditemui dalam banyak kasus praktis sehingga disertasi yang ia hasilkan menjadi karya referensi.

Dan untuk berkomentar lebih jauh tentang pernyataan bahwa Perl parsing is not computable, apa pun yang dimaksud dengan kalimat itu, ada masalah yang sama dengan ML, yang merupakan bahasa yang diformalkan dengan sangat baik. Type checking complexity in ML is a double exponential in the lenght of the program.Itu adalah hasil yang sangat tepat dan formal dalam kompleksitas kasus terburuk ... yang tidak masalah sama sekali. Afaik, pengguna ML masih menunggu program praktis yang akan meledakkan pemeriksa tipe.

Dalam banyak kasus, seperti sebelumnya, waktu dan kompetensi manusia lebih langka daripada daya komputasi.

Masalah sebenarnya di masa depan adalah untuk mengembangkan bahasa kita untuk mengintegrasikan pengetahuan baru, bentuk pemrograman baru, tanpa harus menulis ulang semua perangkat lunak lama yang masih digunakan.

Jika Anda melihat matematika, itu adalah kumpulan pengetahuan yang sangat besar. Bahasa yang digunakan untuk mengekspresikannya, notasi dan konsep telah berkembang selama berabad-abad. Sangat mudah untuk menulis teorema lama dengan konsep-konsep baru. Kami mengadaptasi bukti-bukti utama, tetapi tidak repot untuk banyak hasil.

Tetapi dalam hal pemrograman, kita mungkin harus menulis ulang semua bukti dari awal (program adalah bukti). Mungkin yang kita butuhkan adalah bahasa pemrograman yang sangat tinggi dan berevolusi. Desainer pengoptimal akan senang untuk mengikuti.

babou
sumber
0

Beberapa catatan:

  • Tidak semua bahasa tingkat tinggi bersifat dinamis. Haskell adalah level yang sangat tinggi, tetapi sepenuhnya diketik secara statis. Bahkan bahasa pemrograman sistem seperti Rust, Nim, dan D dapat mengekspresikan abstraksi tingkat tinggi secara ringkas dan efisien. Bahkan, mereka bisa sekompres bahasa dinamis.

  • Kompiler terdepan yang sangat optomisasi untuk bahasa dinamis ada. Implementasi Lisp yang baik mencapai setengah kecepatan setara C.

  • Kompilasi JIT bisa menjadi kemenangan besar di sini. Firewall Aplikasi Web CloudFlare menghasilkan kode Lua yang dijalankan oleh LuaJIT. LuaJIT sangat mengoptimalkan jalur eksekusi yang sebenarnya diambil (biasanya, jalur non-serangan), dengan hasil bahwa kode berjalan jauh lebih cepat daripada kode yang dihasilkan oleh kompiler statis pada beban kerja yang sebenarnya. Tidak seperti kompiler statis dengan optimasi dipandu profil, LuaJIT beradaptasi dengan perubahan dalam jalur eksekusi saat runtime.

  • Deoptimisasi juga penting. Alih-alih kode yang dikompilasi JIT perlu memeriksa untuk kelas yang monkeypatched, tindakan monkeypatching memicu kait dalam sistem runtime yang membuang kode mesin yang bergantung pada definisi lama.

Demi
sumber
Bagaimana ini jawabannya? Nah, peluru tiga mungkin, jika Anda menambahkan referensi.
Raphael
Saya sangat skeptis terhadap klaim bahwa PGO tidak dapat menyamai kinerja LuaJIT untuk kode aplikasi web di bawah beban kerja yang khas.
Konrad Rudolph
@KonradRudolph Keuntungan utama dari JIT adalah bahwa JIT mengadaptasi kode ketika jalur yang berbeda menjadi panas.
Demi
@ Demetri saya tahu ini. Tetapi sangat sulit untuk mengukur apakah ini merupakan keuntungan - lihat jawaban saya dan diskusi komentar di sana. Singkatnya: sementara JIT dapat beradaptasi dengan perubahan dalam penggunaan, itu juga perlu melacak hal-hal saat runtime, yang menimbulkan overhead. Titik impas untuk ini adalah secara intuitif hanya di mana perubahan perilaku yang sering terjadi. Untuk aplikasi web, mungkin ada hanya satu (atau sangat sedikit) pola penggunaan yang optimasi terbayar, sehingga peningkatan kinerja minimal karena kemampuan beradaptasi tidak mengimbangi overhead dari profil yang berkelanjutan.
Konrad Rudolph