Kompiler LISP / Skema kualitas untuk bersaing dengan C / C ++

8

Secara teoritis, apakah mungkin untuk memiliki kompiler Lisp / Skema yang dapat menghasilkan kode yang dapat bersaing dengan kompilasi C, katakanlah dalam margin 15-25%?

Dalam pengujian saya, saya telah menemukan bahwa tanaman kompiler saat ini (Bigloo, SBCL, Gambit, Chicken, dll) 20-50 kali lebih lambat daripada kode C yang setara .

Satu- satunya pencilan adalah kompiler Stalin . Untuk program sederhana, ia menghasilkan binari yang setara dengan C. Namun, yang saya rasa mencurigakan adalah tidak ada proyek lain (Bigloo, Chicken, Clozure, dll) yang mencoba menerapkan trik apa pun yang digunakan Stalin ("optimasi seluruh program", dll).

Saya penggemar berat LISP sejak pertengahan 90-an dan ingin membawanya ke papan sehingga tim saya dapat memutar proyek dalam waktu setengah dari biasanya menggunakan C / C ++ /. NET / etc, tapi ... kinerjanya masalah adalah penghalang besar.

Saya bertanya-tanya apakah kurangnya penyusun LISP yang berkualitas disebabkan oleh fakta bahwa tidak ada waktu dan uang yang serius telah diinvestasikan ke dalam subjek ATAU jika ini bukan tugas yang layak mengingat keadaan teknologi kompiler saat ini ??

optimization compilers pengguna6703
sumber
1
Saya percaya Anda menguji kompiler Lisp Umum dengan (declare (optimize ...)), (declare (<type> <var))dan (the <type> <expr>)dalam fungsi Anda? Kalau tidak, ini bukan perbandingan yang adil :)
Jakub Lédl
1
Saya pikir cs.stackexchange.com/questions/842/… menjawab pertanyaan ini.
Kyle Jones
@KyleJones Melakukannya? Dugaan saya adalah bahwa dengan optimalisasi maksimum, Common Lisp dapat mencapai margin yang ditentukan oleh OP, jika tidak lebih dekat.
Jakub Lédl
Mengubah bahasa pemrograman saja tidak akan membuat tim Anda mengeluarkan kode yang benar sebanyak empat kali lebih banyak dalam waktu yang bersamaan. Apa yang telah ditunjukkan oleh penelitian adalah bahwa programmer yang berpengalaman dalam bahasa tersebut menghasilkan kurang lebih jumlah baris kode yang sama per unit waktu untuk kompleksitas masalah yang diperbaiki, terlepas dari bahasa. Jadi Anda tidak akan mendapatkan apa pun kecuali di area masalah Anda, program LISP jauh lebih pendek. Satu hal yang perlu dipertimbangkan adalah Anda harus membuat orang-orang berpengalaman dalam LISP untuk pengembangan dan pemeliharaan. Dan itu jauh di antara keduanya.
vonbrand
1
Tampaknya bagi saya bahwa pertanyaan ini lebih banyak menanyakan pengalaman programmer daripada jawaban ilmiah. Karena itu, ini mungkin situs yang salah untuk pertanyaan itu.
Raphael

Jawaban:

7

Seperti disebutkan dalam komentar, tidak terlalu tepat untuk menyatakan "tanaman kompiler saat ini (Bigloo, SBCL, Gambit, Chicken, dll) 20-50 kali lebih lambat daripada kode C yang setara", tanpa kualifikasi bagaimana Anda menguji dan apa kamu diuji.

Untuk penggunaan saya , saya menemukan bahwa untuk banyak hal Gambit dan Chicken Scheme cukup dekat dengan kode 'C' yang setara dalam kecepatan, dengan versi Gambit saat ini (4.7.3) umumnya lebih cepat daripada Chicken (4.9.0.1) tetapi lebih awal Mengoptimalkankode 'C' keluaran (membuat asumsi tentang jumlah register yang tersedia - mengasumsikan x686 - dan memaksa penggunaan memori tumpukan untuk setiap persyaratan memori tambahan, yang keputusannya harus diserahkan kepada kompiler 'C' seperti halnya Chicken, yang seringkali menghilangkan persyaratan untuk register tambahan dan menggabungkan langkah-langkah pemrosesan) untuk mencegah kompiler 'C' melakukan optimasi sendiri menghasilkan loop kecil sangat ketat hingga sekitar dua kali lebih lambat dari loop kecil ketat yang sama di 'C' (atau Ayam ); Ayam hanya mendefinisikan banyak variabel lokal ke fungsi yang diberikan sesuai keinginan (sebagian besar digunakan secara tidak langsung) dan kemudian tergantung pada kompiler untuk mengoptimalkan sebagian besar dari mereka yang jauh. Ayam tidak

