Mengapa Haskell (GHC) begitu cepat?

246

Haskell (dengan GHCkompiler) jauh lebih cepat dari yang Anda harapkan . Digunakan dengan benar, ini bisa mendekati bahasa tingkat rendah. (Hal favorit yang harus dilakukan Haskellers adalah mencoba dan mendapatkan dalam 5% dari C (atau bahkan mengalahkannya, tetapi itu berarti Anda menggunakan program C yang tidak efisien, karena GHC mengkompilasi Haskell ke C).) Pertanyaan saya adalah, mengapa?

Haskell bersifat deklaratif dan berdasarkan pada kalkulus lambda. Arsitektur mesin jelas sangat penting, didasarkan pada mesin turing, secara kasar. Memang, Haskell bahkan tidak memiliki urutan evaluasi khusus. Selain itu, alih-alih berurusan dengan tipe data mesin, Anda membuat tipe data aljabar setiap saat.

Yang paling aneh dari semuanya adalah fungsi urutan yang lebih tinggi. Anda akan berpikir bahwa membuat fungsi dengan cepat, dan melemparkannya, akan membuat program lebih lambat. Tetapi menggunakan fungsi tingkat tinggi sebenarnya membuat Haskell lebih cepat. Memang, tampaknya, untuk mengoptimalkan kode Haskell, Anda perlu membuatnya lebih elegan dan abstrak daripada lebih seperti mesin. Tak satu pun dari fitur Haskell yang lebih canggih tampaknya bahkan memengaruhi kinerjanya, jika mereka tidak memperbaikinya.

Maaf jika ini terdengar ranty, tetapi inilah pertanyaan saya: Mengapa Haskell (dikompilasi dengan GHC) begitu cepat, mengingat sifat abstrak dan perbedaan dari mesin fisik?

Catatan: Alasan saya mengatakan C dan bahasa imperatif lainnya agak mirip dengan Mesin Turing (tetapi tidak sejauh Haskell mirip dengan Lambda Calculus) adalah bahwa dalam bahasa imperatif, Anda memiliki sejumlah negara terbatas (alias nomor baris) , bersama dengan Tape (ram), sehingga negara dan rekaman saat ini menentukan apa yang harus dilakukan untuk rekaman itu. Lihat entri Wikipedia, setara mesin Turing , untuk transisi dari Mesin Turing ke komputer.

PyRulez
sumber
27
"Karena GHC mengkompilasi Haskell ke C" - tidak. GHC memiliki banyak backend. Yang tertua (tetapi bukan yang default) adalah generator C. Itu menghasilkan kode Cmm untuk IR, tapi itu bukan "kompilasi ke C" yang biasanya Anda harapkan. ( downloads.haskell.org/~ghc/latest/docs/html/users_guide/… )
viraptor
19
Saya sangat merekomendasikan membaca Implementasi Bahasa Pemrograman Fungsional oleh Simon Payton Jones (pelaksana utama GHC) itu akan menjawab banyak pertanyaan Anda.
Joe Hillenbrand
94
Mengapa? 25 tahun kerja keras.
Agustus
31
"Meskipun mungkin ada jawaban faktual untuk itu, itu tidak akan melakukan apa-apa selain mengumpulkan pendapat." - Ini adalah alasan terburuk untuk menutup pertanyaan. Karena mungkin memiliki jawaban yang baik, tetapi berpotensi juga menarik yang berkualitas rendah. Huek! Kebetulan saya memiliki jawaban yang baik, historis, faktual tentang penelitian akademis dan ketika perkembangan tertentu terjadi. Tetapi saya tidak dapat mempostingnya karena orang khawatir pertanyaan ini juga dapat menarik jawaban berkualitas rendah. Sekali lagi, huek.
sclv
7
@cimmanon Saya akan membutuhkan satu bulan atau beberapa posting blog untuk mempelajari dasar-dasar detail bagaimana sebuah kompiler fungsional bekerja. Saya hanya perlu jawaban SO untuk membuat sketsa secara garis besar bagaimana mesin grafik dapat diimplementasikan dengan bersih pada perangkat keras stok dan arahkan ke sumber yang relevan untuk membaca lebih lanjut ...
sclv

Jawaban:

264

