Apakah kompiler seperti Javac secara otomatis mendeteksi fungsi murni dan memparalelkannya?

Fungsi murni dikenal untuk memfasilitasi pembuatan parellel. Ada apa dengan pemrograman fungsional yang membuatnya secara inheren disesuaikan dengan eksekusi paralel?

Apakah kompiler seperti Javac cukup pintar untuk mendeteksi kapan suatu metode merupakan fungsi murni? Seseorang selalu dapat mengimplementasikan kelas yang mengimplementasikan antarmuka fungsional seperti Fungsi , tetapi memiliki efek samping.

functional-programming Naveen
sumber

Pertanyaannya bukan hanya apakah kompiler dapat mengetahui apakah suatu fungsi murni, tetapi juga apakah ia dapat secara cerdas menjadwalkan eksekusi paralel fungsi murni. Tidak cukup untuk meluncurkan utas baru untuk masing-masing: ini tidak efisien. GHC (Haskell) berurusan dengan ini menggunakan kemalasan dan "utas hijau"; Jujur saya akan terkejut jika ada bahasa tidak murni bahkan mencoba, mengingat kesulitan tambahan untuk memastikan utas murni dijadwalkan dengan benar sehubungan dengan utas murni tidak murni.

Ryan Reich

@RyanReich, apakah ada keuntungan kinerja menggunakan pemrograman fungsional dalam bahasa fungsional yang tidak murni seperti Java? Apakah keuntungan pemrograman fungsional murni fungsional seperti modularitas?

Naveen

@RyanReich GHC menangani masalah ini dengan membuat programmer membuat catatan ketika mereka menginginkan paralelisme. Purity menyiratkan bahwa anotasi ini tidak pernah mengubah semantik, hanya kinerja. (Ada juga mekanisme konkurensi yang dapat menimbulkan paralelisme, tetapi ini adalah ketel ikan yang berbeda.)

Derek Elkins meninggalkan SE

@Naveen Ada manfaat lain untuk fungsi murni sehubungan dengan optimisasi selain paralelisme seperti kode pemesanan ulang kebebasan yang lebih besar, memoisasi dan penghapusan sub-ekspresi umum. Saya bisa saja salah, tetapi saya ragu upaya javac untuk mendeteksi kemurnian, karena itu mungkin cukup langka dalam kode idiomatik dan agak sulit untuk semua kecuali kasus yang paling sepele. Misalnya, Anda perlu tahu bahwa tidak akan ada NullPointerException. Manfaat optimasi berdasarkan ini juga mungkin cukup kecil untuk aplikasi Java yang khas.

Derek Elkins meninggalkan SE

javac adalah kompiler java, yang mengambil kode sumber java dan menghasilkan file kelas kode byte java. Hal ini sangat terbatas pada apa yang dapat (dan seharusnya) dilakukan. Itu tidak memiliki kebebasan atau mekanisme mendasar yang diperlukan untuk memperkenalkan paralelisme ke dalam file kelas kode byte.

Erik Eidt

Jawaban:

adalah kompiler seperti Javac cukup pintar untuk mendeteksi kapan suatu metode adalah fungsi murni.

Ini bukan pertanyaan "cukup pintar". Ini disebut Analisis Kemurnian dan terbukti mustahil dalam kasus umum: ini setara dengan menyelesaikan Masalah Pemutusan Hubungan.

Sekarang, tentu saja, pengoptimal melakukan hal-hal yang terbukti mustahil sepanjang waktu, "terbukti tidak mungkin dalam kasus umum" tidak berarti tidak pernah berhasil, itu hanya berarti tidak dapat berfungsi dalam semua kasus. Jadi, sebenarnya ada algoritma untuk memeriksa apakah suatu fungsi murni atau tidak, hanya saja lebih sering hasilnya adalah "Saya tidak tahu", yang berarti bahwa untuk alasan keamanan dan kebenaran, Anda perlu mengasumsikan bahwa fungsi khusus ini mungkin tidak murni.

Dan bahkan dalam kasus di mana tidak bekerja, algoritma yang kompleks dan mahal.

Jadi, itulah Masalah # 1: itu hanya berfungsi untuk kasus khusus .

Masalah # 2: Perpustakaan . Agar suatu fungsi menjadi murni, ia hanya dapat memanggil fungsi murni (dan fungsi tersebut hanya dapat memanggil fungsi murni, dan seterusnya dan seterusnya). Javac jelas hanya tahu tentang Java, dan hanya tahu tentang kode yang dapat dilihatnya. Jadi, jika fungsi Anda memanggil fungsi di unit kompilasi lain, Anda tidak bisa tahu apakah itu murni atau tidak. Jika itu memanggil fungsi yang ditulis dalam bahasa lain, Anda tidak bisa tahu. Jika itu memanggil fungsi di perpustakaan yang bahkan mungkin belum diinstal, Anda tidak bisa tahu. Dan seterusnya.