EDIT_ADD: Saya telah melakukan penelitian lebih lanjut tentang versi Skema Ayam dan Gambit-C dan telah menemukan yang berikut:

  1. Ayam lebih cepat daripada Gambit untuk loop ketat kecil karena alasan di atas (lebih tergantung pada kompiler 'C' untuk optimasi tanpa melakukan sebanyak itu sendiri dan dengan demikian mengambil keuntungan lebih baik dari register tambahan x86-64), tetapi juga karena itu tidak termasuk pemeriksaan pemeliharaan tumpukan "POLL" di dalam loop, sedangkan Gambit menyertakan pemeriksaan "POLL" di dalam loop. Bahkan ketika ini tidak dipicu (kasus biasa), akan diperlukan beberapa siklus jam CPU untuk menentukan bahwa tidak ada yang diperlukan (sekitar 6 siklus). Kompiler yang lebih pintar di masa depan mungkin melihat bahwa tidak perlu melakukan pemeriksaan tumpukan ketika berada di dalam loop ketat dan tidak melakukan operasi pembuatan tumpukan, melakukannya hanya sebelum atau setelah loop dan menghemat waktu ini.

  2. Makro 'C' Gambit melakukan terlalu banyak pekerjaan, seperti yang dikatakan, dalam mendefinisikan secara tepat bagaimana operasi harus dilakukan, terutama termasuk operasi ukuran tumpukan tetap, dan ini kemungkinan lebih sulit untuk dioptimalkan oleh kompiler 'C'; menggunakan register secara lebih efektif dapat mengurangi waktu putaran ketat mungkin 4 siklus, yang dikombinasikan dengan yang di atas akan memasukkannya ke dalam Chicken Ballpark.

  3. Baik output "baca / modifikasi / tulis" optimisasi untuk mengatakan operasi vektor yang memodifikasi di tempat dan jangan output kode sehingga kompiler melakukannya. Backend yang lebih cerdas seperti LLVM saat digunakan dengan Haskell melakukan hal semacam ini. Ini akan mengurangi penggunaan register oleh satu dan waktu pelaksanaan dalam menggunakan hanya satu instruksi daripada membaca terpisah, perhitungan modifikasi, dan menulis ke lokasi yang sama; ini akan menjadi hanya perhitungan modifikasi (katakan sedikit atau), dan kemudian baca modifikasi (| =) tulis instruksi tunggal. Ini mungkin membuat kecepatan lebih cepat dengan satu siklus atau lebih

  4. Keduanya diketik secara dinamis dan memproses data "tag" bit sebagai bagian dari data mereka. Tidak ada yang cukup pintar untuk loop ketat untuk mengurangi tag, melakukan loop "tag-less", kemudian menambahkan tag kembali untuk setiap hasil dari loop, juga tidak menghasilkan kode di mana kompiler 'C' dapat melihat untuk melakukan ini walaupun itu menggabungkan operasi ini untuk beberapa kasus. Optimalisasi di sini dapat mengurangi waktu loop oleh beberapa siklus CPU atau lebih, tergantung pada loop.

  5. Loop 'C' yang sangat ketat dapat memakan waktu sekitar 3,5 siklus clock CPU per loop pada CPU yang cepat yang kecepatan akses cache memory tidak dibatasi (seperti AMD Bulldozer, yang sekitar dua kali lebih lambat); loop yang sama di Chicken saat ini membutuhkan waktu sekitar 6 siklus dan Gambit membutuhkan sekitar 16,9 siklus. Dengan semua optimasi seperti di atas, tidak ada alasan bahwa implementasi Skema ini tidak dapat melakukan itu, namun beberapa pekerjaan diperlukan:

  6. Dalam kasus Gambit, pekerjaan yang lebih sulit mungkin adalah meningkatkan analisis aliran untuk mengenali ketika tidak ada tes "POLL" yang perlu dimasukkan (mis. Bisakah ini didorong oleh interupsi, meskipun kompiler memungkinkan interupsi dimatikan untuk beberapa penggunaan? ); perbaikan yang lebih mudah adalah dengan hanya menerapkan penggunaan register yang lebih baik (mis. mengenali register x86-64 lebih baik daripada arsitektur x686 default). Untuk keduanya, analisis aliran yang lebih baik untuk mengenali bahwa mereka dapat "membatalkan" data, terutama "fixnum", "flonum", dan vektor, data sehingga operasi ini tidak diperlukan di dalam loop ketat dan menggabungkan instruksi baca / modifikasi / tulis. Kedua tujuan ini dapat dicapai dengan menggunakan backend yang lebih baik seperti LLVM (bukan jumlah pekerjaan sepele, tetapi keduanya sudah sebagian ada di sana).

