parallel 3.2.0.6 → 3.3.0.0
raw patch · 5 files changed
Files
- Control/Parallel.hs +23/−11
- Control/Parallel/Strategies.hs +295/−201
- Control/Seq.hs +13/−3
- changelog.md +42/−7
- parallel.cabal +31/−7
Control/Parallel.hs view
@@ -10,8 +10,16 @@ -- Stability : stable -- Portability : portable ----- Parallel Constructs+-- Parallel constructs. --+-- A common pattern to evaluate two values in parallel is:+--+-- > x `par` y `pseq` someFunc x y+--+-- The effect of this pattern is to cause @x@ to be evaluated in+-- parallel with @y@. When the evaluation of @y@ is complete, computation+-- proceeds by evaluating @someFunc x y@.+-- ----------------------------------------------------------------------------- module Control.Parallel (@@ -19,10 +27,10 @@ ) where #ifdef __GLASGOW_HASKELL__-import qualified GHC.Conc ( par, pseq )+import qualified GHC.Conc (par, pseq)+#endif infixr 0 `par`, `pseq`-#endif -- Maybe parIO and the like could be added here later. @@ -30,7 +38,8 @@ -- argument in parallel with the second. Returns the value of the -- second argument. ----- @a ``par`` b@ is exactly equivalent semantically to @b@.+-- The result of @a ``par`` b@ is always @b@, regardless of whether+-- @a@ evaluates to a bottom, so for example @par undefined x = x@. -- -- @par@ is generally used when the value of @a@ is likely to be -- required later, but not immediately. Also it is a good idea to@@ -39,19 +48,23 @@ -- running it in parallel. -- -- Note that actual parallelism is only supported by certain--- implementations (GHC with the @-threaded@ option, and GPH, for--- now). On other implementations, @par a b = b@.---+-- implementations (GHC with the @-threaded@ option, for now).+-- On other implementations, @par a b = b@. par :: a -> b -> b #ifdef __GLASGOW_HASKELL__ par = GHC.Conc.par #else--- For now, Hugs does not support par properly.+-- For now, Hugs and MicroHs don't support par properly. par a b = b #endif --- | Semantically identical to 'seq', but with a subtle operational--- difference: 'seq' is strict in both its arguments, so the compiler+-- | Like 'seq' but ensures that the first argument is evaluated before returning.+--+-- @a ``pseq`` b@ evaluates @a@ to weak head normal form (WHNF)+-- before returning @b@.+--+-- This is similar to 'seq', but with a subtle difference:+-- 'seq' is strict in both its arguments, so the compiler -- may, for example, rearrange @a ``seq`` b@ into @b ``seq`` a ``seq`` b@. -- This is normally no problem when using 'seq' to express strictness, -- but it can be a problem when annotating code for parallelism,@@ -63,7 +76,6 @@ -- strict in its first argument (as far as the compiler is concerned), -- which restricts the transformations that the compiler can do, and -- ensures that the user can retain control of the evaluation order.--- pseq :: a -> b -> b #ifdef __GLASGOW_HASKELL__ pseq = GHC.Conc.pseq
Control/Parallel/Strategies.hs view
@@ -1,4 +1,6 @@ {-# LANGUAGE BangPatterns, CPP, MagicHash, UnboxedTuples #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE RecursiveDo #-} ----------------------------------------------------------------------------- -- | -- Module : Control.Parallel.Strategies@@ -9,25 +11,25 @@ -- Stability : experimental -- Portability : portable ----- Parallel Evaluation Strategies, or Strategies for short, provide+-- Parallel evaluation strategies, or strategies for short, provide -- ways to express parallel computations. Strategies have the following -- key features: -- -- * Strategies express /deterministic parallelism/: -- the result of the program is unaffected by evaluating in parallel.--- The parallel tasks evaluated by a Strategy may have no side effects.+-- The parallel tasks evaluated by a strategy may have no side effects. -- For non-deterministic parallel programming, see "Control.Concurrent". -- -- * Strategies let you separate the description of the parallelism from the -- logic of your program, enabling modular parallelism. The basic idea -- is to build a lazy data structure representing the computation, and--- then write a Strategy that describes how to traverse the data structure+-- then write a strategy that describes how to traverse the data structure -- and evaluate components of it sequentially or in parallel. -- -- * Strategies are /compositional/: larger strategies can be built -- by gluing together smaller ones. ----- * 'Monad' and 'Applicative' instances are provided, for quickly building+-- * The 'Eval' monad is provided, for quickly building -- strategies that involve traversing structures in a regular way. -- -- For API history and changes in this release, see "Control.Parallel.Strategies#history".@@ -41,6 +43,8 @@ -- * Application of strategies , using -- :: a -> Strategy a -> a , withStrategy -- :: Strategy a -> a -> a+ , usingIO -- :: a -> Strategy a -> IO a+ , withStrategyIO -- :: Strategy a -> a -> IO a -- * Composition of strategies , dot -- :: Strategy a -> Strategy a -> Strategy a@@ -59,6 +63,7 @@ -- * Strategies for traversable data types , evalTraversable -- :: Traversable t => Strategy a -> Strategy (t a) , parTraversable+ , parFmap -- * Strategies for lists , evalList -- :: Strategy a -> Strategy [a]@@ -113,7 +118,9 @@ -- * For Strategy programmers , Eval -- instances: Monad, Functor, Applicative+ , parEval -- :: Eval a -> Eval a , runEval -- :: Eval a -> a+ , runEvalIO -- :: Eval a -> IO a , -- * API History@@ -135,30 +142,44 @@ -- * For API completeness - -- | so users of 'rdeepseq' aren't required to import Control.DeepSeq:+ -- | So that users of 'rdeepseq' aren't required to import @Control.DeepSeq@: NFData ) where -#if !MIN_VERSION_base(4,8,0)+#if defined(__MHS__) || !MIN_VERSION_base(4,8,0) import Data.Traversable+#endif+#if !MIN_VERSION_base(4,8,0) import Control.Applicative #endif import Control.Parallel-import Control.DeepSeq+import Control.DeepSeq (NFData(rnf))+import Control.Monad.Fix (MonadFix (..))++#if defined(__GLASGOW_HASKELL__) && MIN_VERSION_base(4,4,0)+import System.IO.Unsafe (unsafeDupablePerformIO)+import Control.Exception (evaluate)+#else+import System.IO.Unsafe (unsafePerformIO) import Control.Monad+#endif import qualified Control.Seq +#ifdef __GLASGOW_HASKELL__ import GHC.Exts+import GHC.IO (IO (..))+#endif infixr 9 `dot` -- same as (.) infixl 0 `using` -- lowest precedence and associate to the left+infixl 0 `usingIO` -- lowest precedence and associate to the left -- ----------------------------------------------------------------------------- -- Eval monad (isomorphic to Lift monad from MonadLib 3.6.1) --- | 'Eval' is a Monad that makes it easier to define parallel--- strategies. It is a strict identity monad: that is, in+-- | 'Eval' is a monad that makes it easier to define parallel+-- strategies. It is a strict identity monad, that is, in -- -- > m >>= f --@@ -180,7 +201,7 @@ -- Applicative style as -- -- > myStrat (a,b) = (,) <$> rpar a <*> rseq b-+-- -- More examples, using the Applicative instance: -- -- > parList :: Strategy a -> Strategy [a]@@ -192,20 +213,55 @@ #if __GLASGOW_HASKELL__ >= 702 -newtype Eval a = Eval (State# RealWorld -> (# State# RealWorld, a #))+newtype Eval a = Eval {unEval_ :: IO a}+ deriving (Functor, Applicative, Monad) -- GHC 7.2.1 added the seq# and spark# primitives, that we use in -- the Eval monad implementation in order to get the correct -- strictness behaviour. --- | Pull the result out of the monad.+-- | Run the evaluation. runEval :: Eval a -> a-runEval (Eval x) = case x realWorld# of (# _, a #) -> a+# if MIN_VERSION_base(4,4,0)+runEval = unsafeDupablePerformIO . unEval_+# else+runEval = unsafePerformIO . unEval_+# endif -instance Monad Eval where- return x = Eval $ \s -> (# s, x #)- Eval x >>= k = Eval $ \s -> case x s of- (# s', a #) -> case k a of- Eval f -> f s'+-- | Run the evaluation in the 'IO' monad. This allows sequencing of+-- evaluations relative to 'IO' actions.+runEvalIO :: Eval a -> IO a+runEvalIO = unEval_++-- We don't use GND to derive MonadFix from the IO instance. The IO instance+-- has to be very careful to ensure that lazy blackholing doesn't cause IO+-- actions to be duplicated in case of an infinite loop. This has a small+-- performance cost. Eval computations are always assumed to be pure, so+-- duplicating them is okay. What about ST computations embedded in Eval ones?+-- Those also shouldn't be a problem: the ST computations are "closed", so it's+-- safe to duplicate them, and the RTS already takes care to avoid resuming+-- a computation paused by an asynchronous exception in multiple threads.+-- Lazy ST takes care of itself with noDuplicate#, so we don't really need+-- to think about it too much.+--+-- Note:+-- mfix f = let res = runEval (Lift <$> f (unLift res))+-- in case res of Lift r -> return r+-- data Lift a = Lift a+instance MonadFix Eval where+ -- Borrowed from the instance for ST+ mfix k = Eval $ IO $ \ s ->+ let ans = liftEv (k r) s+ Evret _ r = ans+ in+ case ans of Evret s' x -> (# s', x #)++data Evret a = Evret (State# RealWorld) a++-- liftEv is useful when we want a lifted result from an Eval computation. It+-- is used to implement mfix.+liftEv :: Eval a -> State# RealWorld -> Evret a+liftEv (Eval (IO m)) = \s -> case m s of (# s', r #) -> Evret s' r+ #else data Eval a = Done a@@ -214,23 +270,31 @@ runEval :: Eval a -> a runEval (Done x) = x -instance Monad Eval where- return x = Done x- Done x >>= k = lazy (k x) -- Note: pattern 'Done x' makes '>>=' strict--{-# RULES "lazy Done" forall x . lazy (Done x) = Done x #-}--#endif-+-- | Run the evaluation in the 'IO' monad. This allows sequencing of+-- evaluations relative to 'IO' actions.+runEvalIO :: Eval a -> IO a+runEvalIO (Done x) = return x instance Functor Eval where fmap = liftM instance Applicative Eval where+ pure = Done (<*>) = ap- pure = return +instance Monad Eval where+ return = pure+# ifdef __GLASGOW_HASKELL__+ Done x >>= k = lazy (k x) -- Note: pattern 'Done x' makes '>>=' strict+# else+ Done x >>= k = k x+# endif +instance MonadFix Eval where+ mfix f = let r = f (runEval r) in r++{-# RULES "lazy Done" forall x . lazy (Done x) = Done x #-}+ -- The Eval monad satisfies the monad laws. -- -- (1) Left identity:@@ -253,7 +317,9 @@ -- ==> undefined <== undefined >>= (\x -> f x >>= g) -- <*= m >>= (\x -> f x >>= g) +#endif + -- ----------------------------------------------------------------------------- -- Strategies @@ -281,20 +347,44 @@ using :: a -> Strategy a -> a x `using` strat = runEval (strat x) --- | evaluate a value using the given 'Strategy'. This is simply+-- | Evaluate a value using the given 'Strategy'. This is simply -- 'using' with the arguments reversed. -- withStrategy :: Strategy a -> a -> a withStrategy = flip using --- | Compose two strategies sequentially.--- This is the analogue to function composition on strategies.+-- | Evaluate a value using the given 'Strategy' inside the 'IO' monad. See+-- also 'runEvalIO'. --+-- > x `usingIO` s = runEvalIO (s x)+--+usingIO :: a -> Strategy a -> IO a+x `usingIO` strat = runEvalIO (strat x)++-- | Evaluate a value using the given 'Strategy' inside the 'IO' monad. This+-- is simply 'usingIO' with the arguments reversed.+--+withStrategyIO :: Strategy a -> a -> IO a+withStrategyIO = flip usingIO++-- | Compose two strategies.+-- -- > strat2 `dot` strat1 == strat2 . withStrategy strat1 --+-- 'dot' is associative:+--+-- > (strat1 `dot` strat2) `dot` strat3 == strat1 `dot` (strat2 `dot` strat3)+--+-- 'r0' and 'rseq' are one-sided identities of 'dot':+--+-- > strat `dot` r0 == strat+-- > strat `dot` rseq == strat+{-# DEPRECATED dot "'dot' is an unintuitive composition operator. Use 'Control.Monad.<=<` instead." #-} dot :: Strategy a -> Strategy a -> Strategy a strat2 `dot` strat1 = strat2 . runEval . strat1 +-- Note [dot proofs]+-- ~~~~~~~~~~~~~~~~~ -- Proof of strat2 `dot` strat1 == strat2 . withStrategy strat1 -- -- strat2 . withStrategy strat1@@ -303,33 +393,30 @@ -- == \x -> strat2 (runEval (strat1 x)) -- == \x -> (strat2 . runEval . strat1) x -- == strat2 `dot` strat1---- One might be tempted to think that 'dot' is equivalent to '(<=<)',--- the right-to-left Kleisli composition in the Eval monad, because--- '(<=<)' can take the type @Strategy a -> Strategy a -> Strategy a@--- and intuitively does what 'dot' does: First apply the strategy to the--- right then the one to the left. However, there is a subtle difference--- in strictness, witnessed by the following example: ----- > (r0 `dot` rseq) undefined == Done undefined--- > (r0 <=< rseq) undefined == undefined+-- Proof of associativity --+-- (strat1 `dot` strat2) `dot` strat3+-- == (strat1 . runEval . strat2) . runEval . strat3+-- == strat1 . runEval . strat2 . runEval . strat3+-- == strat1 . runEval . (strat2 . runEval . strat3)+-- == strat1 `dot` (strat2 `dot` strat3) --- | Inject a sequential strategy (ie. coerce a sequential strategy+-- | Inject a sequential strategy (i.e., coerce a sequential strategy -- to a general strategy). ----- Thanks to 'evalSeq', the type @Control.Seq.Strategy a@ is a subtype+-- Thanks to 'evalSeq', the type @'SeqStrategy' a@ is a subtype -- of @'Strategy' a@. evalSeq :: SeqStrategy a -> Strategy a evalSeq strat x = strat x `pseq` return x --- | a name for @Control.Seq.Strategy@, for documetnation only.+-- | A name for @Control.Seq.Strategy@, for documentation only. type SeqStrategy a = Control.Seq.Strategy a -- -------------------------------------------------------------------------- -- Basic strategies (some imported from SeqStrategies) --- | 'r0' performs *no* evaluation.+-- | 'r0' performs /no/ evaluation. -- -- > r0 == evalSeq Control.Seq.r0 --@@ -350,11 +437,14 @@ -- rseq :: Strategy a #if __GLASGOW_HASKELL__ >= 702-rseq x = Eval $ \s -> seq# x s+rseq x = Eval (evaluate x) #else rseq x = x `seq` return x #endif+-- Staged NOINLINE so we can match on rseq in RULES+{-# NOINLINE [1] rseq #-} + -- Proof of rseq == evalSeq Control.Seq.rseq -- -- evalSeq Control.Seq.rseq@@ -380,35 +470,69 @@ -- == rdeepseq -- | 'rpar' sparks its argument (for evaluation in parallel).-rpar :: a -> Eval a+rpar :: Strategy a+#ifdef __GLASGOW_HASKELL__ #if __GLASGOW_HASKELL__ >= 702-rpar x = Eval $ \s -> spark# x s+rpar x = Eval $ IO $ \s -> spark# x s #else-rpar x = case (par# x) of { _ -> Done x }+rpar x = case (par# x) of _ -> Done x #endif+#else+rpar x = case par x () of () -> Done x+#endif {-# INLINE rpar #-} --- | instead of saying @rpar `dot` strat@, you can say--- @rparWith strat@. Compared to 'rpar', 'rparWith'+-- | Perform a computation in parallel using a strategy. ----- * does not exit the `Eval` monad+-- @+-- rparWith strat x+-- @ ----- * does not have a built-in `rseq`, so for example `rparWith r0`--- behaves as you might expect (it is a strategy that creates a--- spark that does no evaluation).+-- will spark @strat x@. Note that @rparWith strat@ is /not/ the+-- same as @rpar ``dot`` strat@. Specifically, @rpar ``dot`` strat@+-- always sparks a computation to reduce the result of the+-- strategic computation to WHNF, while @rparWith strat@ need+-- not. --+-- > rparWith r0 = r0+-- > rparWith rpar = rpar+-- > rparWith rseq = rpar --+-- @rparWith rpar x@ creates a spark that immediately creates another+-- spark to evaluate @x@. We consider this equivalent to @rpar@ because+-- there isn't any real additional parallelism. However, it is always+-- less efficient because there's a bit of extra work to create the+-- first (useless) spark. Similarly, @rparWith r0@ creates a spark+-- that does precisely nothing. No real parallelism is added, but there+-- is a bit of extra work to do nothing. rparWith :: Strategy a -> Strategy a-#if __GLASGOW_HASKELL__ >= 702-rparWith s a = do l <- rpar r; return (case l of Lift x -> x)- where r = case s a of- Eval f -> case f realWorld# of- (# _, a' #) -> Lift a'+rparWith strat = parEval . strat +-- | 'parEval' sparks the computation of its argument for evaluation in+-- parallel. Unlike @'rpar' . 'runEval'@, 'parEval'+--+-- * does not exit the `Eval` monad+--+-- * does not have a built-in `rseq`, so for example @'parEval' ('r0' x)@+-- behaves as you might expect (it creates a spark that does no+-- evaluation).+--+-- It is related to 'rparWith' by the following equality:+--+-- > parEval . strat = rparWith strat+--+parEval :: Eval a -> Eval a+-- The intermediate `Lift` box is necessary, in order to avoid a built-in+-- `rseq` in `parEval`. In particular, we want @parEval . r0 = r0@, not+-- @parEval . r0 = rpar@.+parEval m = do+ l <- rpar r+ return (case l of Lift x -> x)++ where+ r = runEval (Lift <$> m)+ data Lift a = Lift a-#else-rparWith s a = do l <- rpar (s a); return (case l of Done x -> x)-#endif -- -------------------------------------------------------------------------- -- Strategy combinators for Traversable data types@@ -419,7 +543,7 @@ evalTraversable = traverse {-# INLINE evalTraversable #-} --- | Like 'evalTraversable' but evaluates all elements in parallel.+-- | Like 'evalTraversable', but evaluates all elements in parallel. parTraversable :: Traversable t => Strategy a -> Strategy (t a) parTraversable strat = evalTraversable (rparWith strat) {-# INLINE parTraversable #-}@@ -428,7 +552,10 @@ -- Strategies for lists -- | Evaluate each element of a list according to the given strategy.--- Equivalent to 'evalTraversable' at the list type.+-- Equivalent to 'evalTraversable' at the list type.+--+-- __Warning:__ This strategy evaluates the spine of the list+-- and thus does not work on infinite lists. evalList :: Strategy a -> Strategy [a] evalList = evalTraversable -- Alternative explicitly recursive definition:@@ -438,14 +565,17 @@ -- return (x':xs') -- | Evaluate each element of a list in parallel according to given strategy.--- Equivalent to 'parTraversable' at the list type.+-- Equivalent to 'parTraversable' at the list type.+--+-- __Warning:__ This strategy evaluates the spine of the list+-- and thus does not work on infinite lists. parList :: Strategy a -> Strategy [a] parList = parTraversable -- Alternative definition via evalList: -- parList strat = evalList (rparWith strat) -- | @'evaListSplitAt' n stratPref stratSuff@ evaluates the prefix--- (of length @n@) of a list according to @stratPref@ and its the suffix+-- (of length @n@) of a list according to @stratPref@ and the suffix -- according to @stratSuff@. evalListSplitAt :: Int -> Strategy [a] -> Strategy [a] -> Strategy [a] evalListSplitAt n stratPref stratSuff xs@@ -454,7 +584,7 @@ stratSuff zs >>= \zs' -> return (ys' ++ zs') --- | Like 'evalListSplitAt' but evaluates both sublists in parallel.+-- | Like 'evalListSplitAt', but evaluates both sublists in parallel. parListSplitAt :: Int -> Strategy [a] -> Strategy [a] -> Strategy [a] parListSplitAt n stratPref stratSuff = evalListSplitAt n (rparWith stratPref) (rparWith stratSuff) @@ -462,56 +592,57 @@ evalListN :: Int -> Strategy a -> Strategy [a] evalListN n strat = evalListSplitAt n (evalList strat) r0 --- | Like 'evalListN' but evaluates the first n elements in parallel.+-- | Like 'evalListN', but evaluates the first n elements in parallel. parListN :: Int -> Strategy a -> Strategy [a] parListN n strat = evalListN n (rparWith strat) -- | Evaluate the nth element of a list (if there is such) according to -- the given strategy.+-- This nth is 0-based. For example, @[1, 2, 3, 4, 5] ``using`` evalListNth 4 rseq@+-- will eval @5@, not @4@. -- The spine of the list up to the nth element is evaluated as a side effect. evalListNth :: Int -> Strategy a -> Strategy [a] evalListNth n strat = evalListSplitAt n r0 (evalListN 1 strat) --- | Like 'evalListN' but evaluates the nth element in parallel.+-- | Like 'evalListNth', but evaluates the nth element in parallel. parListNth :: Int -> Strategy a -> Strategy [a] parListNth n strat = evalListNth n (rparWith strat) -- | Divides a list into chunks, and applies the strategy -- @'evalList' strat@ to each chunk in parallel. ----- It is expected that this function will be replaced by a more--- generic clustering infrastructure in the future.--- -- If the chunk size is 1 or less, 'parListChunk' is equivalent to -- 'parList' --+-- This function may be replaced by a more+-- generic clustering infrastructure in the future.+--+-- __Warning:__ This strategy evaluates the spine of the list+-- and thus does not work on infinite lists. parListChunk :: Int -> Strategy a -> Strategy [a]-parListChunk n strat xs- | n <= 1 = parList strat xs- | otherwise = concat `fmap` parList (evalList strat) (chunk n xs)--chunk :: Int -> [a] -> [[a]]-chunk _ [] = []-chunk n xs = as : chunk n bs where (as,bs) = splitAt n xs---- Non-compositional version of 'parList', evaluating list elements--- to weak head normal form.--- Not to be exported; used for optimisation.---- | DEPRECATED: use @'parList' 'rseq'@ instead-parListWHNF :: Strategy [a]-parListWHNF xs = go xs `pseq` return xs- where -- go :: [a] -> [a]- go [] = []- go (y:ys) = y `par` go ys+parListChunk n strat+ | n <= 1 = parList strat+ | otherwise = go+ where+ go [] = pure []+ go as = mdo+ -- Calculate the first chunk in parallel, passing it the result+ -- of calculating the rest+ bs <- rpar $ runEval $ evalChunk strat more n as --- The non-compositional 'parListWHNF' might be more efficient than its--- more compositional counterpart; use RULES to do the specialisation.+ -- Calculate the rest+ more <- go (drop n as)+ return bs -{-# NOINLINE [1] parList #-}-{-# RULES- "parList/rseq" parList rseq = parListWHNF- #-}+-- | @evalChunk strat end n as@ uses @strat@ to evaluate the first @n@+-- elements of @as@ (ignoring the rest) and appends @end@ to the result.+evalChunk :: Strategy a -> [a] -> Int -> Strategy [a]+evalChunk strat = \end ->+ let+ go !_n [] = pure end+ go 0 _ = pure end+ go n (a:as) = (:) <$> strat a <*> go (n - 1) as+ in go -- -------------------------------------------------------------------------- -- Convenience@@ -520,68 +651,49 @@ -- -- > parMap strat f = withStrategy (parList strat) . map f --+-- __Warning:__ This function evaluates the spine of the list+-- and thus does not work on infinite lists. parMap :: Strategy b -> (a -> b) -> [a] -> [b] parMap strat f = (`using` parList strat) . map f --- ----------------------------------------------------------------------------- Strategies for lazy lists --- List-based non-compositional rolling buffer strategy, evaluating list--- elements to weak head normal form.--- Not to be exported; used in evalBuffer and for optimisation.-evalBufferWHNF :: Int -> Strategy [a]-evalBufferWHNF n0 xs0 = return (ret xs0 (start n0 xs0))- where -- ret :: [a] -> [a] -> [a]- ret (x:xs) (y:ys) = y `pseq` (x : ret xs ys)- ret xs _ = xs-- -- start :: Int -> [a] -> [a]- start 0 ys = ys- start !_n [] = []- start !n (y:ys) = y `pseq` start (n-1) ys---- | 'evalBuffer' is a rolling buffer strategy combinator for (lazy) lists.------ 'evalBuffer' is not as compositional as the type suggests. In fact,--- it evaluates list elements at least to weak head normal form,--- disregarding a strategy argument 'r0'.+-- | A generalisation of 'parMap' using 'parTraversable' and `fmap`: ----- > evalBuffer n r0 == evalBuffer n rseq+-- > parFmap strat g = withStrategy (parTraversable strat) . fmap f ---evalBuffer :: Int -> Strategy a -> Strategy [a]-evalBuffer n strat = evalBufferWHNF n . map (withStrategy strat)+parFmap :: Traversable t => Strategy b -> (a -> b) -> t a -> t b+parFmap strat f = (`using` parTraversable strat) . fmap f --- Like evalBufferWHNF but sparks the list elements when pushing them--- into the buffer.--- Not to be exported; used in parBuffer and for optimisation.-parBufferWHNF :: Int -> Strategy [a]-parBufferWHNF n0 xs0 = return (ret xs0 (start n0 xs0))- where -- ret :: [a] -> [a] -> [a]- ret (x:xs) (y:ys) = y `par` (x : ret xs ys)- ret xs _ = xs+-- --------------------------------------------------------------------------+-- Strategies for lazy lists - -- start :: Int -> [a] -> [a]- start 0 ys = ys- start !_n [] = []- start !n (y:ys) = y `par` start (n-1) ys+-- | 'evalBuffer' is a rolling buffer strategy combinator for lazy lists.+-- Pattern matching on the result of @evalBuffer n strat xs@ will evaluate the+-- first @n+1@ elements of @xs@ using @strat@. Pattern matching on each+-- additional list cons will evaluate an additional element using @strat@.+evalBuffer :: Int -> Strategy a -> Strategy [a]+evalBuffer n0 strat xs0 = return (ret tied (drop n0 tied))+ where+ -- This is the heart of the strategy. The idea is to tie the evaluation+ -- of each cons (to WHNF) to the evaluation of its contents (according+ -- to strat). Walking the spine of the result will thus perform+ -- the requested Eval actions.+ tied = foldr go [] xs0+ where+ go x r = runEval ((: r) <$> strat x) + ret (x : xs) (_y : ys) = x : ret xs ys+ ret xs _ = xs --- | Like 'evalBuffer' but evaluates the list elements in parallel when--- pushing them into the buffer.+-- | 'parBuffer' is a rolling buffer strategy combinator for lazy lists.+-- Pattern matching on the result of @parBuffer n s xs@ sparks+-- computations to evaluate the first @n+1@ elements of @xs@ using the+-- strategy @s@. Pattern matching on each additional list cons will+-- spark an additional computation.+--+-- @parBuffer n strat = 'evalBuffer' n ('rparWith' strat)@ parBuffer :: Int -> Strategy a -> Strategy [a]-parBuffer n strat = parBufferWHNF n . map (withStrategy strat)--- Alternative definition via evalBuffer (may compromise firing of RULES):--- parBuffer n strat = evalBuffer n (rparWith strat)---- Deforest the intermediate list in parBuffer/evalBuffer when it is--- unnecessary:--{-# NOINLINE [1] evalBuffer #-}-{-# NOINLINE [1] parBuffer #-}-{-# RULES-"evalBuffer/rseq" forall n . evalBuffer n rseq = evalBufferWHNF n-"parBuffer/rseq" forall n . parBuffer n rseq = parBufferWHNF n- #-}+parBuffer n strat = evalBuffer n (rparWith strat) -- -------------------------------------------------------------------------- -- Strategies for tuples@@ -654,43 +766,40 @@ -- Strategic function application {--These are very handy when writing pipeline parallelism asa sequence of+These are 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 only as second arguments to @$|@ and @$||@. -} -- | Sequential function application. The argument is evaluated using--- the given strategy before it is given to the function.+-- the given strategy before it is given to the function. ($|) :: (a -> b) -> Strategy a -> a -> b-f $| s = \ x -> let z = x `using` s in z `pseq` f z+f $| s = \x -> runEval (f <$> 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 -> let z = x `using` s in z `par` f z+f $|| s = \x -> runEval (f <$> rparWith 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 z = g x `using` s in- z `pseq` f z+(.|) f s g = \x -> runEval (f <$> s (g x)) -- | 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 z = g x `using` s in- z `par` f z+(.||) f s g = \x -> runEval (f <$> rparWith s (g x)) -- | 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 z = f x `using` s in- z `pseq` g z+(-|) f s g = \x -> runEval (g <$> s (f x)) -- | Parallel inverse function composition, -- for those who read their programs from left to right.@@ -698,80 +807,63 @@ -- given strategy, in parallel with the application of the -- second function. (-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)-(-||) f s g = \ x -> let z = f x `using` s in- z `par` g z+(-||) f s g = \x -> runEval (g <$> rparWith s (f x)) -- ----------------------------------------------------------------------------- -- Old/deprecated stuff {-# DEPRECATED Done "The Strategy type is now a -> Eval a, not a -> Done" #-}--- | DEPRECCATED: replaced by the 'Eval' monad type Done = () -{-# DEPRECATED demanding "Use pseq or $| instead" #-}--- | DEPRECATED: Use 'pseq' or '$|' instead+{-# DEPRECATED demanding "Use 'pseq' or '$|' instead" #-} demanding :: a -> Done -> a demanding = flip pseq -{-# DEPRECATED sparking "Use par or $|| instead" #-}--- | DEPRECATED: Use 'par' or '$||' instead+{-# DEPRECATED sparking "Use 'par' or '$||' instead" #-} sparking :: a -> Done -> a sparking = flip par -{-# DEPRECATED (>|) "Use pseq or $| instead" #-}--- | DEPRECATED: Use 'pseq' or '$|' instead+{-# DEPRECATED (>|) "Use 'pseq' or '$|' instead" #-} (>|) :: Done -> Done -> Done (>|) = Prelude.seq -{-# DEPRECATED (>||) "Use par or $|| instead" #-}--- | DEPRECATED: Use 'par' or '$||' instead+{-# DEPRECATED (>||) "Use 'par' or '$||' instead" #-} (>||) :: Done -> Done -> Done (>||) = par -{-# DEPRECATED rwhnf "renamed to rseq" #-}--- | DEPRECATED: renamed to 'rseq'+{-# DEPRECATED rwhnf "renamed to 'rseq'" #-} rwhnf :: Strategy a rwhnf = rseq -{-# DEPRECATED seqTraverse "renamed to evalTraversable" #-}--- | DEPRECATED: renamed to 'evalTraversable'+{-# DEPRECATED seqTraverse "renamed to 'evalTraversable'" #-} seqTraverse :: Traversable t => Strategy a -> Strategy (t a) seqTraverse = evalTraversable -{-# DEPRECATED parTraverse "renamed to parTraversable" #-}--- | DEPRECATED: renamed to 'parTraversable'+{-# DEPRECATED parTraverse "renamed to 'parTraversable'" #-} parTraverse :: Traversable t => Strategy a -> Strategy (t a) parTraverse = parTraversable -{-# DEPRECATED parListWHNF "use (parList rseq) instead" #-}--{-# DEPRECATED seqList "renamed to evalList" #-}--- | DEPRECATED: renamed to 'evalList'+{-# DEPRECATED seqList "renamed to 'evalList'" #-} seqList :: Strategy a -> Strategy [a] seqList = evalList -{-# DEPRECATED seqPair "renamed to evalTuple2" #-}--- | DEPRECATED: renamed to 'evalTuple2'+{-# DEPRECATED seqPair "renamed to 'evalTuple2'" #-} seqPair :: Strategy a -> Strategy b -> Strategy (a,b) seqPair = evalTuple2 -{-# DEPRECATED parPair "renamed to parTuple2" #-}--- | DEPRECATED: renamed to 'parTuple2'+{-# DEPRECATED parPair "renamed to 'parTuple2'" #-} parPair :: Strategy a -> Strategy b -> Strategy (a,b) parPair = parTuple2 -{-# DEPRECATED seqTriple "renamed to evalTuple3" #-}--- | DEPRECATED: renamed to 'evalTuple3'+{-# DEPRECATED seqTriple "renamed to 'evalTuple3'" #-} seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c) seqTriple = evalTuple3 -{-# DEPRECATED parTriple "renamed to parTuple3" #-}--- | DEPRECATED: renamed to 'parTuple3'+{-# DEPRECATED parTriple "renamed to 'parTuple3'" #-} parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c) parTriple = parTuple3 -{-# DEPRECATED unEval "renamed to runEval" #-}--- | DEPRECATED: renamed to 'runEval'+{-# DEPRECATED unEval "renamed to 'runEval'" #-} unEval :: Eval a -> a unEval = runEval @@ -782,22 +874,22 @@ interest to those who are familiar with an older version, or need to adapt old code to use the newer API. -Version 1.x+=== Version 1.x - The original Strategies design is described in /Algorithm + Strategy = Parallelism/ <http://www.macs.hw.ac.uk/~dsg/gph/papers/html/Strategies/strategies.html>+ The original Strategies design is described in [/Algorithm + Strategy = Parallelism/](https://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+=== 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>.+the paper [/Runtime Support for Multicore Haskell/](https://www.microsoft.com/en-us/research/wp-content/uploads/2009/09/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+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@@ -810,7 +902,7 @@ 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+should probably discard 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@@ -822,7 +914,7 @@ 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))@+ type, 'Eval'. e.g. @parList s = traverse (rpar . (``using`` s))@ * 'parList' has been generalised to 'parTraverse', which works on any 'Traversable' type, and similarly 'seqList' has been generalised@@ -836,7 +928,7 @@ package. Note that since the 'Strategy' type changed, 'rnf' is no longer a 'Strategy': use 'rdeepseq' instead. -Version 2.1 moved NFData into a separate package, @deepseq@.+Version 2.1 moved 'NFData' into a separate package, @deepseq@. Version 2.2 changed the type of Strategy to @a -> Eval a@, and re-introduced the @r0@ strategy which was missing in version 2.1.@@ -847,22 +939,24 @@ noticed that @Eval@ didn't satisfy the monad laws, and that a simpler version would fix that problem. -(version 2.3 was not released on Hackage).+(Version 2.3 was not released on Hackage.) +=== Version 3.x+ Version 3 introduced a major overhaul of the API, to match what is presented in the paper - /Seq no More: Better Strategies for Parallel Haskell/- <http://www.haskell.org/~simonmar/papers/strategies.pdf>+ [/Seq no More: Better Strategies for Parallel Haskell/]+ (https://simonmar.github.io/bib/papers/strategies.pdf) -The major differenes in the API are:+The major differences in the API are: - * The addition of Sequential strategies ("Control.Seq") as+ * The addition of sequential strategies ("Control.Seq") as a composable means for specifying sequential evaluation. * Changes to the naming scheme: 'rwhnf' renamed to 'rseq', 'seqList' renamed to 'evalList', 'seqPair' renamed to- 'evalTuple2',+ 'evalTuple2'. The naming scheme is now as follows:
Control/Seq.hs view
@@ -14,7 +14,7 @@ -- Sequential strategies provide ways to compositionally specify -- the degree of evaluation of a data type between the extremes of -- no evaluation and full evaluation.--- Sequential strategies may be viewed as complimentary to the parallel+-- Sequential strategies may be viewed as complementary to the parallel -- ones (see module "Control.Parallel.Strategies"). -- @@ -59,14 +59,16 @@ ) where import Control.DeepSeq (NFData, deepseq)-#if MIN_VERSION_base(4,8,0)+#if defined(__GLASGOW_HASKELL__) && MIN_VERSION_base(4,8,0) import Data.Foldable (toList) #else import Data.Foldable (Foldable, toList) #endif import Data.Map (Map) import qualified Data.Map (toList)+#if !((__GLASGOW_HASKELL__ >= 711) && MIN_VERSION_array(0,5,1)) import Data.Ix (Ix)+#endif import Data.Array (Array) import qualified Data.Array (bounds, elems) @@ -92,7 +94,7 @@ -- -------------------------------------------------------------------------- -- Basic sequential strategies --- | 'r0' performs *no* evaluation.+-- | 'r0' performs /no/ evaluation. r0 :: Strategy a r0 _ = () @@ -146,11 +148,19 @@ -- | Evaluate the elements of an array according to the given strategy. -- Evaluation of the array bounds may be triggered as a side effect.+#if (__GLASGOW_HASKELL__ >= 711) && MIN_VERSION_array(0,5,1)+seqArray :: Strategy a -> Strategy (Array i a)+#else seqArray :: Ix i => Strategy a -> Strategy (Array i a)+#endif seqArray strat = seqList strat . Data.Array.elems -- | Evaluate the bounds of an array according to the given strategy.+#if (__GLASGOW_HASKELL__ >= 711) && MIN_VERSION_array(0,5,1)+seqArrayBounds :: Strategy i -> Strategy (Array i a)+#else seqArrayBounds :: Ix i => Strategy i -> Strategy (Array i a)+#endif seqArrayBounds strat = seqTuple2 strat strat . Data.Array.bounds -- | Evaluate the keys and values of a map according to the given strategies.
changelog.md view
@@ -1,17 +1,52 @@ # Changelog for [`parallel` package](http://hackage.haskell.org/package/parallel) +## 3.3.0.0 *Oct 2025*++* Bump dependency bounds+* Support MicroHs ([#81](https://github.com/haskell/parallel/pull/81))+* Make rolling buffer strategies compositional ([#77](https://github.com/haskell/parallel/pull/77))+* Deprecate `dot` ([#75](https://github.com/haskell/parallel/pull/75))+* Make strategic function application operators handle strategies correctly ([#61](https://github.com/haskell/parallel/pull/61))+* Add `parFmap` ([#53](https://github.com/haskell/parallel/pull/53))+* Make `parListChunk` more efficient ([#45](https://github.com/haskell/parallel/issues/45))+* Update documentation++## 3.2.2.0 *Jul 2018*++* Bump dependency bounds+* Add `parEval`+* Add a `MonadFix Eval` instance++## 3.2.1.1 *Apr 2017*++* Compatibility with `deepseq-1.4.3`+* Minor documentation clarifications++## 3.2.1.0 *Jan 2016*++* Support `base-4.9.0.0`+* Add `{-# NOINLINE[1] rseq #-}` to make the `RULE` more robust+* Fix broken links to papers in Haddock+* Make `rpar` type signature consistent with `rseq` via type synonym+* Drop redundant `Ix`-constraint on `seqArray`/`seqArrayBounds` for GHC >= 8.0+ ## 3.2.0.6 *Dec 2014* - - Make `-Wall` message free for all supported `base` versions+* Make `-Wall` message free for all supported `base` versions ## 3.2.0.5 *Dec 2014* - - Support `base-4.8.0.0`/`deepseq-1.4.0.0` (and thus GHC 7.10)+* Support `base-4.8.0.0`/`deepseq-1.4.0.0` (and thus GHC 7.10) ## 3.2.0.4 *Nov 2013* - * Update package description to Cabal 1.10 format- * Add support for GHC 7.8- * Drop support for GHCs older than GHC 7.0.1- * Add NOINLINE pragmas to `parBuffer`, `parList`, and `evalBuffer`- to make RULEs more likely to fire+* Update package description to Cabal 1.10 format+* Add support for GHC 7.8+* Drop support for GHCs older than GHC 7.0.1+* Add NOINLINE pragmas to `parBuffer`, `parList`, and `evalBuffer`+ to make RULEs more likely to fire++## Older versions++* This package has a long history which is described in the Haddock documentation+ in the ["API History" section](./docs/Control-Parallel-Strategies.html#history)
parallel.cabal view
@@ -1,5 +1,6 @@+cabal-version: >=1.10 name: parallel-version: 3.2.0.6+version: 3.3.0.0 -- NOTE: Don't forget to update ./changelog.md license: BSD3 license-file: LICENSE@@ -8,11 +9,35 @@ synopsis: Parallel programming library category: Control, Parallelism build-type: Simple-cabal-version: >=1.10-tested-with: GHC==7.6.3, GHC==7.6.2, GHC==7.6.1, GHC==7.4.2, GHC==7.4.1, GHC==7.2.2, GHC==7.2.1, GHC==7.0.4, GHC==7.0.3, GHC==7.0.2, GHC==7.0.1++tested-with:+ GHC == 9.12.2+ GHC == 9.10.1+ GHC == 9.8.4+ GHC == 9.6.7+ GHC == 9.4.8+ GHC == 9.2.8+ GHC == 9.0.2+ GHC == 8.10.7+ GHC == 8.8.4+ GHC == 8.6.5+ GHC == 8.4.4+ GHC == 8.2.2+ GHC == 8.0.2+ MHS+ description: This package provides a library for parallel programming.+ .+ For documentation, start from the "Control.Parallel.Strategies"+ module below.+ .+ For more tutorial documentation, see the book <https://simonmar.github.io/pages/pcph.html Parallel and Concurrent Programming in Haskell>.+ .+ To understand the principles behind the library, see+ <https://simonmar.github.io/bib/papers/strategies.pdf Seq no more: Better Strategies for Parallel Haskell>. + extra-source-files: changelog.md source-repository head@@ -24,7 +49,6 @@ other-extensions: BangPatterns CPP- FlexibleInstances MagicHash UnboxedTuples @@ -35,9 +59,9 @@ build-depends: array >= 0.3 && < 0.6,- base >= 4.3 && < 4.9,- containers >= 0.4 && < 0.6,- deepseq >= 1.1 && < 1.5+ base >= 4.3 && < 4.22,+ containers >= 0.4 && < 0.9,+ deepseq >= 1.1 && < 1.6 ghc-options: -Wall