X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=Control%2FParallel%2FStrategies.hs;h=dad5287b74c56892ae85b7a01fed926c9c31ef95;hb=ec129314cd6ee28c370e1a4d2a9241ee965ce069;hp=294239bf0ae1c1c3f5b96ea2b8265a14f8e8c0b2;hpb=b6ef4d7236a944f4ffed7aaa0fa8fcfe18cb77b9;p=haskell-directory.git diff --git a/Control/Parallel/Strategies.hs b/Control/Parallel/Strategies.hs index 294239b..dad5287 100644 --- a/Control/Parallel/Strategies.hs +++ b/Control/Parallel/Strategies.hs @@ -8,26 +8,57 @@ -- Stability : experimental -- Portability : non-portable -- --- Parallel strategy combinators --- ------------------------------------------------------------------------------ -module Control.Parallel.Strategies where - --- based on hslibs/concurrent/Strategies.lhs; see it for more detailed --- code comments. Original authors: +-- 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 -#ifdef __HADDOCK__ -import Prelude -#endif +-- based on hslibs/concurrent/Strategies.lhs; see it for more detailed +-- code comments. -import Control.Parallel as Parallel -import Data.Ix +import Control.Parallel as Parallel (par, pseq) import Data.Array import Data.Complex -import Data.Ratio +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__ @@ -49,93 +80,104 @@ infixr 3 >| -- another name for seq infixl 6 $||, $| -- strategic function application (seq and par) infixl 9 .|, .||, -|, -|| -- strategic (inverse) function composition +-- We need 'pseq', not the Prelude 'seq' here. See the documentation +-- with 'pseq' in Control.Parallel. +seq = Parallel.pseq + ------------------------------------------------------------------------------ --- Strategy Type, Application and Semantics +-- * Strategy Type, Application and Semantics ------------------------------------------------------------------------------ -type Done = () -type Strategy a = a -> Done {- -A strategy takes a value and returns a dummy `done' value to indicate that -the specifed evaluation has been performed. - -The basic combinators for strategies are @par@ and @seq@ but with types that +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 infix fcts >| and >|| are alternative names for `seq` and `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. -} -{- -par and seq have the same types as before; >| and >|| are more specific -and can only be used when composing strategies. --} +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 + -(>|), (>||) :: Done -> Done -> Done +-- | Evaluates the first argument before the second. +(>|) :: Done -> Done -> Done {-# INLINE (>|) #-} -{-# 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 -{- -using takes a strategy and a value, 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 - - - and idempotent: (x `using` s) `using` s = x `using` s +-- | 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 -demanding and sparking are used to express control-oriented -parallelism. Their second argument is usually a sequence of strategy -applications combined `par` and `seq`. Sparking should only be used -with a singleton sequence as it is not necessarily excuted --} -demanding, sparking :: a -> Done -> a -demanding = flip Parallel.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. -{- -sPar and sSeq have been superceded by sparking and demanding: replace - e `using` sPar x with e `sparking` x - e `using` sSeq x with e `demanding` x - -sPar is a strategy corresponding to par. i.e. x `par` e <=> e `using` sPar x --} - +-- | 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` () -{- -sSeq is a strategy corresponding to seq. i.e. x `seq` e <=> e `using` sSeq x --} +-- | 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 +-- * Basic Strategies ----------------------------------------------------------------------------- --- r0 performs *no* evaluation on its argument. +-- | Performs /no/ evaluation of its argument. r0 :: Strategy a r0 x = () ---rwhnf reduces its argument to weak head normal form. +-- | Reduces its argument to weak head normal form. rwhnf :: Strategy a rwhnf x = x `seq` () class NFData a where - -- rnf reduces its argument to (head) normal form + -- | Reduces its argument to (head) normal form. rnf :: Strategy a -- Default method. Useful for base types. A specific method is necessay for -- constructed types @@ -145,40 +187,55 @@ class (NFData a, Integral a) => NFDataIntegral a class (NFData a, Ord a) => NFDataOrd a ------------------------------------------------------------------------------ --- Strategic Function Application +-- * Strategic Function Application ------------------------------------------------------------------------------ {- -The two infix functions @$|@ and @$||@ perform sequential and parallel -function application, respectively. They are parameterised with a strategy -that is applied to the argument of the function application. This is very -handy when writing pipeline parallelism as a 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 +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 @$||@. -} -($|), ($||) :: (a -> b) -> Strategy a -> a -> b - +-- | 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 -f $|| s = \ x -> f x `sparking` s x - -{- -The same thing for function composition (.| and .||) and inverse function -composition (-| and -||) for those who read their programs from left to -right. --} -(.|), (.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c) -(-|), (-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c) +-- | 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 @@ -210,7 +267,7 @@ markStrat n s x = unsafePerformPrimIO ( ----------------------------------------------------------------------------- ----------------------------------------------------------------------------- --- Tuples +-- * Tuples ----------------------------------------------------------------------------- {- @@ -285,24 +342,27 @@ instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFDa 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 -{- -The reason for the second `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` @@ -310,6 +370,10 @@ parTriple strata stratb stratc (x,y,z) = stratc z `par` () +----------------------------------------------------------------------------- +-- Atomic types +----------------------------------------------------------------------------- + {- Weak head normal form and normal form are identical for integers, so the default rnf is sufficient. @@ -319,6 +383,16 @@ 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 @@ -339,31 +413,58 @@ instance NFData Bool instance NFData () ----------------------------------------------------------------------------- --- Lists ----------------------------------------------------------------------------- +-- 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 +-- * Lists: Parallel Strategies ---------------------------------------------------------------------------- --- | Applies a strategy to every element of a list in parallel +-- | 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 +-- | 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 --- `strat' to the Nth element (if there is one) in parallel with the --- result. e.g. parListNth 2 [e1, e2, e3] evaluates e2 +-- | 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 = () @@ -371,47 +472,50 @@ parListNth n strat xs where rest = drop n xs --- | 'parListChunk' sequentially applies a strategy to chunks --- (sub-sequences) of a list in parallel. Useful to increase grain size +-- | 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) --- | 'parMap' applies a function to each element of the argument list in --- parallel. The result of the function is evaluated using `strat' +-- | 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 +parMap strat f xs = map f xs `using` parList strat --- | 'parFlatMap' uses 'parMap' to apply a list-valued function to each --- element of the argument list in parallel. The result of the function --- is evaluated using `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) --- | 'parZipWith' zips together two lists with a function z in parallel +-- | 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 +-- * Lists: Sequential Strategies ---------------------------------------------------------------------------- --- | Sequentially applies a strategy to each element of a list +-- | 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 +-- | Sequentially applies a strategy to the first n elements of a list. 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) --- | 'seqListNth' applies a strategy to the Nth element of it's argument --- (if there is one) before returning the result. e.g. seqListNth 2 [e1, --- e2, e3] evaluates e2 +-- | 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 = () @@ -420,7 +524,7 @@ seqListNth n strat xs rest = drop n xs -- | Parallel n-buffer function added for the revised version of the strategies --- paper. 'parBuffer' supersedes the older 'fringeList'. It has the same +-- paper. 'parBuffer' supersedes the older @fringeList@. It has the same -- semantics. parBuffer :: Int -> Strategy a -> [a] -> [a] parBuffer n s xs = @@ -451,36 +555,37 @@ fringeList n strat (r:rs) = -} ------------------------------------------------------------------------------ --- Arrays +-- * 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 in parallel. This can be done --- either in sequentially or in parallel (same as with lists, really). +-- | 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) --- Associations maybe useful even without mentioning Arrays. - +{-# 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 +-- * 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