Kesimpulan: Ayam saat ini sekitar 50% lebih lambat dari 'C' pada CPU tercepat (bukan Bulldozer saya, di mana kecepatannya hampir sama karena pembatasan cache kode 'C') dan Gambit sekitar 400% lebih lambat (hanya sekitar 125% lebih lambat pada Bulldozer saya yang lambat). Namun, perbaikan di masa depan untuk kompiler dapat mengurangi ini sehingga salah satu kode tidak lebih lambat dari 'C' atau dalam margin yang ditentukan OP.

Bahasa yang lebih kompleks seperti Haskell, ketika menggunakan backend LLVM, memperhatikan dengan seksama penggunaan yang ketat (bukan masalah dengan skema yang selalu ingin secara default), dan menggunakan struktur data yang sesuai (ST array tanpa kotak daripada daftar untuk loop ketat; agak berlaku untuk Skema menggunakan vektor), berjalan pada kecepatan yang sama seperti 'C' jika backend LLVM digunakan dengan optimisasi penuh. Jika dapat melakukan ini, begitu juga Skema dengan peningkatan kompiler di atas.

LAGI, tidak ada cara yang salah satu dari ini adalah 20 sampai 50 kali lebih lambat bila digunakan dengan flag optimasi yang tepat. END_EDIT_ADD

Tentu saja, semua tolok ukur tidak valid jika seseorang tidak menggunakan pengaturan optimasi yang sesuai untuk masing-masing seperti yang akan dilakukan dalam lingkungan produksi ...

Saya akan berpikir bahwa kompiler Chez Scheme komersial akan berada di stadion baseball untuk menghasilkan output kinerja tinggi seperti halnya Gambit dan Chicken, sebagai komersial itu pasti memiliki "waktu dan uang yang serius diinvestasikan ke dalamnya".

Satu-satunya cara saya dapat membuat Gambit atau Chicken berjalan selambatnya "20 hingga 50 kali lebih lambat dari 'C'" adalah dengan tidak menggunakan pengaturan pengoptimalan, dalam hal ini mereka sering tidak berjalan lebih cepat daripada yang ditafsirkan dalam REPL mereka - 10 kali lebih lambat daripada menggunakan pengaturan itu dengan benar.

Apakah mungkin OP belum diuji menggunakan pengaturan ini dengan benar?

Jika OP ingin memperjelas prosedur pengujiannya, saya dengan senang hati akan mengedit jawaban ini untuk menunjukkan bahwa setidaknya Gambit dan Chicken tidak harus selambat itu.

GordonBGood
sumber
Apakah ini dengan pemeriksaan jenis runtime dinonaktifkan? Saya tidak ingin melakukan itu dalam produksi, karena membuat bug dieksploitasi yang sebelumnya tidak.
Demi
@ Demetri, dengan sebagian besar penyusun Skema seperti Gambit-C, Chicken, atau Bigloo, seseorang mendapat kecepatan tiga kali lipat untuk banyak tolok ukur dengan menonaktifkan semua pemeriksaan runtime, tetapi kode tersebut masih tidak "20 hingga 50 kali lebih lambat" seperti yang dinyatakan oleh pertanyaan OP. Bahkan, banyak dari pemeriksaan ini dapat dinonaktifkan dengan aman dalam kode produksi setelah memeriksa masalah dalam debugging tanpa risiko dengan menulis kode sehingga pemeriksaan semacam itu hanya ada di dalam kode hanya jika diperlukan.
GordonBGood
@ Demetri Saya bisa membuktikan skema ayam berada di stadion baseball 1,5-2,5x lebih lambat dari C untuk kode benchmark, jika dikompilasi dengan optimisasi. Tapi ya itu sangat lambat jika dikompilasi tanpa optimasi. FWIW Saya mendapatkan hasil terbaik dari menggunakan fixnum-ops, objek unboxed dan memungkinkan kompilasi blok, yaitu analisis statis yang lebih baik yang mengarah ke optimasi yang lebih baik.
Morten Jensen
Saya lebih khawatir tentang pemeriksaan keamanan runtime - Saya tidak ingin bug yang tidak muncul dalam pengujian menjadi buffer overflow yang dapat dieksploitasi. Jelas seseorang akan mengaktifkan optimisasi.
Demi
@ Demetri bisa dimengerti. Pengalaman saya adalah bahwa overhead runtime-cek sangat tergantung pada jenis kode yang Anda tulis. Terkadang biaya overhead lebih dari 10 kali lipat berjalan tanpa pemeriksaan dalam pengujian saya.
Morten Jensen