1 -----------------------------------------------------------------------------
3 -- Module : Control.Parallel.Strategies
4 -- Copyright : (c) The University of Glasgow 2001
5 -- License : BSD-style (see the file libraries/base/LICENSE)
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : non-portable
11 -- Parallel strategy combinators. See
12 -- <http://www.macs.hw.ac.uk/~dsg/gph/papers/html/Strategies/strategies.html>
13 -- for more information.
16 -- Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al.
18 -----------------------------------------------------------------------------
19 module Control.Parallel.Strategies (
20 -- * Strategy Type, Application and Semantics
23 using, demanding, sparking,
25 r0, rwhnf, NFData(..),
26 -- * Strategic Function Application
33 -- * Lists: Parallel Strategies
34 parList, parListN, parListNth, parListChunk,
35 parMap, parFlatMap, parZipWith,
36 -- * Lists: Sequential Strategies
37 seqList, seqListN, seqListNth, parBuffer,
40 -- * Deprecated types and functions
43 fstPairFstList, force, sforce
46 -- based on hslibs/concurrent/Strategies.lhs; see it for more detailed
49 import Control.Parallel as Parallel (par, pseq)
53 import qualified Data.IntMap (IntMap, toList)
54 import qualified Data.IntSet (IntSet, toList)
55 import qualified Data.Map (Map, toList)
56 import qualified Data.Set (Set, toList)
57 import qualified Data.Tree (Tree(..))
60 import Prelude hiding (seq)
61 import qualified Prelude (seq)
63 -- not a terribly portable way of getting at Ratio rep.
64 #ifdef __GLASGOW_HASKELL__
65 import GHC.Real (Ratio(..)) -- The basic defns for Ratio
69 import Hugs.Prelude(Ratio(..) )
73 import Ratio (Ratio(..) )
76 infixl 0 `using`,`demanding`,`sparking` -- weakest precedence!
78 infixr 2 >|| -- another name for par
79 infixr 3 >| -- another name for seq
80 infixl 6 $||, $| -- strategic function application (seq and par)
81 infixl 9 .|, .||, -|, -|| -- strategic (inverse) function composition
83 -- We need 'pseq', not the Prelude 'seq' here. See the documentation
84 -- with 'pseq' in Control.Parallel.
87 ------------------------------------------------------------------------------
88 -- * Strategy Type, Application and Semantics
89 ------------------------------------------------------------------------------
92 The basic combinators for strategies are 'par' and 'seq' but with types that
93 indicate that they only combine the results of a strategy application.
95 NB: This version can be used with Haskell 1.4 (GHC 2.05 and beyond), *but*
96 you won't get strategy checking on seq (only on par)!
98 The operators >| and >|| are alternative names for `seq` and `par`.
99 With the introduction of a Prelude function `seq` separating the Prelude
100 function from the Strategy function becomes a pain. The notation also matches
101 the notation for strategic function application.
106 -- | A strategy takes a value and returns a 'Done' value to indicate that
107 -- the specifed evaluation has been performed.
108 type Strategy a = a -> Done
111 -- | Evaluates the first argument before the second.
112 (>|) :: Done -> Done -> Done
116 -- | Evaluates the first argument in parallel with the second.
117 (>||) :: Done -> Done -> Done
122 -- | Takes a value and a strategy, and applies the strategy to the
123 -- value before returning the value. Used to express data-oriented
124 -- parallelism. @x \`using\` s@ is a projection on @x@, i.e. both:
126 -- [a retraction] @x \`using\` s@ ⊑ @x@
128 -- [idempotent] @(x \`using\` s) \`using\` s@ = @x \`using\` s@
130 using :: a -> Strategy a -> a
131 using x s = s x `seq` x
134 -- | Evaluates the second argument before the first.
135 -- Used to express control-oriented parallelism. The second
136 -- argument is usually a strategy application.
137 demanding :: a -> Done -> a
141 -- | Evaluates the second argument in parallel with the first.
142 -- Used to express control-oriented
143 -- parallelism. The second argument is usually a strategy application.
144 sparking :: a -> Done -> a
145 sparking = flip Parallel.par
146 -- Sparking should only be used
147 -- with a singleton sequence as it is not necessarily executed.
149 -- | A strategy corresponding to 'par':
150 -- @x \`par\` e@ = @e \`using\` sPar x@.
152 -- 'sPar' has been superceded by 'sparking'.
153 -- Replace @e \`using\` sPar x@ with @e \`sparking\` rwhnf x@.
154 {-# DEPRECATED sPar "Use sparking instead." #-}
155 sPar :: a -> Strategy b
156 sPar x y = x `par` ()
158 -- | A strategy corresponding to 'seq':
159 -- @x \`seq\` e@ = @e \`using\` sSeq x@.
161 -- 'sSeq' has been superceded by 'demanding'.
162 -- Replace @e \`using\` sSeq x@ with @e \`demanding\` rwhnf x@.
163 {-# DEPRECATED sSeq "Use demanding instead." #-}
164 sSeq :: a -> Strategy b
165 sSeq x y = x `seq` ()
167 -----------------------------------------------------------------------------
168 -- * Basic Strategies
169 -----------------------------------------------------------------------------
171 -- | Performs /no/ evaluation of its argument.
175 -- | Reduces its argument to weak head normal form.
180 -- | Reduces its argument to (head) normal form.
182 -- Default method. Useful for base types. A specific method is necessay for
186 class (NFData a, Integral a) => NFDataIntegral a
187 class (NFData a, Ord a) => NFDataOrd a
189 ------------------------------------------------------------------------------
190 -- * Strategic Function Application
191 ------------------------------------------------------------------------------
195 handy when writing pipeline parallelism asa sequence of @$@, @$|@ and
196 @$||@'s. There is no need of naming intermediate values in this case. The
197 separation of algorithm from strategy is achieved by allowing strategies
198 only as second arguments to @$|@ and @$||@.
201 -- | Sequential function application. The argument is evaluated using
202 -- the given strategy before it is given to the function.
203 ($|) :: (a -> b) -> Strategy a -> a -> b
204 f $| s = \ x -> f x `demanding` s x
206 -- | Parallel function application. The argument is evaluated using
207 -- the given strategy, in parallel with the function application.
208 ($||) :: (a -> b) -> Strategy a -> a -> b
209 f $|| s = \ x -> f x `sparking` s x
211 -- | Sequential function composition. The result of
212 -- the second function is evaluated using the given strategy,
213 -- and then given to the first function.
214 (.|) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)
215 (.|) f s g = \ x -> let gx = g x
216 in f gx `demanding` s gx
218 -- | Parallel function composition. The result of the second
219 -- function is evaluated using the given strategy,
220 -- in parallel with the application of the first function.
221 (.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)
222 (.||) f s g = \ x -> let gx = g x
223 in f gx `sparking` s gx
225 -- | Sequential inverse function composition,
226 -- for those who read their programs from left to right.
227 -- The result of the first function is evaluated using the
228 -- given strategy, and then given to the second function.
229 (-|) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)
230 (-|) f s g = \ x -> let fx = f x
231 in g fx `demanding` s fx
233 -- | Parallel inverse function composition,
234 -- for those who read their programs from left to right.
235 -- The result of the first function is evaluated using the
236 -- given strategy, in parallel with the application of the
238 (-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)
239 (-||) f s g = \ x -> let fx = f x
240 in g fx `sparking` s fx
242 ------------------------------------------------------------------------------
243 -- Marking a Strategy
244 ------------------------------------------------------------------------------
249 Actually, @markStrat@ sticks a label @n@ into the sparkname field of the
250 thread executing strategy @s@. Together with a runtime-system that supports
251 propagation of sparknames to the children this means that this strategy and
252 all its children have the sparkname @n@ (if the static sparkname field in
253 the @parGlobal@ annotation contains the value 1). Note, that the @SN@ field
254 of starting the marked strategy itself contains the sparkname of the parent
255 thread. The END event contains @n@ as sparkname.
259 markStrat :: Int -> Strategy a -> Strategy a
260 markStrat n s x = unsafePerformPrimIO (
261 _casm_ ``%r = set_sparkname(CurrentTSO, %0);'' n `thenPrimIO` \ z ->
265 -----------------------------------------------------------------------------
266 -- Strategy Instances and Functions
267 -----------------------------------------------------------------------------
269 -----------------------------------------------------------------------------
271 -----------------------------------------------------------------------------
274 We currently support up to 9-tuples. If you need longer tuples you have to
275 add the instance explicitly to your program.
278 instance (NFData a, NFData b) => NFData (a,b) where
279 rnf (x,y) = rnf x `seq` rnf y
281 instance (NFData a, NFData b, NFData c) => NFData (a,b,c) where
282 rnf (x,y,z) = rnf x `seq` rnf y `seq` rnf z
284 instance (NFData a, NFData b, NFData c, NFData d) => NFData (a,b,c,d) where
285 rnf (x1,x2,x3,x4) = rnf x1 `seq`
290 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5) =>
291 NFData (a1, a2, a3, a4, a5) where
292 rnf (x1, x2, x3, x4, x5) =
299 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6) =>
300 NFData (a1, a2, a3, a4, a5, a6) where
301 rnf (x1, x2, x3, x4, x5, x6) =
309 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7) =>
310 NFData (a1, a2, a3, a4, a5, a6, a7) where
311 rnf (x1, x2, x3, x4, x5, x6, x7) =
320 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8) =>
321 NFData (a1, a2, a3, a4, a5, a6, a7, a8) where
322 rnf (x1, x2, x3, x4, x5, x6, x7, x8) =
332 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8, NFData a9) =>
333 NFData (a1, a2, a3, a4, a5, a6, a7, a8, a9) where
334 rnf (x1, x2, x3, x4, x5, x6, x7, x8, x9) =
345 -- | Apply two strategies to the elements of a pair sequentially
346 -- from left to right.
347 seqPair :: Strategy a -> Strategy b -> Strategy (a,b)
348 seqPair strata stratb (x,y) = strata x `seq` stratb y
350 -- | Apply two strategies to the elements of a pair in parallel.
351 parPair :: Strategy a -> Strategy b -> Strategy (a,b)
352 parPair strata stratb (x,y) = strata x `par` stratb y `par` ()
353 -- The reason for the last 'par' is so that the strategy terminates
354 -- quickly. This is important if the strategy is used as the 1st
357 -- | Apply three strategies to the elements of a triple in sequentially
358 -- from left to right.
359 seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)
360 seqTriple strata stratb stratc p@(x,y,z) =
365 -- | Apply three strategies to the elements of a triple in parallel.
366 parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)
367 parTriple strata stratb stratc (x,y,z) =
373 -----------------------------------------------------------------------------
375 -----------------------------------------------------------------------------
378 Weak head normal form and normal form are identical for integers, so the
379 default rnf is sufficient.
382 instance NFData Integer
383 instance NFData Float
384 instance NFData Double
387 instance NFData Int16
388 instance NFData Int32
389 instance NFData Int64
391 instance NFData Word8
392 instance NFData Word16
393 instance NFData Word32
394 instance NFData Word64
396 instance NFDataIntegral Int
397 instance NFDataOrd Int
399 --Rational and complex numbers.
401 instance (Integral a, NFData a) => NFData (Ratio a) where
402 rnf (x:%y) = rnf x `seq`
406 instance (RealFloat a, NFData a) => NFData (Complex a) where
407 rnf (x:+y) = rnf x `seq`
415 -----------------------------------------------------------------------------
416 -- Various library types
417 -----------------------------------------------------------------------------
419 instance NFData a => NFData (Maybe a) where
423 instance (NFData a, NFData b) => NFData (Either a b) where
425 rnf (Right y) = rnf y
427 instance (NFData k, NFData a) => NFData (Data.Map.Map k a) where
428 rnf = rnf . Data.Map.toList
430 instance NFData a => NFData (Data.Set.Set a) where
431 rnf = rnf . Data.Set.toList
433 instance NFData a => NFData (Data.Tree.Tree a) where
434 rnf (Data.Tree.Node r f) = rnf r `seq` rnf f
436 instance NFData a => NFData (Data.IntMap.IntMap a) where
437 rnf = rnf . Data.IntMap.toList
439 instance NFData Data.IntSet.IntSet where
440 rnf = rnf . Data.IntSet.toList
442 -----------------------------------------------------------------------------
444 -----------------------------------------------------------------------------
446 instance NFData a => NFData [a] where
448 rnf (x:xs) = rnf x `seq` rnf xs
450 ----------------------------------------------------------------------------
451 -- * Lists: Parallel Strategies
452 ----------------------------------------------------------------------------
454 -- | Applies a strategy to every element of a list in parallel.
455 parList :: Strategy a -> Strategy [a]
456 parList strat [] = ()
457 parList strat (x:xs) = strat x `par` (parList strat xs)
459 -- | Applies a strategy to the first @n@ elements of a list in parallel.
460 parListN :: (Integral b) => b -> Strategy a -> Strategy [a]
461 parListN n strat [] = ()
462 parListN 0 strat xs = ()
463 parListN n strat (x:xs) = strat x `par` (parListN (n-1) strat xs)
465 -- | Evaluates @n@ elements of the spine of the argument list and applies
466 -- the given strategy to the @n@th element (if there is one) in parallel with
467 -- the result. E.g. @parListNth 2 [e1, e2, e3]@ evaluates @e3@.
468 parListNth :: Int -> Strategy a -> Strategy [a]
469 parListNth n strat xs
471 | otherwise = strat (head rest) `par` ()
475 -- | Splits a list into chunks (sub-sequences) of length @n@,
476 -- and applies a strategy sequentially to the elements in each
477 -- chunk. The chunks are evaluated in parallel.
478 -- This is useful for increasing the grain size.
479 parListChunk :: Int -> Strategy a -> Strategy [a]
480 parListChunk n strat [] = ()
481 parListChunk n strat xs = seqListN n strat xs `par`
482 parListChunk n strat (drop n xs)
484 -- | Applies a function to each element of a list and
485 -- and evaluates the result list in parallel,
486 -- using the given strategy for each element.
487 parMap :: Strategy b -> (a -> b) -> [a] -> [b]
488 parMap strat f xs = map f xs `using` parList strat
490 -- | Uses 'parMap' to apply a list-valued function to each
491 -- element of a list in parallel, and concatenates the results.
492 parFlatMap :: Strategy [b] -> (a -> [b]) -> [a] -> [b]
493 parFlatMap strat f xs = concat (parMap strat f xs)
495 -- | Zips together two lists using a function,
496 -- and evaluates the result list in parallel.
497 parZipWith :: Strategy c -> (a -> b -> c) -> [a] -> [b] -> [c]
498 parZipWith strat z as bs =
499 zipWith z as bs `using` parList strat
501 ----------------------------------------------------------------------------
502 -- * Lists: Sequential Strategies
503 ----------------------------------------------------------------------------
505 -- | Sequentially applies a strategy to each element of a list.
506 seqList :: Strategy a -> Strategy [a]
507 seqList strat [] = ()
508 seqList strat (x:xs) = strat x `seq` (seqList strat xs)
510 -- | Sequentially applies a strategy to the first n elements of a list.
511 seqListN :: (Integral a) => a -> Strategy b -> Strategy [b]
512 seqListN n strat [] = ()
513 seqListN 0 strat xs = ()
514 seqListN n strat (x:xs) = strat x `seq` (seqListN (n-1) strat xs)
516 -- | Applies a strategy to the @n@th element of a list
517 -- (if there is one) before returning the result.
518 -- E.g. @seqListNth 2 [e1, e2, e3]@ evaluates @e3@.
519 seqListNth :: Int -> Strategy b -> Strategy [b]
520 seqListNth n strat xs
522 | otherwise = strat (head rest)
526 -- | Parallel n-buffer function added for the revised version of the strategies
527 -- paper. 'parBuffer' supersedes the older @fringeList@. It has the same
529 parBuffer :: Int -> Strategy a -> [a] -> [a]
531 return xs (start n xs)
533 return (x:xs) (y:ys) = (x:return xs ys) `sparking` s y
538 start n (y:ys) = start (n-1) ys `sparking` s y
541 'fringeList' implements a `rolling buffer' of length n, i.e.applies a
542 strategy to the nth element of list when the head is demanded. More
545 semantics: fringeList n s = id :: [b] -> [b]
546 dynamic behaviour: evalutates the nth element of the list when the
549 The idea is to provide a `rolling buffer' of length n.
550 fringeList :: (Integral a) => a -> Strategy b -> [b] -> [b]
551 fringeList n strat [] = []
552 fringeList n strat (r:rs) =
553 seqListNth n strat rs `par`
554 r:fringeList n strat rs
557 ------------------------------------------------------------------------------
559 ------------------------------------------------------------------------------
560 instance (Ix a, NFData a, NFData b) => NFData (Array a b) where
561 rnf x = rnf (bounds x) `seq` seqList rnf (elems x) `seq` ()
563 -- | Apply a strategy to all elements of an array sequentially.
564 seqArr :: (Ix b) => Strategy a -> Strategy (Array b a)
565 seqArr s arr = seqList s (elems arr)
567 -- | Apply a strategy to all elements of an array in parallel.
568 parArr :: (Ix b) => Strategy a -> Strategy (Array b a)
569 parArr s arr = parList s (elems arr)
571 {-# DEPRECATED Assoc "Does not belong in Control.Parallel.Strategies" #-}
572 data Assoc a b = a := b deriving ()
574 instance (NFData a, NFData b) => NFData (Assoc a b) where
575 rnf (x := y) = rnf x `seq` rnf y `seq` ()
577 ------------------------------------------------------------------------------
578 -- * Some strategies specific for Lolita
579 ------------------------------------------------------------------------------
581 {-# DEPRECATED fstPairFstList "This was just an example. Write your own." #-}
582 fstPairFstList :: (NFData a) => Strategy [(a,b)]
583 fstPairFstList = seqListN 1 (seqPair rwhnf r0)
585 -- Some HACKs for Lolita. AFAIK force is just another name for our rnf and
586 -- sforce is a shortcut (definition here is identical to the one in Force.lhs)
588 {-# DEPRECATED force, sforce "Lolita-specific hacks." #-}
589 force :: (NFData a) => a -> a
590 sforce :: (NFData a) => a -> b -> b
593 sforce x y = force x `seq` y