Ini hanya berfungsi, ketika Anda memiliki analisis seluruh program, ketika seluruh program ditulis dalam bahasa yang sama, dan semua dikompilasi sekaligus dalam satu waktu. Anda tidak dapat menggunakan perpustakaan apa pun.

Masalah # 3: Penjadwalan . Setelah Anda mengetahui bagian mana yang murni, Anda masih harus menjadwalkannya untuk memisahkan utas. Atau tidak. Memulai dan menghentikan utas sangat mahal (terutama di Jawa). Bahkan jika Anda menyimpan kumpulan utas dan tidak memulai atau menghentikannya, pergantian konteks utas juga mahal. Anda harus yakin bahwa perhitungan akan berjalan jauh lebih lama daripada waktu yang diperlukan untuk menjadwalkan dan mengubah konteks, jika tidak, Anda akan kehilangan kinerja, bukan memperolehnya.

Seperti yang mungkin sudah Anda tebak sekarang, mencari tahu berapa lama perhitungan akan terbukti tidak mungkin dalam kasus umum (kami bahkan tidak dapat menentukan apakah akan membutuhkan waktu yang terbatas, apalagi berapa lama) dan sulit dan mahal bahkan di kasus khusus.

Selain: Javac dan optimisasi . Perhatikan bahwa sebagian besar implementasi javac tidak benar-benar melakukan banyak optimasi. Implementasi Oracle dari javac, misalnya, bergantung pada mesin eksekusi yang mendasari untuk melakukan optimasi . Ini mengarah ke serangkaian masalah lain: katakanlah, javac memutuskan bahwa fungsi tertentu murni dan cukup mahal, sehingga mengkompilasinya untuk dieksekusi pada utas yang berbeda. Kemudian, pengoptimal platform (misalnya, kompiler JIT HotSpot C2) datang dan mengoptimalkan seluruh fungsi. Sekarang, Anda memiliki utas kosong yang tidak melakukan apa-apa. Atau, bayangkan, sekali lagi, javac memutuskan untuk menjadwalkan fungsi pada utas yang berbeda, dan pengoptimal platform bisa mengoptimalkannya sepenuhnya, kecuali itu tidak dapat melakukan inlining melintasi batas-batas thread, dan fungsi yang dapat dioptimalkan sepenuhnya sepenuhnya sekarang dieksekusi tanpa perlu.

Jadi, melakukan sesuatu seperti ini hanya benar-benar masuk akal jika Anda memiliki satu kompiler membuat sebagian besar optimasi dalam sekali jalan, sehingga kompiler mengetahui dan dapat mengeksploitasi semua optimasi yang berbeda di tingkat yang berbeda dan interaksinya satu sama lain.

Perhatikan bahwa, misalnya, kompiler HotSpot C2 JIT benar - benar melakukan beberapa auto-vektorisasi, yang juga merupakan bentuk paralelisasi otomatis.

Jörg W Mittag
sumber

Nah, tergantung pada definisi Anda tentang "fungsi murni", menggunakan fungsi tidak murni dalam implementasi mungkin diperbolehkan.

Deduplicator

@Deduplicator Nah, tergantung pada definisi Anda tentang definition, menggunakan berbeda definitiondari puritymungkin jelas

kucing

Masalah Anda # 2 sebagian besar batal karena fakta bahwa hampir semua optimasi dijalankan oleh JIT (Anda jelas tahu itu, tetapi abaikan saja). Demikian pula masalah # 3 menjadi tidak valid sebagian karena JIT sangat bergantung pada statistik yang dikumpulkan oleh penerjemah. Saya terutama tidak setuju dengan "Anda tidak dapat menggunakan perpustakaan apa pun" karena ada deoptimisasi untuk menyelamatkan. Saya setuju bahwa kompleksitas yang ditambahkan akan menjadi masalah.

maaartinus

@maaartinus: Selain itu, hanya akhir dari jawaban saya yang spesifik untuk javac. Saya secara khusus melakukan menyebutkan, misalnya, bahwa "ini hanya bekerja, ketika Anda memiliki analisis keseluruhan-program, ketika seluruh program ditulis dalam bahasa yang sama, dan semua dikompilasi sekaligus dalam satu pergi." Ini jelas benar untuk C2: ini hanya berurusan dengan satu bahasa (bytecode JVM), dan memiliki akses ke seluruh program sekaligus.