Saya setuju dengan Dietrich Epp: kombinasi dari beberapa hal yang membuat GHC cepat.

Pertama dan terpenting, Haskell sangat tingkat tinggi. Ini memungkinkan kompiler melakukan optimisasi agresif tanpa melanggar kode Anda.

Pikirkan tentang SQL. Sekarang, ketika saya menulis SELECTpernyataan, itu mungkin terlihat seperti loop keharusan, tetapi tidak . Ini mungkin terlihat seperti loop di semua baris dalam tabel itu mencoba untuk menemukan satu yang cocok dengan kondisi yang ditentukan, tetapi sebenarnya "kompiler" (mesin DB) dapat melakukan pencarian indeks sebagai gantinya - yang memiliki karakteristik kinerja yang sama sekali berbeda. Tetapi karena SQL sangat tingkat tinggi, "kompiler" dapat menggantikan algoritma yang sama sekali berbeda, menerapkan beberapa prosesor atau saluran I / O atau seluruh server secara transparan, dan banyak lagi.

Saya menganggap Haskell sama. Anda mungkin berpikir Anda baru saja meminta Haskell untuk memetakan daftar input ke daftar kedua, memfilter daftar kedua ke daftar ketiga, dan kemudian menghitung berapa banyak item yang dihasilkan. Tetapi Anda tidak melihat GHC menerapkan aturan penulisan ulang aliran-fusi di belakang layar, mengubah semuanya menjadi satu loop kode mesin ketat yang melakukan seluruh pekerjaan dalam sekali melewati data tanpa alokasi - jenis hal yang akan menjadi membosankan, rawan kesalahan dan tidak dapat dipertahankan untuk menulis dengan tangan. Itu hanya sangat mungkin karena kurangnya detail level rendah dalam kode.

Cara lain untuk melihatnya mungkin ... mengapa Haskell tidak boleh cepat? Apa fungsinya yang membuatnya lambat?

Ini bukan bahasa yang ditafsirkan seperti Perl atau JavaScript. Ini bahkan bukan sistem mesin virtual seperti Java atau C #. Ini mengkompilasi sampai ke kode mesin asli, jadi tidak ada overhead di sana.

