 | parallel-2.2.0.1: Parallel programming library | Contents | Index |
| Control.Parallel.Strategies |
|
| Contents |
Parallel Evaluation Strategies, or Strategies for short, specify a way to evaluate a structure with components in sequence or in parallel.
Strategies are for expressing deterministic parallelism: the result of the program is unaffected by evaluating in parallel. For non-deterministic parallel programming, see Control.Concurrent.
Strategies let you separate the description of parallelism from the logic of your program, enabling modular parallelism.
Version 1.x
The original Strategies design is described in http://www.macs.hw.ac.uk/~dsg/gph/papers/html/Strategies/strategies.html and the code was written by Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al.
Version 2.x
Later, during work on the shared-memory implementation of parallelism in GHC, we discovered that the original formulation of Strategies had some problems, in particular it lead to space leaks and difficulties expressing speculative parallelism. Details are in the paper "Runtime Support for Multicore Haskell" http://www.haskell.org/~simonmar/papers/multicore-ghc.pdf.
This module has been rewritten in version 2. The main change is to the 'Strategy a' type synonym, which was previously a -> Done and is now a -> Eval a. This change helps to fix the space leak described in "Runtime Support for Multicore Haskell". The problem is that the runtime will currently retain the memory referenced by all sparks, until they are evaluated. Hence, we must arrange to evaluate all the sparks eventually, just in case they aren't evaluated in parallel, so that they don't cause a space leak. This is why we must return a "new" value after applying a Strategy, so that the application can evaluate each spark created by the Strategy.
The simple rule is this: you must use the result of applying a Strategy if the strategy creates parallel sparks, and you should probably discard the the original value. If you don't do this, currently it may result in a space leak. In the future (GHC 6.14), it will probably result in lost parallelism instead, as we plan to change GHC so that unreferenced sparks are discarded rather than retained (we can't make this change until most code is switched over to this new version of Strategies, because code using the old verison of Strategies would be broken by the change in policy).
The other changes in version 2.x are:
- Strategies can now be defined using a convenient Monad/Applicative type, Eval. e.g. parList s = traverse (Par . (`using` s))
- parList has been generalised to parTraverse, which works on any Traversable type, and similarly seqList has been generalised to seqTraverse
- parList and parBuffer have versions specialised to rwhnf, and there are transformation rules that automatically translate e.g. parList rwnhf into a call to the optimised version.
- NFData has been moved to Control.DeepSeq in the deepseq package. Note that since the Strategy type changed, rnf is no longer a Strategy: use rdeepseq instead.
| type Strategy a = a -> Eval a | |||||
| using :: a -> Strategy a -> a | |||||
| withStrategy :: Strategy a -> a -> a | |||||
| rwhnf :: Strategy a | |||||
| rdeepseq :: NFData a => Strategy a | |||||
| r0 :: Strategy a | |||||
| rpar :: Strategy a | |||||
| seqPair :: Strategy a -> Strategy b -> Strategy (a, b) | |||||
| parPair :: Strategy a -> Strategy b -> Strategy (a, b) | |||||
| seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a, b, c) | |||||
| parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a, b, c) | |||||
| seqTraverse :: Traversable t => Strategy a -> Strategy (t a) | |||||
| parTraverse :: Traversable t => Strategy a -> Strategy (t a) | |||||
| parList :: Strategy a -> Strategy [a] | |||||
| seqList :: Strategy a -> Strategy [a] | |||||
| parListN :: Int -> Strategy a -> Strategy [a] | |||||
| parListChunk :: Int -> Strategy a -> Strategy [a] | |||||
| parMap :: Strategy b -> (a -> b) -> [a] -> [b] | |||||
| parBuffer :: Int -> Strategy a -> [a] -> [a] | |||||
| parListWHNF :: Strategy [a] | |||||
| parBufferWHNF :: Int -> Strategy [a] | |||||
| ($|) :: (a -> b) -> Strategy a -> a -> b | |||||
| ($||) :: (a -> b) -> Strategy a -> a -> b | |||||
| (.|) :: (b -> c) -> Strategy b -> (a -> b) -> a -> c | |||||
| (.||) :: (b -> c) -> Strategy b -> (a -> b) -> a -> c | |||||
| (-|) :: (a -> b) -> Strategy b -> (b -> c) -> a -> c | |||||
| (-||) :: (a -> b) -> Strategy b -> (b -> c) -> a -> c | |||||
| |||||
| unEval :: Eval a -> a | |||||
| class NFData a where | |||||
| |||||
| type Done = () | |||||
| demanding :: a -> Done -> a | |||||
| sparking :: a -> Done -> a | |||||
| (>|) :: Done -> Done -> Done | |||||
| (>||) :: Done -> Done -> Done |
A Strategy is a function that embodies a parallel evaluation strategy. The function traverses (parts of) its argument, evaluating subexpressions in parallel or in sequence.
A Strategy may do an arbitrary amount of evaluation of its argument, but should not return a value different from the one it was passed.
Parallel computations may be discarded by the runtime system if the program no longer requires their result, which is why a Strategy function returns a new value equivalent to the old value. The intention is that the program applies the Strategy to a structure, and then uses the returned value, discarding the old value. This idiom is expressed by the using function.
evaluate a value using the given Strategy.
using x s = s x
A Strategy that fully evaluates its argument
rdeepseq a = rnf a `pseq` a
Applies a strategy to the nth element of list when the head is demanded. More precisely:
- semantics: parBuffer n s = id :: [a] -> [a]
- dynamic behaviour: evalutates the nth element of the list when the head is demanded.
The idea is to provide a `rolling buffer' of length n. It is a better than parList for a lazy stream, because parList will evaluate the entire list, whereas parBuffer will only evaluate a fixed number of elements ahead.
Eval is an Applicative Functor that makes it easier to define parallel strategies that involve traversing structures. a Seq value will be evaluated strictly in sequence in its context, whereas a Par value wraps an expression that may be evaluated in parallel. The Applicative instance allows sequential composition, making it possible to describe an evaluateion strategy by composing Par and Seq with <*>. For example, parList :: Strategy a -> Strategy [a] parList strat = traverse (Par . (`using` strat)) seqPair :: Strategy a -> Strategy b -> Strategy (a,b) seqPair f g (a,b) = pure (,) <$> f a <*> g b | ||||||
| Constructors | ||||||
| ||||||
 Instances | ||||||
| Methods | ||
| ||
| Instances | ||