Apakah pemrograman fungsional lebih cepat dalam multithreading karena saya menulis sesuatu secara berbeda atau karena berbagai hal dikompilasi secara berbeda?

63

Saya terjun ke dunia pemrograman fungsional dan saya terus membaca di mana-mana bahwa bahasa fungsional lebih baik untuk program multithreading / multicore. Saya mengerti bagaimana bahasa fungsional melakukan banyak hal secara berbeda, seperti rekursi , angka acak , dll. Tetapi saya tidak dapat menemukan apakah multithreading lebih cepat dalam bahasa fungsional karena dikompilasi secara berbeda atau karena saya menulisnya secara berbeda.

Sebagai contoh, saya telah menulis sebuah program di Jawa yang mengimplementasikan protokol tertentu. Dalam protokol ini, kedua pihak saling mengirim dan menerima satu sama lain ribuan pesan, mereka mengenkripsi pesan-pesan itu dan mengirim ulang (dan menerimanya) berulang-ulang. Seperti yang diharapkan, multithreading adalah kunci ketika Anda berurusan dengan skala ribuan. Dalam program ini tidak ada penguncian yang terlibat .

Jika saya menulis program yang sama di Scala (yang menggunakan JVM), apakah implementasi ini akan lebih cepat? Jika ya, mengapa? Apakah karena gaya penulisan? Jika ini karena gaya penulisan, sekarang Jawa termasuk ekspresi lambda, tidak bisa saya mencapai hasil yang sama dengan menggunakan Java dengan lambda? Atau lebih cepat karena Scala akan mengkompilasi berbagai hal secara berbeda?

java functional-programming scala Aventinus
sumber
64
Pemrograman fungsional afaik tidak membuat multithreading lebih cepat. Itu membuat multithreading lebih mudah untuk diimplementasikan dan lebih aman karena ada beberapa fitur pemrograman fungsional seperti ketidakmampuan dan fungsi tidak memiliki efek samping yang membantu dalam hal ini.
Pieter B
7
Perhatikan bahwa 1) lebih baik tidak benar-benar didefinisikan 2) itu pasti tidak didefinisikan hanya sebagai "lebih cepat". Bahasa X yang membutuhkan satu miliar kali ukuran kode untuk kinerja gain 0,1% sehubungan dengan Y tidak lebih baik daripada Y untuk setiap definisi masuk akal yang lebih baik.
Bakuriu
2
Apakah Anda bermaksud bertanya tentang "pemrograman fungsional" atau "program yang ditulis dengan gaya fungsional"? Seringkali pemrograman yang lebih cepat tidak menghasilkan program yang lebih cepat.
Ben Voigt
1
Jangan lupa selalu ada GC yang harus berjalan di latar belakang dan mengikuti tuntutan alokasi Anda ... dan saya tidak yakin itu multithreaded ...
Mehrdad
4
Jawaban paling sederhana di sini adalah: pemrograman fungsional memungkinkan program menulis yang akan mempertimbangkan lebih sedikit masalah kondisi ras, namun itu tidak berarti bahwa program yang ditulis dengan gaya imperatif akan lebih lambat.
Dawid Pura

Jawaban:

97

Alasan orang mengatakan bahasa fungsional lebih baik untuk pemrosesan paralel adalah karena fakta bahwa mereka biasanya menghindari keadaan yang bisa berubah. Keadaan yang bisa berubah adalah "akar dari segala kejahatan" dalam konteks pemrosesan paralel; mereka membuatnya sangat mudah untuk mengalami kondisi lomba ketika mereka dibagi di antara proses bersamaan. Solusi untuk kondisi balapan kemudian melibatkan mekanisme penguncian dan sinkronisasi, seperti yang Anda sebutkan, yang menyebabkan runtime overhead, karena proses menunggu satu sama lain untuk menggunakan sumber daya bersama, dan kompleksitas desain yang lebih besar, karena semua konsep ini cenderung bersarang dalam aplikasi tersebut.

Saat Anda menghindari keadaan yang bisa berubah, kebutuhan untuk sinkronisasi dan mekanisme penguncian menghilang bersamaan dengannya. Karena bahasa fungsional biasanya menghindari keadaan berubah-ubah, mereka secara alami lebih efisien dan efektif untuk pemrosesan paralel - Anda tidak akan memiliki overhead runtime sumber daya bersama, dan Anda tidak akan memiliki kompleksitas desain tambahan yang biasanya mengikuti.