Tidak seperti bahasa OO [Java, C #, JavaScript ...], Haskell memiliki penghapusan tipe penuh [seperti C, C ++, Pascal ...]. Semua pemeriksaan tipe hanya terjadi pada waktu kompilasi. Jadi tidak ada pemeriksaan run-time untuk memperlambat Anda. (Tidak ada pemeriksaan null-pointer, dalam hal ini. Dalam, katakanlah, Java, JVM harus memeriksa pointer nol dan melemparkan pengecualian jika Anda menghormati satu. Haskell tidak perlu repot dengan pemeriksaan itu.)

Anda mengatakan itu terdengar lambat untuk "membuat fungsi dengan cepat pada saat run-time", tetapi jika Anda melihat dengan sangat hati-hati, Anda sebenarnya tidak melakukannya. Mungkin terlihat seperti yang Anda lakukan, tetapi Anda tidak melakukannya. Jika Anda berkata (+5), yah, itu kode-keras ke dalam kode sumber Anda. Itu tidak dapat berubah pada saat run-time. Jadi sebenarnya bukan fungsi yang dinamis. Bahkan fungsi kari benar-benar hanya menyimpan parameter ke dalam blok data. Semua kode yang dapat dieksekusi benar-benar ada pada waktu kompilasi; tidak ada interpretasi run-time. (Tidak seperti beberapa bahasa lain yang memiliki "fungsi eval".)

Pikirkan tentang Pascal. Ini sudah tua dan tidak ada yang benar-benar menggunakannya lagi, tetapi tidak ada yang akan mengeluh bahwa Pascal lambat . Ada banyak hal yang tidak disukai tentang hal itu, tetapi kelambatan sebenarnya bukan salah satunya. Haskell tidak benar-benar melakukan banyak hal yang berbeda dengan Pascal, selain memiliki pengumpulan sampah daripada manajemen memori manual. Dan data yang tidak dapat diubah memungkinkan beberapa optimisasi ke mesin GC [yang kemudian sedikit evaluasi rumit].

Saya pikir masalahnya adalah bahwa Haskell terlihat canggih dan canggih dan tingkat tinggi, dan semua orang berpikir "oh wow, ini benar-benar kuat, pasti sangat lambat! " Tetapi tidak. Atau setidaknya, itu tidak seperti yang Anda harapkan. Ya, ini memiliki sistem tipe yang menakjubkan. Tapi tahukah Anda? Itu semua terjadi pada waktu kompilasi. Dengan run-time, itu hilang. Ya, ini memungkinkan Anda membuat ADT yang rumit dengan sebaris kode. Tapi tahukah Anda? Sebuah ADT hanya C biasa polos uniondari structs. Tidak ada lagi.

Pembunuh sebenarnya adalah evaluasi malas. Ketika Anda mendapatkan keketatan / kemalasan kode Anda dengan benar, Anda dapat menulis kode cepat bodoh yang masih elegan dan indah. Tetapi jika Anda salah melakukan hal ini, program Anda berjalan ribuan kali lebih lambat , dan itu benar-benar tidak jelas mengapa ini terjadi.

Sebagai contoh, saya menulis sebuah program kecil yang sepele untuk menghitung berapa kali setiap byte muncul dalam sebuah file. Untuk file input 25KB, program membutuhkan waktu 20 menit untuk menjalankan dan menelan 6 gigabytes RAM! Itu tidak masuk akal !! Tapi kemudian saya menyadari apa masalahnya, menambahkan satu pola bang, dan waktu tayang turun menjadi 0,02 detik .

Ini adalah tempat Haskell pergi tiba-tiba perlahan-lahan. Dan tentu saja butuh waktu untuk terbiasa. Namun seiring waktu, semakin mudah untuk menulis kode yang sangat cepat.

Apa yang membuat Haskell begitu cepat? Kemurnian. Jenis statis. Kemalasan. Tetapi di atas semua itu, karena kompiler tingkat tinggi yang cukup dapat secara radikal mengubah implementasi tanpa melanggar harapan kode Anda.

Tapi saya kira itu hanya pendapat saya ...

Matematika Matematika
sumber
13
@immanon Saya tidak berpikir itu murni berdasarkan opini. Ini pertanyaan menarik yang mungkin orang lain inginkan jawabannya. Tapi saya kira kita akan melihat apa yang dipikirkan pemilih lain.
MathematicalOrchid
8
@immanon - bahwa pencarian hanya memberikan satu setengah utas, dan semuanya harus dilakukan dengan audit ulasan. dan jawaban terangkat ke utas mengatakan "tolong hentikan moderasi hal-hal yang tidak Anda mengerti." Saya akan menyarankan bahwa jika seseorang berpikir jawaban untuk ini terlalu luas maka mereka akan terkejut dan menikmati jawabannya, karena jawabannya tidak terlalu luas.
sclv
34
"Dalam, katakanlah, Java, JVM harus memeriksa pointer nol dan melemparkan pengecualian jika Anda menghormati satu." Pemeriksaan nol implisit Java (sebagian besar) tidak berbayar. Implementasi Java dapat dan memanfaatkan memori virtual untuk memetakan alamat null ke halaman yang hilang, jadi penereferensi pointer nol memicu kesalahan halaman di tingkat CPU, yang ditangkap dan dilempar Java sebagai pengecualian tingkat tinggi. Jadi sebagian besar pemeriksaan nol dilakukan oleh unit pemetaan memori di CPU, gratis.
Boann
4
@cimmanon: Mungkin itu karena pengguna Haskell tampaknya menjadi satu-satunya komunitas yang sebenarnya adalah sekelompok orang ramah yang berpikiran terbuka ... yang Anda anggap sebagai "lelucon" ..., alih-alih komunitas anjing pemakan-anjing dari pemerintahan Nazi yang saling merobek yang baru di setiap kesempatan yang mereka dapatkan ... yang tampaknya menjadi apa yang Anda anggap "normal".
Evi1M4chine
14
@MathematicalOrchid: apakah Anda memiliki salinan program asli Anda yang membutuhkan waktu 20 menit untuk dijalankan? Saya pikir akan cukup instruktif untuk mempelajari mengapa ini sangat lambat.
George
79

Untuk waktu yang lama dianggap bahwa bahasa fungsional tidak bisa cepat - dan terutama bahasa fungsional yang malas. Tapi ini karena implementasi awal mereka, pada dasarnya, ditafsirkan dan tidak benar-benar dikompilasi.

Gelombang desain kedua muncul berdasarkan pengurangan grafik, dan membuka kemungkinan untuk kompilasi yang jauh lebih efisien. Simon Peyton Jones menulis tentang penelitian ini dalam dua bukunya , Implementasi Bahasa Pemrograman Fungsional dan Mengimplementasikan bahasa fungsional: tutorial (sebelumnya dengan bagian oleh Wadler dan Hancock, dan yang terakhir ditulis dengan David Lester). (Lennart Augustsson juga memberi tahu saya bahwa salah satu motivasi utama untuk buku terdahulu adalah menggambarkan cara kompiler LML-nya, yang tidak banyak dikomentari, menyelesaikan kompilasi).

Gagasan utama di balik pendekatan pengurangan grafik seperti yang dijelaskan dalam karya-karya ini adalah bahwa kita tidak menganggap program sebagai urutan instruksi, tetapi grafik ketergantungan yang dievaluasi melalui serangkaian pengurangan lokal. Wawasan kunci kedua adalah evaluasi grafik seperti itu tidak perlu ditafsirkan tetapi sebaliknya grafik itu sendiri dapat dibangun dari kode . Secara khusus, kita dapat merepresentasikan simpul dari grafik bukan sebagai "nilai atau 'opcode' dan nilai untuk beroperasi" tetapi sebagai fungsi yang ketika dipanggil, mengembalikan nilai yang diinginkan. Pertama kali dipanggil, ia meminta subnode untuk nilai-nilai mereka dan kemudian beroperasi pada mereka, dan kemudian menimpa dirinya sendiri dengan instruksi baru yang hanya mengatakan "kembalikan hasilnya.

Ini dijelaskan dalam makalah selanjutnya yang menjabarkan dasar-dasar bagaimana GHC masih bekerja hari ini (meskipun modulo banyak berbagai tweak): "Menerapkan Bahasa Fungsional Malas pada Perangkat Keras Stok: Mesin G-Tag Tanpa Spineless." . Model eksekusi GHC saat ini didokumentasikan secara lebih rinci di GHC Wiki .

Jadi wawasannya adalah perbedaan ketat dari "data" dan "kode" yang kami anggap "mendasar" untuk bagaimana mesin bekerja bukanlah bagaimana mereka harus bekerja, tetapi dipaksakan oleh kompiler kami. Jadi kita dapat membuangnya, dan memiliki kode (kompiler) yang menghasilkan kode modifikasi sendiri (yang dapat dieksekusi) dan semuanya dapat bekerja dengan cukup baik.

Dengan demikian ternyata bahwa sementara arsitektur mesin sangat penting dalam arti tertentu, bahasa dapat memetakan kepada mereka dengan cara yang sangat mengejutkan yang tidak terlihat seperti kontrol aliran gaya-C konvensional, dan jika kita berpikir tingkat rendah cukup, ini mungkin juga efisien.

Di atas semua ini ada banyak optimisasi lain yang dibuka oleh kemurnian pada khususnya, karena memungkinkan transformasi yang lebih besar "aman". Kapan dan bagaimana menerapkan transformasi ini sedemikian rupa sehingga mereka membuat segalanya lebih baik dan tidak lebih buruk tentu saja merupakan pertanyaan empiris, dan mengenai ini dan banyak pilihan kecil lainnya, bertahun-tahun kerja telah dimasukkan ke dalam pekerjaan teoretis dan pembandingan praktis. Jadi ini tentu saja memainkan peran juga. Sebuah makalah yang memberikan contoh yang baik dari jenis penelitian ini adalah " Membuat Kari Cepat: Dorong / Masuk vs. Eval / Terapkan untuk Bahasa Tingkat Tinggi."

Akhirnya, perlu dicatat bahwa model ini masih memperkenalkan overhead karena tipuan. Ini dapat dihindari dalam kasus-kasus di mana kita tahu bahwa "aman" untuk melakukan hal-hal secara ketat dan karenanya menghilangkan tipuan grafik. Mekanisme yang menyimpulkan keketatan / permintaan sekali lagi didokumentasikan dalam beberapa detail di GHC Wiki .

sclv
sumber
2
Tautan penganalisa permintaan sepadan dengan bobotnya dalam emas! Akhirnya sesuatu tentang topik yang tidak bertindak seolah-olah pada dasarnya adalah ilmu hitam yang tidak dapat dijelaskan. Bagaimana saya tidak pernah mendengar ini ?? Itu harus dihubungkan dari mana-mana di mana ada yang bertanya bagaimana mengatasi masalah dengan kemalasan!
Evi1M4chine
@ Evi1M4chine Saya tidak melihat tautan yang terkait dengan penganalisa permintaan, mungkin entah bagaimana telah hilang. Dapatkah seseorang mengembalikan tautan atau memperjelas referensi? Kedengarannya cukup menarik.
Cris P
1
@ CrisP Saya yakin tautan terakhir adalah yang dimaksud. Ia pergi ke halaman di Wiki GHC tentang penganalisa permintaan di GHC.
Serp C
@Serpentine Cougar, Chris P: Yap, Itu yang saya maksud.
Evi1M4chine
19

Ada banyak yang perlu dikomentari di sini. Saya akan mencoba menjawab sebanyak yang saya bisa.

Digunakan dengan benar, ini bisa mendekati bahasa tingkat rendah.

Dalam pengalaman saya, biasanya memungkinkan untuk mendapatkan 2x kinerja Rust dalam banyak kasus. Tetapi ada juga beberapa kasus penggunaan (luas) di mana kinerjanya buruk dibandingkan dengan bahasa tingkat rendah.

atau bahkan mengalahkannya, tetapi itu berarti Anda menggunakan program C yang tidak efisien, karena GHC mengkompilasi Haskell ke C)

