Równoległe „dowolne” lub „wszystkie” w Haskell

Wzorzec, z którym się zetknąłem już wiele razy, jest taki, w którym należy sprawdzić listę wartości, mapując na niej jakiś test i sprawdzając, czy którykolwiek lub wszystkie elementy przeszły. Typowym rozwiązaniem jest po prostu użycie wygodnych wbudowanych alli any.

Problem polega na tym, że oceniają one szeregowo. W wielu przypadkach ocena byłaby znacznie szybsza równolegle z zakończeniem procesu, gdy jakikolwiek wątek znajdzie „Fałsz” alllub „Prawda” dla any. Jestem całkiem pewien, że zachowanie zwarciowe nie może być zaimplementowane przy użyciu Control.Parallel, ponieważ wymaga komunikacji między procesami i nie rozumiem nigdzie wystarczająco blisko Control.Concurrent, aby to zaimplementować.

Jest to dość powszechny wzorzec w matematyce (np. Miller-Rabin Primality), więc wydaje mi się, że ktoś prawdopodobnie już wymyślił rozwiązanie tego problemu, ale z oczywistych powodów szuka w Google hasła „równoległe lub / i / dowolne / wszystkie na liście” haskell ”nie zwraca wielu trafnych wyników.

W wielu realistycznych programach można w tym celu stosować strategie równoległe. Wynika to z faktu, że chociaż nie ma jawnego mechanizmu anulowania niepotrzebnych obliczeń, nastąpi to niejawnie, gdy uruchomi się moduł czyszczenia pamięci. Jako konkretny przykład rozważ następujący program:

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)

Wykorzystuje strategię listy równoległej do wyszukiwania waldo = 0(które nigdy nie zostaną znalezione) w danych wyjściowych 100 strumieni PRNG po 40 milionów liczb. Skompiluj i uruchom:

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

i ustala cztery rdzenie przez około 16s, ostatecznie drukując False. Zwróć uwagę w statystykach, że wszystkie 100 iskier jest „konwertowanych” i dlatego biegną do końca:

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

Teraz zmień waldona wartość, którą można znaleźć wcześnie:

waldo = 531186389   -- lcgs 5 !! 50000

i zmodyfikuj, mainaby utrzymać wątek przy życiu przez 10 sekund:

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

Zauważysz, że drukuje Trueprawie natychmiast, ale 4 rdzenie pozostają na 100% procesorze (przynajmniej przez krótką chwilę), co ilustruje, że niepotrzebne obliczenia nadal działają i nie są zwarte, tak jak się obawiałeś.

ALE , rzeczy się zmieniają, jeśli wymusisz odśmiecanie po otrzymaniu odpowiedzi:

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

Teraz zobaczysz, że procesor przechodzi w stan bezczynności wkrótce po wydrukowaniu True, a statystyki pokazują, że większość obliczeń została wyrzucona przez śmieci przed uruchomieniem:

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

W realistycznych programach wyraźne performGCnie będzie potrzebne, ponieważ GC będą przeprowadzane regularnie. Niektóre niepotrzebne obliczenia będą nadal działać po znalezieniu odpowiedzi, ale w wielu realistycznych scenariuszach część niepotrzebnych obliczeń nie będzie szczególnie ważnym czynnikiem.

W szczególności, jeśli lista jest duża, a każdy pojedynczy test elementu listy jest szybki, strategie równoległe będą miały doskonałą wydajność w świecie rzeczywistym i będą łatwe do wdrożenia w okazjach.