Parallèle «tout» ou «tout» dans Haskell

Un modèle que j'ai rencontré un certain nombre de fois maintenant est celui où une liste de valeurs doit être vérifiée en mappant un test dessus et en voyant si certains ou tous les éléments ont réussi. La solution typique consiste simplement à utiliser les fonctions intégrées allet any.

Le problème est que ceux-ci sont évalués en série. Dans de nombreux cas, il serait beaucoup plus rapide d'évaluer en parallèle avec le processus étant terminé une fois qu'un thread trouve un "False" pour allou un "True" pour any. Je suis à peu près sûr que le comportement de court-circuit ne peut pas être implémenté à l'aide de Control.Parallel car il nécessite une communication inter-processus et je ne comprends pas assez près de Control.Concurrent pour l'implémenter.

C'est un modèle assez courant en mathématiques (par exemple Miller-Rabin Primality), donc j'ai l'impression que quelqu'un a probablement déjà trouvé une solution pour cela, mais pour des raisons évidentes, faire une recherche Google pour "parallèle ou / et / tout / tout sur la liste" haskell "ne renvoie pas beaucoup de résultats pertinents.

Dans de nombreux programmes réalistes, vous pouvez utiliser des stratégies parallèles à cet effet. En effet, même s'il n'existe aucun mécanisme explicite pour annuler les calculs inutiles, cela se produira implicitement lorsque le garbage collector s'exécute. À titre d'exemple concret, considérons le programme suivant:

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)

Il utilise une stratégie de liste parallèle pour rechercher waldo = 0(qui ne sera jamais trouvée) dans la sortie de 100 flux PRNG de 40 millions de numéros chacun. Compilez-le et exécutez-le:

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

et il accroche quatre cœurs pendant environ 16 secondes, puis imprime False. Notez dans les statistiques que les 100 étincelles sont "converties" et donc exécutées jusqu'à la fin:

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

Maintenant, changez waldopour une valeur qui peut être trouvée tôt:

waldo = 531186389   -- lcgs 5 !! 50000

et modifiez mainpour garder le fil vivant pendant 10 secondes:

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

Vous remarquerez qu'il s'imprime Truepresque immédiatement, mais 4 cœurs restent ancrés à 100% du processeur (au moins pendant un petit moment), illustrant que les calculs inutiles continuent de fonctionner et ne sont pas court-circuités, comme vous auriez pu le craindre.

MAIS , les choses changent si vous forcez un ramasse-miettes après avoir obtenu la réponse:

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

Maintenant, vous verrez que le CPU devient inactif peu de temps après l'impression True, et les statistiques montrent que la plupart des calculs ont été récupérés avant de s'exécuter:

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

Dans les programmes réalistes, un explicite performGCne sera pas nécessaire, car les GC seront effectués régulièrement de manière régulière. Certains calculs inutiles continueront de s'exécuter une fois la réponse trouvée, mais dans de nombreux scénarios réalistes, la fraction des calculs inutiles ne sera pas un facteur particulièrement important.

En particulier, si la liste est longue et que chaque test individuel d'un élément de liste est rapide, les stratégies parallèles auront d'excellentes performances dans le monde réel et sont faciles à mettre en œuvre dans le marché.