Namun, ini semua kebetulan. Jika solusi Anda di Jawa juga menghindari keadaan yang dapat berubah (khusus dibagi di antara utas), mengonversinya menjadi bahasa fungsional seperti Scala atau Clojure tidak akan menghasilkan manfaat dalam hal efisiensi bersamaan, karena solusi asli sudah bebas dari biaya overhead yang disebabkan oleh mekanisme penguncian dan sinkronisasi.

TL; DR: Jika solusi di Scala lebih efisien dalam pemrosesan paralel daripada di Jawa, itu bukan karena cara kode dikompilasi atau dijalankan melalui JVM, tetapi karena solusi Java berbagi keadaan yang dapat berubah antar thread, baik menyebabkan kondisi balapan atau menambahkan overhead sinkronisasi untuk menghindarinya.

MichelHenrich
sumber
2
Jika hanya satu utas memodifikasi sepotong data; tidak diperlukan perawatan khusus. Hanya ketika beberapa utas dapat mengubah data yang sama Anda memerlukan semacam perawatan khusus (sinkronisasi, memori transaksional, penguncian, apa pun). Contohnya adalah tumpukan thread, yang terus-menerus bermutasi oleh kode fungsional tetapi tidak dimodifikasi oleh banyak utas.
Brendan
31
Memiliki satu utas bermutasi data sementara yang lain membacanya cukup bahwa Anda harus mulai mengambil "perawatan khusus".
Peter Green
10
@ Brendan: Tidak, jika satu utas mengubah data sementara utas lainnya membaca dari data yang sama, maka Anda memiliki kondisi balapan. Perhatian khusus diperlukan bahkan jika hanya satu utas yang memodifikasi.
Cornstalks
3
Keadaan yang bisa berubah adalah "akar dari semua kejahatan" dalam konteks pemrosesan paralel => jika Anda belum melihat Rust, saya sarankan Anda mengintipnya. Ia mengelola untuk memungkinkan mutabilitas dengan sangat efisien dengan menyadari bahwa masalah yang sebenarnya dapat diubah bercampur dengan aliasing: jika Anda hanya memiliki aliasing atau hanya memiliki mutabilitas, tidak ada masalah.
Matthieu M.
2
@ MatthieuM. Benar terima kasih! Saya mengedit untuk mengungkapkan hal-hal lebih jelas dalam jawaban saya. Keadaan yang bisa berubah hanyalah "akar dari semua kejahatan" ketika ia dibagikan di antara proses-proses bersamaan - sesuatu yang Rust hindari dengan mekanisme kontrol kepemilikannya.
MichelHenrich
8

Semacam keduanya. Lebih cepat karena lebih mudah menulis kode Anda dengan cara yang lebih mudah untuk dikompilasi lebih cepat. Anda tidak perlu mendapatkan perbedaan kecepatan dengan mengganti bahasa, tetapi jika Anda memulai dengan bahasa fungsional, Anda mungkin bisa melakukan multithreading dengan upaya programmer yang jauh lebih sedikit . Sejalan dengan itu, jauh lebih mudah bagi seorang programmer untuk membuat kesalahan threading yang akan membutuhkan biaya dalam bahasa yang sangat penting, dan jauh lebih sulit untuk melihat kesalahan-kesalahan itu.

Alasannya adalah pemrogram yang sangat penting umumnya mencoba untuk meletakkan semua kode bebas-penguncian dalam kotak sekecil mungkin, dan menghindarinya sesegera mungkin, kembali ke dunia sinkron mereka yang nyaman dan dapat diubah. Sebagian besar kesalahan yang membuat Anda kecepatan dibuat pada antarmuka batas itu. Dalam bahasa pemrograman fungsional, Anda tidak perlu terlalu khawatir membuat kesalahan pada batas itu. Sebagian besar kode panggilan Anda juga "di dalam kotak," untuk berbicara.

Karl Bielefeldt
sumber
7

Pemrograman fungsional tidak membuat untuk program yang lebih cepat, sebagai aturan umum. Apa yang membuatnya adalah untuk pemrograman paralel dan bersamaan yang lebih mudah . Ada dua kunci utama untuk ini:

  1. Menghindari keadaan yang bisa berubah cenderung mengurangi jumlah hal yang bisa salah dalam suatu program, dan bahkan lebih lagi dalam program bersamaan.
  2. Menghindari primitif berbagi-memori dan sinkronisasi berbasis kunci yang mendukung konsep-konsep tingkat tinggi cenderung menyederhanakan sinkronisasi antara utas kode.

