Paralel “apa saja” atau “semua” di Haskell

Pola yang saya temui beberapa kali sekarang adalah pola di mana daftar nilai perlu diperiksa dengan memetakan beberapa tes di atasnya dan melihat apakah ada atau semua elemen lulus. Solusi khasnya adalah hanya menggunakan built-in alldan nyaman any.

Masalahnya adalah ini mengevaluasi secara serial. Dalam banyak kasus akan jauh lebih cepat untuk mengevaluasi secara paralel dengan proses yang selesai setelah setiap thread menemukan "Salah" untuk allatau "Benar" untuk any. Saya cukup yakin bahwa perilaku hubungan arus pendek tidak dapat diimplementasikan menggunakan Control.Paralel karena memerlukan komunikasi antar-proses dan saya tidak mengerti cukup dekat dengan Control.Concurrent untuk mengimplementasikan ini.

Ini adalah pola yang cukup umum dalam matematika (misalnya Miller-Rabin Primality) jadi saya merasa seperti seseorang mungkin telah menemukan solusi untuk ini, tetapi untuk alasan yang jelas melakukan pencarian google untuk "parallel atau / dan / any / all / all pada daftar haskell "tidak menghasilkan banyak hasil yang relevan.

Dalam banyak program realistis, Anda dapat menggunakan strategi paralel untuk tujuan ini. Itu karena, meskipun tidak ada mekanisme eksplisit untuk membatalkan perhitungan yang tidak dibutuhkan, ini akan terjadi secara implisit ketika pengumpul sampah berjalan. Sebagai contoh nyata, pertimbangkan program berikut:

import Control.Concurrent
import Control.Parallel.Strategies
import Data.Int
import System.Mem

lcgs :: Int32 -> [Int32]
lcgs = iterate lcg
  where lcg x = 1664525 * x + 1013904223

hasWaldo :: Int32 -> Bool
hasWaldo x = waldo `elem` take 40000000 (lcgs x)

waldo :: Int32
waldo = 0

main :: IO ()
main = do
  print $ or (map hasWaldo [1..100] `using` parList rseq)

Ini menggunakan strategi daftar paralel untuk mencari waldo = 0(yang tidak akan pernah ditemukan) dalam output 100 aliran PRNG masing-masing 40 juta angka. Kompilasi dan jalankan:

ghc -threaded -O2 ParallelAny.hs
./ParallelAny +RTS -s -N4

dan itu mematok empat inti selama sekitar 16-an, akhirnya mencetak False. Perhatikan dalam statistik bahwa semua 100 bunga api "dikonversi" dan berjalan sampai selesai:

SPARKS: 100(100 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)

Sekarang, ubah waldoke nilai yang dapat ditemukan lebih awal:

waldo = 531186389   -- lcgs 5 !! 50000

dan modifikasi mainuntuk menjaga utas tetap hidup selama 10 detik:

main :: IO ()
main = do
  print $ or (map hasWaldo [1..100] `using` parList rseq)
  threadDelay 10000000

Anda akan mengamati bahwa ia mencetak Truehampir segera, tetapi 4 core tetap dipatok pada CPU 100% (setidaknya untuk beberapa saat), menggambarkan bahwa perhitungan yang tidak dibutuhkan terus berjalan dan tidak mengalami hubungan pendek, seperti yang mungkin Anda takuti.

TETAPI , segalanya berubah jika Anda memaksakan pengumpulan sampah setelah mendapatkan jawabannya:

main :: IO ()
main = do
  print $ or (map hasWaldo [1..100] `using` parList rseq)
  performGC
  threadDelay 10000000

Sekarang, Anda akan melihat bahwa CPU menjadi idle tak lama setelah pencetakan True, dan statistik menunjukkan bahwa sebagian besar perhitungan adalah sampah yang dikumpulkan sebelum dijalankan:

SPARKS: 100(9 converted, 0 overflowed, 0 dud, 91 GC'd, 0 fizzled)

Dalam program yang realistis, eksplisit performGCtidak diperlukan, karena GC akan dilakukan secara teratur sebagai hal yang biasa. Beberapa perhitungan yang tidak perlu akan terus berjalan setelah jawabannya ditemukan, tetapi dalam banyak skenario realistis, fraksi perhitungan yang tidak perlu tidak akan menjadi faktor yang sangat penting.

Secara khusus, jika daftar tersebut besar dan setiap tes individu dari elemen daftar cepat, strategi paralel akan memiliki kinerja dunia nyata yang sangat baik dan mudah diimplementasikan ke dalam tawar-menawar.