----------------------------------------------------------------------------- -- | -- Module : Control.Parallel.Strategies -- Copyright : (c) The University of Glasgow 2001 -- License : BSD-style (see the file libraries/base/LICENSE) -- -- Maintainer : libraries@haskell.org -- Stability : experimental -- Portability : non-portable -- -- Parallel strategy combinators. See -- -- for more information. -- -- Original authors: -- Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al. -- ----------------------------------------------------------------------------- module Control.Parallel.Strategies ( -- * Strategy Type, Application and Semantics Done, Strategy, (>|), (>||), using, demanding, sparking, -- * Basic Strategies r0, rwhnf, NFData(..), -- * Strategic Function Application ($|), ($||), (.|), (.||), (-|), (-||), -- * Tuples seqPair, parPair, seqTriple, parTriple, -- * Lists: Parallel Strategies parList, parListN, parListNth, parListChunk, parMap, parFlatMap, parZipWith, -- * Lists: Sequential Strategies seqList, seqListN, seqListNth, parBuffer, -- * Arrays seqArr, parArr, -- * Deprecated types and functions sPar, sSeq, Assoc(..), fstPairFstList, force, sforce ) where -- based on hslibs/concurrent/Strategies.lhs; see it for more detailed -- code comments. import Control.Parallel as Parallel (par, pseq) import Data.Array import Data.Complex import Data.Int import qualified Data.IntMap (IntMap, toList) import qualified Data.IntSet (IntSet, toList) import qualified Data.Map (Map, toList) import qualified Data.Set (Set, toList) import qualified Data.Tree (Tree(..)) import Data.Word import Prelude hiding (seq) import qualified Prelude (seq) -- not a terribly portable way of getting at Ratio rep. #ifdef __GLASGOW_HASKELL__ import GHC.Real (Ratio(..)) -- The basic defns for Ratio #endif #ifdef __HUGS__ import Hugs.Prelude(Ratio(..) ) #endif #ifdef __NHC__ import Ratio (Ratio(..) ) #endif infixl 0 `using`,`demanding`,`sparking` -- weakest precedence! infixr 2 >|| -- another name for par infixr 3 >| -- another name for seq infixl 6 $||, $| -- strategic function application (seq and par) infixl 9 .|, .||, -|, -|| -- strategic (inverse) function composition infixl 0 `seq` -- We need 'pseq', not the Prelude 'seq' here. See the documentation -- with 'pseq' in Control.Parallel. seq = Parallel.pseq ------------------------------------------------------------------------------ -- * Strategy Type, Application and Semantics ------------------------------------------------------------------------------ {- The basic combinators for strategies are 'par' and 'seq' but with types that indicate that they only combine the results of a strategy application. NB: This version can be used with Haskell 1.4 (GHC 2.05 and beyond), *but* you won't get strategy checking on seq (only on par)! The operators >| and >|| are alternative names for `seq` and `par`. With the introduction of a Prelude function `seq` separating the Prelude function from the Strategy function becomes a pain. The notation also matches the notation for strategic function application. -} type Done = () -- | A strategy takes a value and returns a 'Done' value to indicate that -- the specifed evaluation has been performed. type Strategy a = a -> Done -- | Evaluates the first argument before the second. (>|) :: Done -> Done -> Done {-# INLINE (>|) #-} (>|) = Prelude.seq -- | Evaluates the first argument in parallel with the second. (>||) :: Done -> Done -> Done {-# INLINE (>||) #-} (>||) = Parallel.par -- | Takes a value and a strategy, and applies the strategy to the -- value before returning the value. Used to express data-oriented -- parallelism. @x \`using\` s@ is a projection on @x@, i.e. both: -- -- [a retraction] @x \`using\` s@ ⊑ @x@ -- -- [idempotent] @(x \`using\` s) \`using\` s@ = @x \`using\` s@ -- using :: a -> Strategy a -> a using x s = s x `seq` x -- | Evaluates the second argument before the first. -- Used to express control-oriented parallelism. The second -- argument is usually a strategy application. demanding :: a -> Done -> a demanding = flip seq -- | Evaluates the second argument in parallel with the first. -- Used to express control-oriented -- parallelism. The second argument is usually a strategy application. sparking :: a -> Done -> a sparking = flip Parallel.par -- Sparking should only be used -- with a singleton sequence as it is not necessarily executed. -- | A strategy corresponding to 'par': -- @x \`par\` e@ = @e \`using\` sPar x@. -- -- 'sPar' has been superceded by 'sparking'. -- Replace @e \`using\` sPar x@ with @e \`sparking\` rwhnf x@. {-# DEPRECATED sPar "Use sparking instead." #-} sPar :: a -> Strategy b sPar x y = x `par` () -- | A strategy corresponding to 'seq': -- @x \`seq\` e@ = @e \`using\` sSeq x@. -- -- 'sSeq' has been superceded by 'demanding'. -- Replace @e \`using\` sSeq x@ with @e \`demanding\` rwhnf x@. {-# DEPRECATED sSeq "Use demanding instead." #-} sSeq :: a -> Strategy b sSeq x y = x `seq` () ----------------------------------------------------------------------------- -- * Basic Strategies ----------------------------------------------------------------------------- -- | Performs /no/ evaluation of its argument. r0 :: Strategy a r0 x = () -- | Reduces its argument to weak head normal form. rwhnf :: Strategy a rwhnf x = x `seq` () class NFData a where -- | Reduces its argument to (head) normal form. rnf :: Strategy a -- Default method. Useful for base types. A specific method is necessay for -- constructed types rnf = rwhnf class (NFData a, Integral a) => NFDataIntegral a class (NFData a, Ord a) => NFDataOrd a ------------------------------------------------------------------------------ -- * Strategic Function Application ------------------------------------------------------------------------------ {- These are very handy when writing pipeline parallelism asa sequence of @$@, @$|@ and @$||@'s. There is no need of naming intermediate values in this case. The separation of algorithm from strategy is achieved by allowing strategies only as second arguments to @$|@ and @$||@. -} -- | Sequential function application. The argument is evaluated using -- the given strategy before it is given to the function. ($|) :: (a -> b) -> Strategy a -> a -> b f $| s = \ x -> f x `demanding` s x -- | Parallel function application. The argument is evaluated using -- the given strategy, in parallel with the function application. ($||) :: (a -> b) -> Strategy a -> a -> b f $|| s = \ x -> f x `sparking` s x -- | Sequential function composition. The result of -- the second function is evaluated using the given strategy, -- and then given to the first function. (.|) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c) (.|) f s g = \ x -> let gx = g x in f gx `demanding` s gx -- | Parallel function composition. The result of the second -- function is evaluated using the given strategy, -- in parallel with the application of the first function. (.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c) (.||) f s g = \ x -> let gx = g x in f gx `sparking` s gx -- | Sequential inverse function composition, -- for those who read their programs from left to right. -- The result of the first function is evaluated using the -- given strategy, and then given to the second function. (-|) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c) (-|) f s g = \ x -> let fx = f x in g fx `demanding` s fx -- | Parallel inverse function composition, -- for those who read their programs from left to right. -- The result of the first function is evaluated using the -- given strategy, in parallel with the application of the -- second function. (-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c) (-||) f s g = \ x -> let fx = f x in g fx `sparking` s fx ------------------------------------------------------------------------------ -- Marking a Strategy ------------------------------------------------------------------------------ {- Marking a strategy. Actually, @markStrat@ sticks a label @n@ into the sparkname field of the thread executing strategy @s@. Together with a runtime-system that supports propagation of sparknames to the children this means that this strategy and all its children have the sparkname @n@ (if the static sparkname field in the @parGlobal@ annotation contains the value 1). Note, that the @SN@ field of starting the marked strategy itself contains the sparkname of the parent thread. The END event contains @n@ as sparkname. -} #if 0 markStrat :: Int -> Strategy a -> Strategy a markStrat n s x = unsafePerformPrimIO ( _casm_ ``%r = set_sparkname(CurrentTSO, %0);'' n `thenPrimIO` \ z -> returnPrimIO (s x)) #endif ----------------------------------------------------------------------------- -- Strategy Instances and Functions ----------------------------------------------------------------------------- ----------------------------------------------------------------------------- -- * Tuples ----------------------------------------------------------------------------- {- We currently support up to 9-tuples. If you need longer tuples you have to add the instance explicitly to your program. -} instance (NFData a, NFData b) => NFData (a,b) where rnf (x,y) = rnf x `seq` rnf y instance (NFData a, NFData b, NFData c) => NFData (a,b,c) where rnf (x,y,z) = rnf x `seq` rnf y `seq` rnf z instance (NFData a, NFData b, NFData c, NFData d) => NFData (a,b,c,d) where rnf (x1,x2,x3,x4) = rnf x1 `seq` rnf x2 `seq` rnf x3 `seq` rnf x4 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5) => NFData (a1, a2, a3, a4, a5) where rnf (x1, x2, x3, x4, x5) = rnf x1 `seq` rnf x2 `seq` rnf x3 `seq` rnf x4 `seq` rnf x5 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6) => NFData (a1, a2, a3, a4, a5, a6) where rnf (x1, x2, x3, x4, x5, x6) = rnf x1 `seq` rnf x2 `seq` rnf x3 `seq` rnf x4 `seq` rnf x5 `seq` rnf x6 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7) => NFData (a1, a2, a3, a4, a5, a6, a7) where rnf (x1, x2, x3, x4, x5, x6, x7) = rnf x1 `seq` rnf x2 `seq` rnf x3 `seq` rnf x4 `seq` rnf x5 `seq` rnf x6 `seq` rnf x7 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8) => NFData (a1, a2, a3, a4, a5, a6, a7, a8) where rnf (x1, x2, x3, x4, x5, x6, x7, x8) = rnf x1 `seq` rnf x2 `seq` rnf x3 `seq` rnf x4 `seq` rnf x5 `seq` rnf x6 `seq` rnf x7 `seq` rnf x8 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8, NFData a9) => NFData (a1, a2, a3, a4, a5, a6, a7, a8, a9) where rnf (x1, x2, x3, x4, x5, x6, x7, x8, x9) = rnf x1 `seq` rnf x2 `seq` rnf x3 `seq` rnf x4 `seq` rnf x5 `seq` rnf x6 `seq` rnf x7 `seq` rnf x8 `seq` rnf x9 -- | Apply two strategies to the elements of a pair sequentially -- from left to right. seqPair :: Strategy a -> Strategy b -> Strategy (a,b) seqPair strata stratb (x,y) = strata x `seq` stratb y -- | Apply two strategies to the elements of a pair in parallel. parPair :: Strategy a -> Strategy b -> Strategy (a,b) parPair strata stratb (x,y) = strata x `par` stratb y `par` () -- The reason for the last 'par' is so that the strategy terminates -- quickly. This is important if the strategy is used as the 1st -- argument of a seq -- | Apply three strategies to the elements of a triple in sequentially -- from left to right. seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c) seqTriple strata stratb stratc p@(x,y,z) = strata x `seq` stratb y `seq` stratc z -- | Apply three strategies to the elements of a triple in parallel. parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c) parTriple strata stratb stratc (x,y,z) = strata x `par` stratb y `par` stratc z `par` () ----------------------------------------------------------------------------- -- Atomic types ----------------------------------------------------------------------------- {- Weak head normal form and normal form are identical for integers, so the default rnf is sufficient. -} instance NFData Int instance NFData Integer instance NFData Float instance NFData Double instance NFData Int8 instance NFData Int16 instance NFData Int32 instance NFData Int64 instance NFData Word8 instance NFData Word16 instance NFData Word32 instance NFData Word64 instance NFDataIntegral Int instance NFDataOrd Int --Rational and complex numbers. instance (Integral a, NFData a) => NFData (Ratio a) where rnf (x:%y) = rnf x `seq` rnf y `seq` () instance (RealFloat a, NFData a) => NFData (Complex a) where rnf (x:+y) = rnf x `seq` rnf y `seq` () instance NFData Char instance NFData Bool instance NFData () ----------------------------------------------------------------------------- -- Various library types ----------------------------------------------------------------------------- instance NFData a => NFData (Maybe a) where rnf Nothing = () rnf (Just x) = rnf x instance (NFData a, NFData b) => NFData (Either a b) where rnf (Left x) = rnf x rnf (Right y) = rnf y instance (NFData k, NFData a) => NFData (Data.Map.Map k a) where rnf = rnf . Data.Map.toList instance NFData a => NFData (Data.Set.Set a) where rnf = rnf . Data.Set.toList instance NFData a => NFData (Data.Tree.Tree a) where rnf (Data.Tree.Node r f) = rnf r `seq` rnf f instance NFData a => NFData (Data.IntMap.IntMap a) where rnf = rnf . Data.IntMap.toList instance NFData Data.IntSet.IntSet where rnf = rnf . Data.IntSet.toList ----------------------------------------------------------------------------- -- Lists ----------------------------------------------------------------------------- instance NFData a => NFData [a] where rnf [] = () rnf (x:xs) = rnf x `seq` rnf xs ---------------------------------------------------------------------------- -- * Lists: Parallel Strategies ---------------------------------------------------------------------------- -- | Applies a strategy to every element of a list in parallel. parList :: Strategy a -> Strategy [a] parList strat [] = () parList strat (x:xs) = strat x `par` (parList strat xs) -- | Applies a strategy to the first @n@ elements of a list in parallel. parListN :: (Integral b) => b -> Strategy a -> Strategy [a] parListN n strat [] = () parListN 0 strat xs = () parListN n strat (x:xs) = strat x `par` (parListN (n-1) strat xs) -- | Evaluates @n@ elements of the spine of the argument list and applies -- the given strategy to the @n@th element (if there is one) in parallel with -- the result. E.g. @parListNth 2 [e1, e2, e3]@ evaluates @e3@. parListNth :: Int -> Strategy a -> Strategy [a] parListNth n strat xs | null rest = () | otherwise = strat (head rest) `par` () where rest = drop n xs -- | Splits a list into chunks (sub-sequences) of length @n@, -- and applies a strategy sequentially to the elements in each -- chunk. The chunks are evaluated in parallel. -- This is useful for increasing the grain size. parListChunk :: Int -> Strategy a -> Strategy [a] parListChunk n strat [] = () parListChunk n strat xs = seqListN n strat xs `par` parListChunk n strat (drop n xs) -- | Applies a function to each element of a list and -- and evaluates the result list in parallel, -- using the given strategy for each element. parMap :: Strategy b -> (a -> b) -> [a] -> [b] parMap strat f xs = map f xs `using` parList strat -- | Uses 'parMap' to apply a list-valued function to each -- element of a list in parallel, and concatenates the results. parFlatMap :: Strategy [b] -> (a -> [b]) -> [a] -> [b] parFlatMap strat f xs = concat (parMap strat f xs) -- | Zips together two lists using a function, -- and evaluates the result list in parallel. parZipWith :: Strategy c -> (a -> b -> c) -> [a] -> [b] -> [c] parZipWith strat z as bs = zipWith z as bs `using` parList strat ---------------------------------------------------------------------------- -- * Lists: Sequential Strategies ---------------------------------------------------------------------------- -- | Sequentially applies a strategy to each element of a list. seqList :: Strategy a -> Strategy [a] seqList strat [] = () seqList strat (x:xs) = strat x `seq` (seqList strat xs) -- | Sequentially applies a strategy to the first n elements of a list. {-# SPECIALISE seqListN :: Int -> Strategy b -> Strategy [b] #-} seqListN :: (Integral a) => a -> Strategy b -> Strategy [b] seqListN n strat [] = () seqListN 0 strat xs = () seqListN n strat (x:xs) = strat x `seq` (seqListN (n-1) strat xs) -- | Applies a strategy to the @n@th element of a list -- (if there is one) before returning the result. -- E.g. @seqListNth 2 [e1, e2, e3]@ evaluates @e3@. seqListNth :: Int -> Strategy b -> Strategy [b] seqListNth n strat xs | null rest = () | otherwise = strat (head rest) where rest = drop n xs -- | 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. -- -- 'parBuffer' has been added for the revised version of the strategies -- paper and supersedes the older @fringeList@. parBuffer :: Int -> Strategy a -> [a] -> [a] parBuffer n s xs = return xs (start n xs) where return (x:xs) (y:ys) = (x:return xs ys) `sparking` s y return xs [] = xs start n [] = [] start 0 ys = ys start n (y:ys) = start (n-1) ys `sparking` s y {- 'fringeList' implements a `rolling buffer' of length n, i.e.applies a strategy to the nth element of list when the head is demanded. More precisely: semantics: fringeList n s = id :: [b] -> [b] 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. fringeList :: (Integral a) => a -> Strategy b -> [b] -> [b] fringeList n strat [] = [] fringeList n strat (r:rs) = seqListNth n strat rs `par` r:fringeList n strat rs -} ------------------------------------------------------------------------------ -- * Arrays ------------------------------------------------------------------------------ instance (Ix a, NFData a, NFData b) => NFData (Array a b) where rnf x = rnf (bounds x) `seq` seqList rnf (elems x) `seq` () -- | Apply a strategy to all elements of an array sequentially. seqArr :: (Ix b) => Strategy a -> Strategy (Array b a) seqArr s arr = seqList s (elems arr) -- | Apply a strategy to all elements of an array in parallel. parArr :: (Ix b) => Strategy a -> Strategy (Array b a) parArr s arr = parList s (elems arr) {-# DEPRECATED Assoc "Does not belong in Control.Parallel.Strategies" #-} data Assoc a b = a := b deriving () instance (NFData a, NFData b) => NFData (Assoc a b) where rnf (x := y) = rnf x `seq` rnf y `seq` () ------------------------------------------------------------------------------ -- * Some strategies specific for Lolita ------------------------------------------------------------------------------ {-# DEPRECATED fstPairFstList "This was just an example. Write your own." #-} fstPairFstList :: (NFData a) => Strategy [(a,b)] fstPairFstList = seqListN 1 (seqPair rwhnf r0) -- Some HACKs for Lolita. AFAIK force is just another name for our rnf and -- sforce is a shortcut (definition here is identical to the one in Force.lhs) {-# DEPRECATED force, sforce "Lolita-specific hacks." #-} force :: (NFData a) => a -> a sforce :: (NFData a) => a -> b -> b force = id $| rnf sforce x y = force x `seq` y