Параллельно «любой» или «все» в Haskell

Question

Шаблон, с которым я сталкивался несколько раз, - это тот, в котором список значений должен быть проверен путем сопоставления некоторого теста и проверки, прошел ли какой-либо или все элементы. Типичное решение - просто использовать удобные встроенные модули all и any.

. Проблема в том, что они оцениваются последовательно. Во многих случаях было бы на намного быстрее вычислять параллельно с завершением процесса, когда любой поток находит "False" для all или "True" для any , Я почти уверен, что поведение короткого замыкания не может быть реализовано с помощью Control.Parallel, поскольку оно требует межпроцессного взаимодействия, и я пока не понимаю достаточно близко к Control.Concurrent, чтобы реализовать это.

Это довольно распространенный паттерн в математике (например, Primality Миллера-Рабина), поэтому я чувствую, что кто-то, возможно, уже нашел решение для этого, но по понятным причинам делает поиск в Google "параллельно или / и / любой / все в списке". haskell "не возвращает много релевантных результатов.

Answer 1

Во многих реалистичных c программах вы можете использовать параллельные стратегии для этой цели. Это потому, что, хотя нет явного механизма отмены ненужных вычислений, это будет происходить неявно, когда запускается сборщик мусора. В качестве конкретного примера рассмотрим следующую программу:

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)

При этом используется стратегия параллельного списка для поиска waldo = 0 (который никогда не будет найден) в выходных данных 100 потоков PRNG по 40 миллионов номеров каждый. , Скомпилируйте и запустите его:

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

, и он привязывает четыре ядра примерно на 16 секунд, в конечном итоге печатая False. Обратите внимание на статистику, что все 100 искр "преобразованы" и поэтому работают до завершения:

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

Теперь измените waldo на значение, которое можно найти раньше:

waldo = 531186389   -- lcgs 5 !! 50000

и измените main, чтобы поддерживать поток в течение 10 секунд:

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

Вы заметите, что он печатает True почти сразу, но 4 ядра остаются привязанными на 100% ЦП (по крайней мере, для немного), иллюстрируя, что ненужные вычисления продолжают работать и не закорачиваются, как вы, возможно, опасались.

НО , все изменится, если вы принудительно выполните сборку мусора после получения ответ:

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

Теперь вы увидите, что ЦП переходит в режим ожидания вскоре после печати True, и статистика показывает, что большинство вычислений были собраны мусором перед запуском:

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

В реализующих c программах явный performGC не потребуется, поскольку GC будут выполняться регулярно, как само собой разумеющееся. Некоторые ненужные вычисления будут продолжать выполняться после того, как ответ найден, но во многих c сценариях ios доля ненужных вычислений не будет особенно важным фактором.

В частности, если список Это большой объем, и каждый отдельный тест элемента списка выполняется быстро, параллельные стратегии будут иметь отличную производительность в реальном мире и их легко внедрить в сделку.