Itu tidak sepenuhnya benar. Haskell mengkompilasi ke C-- (subset dari C), yang kemudian dikompilasi melalui generator kode asli ke assembly. Pembuat kode asli biasanya menghasilkan kode lebih cepat daripada kompiler C, karena ia dapat menerapkan beberapa optimasi yang tidak bisa dilakukan oleh kompiler C biasa.

Arsitektur mesin jelas sangat penting, didasarkan pada mesin turing, secara kasar.

Itu bukan cara yang baik untuk memikirkannya, terutama karena prosesor modern akan mengevaluasi instruksi yang salah dan mungkin pada saat yang sama.

Memang, Haskell bahkan tidak memiliki urutan evaluasi khusus.

Sebenarnya, Haskell melakukannya secara implisit mendefinisikan perintah evaluasi.

Selain itu, alih-alih berurusan dengan tipe data mesin, Anda membuat tipe data aljabar setiap saat.

Mereka bersesuaian dalam banyak kasus, asalkan Anda memiliki kompiler yang cukup canggih.

Anda akan berpikir bahwa membuat fungsi dengan cepat, dan melemparkannya, akan membuat program lebih lambat.

Haskell dikompilasi, dan fungsi tingkat tinggi sebenarnya tidak dibuat dengan cepat.

tampaknya untuk mengoptimalkan kode Haskell, Anda harus membuatnya lebih elegan dan abstrak, bukan lebih seperti mesin.