Salah satu contoh bagus dari poin # 2 adalah bahwa di Haskell kita memiliki perbedaan yang jelas antara paralelisme deterministik vs konkurensi non-deterministik . Tidak ada penjelasan yang lebih baik selain mengutip buku Simon Marlow yang sangat bagus Parallel and Concurrent Programming di Haskell (kutipan dari Bab 1 ):

Sebuah program paralel adalah salah satu yang menggunakan banyaknya hardware komputasi (misalnya, beberapa core prosesor) untuk melakukan perhitungan lebih cepat. Tujuannya adalah untuk sampai pada jawaban sebelumnya, dengan mendelegasikan bagian-bagian berbeda dari perhitungan ke prosesor yang berbeda yang mengeksekusi pada waktu yang sama.

Sebaliknya, konkurensi adalah teknik penataan program di mana ada banyak untaian kontrol. Secara konseptual, utas kontrol menjalankan "pada saat yang sama"; yaitu, pengguna melihat efeknya disisipkan. Apakah mereka benar-benar mengeksekusi pada saat yang sama atau tidak adalah detail implementasi; program konkuren dapat dijalankan pada satu prosesor melalui eksekusi berlevel atau pada beberapa prosesor fisik.

Selain itu, Marlow juga menyebutkan dimensi determinisme :

Perbedaan terkait adalah antara model pemrograman deterministik dan nondeterministik . Model pemrograman deterministik adalah model di mana setiap program hanya dapat memberikan satu hasil, sedangkan model pemrograman nondeterministik mengakui program yang mungkin memiliki hasil yang berbeda, tergantung pada beberapa aspek pelaksanaannya. Model pemrograman konkuren tidak bersifat deterministik karena mereka harus berinteraksi dengan agen eksternal yang menyebabkan peristiwa pada waktu yang tidak terduga. Nondeterminisme memiliki beberapa kelemahan, namun: Program menjadi lebih sulit untuk diuji dan dipikirkan.

Untuk pemrograman paralel, kami ingin menggunakan model pemrograman deterministik jika memungkinkan. Karena tujuannya hanya untuk mencapai jawaban lebih cepat, kami lebih suka tidak membuat program kami lebih sulit untuk di-debug dalam proses. Pemrograman paralel deterministik adalah yang terbaik dari kedua dunia: Pengujian, debugging, dan penalaran dapat dilakukan pada program berurutan, tetapi program berjalan lebih cepat dengan penambahan lebih banyak prosesor.

Dalam Haskell fitur paralelisme dan konkurensi dirancang di sekitar konsep-konsep ini. Secara khusus, apa yang dikelompokkan oleh bahasa lain sebagai satu set fitur, Haskell terbagi menjadi dua:

  • Fitur deterministik dan perpustakaan untuk paralelisme .
  • Fitur dan pustaka non-deterministik untuk konkurensi .

Jika Anda hanya ingin mempercepat perhitungan yang murni dan deterministik, memiliki paralelisme deterministik sering membuat segalanya lebih mudah. Seringkali Anda hanya melakukan sesuatu seperti ini:

  1. Tulis fungsi yang menghasilkan daftar jawaban, yang masing-masing mahal untuk dihitung tetapi tidak terlalu bergantung satu sama lain. Ini Haskell, jadi daftar-daftar itu malas — nilai-nilai elemen mereka tidak benar-benar dihitung sampai konsumen menuntutnya.
  2. Gunakan pustaka Strategies untuk menggunakan elemen daftar hasil fungsi Anda secara paralel di beberapa core.

Saya benar-benar melakukan ini dengan salah satu program proyek mainan saya beberapa minggu yang lalu . Itu sepele untuk memparalelkan program - hal utama yang harus saya lakukan adalah, pada dasarnya, menambahkan beberapa kode yang mengatakan "menghitung elemen-elemen dari daftar ini secara paralel" (baris 90), dan saya mendapat peningkatan throughput linear dekat pada beberapa kasus pengujian saya yang lebih mahal.

