Parallel "any" or "all" in Haskell

Question

A pattern I have come across a number of times now is one where a list of values needs to be checked by mapping some test over it and seeing if any or all of the elements passed. The typical solution is just to use the convenient built-ins all and any.

The problem is that these evaluate in serial. In many cases it would be much faster to evaluate in parallel with the process being complete once any thread finds a "False" for all or a "True" for any. I'm pretty sure that short-circuiting behavior can't be implemented using Control.Parallel as it requires inter-process communication and I don't understand anywhere near enough of Control.Concurrent to implement this yet.

It's a pretty common pattern in math (e.g. Miller-Rabin Primality) so I feel like someone has probably come up with a solution for this already, but for obvious reasons doing a google search for "parallel or/and/any/all on list haskell" doesn't return many relevant results.

Answer 1

In many realistic programs, you can use parallel strategies for this purpose. That's because, even though there is no explicit mechanism to cancel unneeded computations, this will happen implicitly when the garbage collector runs. As a concrete example, consider the following 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)

This uses a parallel list strategy to search for waldo = 0 (which will never be found) in the output of 100 PRNG streams of 40 million numbers each. Compile and run it:

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

and it pegs four cores for about 16s, eventually printing False. Note in the statistics that all 100 sparks are "converted" and so run to completion:

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

Now, change waldo to a value that can be found early:

waldo = 531186389   -- lcgs 5 !! 50000

and modify main to keep the thread alive for 10 seconds:

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

You'll observe that it prints True almost immediately, but 4 cores remain pegged at 100% CPU (at least for a little while), illustrating that unneeded computations keep running and are not short-circuited, just as you might have feared.

BUT, things change if you force a garbage collection after getting the answer:

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

Now, you'll see that the CPU drops to idle shortly after printing True, and the statistics show that most of the computations were garbage collected before running:

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

In realistic programs, an explicit performGC will not be needed, as GCs will be performed regularly as a matter of course. Some unnecessary computations will continue to run after the answer is found, but in many realistic scenarios, the fraction of unnecessary computations will not be a particularly important factor.

In particular, if the list is large and each individual test of a list element is fast, parallel strategies will have excellent real-world performance and is easy to implement into the bargain.