Secara umum, membuat kode lebih "seperti mesin" adalah cara yang tidak produktif untuk mendapatkan kinerja yang lebih baik di Haskell. Tetapi membuatnya lebih abstrak tidak selalu merupakan ide yang baik juga. Apa yang merupakan ide yang baik adalah menggunakan struktur data umum dan fungsi yang telah sangat dioptimalkan (seperti daftar tertaut).

f x = [x]dan f = purehal yang persis sama di Haskell, misalnya. Kompiler yang baik tidak akan menghasilkan kinerja yang lebih baik dalam kasus sebelumnya.

Mengapa Haskell (dikompilasi dengan GHC) begitu cepat, mengingat sifat abstrak dan perbedaan dari mesin fisik?

Jawaban singkatnya adalah "karena dirancang untuk melakukan hal itu." GHC menggunakan mesin tagless g-spinless (STG). Anda dapat membaca makalah tentang itu di sini (ini cukup rumit). GHC melakukan banyak hal lain juga, seperti analisis ketat dan evaluasi optimis .

Alasan saya mengatakan C dan bahasa imperatif lainnya agak mirip dengan Mesin Turing (tetapi tidak sejauh Haskell mirip dengan Lambda Calculus) adalah bahwa dalam bahasa imperatif, Anda memiliki sejumlah negara terbatas (alias nomor baris), bersama dengan selotip (ram), sehingga negara dan pita saat ini menentukan apa yang harus dilakukan terhadap selotip.