Jörg W Mittag

@ JörgWMittag Saya tahu bahwa OP bertanya tentang javac, tapi saya berani bertaruh mereka berasumsi bahwa javac adalah hal yang bertanggung jawab untuk optimasi. Dan mereka hampir tidak tahu bahwa ada C2. Saya tidak mengatakan, jawaban Anda buruk. Hanya saja membiarkan javac melakukan optimasi apa pun (kecuali untuk hal-hal sepele seperti menggunakan StringBuilder) adalah tidak masuk akal, jadi saya akan mengabaikannya dan berasumsi, OP menulis javac tetapi berarti Hotspot. Masalah Anda # 2 adalah alasan yang cukup bagus untuk tidak mengoptimalkan apa pun di javac.

maaartinus

Jawaban yang dipilih gagal mencatat satu hal. Komunikasi sinkron antara utas sangat mahal. Jika fungsi ini mampu dieksekusi pada kecepatan jutaan panggilan per detik, itu sebenarnya lebih menyakitkan Anda untuk memparalelkannya daripada membiarkannya apa adanya.

Bentuk komunikasi inter-thread sinkron tercepat, menggunakan loop sibuk dengan variabel atom, sayangnya tidak efisien energi. Jika Anda harus menggunakan variabel kondisi untuk menghemat energi, kinerja komunikasi antar-thread Anda akan terganggu.

Jadi, kompiler tidak hanya perlu menentukan apakah suatu fungsi murni, tetapi juga perlu memperkirakan waktu eksekusi fungsi untuk melihat apakah paralelisasi adalah kemenangan bersih. Selain itu, perlu memilih antara loop sibuk menggunakan variabel atom atau variabel kondisi. Dan itu perlu membuat utas di belakang Anda.

Jika Anda membuat utas secara dinamis, itu bahkan lebih lambat daripada menggunakan variabel kondisi. Jadi, kompiler perlu menyiapkan sejumlah utas yang sudah berjalan.

Jadi, jawaban untuk pertanyaan Anda adalah tidak , kompiler tidak cukup "pintar" untuk melakukan paralelisasi fungsi murni terutama di dunia Java. Mereka pintar dengan tidak membuat mereka paralel!

ahli hukum agama
sumber

" Mereka pintar dengan tidak membuat mereka paralel! " : Ini terlalu jauh. Meskipun benar bahwa melakukan paralelisasi pada setiap titik yang mungkin hanya demi dirinya sendiri pada umumnya tidak efisien, kompiler pintar akan mengidentifikasi strategi paralelisasi praktis. Saya pikir sebagian besar orang mengerti ini, jadi ketika kita berbicara tentang auto-parallelization, yang kita maksud auto-praktis-paralelisasi.

Nat

@Nat: Sangat sulit. Ini akan membutuhkan pengidentifikasian fungsi-fungsi murni pada skala runtime 100-an milidetik, dan mengharapkan kompiler mendapatkan gagasan runtime loop yang tidak memiliki konstanta dalam iterasi mereka (dan kasus yang Anda inginkan tidak) konyol.

Joshua

Saya setuju - Komentar Nat menyiratkan bahwa paralelisasi tidak selalu berarti banyak utas, yang benar. JIT dapat, misalnya, inline beberapa panggilan ke fungsi murni dan interleave instruksi CPU mereka dalam kasus-kasus tertentu. Misalnya, jika kedua panggilan metode mengambil konstanta, itu bisa diambil sekali dan disimpan dalam register CPU untuk kedua contoh metode yang digunakan. CPU modern adalah binatang buas dengan banyak register tujuan umum dan instruksi khusus yang bisa sangat membantu ketika mengoptimalkan kode.

@ Joshua: Memang jauh lebih mudah untuk kompiler JIT. Kompiler JIT juga dapat mengetahui bahwa suatu fungsi mungkin tidak murni, tetapi sejauh ini tidak ada panggilan yang memanggil perilaku tidak murni.

gnasher729

Saya setuju dengan @ Yosua. Saya memiliki algoritma yang sulit diparalelkan di tempat kerja. Saya telah mencoba untuk memparalelasinya secara manual, bahkan dengan melakukan beberapa penyederhanaan perkiraan (dan dengan demikian memodifikasi algoritme), dan telah gagal total setiap waktu. Bahkan sebuah program yang mengatakan apakah itu layak untuk memparalelkan sesuatu adalah sangat sulit, meskipun itu akan jauh lebih sederhana daripada benar-benar memparalelkannya. Ingat kita sedang berbicara tentang bahasa pemrograman Turing-lengkap.

juhist