Pendekatan "CPS" telah sangat merugikan kinerja di SML / NJ; alasan yang diinginkan

11

Dalam komentar untuk Belajar F #: Buku apa yang menggunakan bahasa pemrograman lain yang dapat diterjemahkan ke F # untuk mempelajari konsep fungsional? Makarius menyatakan:

Perhatikan bahwa pendekatan "CPS" telah sangat merugikan kinerja di SML / NJ. Model evaluasi fisiknya melanggar terlalu banyak asumsi yang dibangun ke dalam perangkat keras. Jika Anda mengambil aplikasi simbolis besar SML seperti Isabelle / HOL, SML / NJ dengan CPS keluar sekitar. 100 kali lebih lambat dari Poly / ML dengan tumpukan konvensionalnya.

Adakah yang bisa menjelaskan alasannya? (Lebih disukai dengan beberapa contoh) Apakah ada ketidakcocokan impedansi di sini?

compilers functional-programming proof-assistants continuations Guy Coder
sumber
1
Pemahaman saya adalah bahwa perangkat keras mengasumsikan disiplin stack, dan dengan demikian pendekatan CPS mengambil kinerja yang baik karena tidak mematuhi asumsi ini. Tapi itu hanya pendapat saya yang kurang informasi.
Andrej Bauer

Jawaban:

9

Pada perkiraan pertama, ada perbedaan dalam "lokalitas" akses memori, ketika sebuah program hanya berjalan maju pada tumpukan dalam gaya CPS, bukannya tumbuh dan menyusut tumpukan tradisional. Perhatikan juga bahwa CPS akan selalu membutuhkan GC untuk memulihkan data Anda yang tampaknya lokal yang diletakkan di heap. Pengamatan ini saja sudah memadai 10 atau 20 tahun yang lalu, ketika perangkat keras jauh lebih sederhana dari hari ini.

Saya sendiri bukan guru perangkat keras atau kompiler, jadi sebagai perkiraan kedua, berikut adalah beberapa alasan konkret untuk kira-kira. faktor 100 terlihat pada Isabelle / HOL:

  • Kehilangan kinerja dasar menurut "perkiraan pertama" di atas.

  • Manajemen tumpukan SML / NJ dan GC memiliki masalah parah untuk skala melebihi beberapa puluh MB; Isabelle sekarang menggunakan 100-1000 MB secara rutin, terkadang beberapa GB.

  • Kompilasi SML / NJ sangat lambat - ini mungkin sama sekali tidak terkait (perhatikan bahwa Isabelle / HOL mengganti kompilasi runtime dan menjalankan kode).

  • SML / NJ tidak memiliki multithreading asli - tidak sepenuhnya tidak terkait, karena CPS diiklankan sebagai "roll utas Anda sendiri di ruang pengguna tanpa tumpukan terpisah".

Korelasi tumpukan dan utas juga dibahas dalam makalah oleh Morriset / Tolmach PPOPP 1993 "Procs and Locks: Platform Multiprocessing Portabel untuk ML Standar New Jersey" ( CiteSeerX ) Catatan: PDF di CiteSeerX mundur, halaman dari dari 10- 1 bukannya 1-10.

Makarius
sumber