Apakah titik kebingungan kemudian bahwa mutabilitas harus mengarah pada kode yang lebih lambat? Kemalasan Haskell sebenarnya berarti bahwa kemampuan berubah tidak penting sebanyak yang Anda pikirkan, ditambah tingkat tinggi sehingga ada banyak optimisasi yang dapat diterapkan oleh kompiler. Dengan demikian, memodifikasi catatan di tempat jarang akan lebih lambat daripada dalam bahasa seperti C.


sumber
3

Mengapa Haskell (GHC) begitu cepat?

Sesuatu pasti telah berubah secara dramatis sejak saya terakhir mengukur kinerja Haskell. Sebagai contoh:

  • Sebuah pemrosesan file RRD patokan mana penulis menemukan bahwa Haskell membutuhkan waktu lebih lama untuk mengembangkan dan berjalan lebih lambat (1,020s) dari Go (130) dan OCaml (67s), yaitu 15x lebih lambat dari OCaml.
  • Sebuah patokan kamus sederhana menunjukkan Haskell berjalan ~ 10x lebih lambat dari F #.
  • The Ray Tracer Bahasa Perbandingan adalah contoh lain di mana Haskell lebih lambat dari C ++, OCaml dan bahkan Jawa dan Lisp.
  • Sebuah quicksort generik paralel di Haskell adalah 55% lebih lambat dari F # dan memerlukan kode substansial lebih.

Jadi apa yang telah berubah? Saya perhatikan daripada pertanyaan atau jawaban yang sekarang merujuk pada tolok ukur yang dapat diverifikasi atau bahkan kode.

Hal favorit yang harus dilakukan Haskellers adalah mencoba dan mendapatkan dalam 5% dari C

Apakah Anda memiliki referensi untuk hasil yang dapat diverifikasi di mana ada orang yang mendekati itu?

Jon Harrop
sumber
6
Apakah seseorang mengatakan nama Harrop di depan cermin tiga kali lagi?
Chuck Adams
2
tidak 10x, tapi tetap saja, seluruh entri ini adalah hype dan babat pemasaran. GHC memang cukup mampu mendekati C atau bahkan kadang-kadang mengatasinya, dalam hal kecepatan, tetapi yang biasanya membutuhkan gaya pemrograman tingkat rendah yang terlibat tidak jauh berbeda dengan pemrograman dalam C itu sendiri. sayangnya. semakin tinggi level kode, biasanya semakin lambat. kebocoran ruang, tipe ADT yang nyaman namun berkinerja buruk ( aljabar , tidak abstrak , seperti yang dijanjikan), dll, dll.
Will Ness
1
Saya hanya memposting ini karena saya melihatnya hari ini chrispenner.ca/posts/wc . Ini merupakan implementasi dari utilitas wc yang ditulis dalam Haskell yang seharusnya mengalahkan versi c.
Garrison
3
@ Garrison terima kasih atas tautannya . 80 baris adalah apa yang saya sebut "gaya pemrograman tingkat rendah tidak jauh berbeda dari pemrograman dalam C itu sendiri." . "kode tingkat yang lebih tinggi", itu akan menjadi "bodoh" fmap (length &&& length . words &&& length . lines) readFile. Jika yang lebih cepat dari (atau bahkan sebanding dengan) C, hype di sini akan benar-benar dibenarkan kemudian . Kita masih harus bekerja keras untuk kecepatan di Haskell seperti di C, intinya.
Will Ness
2
Dilihat oleh diskusi ini di Reddit reddit.com/r/programming/comments/dj4if3/… bahwa kode Haskell benar-benar buggy (misal, garis putus-putus mulai atau berakhir dengan spasi putih, break pada à) dan yang lain tidak dapat mereproduksi hasil kinerja yang diklaim.
Jon Harrop