Apakah program saya lebih cepat daripada jika saya menggunakan utilitas multithreading berbasis kunci konvensional? Saya sangat meragukannya. Hal yang rapi dalam kasus saya adalah mendapatkan begitu banyak dari begitu sedikit uang — kode saya mungkin sangat suboptimal, tetapi karena sangat mudah untuk memaralelkan saya mendapat percepatan yang besar dari itu dengan usaha yang jauh lebih sedikit daripada dengan benar membuat profil dan mengoptimalkannya, dan tidak ada risiko kondisi balapan. Dan itu, saya akan klaim, adalah cara utama pemrograman fungsional memungkinkan Anda untuk menulis program "lebih cepat".

sakundim
sumber
2

Dalam Haskell, modifikasi secara harfiah tidak mungkin tanpa mendapatkan variabel yang dapat dimodifikasi khusus melalui perpustakaan modifikasi. Sebagai gantinya, fungsi membuat variabel yang mereka butuhkan pada saat yang sama dengan nilainya (yang dihitung dengan malas), dan sampah dikumpulkan ketika tidak lagi diperlukan.

Bahkan ketika Anda membutuhkan variabel modifikasi, Anda biasanya bisa menggunakan sparely, dan bersama dengan variabel yang tidak dapat dimodifikasi. (Hal lain yang menyenangkan di haskell adalah STM, yang menggantikan kunci dengan operasi atom, tapi saya tidak yakin apakah ini hanya untuk pemrograman fungsional atau tidak.) Biasanya, hanya satu bagian dari program yang perlu dibuat paralel untuk meningkatkan hal-hal kinerja-bijaksana.

Ini membuat paralelisme di Haskell sangat mudah, dan pada kenyataannya upaya sedang dilakukan untuk membuatnya otomatis. Untuk kode sederhana, paralelisme dan logika bahkan dapat dipisahkan.

Juga, karena fakta bahwa urutan evaluasi tidak penting di Haskell, kompiler hanya membuat antrian hal-hal yang perlu dievaluasi, dan mengirimkannya ke core apa pun yang tersedia, sehingga Anda dapat membuat banyak "utas" yang tidak sebenarnya menjadi utas sampai diperlukan. Urutan evaluasi tidak penting adalah karakteristik kemurnian, yang biasanya memerlukan pemrograman fungsional.

Bacaan Lebih Lanjut
Paralelisme di Haskell (HaskellWiki)
Pemrograman Bersamaan dan Multicore dalam Pemrograman Paralel dan Bersamaan Haskell Nyata di Dunia
oleh Haskell oleh Simon Marlow

PyRulez
sumber
7
grep java this_post. grep scala this_postdan grep jvm this_posttanpa hasil :)
Andres F.
4
Pertanyaannya tidak jelas. Dalam judul dan paragraf pertama, ia bertanya tentang pemrograman fungsional secara umum , pada paragraf kedua dan ketiga, ia bertanya tentang Java dan Scala pada khususnya . Sangat disayangkan, terutama karena salah satu kekuatan inti Scala adalah fakta bahwa itu bukan (hanya) bahasa fungsional. Martin Odersky menyebutnya "pasca-fungsional", yang lain menyebutnya "fungsional-objek". Ada dua definisi berbeda dari istilah "pemrograman fungsional". Salah satunya adalah "pemrograman dengan prosedur kelas satu" (definisi asli sebagaimana diterapkan pada LISP), yang lain adalah ...
Jörg W Mittag
2
"pemrograman dengan fungsi referensial yang transparan, murni, efek samping, dan data persisten yang tidak berubah" (jauh lebih ketat, dan juga interpretasi yang lebih baru). Jawaban ini membahas penafsiran kedua, yang masuk akal, karena a) penafsiran pertama sama sekali tidak terkait dengan paralelisme dan konkurensi, b) penafsiran pertama pada dasarnya menjadi tidak berarti karena dengan pengecualian C hampir setiap bahasa bahkan dalam penggunaan yang tersebar luas. hari ini memiliki prosedur kelas satu (termasuk Jawa), dan c) OP bertanya tentang perbedaan antara Jawa dan Scala, tetapi tidak ada ...
Jörg W Mittag
2
antara keduanya tentang definisi # 1, hanya definisi # 2.
Jörg W Mittag
Hal evaluasi tidak sepenuhnya benar seperti yang tertulis di sini; Secara default, runtime tidak menggunakan multithreading sama sekali, dan IIRC bahkan jika Anda mengaktifkan multithreading, Anda masih harus memberi tahu runtime hal-hal apa yang harus dievaluasi secara paralel.
Kubik