Parallel "any" oder "all" in Haskell

Ein Muster, auf das ich jetzt schon mehrmals gestoßen bin, ist eines, bei dem eine Liste von Werten überprüft werden muss, indem ein Test darüber abgebildet wird und geprüft wird, ob einige oder alle Elemente bestanden wurden. Die typische Lösung besteht darin, nur die praktischen Einbauten allund zu verwenden any.

Das Problem ist, dass diese seriell ausgewertet werden. In vielen Fällen wäre es viel schneller, parallel zum Abschluss des Prozesses zu bewerten, sobald ein Thread ein "False" für alloder ein "True" für findet any. Ich bin mir ziemlich sicher, dass das Kurzschlussverhalten mit Control.Parallel nicht implementiert werden kann, da es eine prozessübergreifende Kommunikation erfordert und ich Control.Concurrent noch nicht annähernd genug verstehe, um dies zu implementieren.

Es ist ein ziemlich verbreitetes Muster in der Mathematik (z. B. Miller-Rabin-Primalität), daher habe ich das Gefühl, dass jemand wahrscheinlich bereits eine Lösung dafür gefunden hat, aber aus offensichtlichen Gründen eine Google-Suche nach "parallel oder / und / any / all on list" durchführt haskell "gibt nicht viele relevante Ergebnisse zurück.

haskell testing concurrency parallel-processing any Arcuritech
quelle

Möglicherweise finden Sie in Haskell die parallele und gleichzeitige Programmierung hilfreich, insbesondere die Kapitel 2 , 3 und 4 .

Braddrn

Dies ist mit unambBibliothek möglich

luqui

@luqui Faszinierend; Ich werde damit herumspielen. Wenn ich eine gute Parallele dazu schreibe, werde ich sie als Antwort posten.

Arcuritech

Überlegen Sie sich vor dem Parallelisieren, wie viele Bedingungen Sie in der Zeit testen können, die zum Verzweigen eines neuen Prozesses erforderlich ist.

Chepper

@chepner wovon redest du? Wir reden hier nicht über Bash! Wir können Parallelität und Parallelität mit Threads herstellen (sei es pthreadsin C oder grüne Threads in Haskell). Sie starten nicht mehrere Webserver, um gleichzeitige Webanforderungen zu verarbeiten, sondern führen mehrere Threads in einem einzigen Prozess aus! Gleiches gilt für die Parallelität. Sie drehen so viele Threads hoch, wie Sie CPUs haben, und teilen Ihre Arbeit gleichmäßig auf, wodurch Sie sich um CPU-gebundene Aufgaben kümmern. Versuchen Sie, diese Bibliothek selbst zu überzeugen github.com/lehins/haskell-scheduler

lehins

Antworten:

In vielen realistischen Programmen können Sie zu diesem Zweck parallele Strategien verwenden. Dies liegt daran, dass, obwohl es keinen expliziten Mechanismus zum Abbrechen nicht benötigter Berechnungen gibt, dies implizit geschieht, wenn der Garbage Collector ausgeführt wird. Betrachten Sie als konkretes Beispiel das folgende Programm:

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)

Dies verwendet eine parallele Listenstrategie, um waldo = 0in der Ausgabe von 100 PRNG-Streams mit jeweils 40 Millionen Nummern zu suchen (was niemals gefunden wird). Kompilieren und ausführen:

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

und es fixiert vier Kerne für ungefähr 16s und druckt schließlich False. Beachten Sie in der Statistik, dass alle 100 Funken "konvertiert" werden und somit vollständig ausgeführt werden:

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

Wechseln Sie jetzt waldozu einem Wert, der früh gefunden werden kann:

waldo = 531186389   -- lcgs 5 !! 50000

und ändern Sie main, um den Thread 10 Sekunden lang am Leben zu halten:

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

Sie werden feststellen, dass es Truefast sofort gedruckt wird , aber 4 Kerne (zumindest für eine kurze Zeit) an 100% CPU gebunden bleiben. Dies zeigt, dass nicht benötigte Berechnungen weiterhin ausgeführt werden und nicht kurzgeschlossen werden, wie Sie vielleicht befürchtet haben.

ABER die Dinge ändern sich, wenn Sie eine Speicherbereinigung erzwingen, nachdem Sie die Antwort erhalten haben:

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

Jetzt werden Sie sehen, dass die CPU kurz nach dem Drucken in den Leerlauf fällt True, und die Statistiken zeigen, dass die meisten Berechnungen vor dem Ausführen durch Müll gesammelt wurden:

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

In realistischen Programmen wird kein explizites Programm performGCbenötigt, da GCs selbstverständlich regelmäßig durchgeführt werden. Einige unnötige Berechnungen werden weiterhin ausgeführt, nachdem die Antwort gefunden wurde. In vielen realistischen Szenarien ist der Anteil unnötiger Berechnungen jedoch kein besonders wichtiger Faktor.

Insbesondere wenn die Liste groß ist und jeder einzelne Test eines Listenelements schnell ist, weisen parallele Strategien eine hervorragende Leistung in der Praxis auf und lassen sich leicht in den Handel umsetzen.

KA Buhr
quelle