Throttling Parallel Computing

Question

Question

I have a finite list of values:

values :: [A] 

... and an expensive but pure function for these values:

 expensiveFunction :: A -> Maybe B 

How to run this function for each value in parallel and return only the first n results that end with Just and stop calculating the unfinished results?

 takeJustsPar :: (NFData b) => Int -> (a -> Maybe b) -> [a] -> [b] takeJustsPar maxJusts f as = ??? 

Motivation

I know how to do this using Control.Concurrent , but I wanted to experiment using the Haskell parallelism functions. In addition, the (scarce) literature that I could find seems to indicate that the Haskell parallelism functions make it cheaper to create parallel computing and adapt the workload to the number of possibilities.

Answer 1

I tried to make two decisions. The first uses the Par monad (i.e. Control.Monad.Par ):

 import Control.Monad.Par (Par, NFData) import Control.Monad.Par.Combinator (parMap) import Data.Maybe (catMaybes) import Data.List.Split (chunksOf) takeJustsPar :: (NFData b) => Int -> Int -> (a -> Maybe b) -> [a] -> Par [b] takeJustsPar n chunkSize f as = go n (chunksOf chunkSize as) where go _ [] = return [] go 0 _ = return [] go numNeeded (chunk:chunks) = do evaluatedChunk <- parMap f chunk let results = catMaybes evaluatedChunk numFound = length results numRemaining = numNeeded - numFound fmap (results ++) $ go numRemaining chunks 

The second attempt was used by Control.Parallel.Strategies :

 import Control.Parallel.Strategies import Data.List.Split (chunksOf) chunkPar :: (NFData a) => Int -> Int -> [a] -> [a] chunkPar innerSize outerSize as = concat ((chunksOf innerSize as) `using` (parBuffer outerSize rdeepseq)) 

The latter turned out to be much more complicated, as I could just write:

 take n $ catMaybes $ chunkPar 1000 10 $ map expensiveFunction xs 

... instead of baking in the take and catMaybes in the parallelism strategy.

The latter solution also gives an almost perfect use. On an awkwardly parallel problem, I tested it, it gave 99% use for 8 cores. I did not test the use of the Par Monad because I borrowed the computer of my colleagues and did not want to waste my time when I was pleased with the performance of Control.Parallel.Strategies .

So, the answer is to use Control.Parallel.Strategies , which gives much more flexible behavior and excellent multi-core use.