1{-# LANGUAGE BangPatterns, CPP, MagicHash, UnboxedTuples #-} 2{-# LANGUAGE GeneralizedNewtypeDeriving #-} 3----------------------------------------------------------------------------- 4-- | 5-- Module : Control.Parallel.Strategies 6-- Copyright : (c) The University of Glasgow 2001-2010 7-- License : BSD-style (see the file libraries/base/LICENSE) 8-- 9-- Maintainer : libraries@haskell.org 10-- Stability : experimental 11-- Portability : portable 12-- 13-- Parallel Evaluation Strategies, or Strategies for short, provide 14-- ways to express parallel computations. Strategies have the following 15-- key features: 16-- 17-- * Strategies express /deterministic parallelism/: 18-- the result of the program is unaffected by evaluating in parallel. 19-- The parallel tasks evaluated by a Strategy may have no side effects. 20-- For non-deterministic parallel programming, see "Control.Concurrent". 21-- 22-- * Strategies let you separate the description of the parallelism from the 23-- logic of your program, enabling modular parallelism. The basic idea 24-- is to build a lazy data structure representing the computation, and 25-- then write a Strategy that describes how to traverse the data structure 26-- and evaluate components of it sequentially or in parallel. 27-- 28-- * Strategies are /compositional/: larger strategies can be built 29-- by gluing together smaller ones. 30-- 31-- * 'Monad' and 'Applicative' instances are provided, for quickly building 32-- strategies that involve traversing structures in a regular way. 33-- 34-- For API history and changes in this release, see "Control.Parallel.Strategies#history". 35 36----------------------------------------------------------------------------- 37 38module Control.Parallel.Strategies ( 39 -- * The strategy type 40 Strategy 41 42 -- * Application of strategies 43 , using -- :: a -> Strategy a -> a 44 , withStrategy -- :: Strategy a -> a -> a 45 , usingIO -- :: a -> Strategy a -> IO a 46 , withStrategyIO -- :: Strategy a -> a -> IO a 47 48 -- * Composition of strategies 49 , dot -- :: Strategy a -> Strategy a -> Strategy a 50 51 -- * Basic strategies 52 , r0 -- :: Strategy a 53 , rseq 54 , rdeepseq -- :: NFData a => Strategy a 55 , rpar -- :: Strategy a 56 , rparWith -- :: Strategy a -> Strategy a 57 58 -- * Injection of sequential strategies 59 , evalSeq -- :: Seq.Strategy a -> Strategy a 60 , SeqStrategy 61 62 -- * Strategies for traversable data types 63 , evalTraversable -- :: Traversable t => Strategy a -> Strategy (t a) 64 , parTraversable 65 66 -- * Strategies for lists 67 , evalList -- :: Strategy a -> Strategy [a] 68 , parList 69 , evalListN -- :: Int -> Strategy a -> Strategy [a] 70 , parListN 71 , evalListNth -- :: Int -> Strategy a -> Strategy [a] 72 , parListNth 73 , evalListSplitAt -- :: Int -> Strategy [a] -> Strategy [a] -> Strategy [a] 74 , parListSplitAt 75 , parListChunk 76 , parMap 77 78 -- ** Strategies for lazy lists 79 , evalBuffer -- :: Int -> Strategy a -> Strategy [a] 80 , parBuffer 81 82 -- * Strategies for tuples 83 84 -- | Evaluate the components of a tuple according to the 85 -- given strategies. 86 87 , evalTuple2 -- :: Strategy a -> ... -> Strategy (a,...) 88 , evalTuple3 89 , evalTuple4 90 , evalTuple5 91 , evalTuple6 92 , evalTuple7 93 , evalTuple8 94 , evalTuple9 95 96 97 -- | Evaluate the components of a tuple in parallel according to 98 -- the given strategies. 99 100 , parTuple2 -- :: Strategy a -> ... -> Strategy (a,...) 101 , parTuple3 102 , parTuple4 103 , parTuple5 104 , parTuple6 105 , parTuple7 106 , parTuple8 107 , parTuple9 108 109 -- * Strategic function application 110 , ($|) -- :: (a -> b) -> Strategy a -> a -> b 111 , ($||) 112 , (.|) -- :: (b -> c) -> Strategy b -> (a -> b) -> a -> c 113 , (.||) 114 , (-|) -- :: (a -> b) -> Strategy b -> (b -> c) -> a -> c 115 , (-||) 116 117 -- * For Strategy programmers 118 , Eval -- instances: Monad, Functor, Applicative 119 , parEval -- :: Eval a -> Eval a 120 , runEval -- :: Eval a -> a 121 , runEvalIO -- :: Eval a -> IO a 122 , 123 124 -- * API History 125 126 -- $history 127 128 -- * Backwards compatibility 129 130 -- | These functions and types are all deprecated, and will be 131 -- removed in a future release. In all cases they have been 132 -- either renamed or replaced with equivalent functionality. 133 134 Done, demanding, sparking, (>|), (>||), 135 rwhnf, unEval, 136 seqTraverse, parTraverse, 137 seqList, 138 seqPair, parPair, 139 seqTriple, parTriple, 140 141 -- * For API completeness 142 143 -- | so users of 'rdeepseq' aren't required to import Control.DeepSeq: 144 NFData 145 ) where 146 147#if !MIN_VERSION_base(4,8,0) 148import Data.Traversable 149import Control.Applicative 150#endif 151import Control.Parallel 152import Control.DeepSeq (NFData(rnf)) 153import Control.Monad.Fix (MonadFix (..)) 154 155#if MIN_VERSION_base(4,4,0) 156import System.IO.Unsafe (unsafeDupablePerformIO) 157import Control.Exception (evaluate) 158#else 159import System.IO.Unsafe (unsafePerformIO) 160import Control.Monad 161#endif 162 163import qualified Control.Seq 164 165import GHC.Exts 166import GHC.IO (IO (..)) 167 168infixr 9 `dot` -- same as (.) 169infixl 0 `using` -- lowest precedence and associate to the left 170infixl 0 `usingIO` -- lowest precedence and associate to the left 171 172-- ----------------------------------------------------------------------------- 173-- Eval monad (isomorphic to Lift monad from MonadLib 3.6.1) 174 175-- | 'Eval' is a Monad that makes it easier to define parallel 176-- strategies. It is a strict identity monad: that is, in 177-- 178-- > m >>= f 179-- 180-- @m@ is evaluated before the result is passed to @f@. 181-- 182-- > instance Monad Eval where 183-- > return = Done 184-- > m >>= k = case m of 185-- > Done x -> k x 186-- 187-- If you wanted to construct a 'Strategy' for a pair that sparked the 188-- first component in parallel and then evaluated the second 189-- component, you could write 190-- 191-- > myStrat :: Strategy (a,b) 192-- > myStrat (a,b) = do { a' <- rpar a; b' <- rseq b; return (a',b') } 193-- 194-- Alternatively, you could write this more compactly using the 195-- Applicative style as 196-- 197-- > myStrat (a,b) = (,) <$> rpar a <*> rseq b 198 199-- More examples, using the Applicative instance: 200-- 201-- > parList :: Strategy a -> Strategy [a] 202-- > parList strat = traverse (rpar `dot` strat)) 203-- 204-- > evalPair :: Strategy a -> Strategy b -> Strategy (a,b) 205-- > evalPair f g (a,b) = pure (,) <$> f a <*> g b 206-- 207 208#if __GLASGOW_HASKELL__ >= 702 209 210newtype Eval a = Eval {unEval_ :: IO a} 211 deriving (Functor, Applicative, Monad) 212 -- GHC 7.2.1 added the seq# and spark# primitives, that we use in 213 -- the Eval monad implementation in order to get the correct 214 -- strictness behaviour. 215 216-- | Pull the result out of the monad. 217runEval :: Eval a -> a 218# if MIN_VERSION_base(4,4,0) 219runEval = unsafeDupablePerformIO . unEval_ 220# else 221runEval = unsafePerformIO . unEval_ 222# endif 223 224-- | Run the evaluation in the 'IO' monad. This allows sequencing of 225-- evaluations relative to 'IO' actions. 226runEvalIO :: Eval a -> IO a 227runEvalIO = unEval_ 228 229-- We don't use GND to derive MonadFix from the IO instance. The IO instance 230-- has to be very careful to ensure that lazy blackholing doesn't cause IO 231-- actions to be duplicated in case of an infinite loop. This has a small 232-- performance cost. Eval computations are always assumed to be pure, so 233-- duplicating them is okay. What about ST computations embedded in Eval ones? 234-- Those also shouldn't be a problem: the ST computations are "closed", so it's 235-- safe to duplicate them, and the RTS already takes care to avoid resuming 236-- a computation paused by an asynchronous exception in multiple threads. 237-- Lazy ST takes care of itself with noDuplicate#, so we don't really need 238-- to think about it too much. 239-- 240-- Note: 241-- mfix f = let res = runEval (Lift <$> f (unLift res)) 242-- in case res of Lift r -> return r 243-- data Lift a = Lift a 244instance MonadFix Eval where 245 -- Borrowed from the instance for ST 246 mfix k = Eval $ IO $ \ s -> 247 let ans = liftEv (k r) s 248 Evret _ r = ans 249 in 250 case ans of Evret s' x -> (# s', x #) 251 252data Evret a = Evret (State# RealWorld) a 253 254-- liftEv is useful when we want a lifted result from an Eval computation. It 255-- is used to implement mfix. 256liftEv :: Eval a -> State# RealWorld -> Evret a 257liftEv (Eval (IO m)) = \s -> case m s of (# s', r #) -> Evret s' r 258 259#else 260 261data Eval a = Done a 262 263-- | Pull the result out of the monad. 264runEval :: Eval a -> a 265runEval (Done x) = x 266 267-- | Run the evaluation in the 'IO' monad. This allows sequencing of 268-- evaluations relative to 'IO' actions. 269runEvalIO :: Eval a -> IO a 270runEvalIO (Done x) = return x 271 272instance Functor Eval where 273 fmap = liftM 274 275instance Applicative Eval where 276 pure = Done 277 (<*>) = ap 278 279instance Monad Eval where 280 return = pure 281 Done x >>= k = lazy (k x) -- Note: pattern 'Done x' makes '>>=' strict 282 283instance MonadFix Eval where 284 mfix f = let r = f (runEval r) in r 285 286{-# RULES "lazy Done" forall x . lazy (Done x) = Done x #-} 287 288-- The Eval monad satisfies the monad laws. 289-- 290-- (1) Left identity: 291-- return x >>= f ==> Done x >>= f ==> f x 292-- 293-- (2) Right identity: 294-- (i) m >>= return =*> Done u >>= return 295-- ==> return u 296-- ==> Done u <*= m 297-- (ii) m >>= return =*> undefined >>= return 298-- ==> undefined <*= m 299-- 300-- (3) Associativity: 301-- (i) (m >>= f) >>= g =*> (Done u >>= f) >>= g 302-- ==> f u >>= g <== (\x -> f x >>= g) u 303-- <== Done u >>= (\x -> f x >>= g) 304-- <*= m >>= (\x -> f x >>= g) 305-- (ii) (m >>= f) >>= g =*> (undefined >>= f) >>= g 306-- ==> undefined >>= g 307-- ==> undefined <== undefined >>= (\x -> f x >>= g) 308-- <*= m >>= (\x -> f x >>= g) 309 310#endif 311 312 313-- ----------------------------------------------------------------------------- 314-- Strategies 315 316-- | A 'Strategy' is a function that embodies a parallel evaluation strategy. 317-- The function traverses (parts of) its argument, evaluating subexpressions 318-- in parallel or in sequence. 319-- 320-- A 'Strategy' may do an arbitrary amount of evaluation of its 321-- argument, but should not return a value different from the one it 322-- was passed. 323-- 324-- Parallel computations may be discarded by the runtime system if the 325-- program no longer requires their result, which is why a 'Strategy' 326-- function returns a new value equivalent to the old value. The 327-- intention is that the program applies the 'Strategy' to a 328-- structure, and then uses the returned value, discarding the old 329-- value. This idiom is expressed by the 'using' function. 330-- 331type Strategy a = a -> Eval a 332 333-- | Evaluate a value using the given 'Strategy'. 334-- 335-- > x `using` s = runEval (s x) 336-- 337using :: a -> Strategy a -> a 338x `using` strat = runEval (strat x) 339 340-- | evaluate a value using the given 'Strategy'. This is simply 341-- 'using' with the arguments reversed. 342-- 343withStrategy :: Strategy a -> a -> a 344withStrategy = flip using 345 346-- | Evaluate a value using the given 'Strategy' inside the 'IO' monad. See 347-- also 'runEvalIO'. 348-- 349-- > x `usingIO` s = runEvalIO (s x) 350-- 351usingIO :: a -> Strategy a -> IO a 352x `usingIO` strat = runEvalIO (strat x) 353 354-- | Evaluate a value using the given 'Strategy' inside the 'IO' monad. This 355-- is simply 'usingIO' with the arguments reversed. 356-- 357withStrategyIO :: Strategy a -> a -> IO a 358withStrategyIO = flip usingIO 359 360-- | Compose two strategies sequentially. 361-- This is the analogue to function composition on strategies. 362-- 363-- For any strategies @strat1@, @strat2@, and @strat3@, 364-- 365-- > (strat1 `dot` strat2) `dot` strat3 == strat1 `dot` (strat2 `dot` strat3) 366-- > strat1 `dot` strat1 = strat1 367-- > strat1 `dot` r0 == strat1 368-- 369-- > strat2 `dot` strat1 == strat2 . withStrategy strat1 370-- 371dot :: Strategy a -> Strategy a -> Strategy a 372strat2 `dot` strat1 = strat2 . runEval . strat1 373 374-- Proof of strat2 `dot` strat1 == strat2 . withStrategy strat1 375-- 376-- strat2 . withStrategy strat1 377-- == \x -> strat2 (withStrategy strat1 x) 378-- == \x -> strat2 (x `using` strat1) 379-- == \x -> strat2 (runEval (strat1 x)) 380-- == \x -> (strat2 . runEval . strat1) x 381-- == strat2 `dot` strat1 382 383-- One might be tempted to think that 'dot' is equivalent to '(<=<)', 384-- the right-to-left Kleisli composition in the Eval monad, because 385-- '(<=<)' can take the type @Strategy a -> Strategy a -> Strategy a@ 386-- and intuitively does what 'dot' does: First apply the strategy to the 387-- right then the one to the left. However, there is a subtle difference 388-- in strictness, witnessed by the following example: 389-- 390-- > (r0 `dot` rseq) undefined == Done undefined 391-- > (r0 <=< rseq) undefined == undefined 392-- 393 394-- | Inject a sequential strategy (ie. coerce a sequential strategy 395-- to a general strategy). 396-- 397-- Thanks to 'evalSeq', the type @Control.Seq.Strategy a@ is a subtype 398-- of @'Strategy' a@. 399evalSeq :: SeqStrategy a -> Strategy a 400evalSeq strat x = strat x `pseq` return x 401 402-- | A name for @Control.Seq.Strategy@, for documentation only. 403type SeqStrategy a = Control.Seq.Strategy a 404 405-- -------------------------------------------------------------------------- 406-- Basic strategies (some imported from SeqStrategies) 407 408-- | 'r0' performs *no* evaluation. 409-- 410-- > r0 == evalSeq Control.Seq.r0 411-- 412r0 :: Strategy a 413r0 x = return x 414 415-- Proof of r0 == evalSeq Control.Seq.r0 416-- 417-- evalSeq Control.Seq.r0 418-- == \x -> Control.Seq.r0 x `pseq` return x 419-- == \x -> Control.Seq.Done `pseq` return x 420-- == \x -> return x 421-- == r0 422 423-- | 'rseq' evaluates its argument to weak head normal form. 424-- 425-- > rseq == evalSeq Control.Seq.rseq 426-- 427rseq :: Strategy a 428#if __GLASGOW_HASKELL__ >= 702 429rseq x = Eval (evaluate x) 430#else 431rseq x = x `seq` return x 432#endif 433-- Staged NOINLINE so we can match on rseq in RULES 434{-# NOINLINE [1] rseq #-} 435 436 437-- Proof of rseq == evalSeq Control.Seq.rseq 438-- 439-- evalSeq Control.Seq.rseq 440-- == \x -> Control.Seq.rseq x `pseq` return x 441-- == \x -> (x `seq` Control.Seq.Done) `pseq` return x 442-- == \x -> x `pseq` return x 443-- == rseq 444 445-- | 'rdeepseq' fully evaluates its argument. 446-- 447-- > rdeepseq == evalSeq Control.Seq.rdeepseq 448-- 449rdeepseq :: NFData a => Strategy a 450rdeepseq x = do rseq (rnf x); return x 451 452-- Proof of rdeepseq == evalSeq Control.Seq.rdeepseq 453-- 454-- evalSeq Control.Seq.rdeepseq 455-- == \x -> Control.Seq.rdeepseq x `pseq` return x 456-- == \x -> (x `deepseq` Control.Seq.Done) `pseq` return x 457-- == \x -> (rnf x `seq` Control.Seq.Done) `pseq` return x 458-- == \x -> rnf x `pseq` return x 459-- == rdeepseq 460 461-- | 'rpar' sparks its argument (for evaluation in parallel). 462rpar :: Strategy a 463#if __GLASGOW_HASKELL__ >= 702 464rpar x = Eval $ IO $ \s -> spark# x s 465#else 466rpar x = case (par# x) of { _ -> Done x } 467#endif 468{-# INLINE rpar #-} 469 470-- | Perform a computation in parallel using a strategy. 471-- 472-- @ 473-- rparWith strat x 474-- @ 475-- 476-- will spark @strat x@. Note that @rparWith strat@ is /not/ the 477-- same as @rpar `dot` strat@. Specifically, @rpar `dot` strat@ 478-- always sparks a computation to reduce the result of the 479-- strategic computation to WHNF, while @rparWith strat@ need 480-- not. 481-- 482-- > rparWith r0 = r0 483-- > rparWith rpar = rpar 484-- > rparWith rseq = rpar 485-- 486-- @rparWith rpar x@ creates a spark that immediately creates another 487-- spark to evaluate @x@. We consider this equivalent to @rpar@ because 488-- there isn't any real additional parallelism. However, it is always 489-- less efficient because there's a bit of extra work to create the 490-- first (useless) spark. Similarly, @rparWith r0@ creates a spark 491-- that does precisely nothing. No real parallelism is added, but there 492-- is a bit of extra work to do nothing. 493rparWith :: Strategy a -> Strategy a 494rparWith strat = parEval . strat 495 496-- | 'parEval' sparks the computation of its argument for evaluation in 497-- parallel. Unlike @'rpar' . 'runEval'@, 'parEval' 498-- 499-- * does not exit the `Eval` monad 500-- 501-- * does not have a built-in `rseq`, so for example @'parEval' ('r0' x)@ 502-- behaves as you might expect (it creates a spark that does no 503-- evaluation). 504-- 505-- It is related to 'rparWith' by the following equality: 506-- 507-- > parEval . strat = rparWith strat 508-- 509parEval :: Eval a -> Eval a 510-- The intermediate `Lift` box is necessary, in order to avoid a built-in 511-- `rseq` in `parEval`. In particular, we want @parEval . r0 = r0@, not 512-- @parEval . r0 = rpar@. 513parEval m = do 514 l <- rpar r 515 return (case l of Lift x -> x) 516 517 where 518 r = runEval (Lift <$> m) 519 520data Lift a = Lift a 521 522-- -------------------------------------------------------------------------- 523-- Strategy combinators for Traversable data types 524 525-- | Evaluate the elements of a traversable data structure 526-- according to the given strategy. 527evalTraversable :: Traversable t => Strategy a -> Strategy (t a) 528evalTraversable = traverse 529{-# INLINE evalTraversable #-} 530 531-- | Like 'evalTraversable' but evaluates all elements in parallel. 532parTraversable :: Traversable t => Strategy a -> Strategy (t a) 533parTraversable strat = evalTraversable (rparWith strat) 534{-# INLINE parTraversable #-} 535 536-- -------------------------------------------------------------------------- 537-- Strategies for lists 538 539-- | Evaluate each element of a list according to the given strategy. 540-- Equivalent to 'evalTraversable' at the list type. 541evalList :: Strategy a -> Strategy [a] 542evalList = evalTraversable 543-- Alternative explicitly recursive definition: 544-- evalList strat [] = return [] 545-- evalList strat (x:xs) = strat x >>= \x' -> 546-- evalList strat xs >>= \xs' -> 547-- return (x':xs') 548 549-- | Evaluate each element of a list in parallel according to given strategy. 550-- Equivalent to 'parTraversable' at the list type. 551parList :: Strategy a -> Strategy [a] 552parList = parTraversable 553-- Alternative definition via evalList: 554-- parList strat = evalList (rparWith strat) 555 556-- | @'evaListSplitAt' n stratPref stratSuff@ evaluates the prefix 557-- (of length @n@) of a list according to @stratPref@ and its the suffix 558-- according to @stratSuff@. 559evalListSplitAt :: Int -> Strategy [a] -> Strategy [a] -> Strategy [a] 560evalListSplitAt n stratPref stratSuff xs 561 = let (ys,zs) = splitAt n xs in 562 stratPref ys >>= \ys' -> 563 stratSuff zs >>= \zs' -> 564 return (ys' ++ zs') 565 566-- | Like 'evalListSplitAt' but evaluates both sublists in parallel. 567parListSplitAt :: Int -> Strategy [a] -> Strategy [a] -> Strategy [a] 568parListSplitAt n stratPref stratSuff = evalListSplitAt n (rparWith stratPref) (rparWith stratSuff) 569 570-- | Evaluate the first n elements of a list according to the given strategy. 571evalListN :: Int -> Strategy a -> Strategy [a] 572evalListN n strat = evalListSplitAt n (evalList strat) r0 573 574-- | Like 'evalListN' but evaluates the first n elements in parallel. 575parListN :: Int -> Strategy a -> Strategy [a] 576parListN n strat = evalListN n (rparWith strat) 577 578-- | Evaluate the nth element of a list (if there is such) according to 579-- the given strategy. 580-- This nth is 0-based. For example, @[1, 2, 3, 4, 5] `using` evalListNth 4 rseq@ 581-- will eval @5@, not @4@. 582-- The spine of the list up to the nth element is evaluated as a side effect. 583evalListNth :: Int -> Strategy a -> Strategy [a] 584evalListNth n strat = evalListSplitAt n r0 (evalListN 1 strat) 585 586-- | Like 'evalListN' but evaluates the nth element in parallel. 587parListNth :: Int -> Strategy a -> Strategy [a] 588parListNth n strat = evalListNth n (rparWith strat) 589 590-- | Divides a list into chunks, and applies the strategy 591-- @'evalList' strat@ to each chunk in parallel. 592-- 593-- It is expected that this function will be replaced by a more 594-- generic clustering infrastructure in the future. 595-- 596-- If the chunk size is 1 or less, 'parListChunk' is equivalent to 597-- 'parList' 598-- 599parListChunk :: Int -> Strategy a -> Strategy [a] 600parListChunk n strat xs 601 | n <= 1 = parList strat xs 602 | otherwise = concat `fmap` parList (evalList strat) (chunk n xs) 603 604chunk :: Int -> [a] -> [[a]] 605chunk _ [] = [] 606chunk n xs = as : chunk n bs where (as,bs) = splitAt n xs 607 608-- -------------------------------------------------------------------------- 609-- Convenience 610 611-- | A combination of 'parList' and 'map', encapsulating a common pattern: 612-- 613-- > parMap strat f = withStrategy (parList strat) . map f 614-- 615parMap :: Strategy b -> (a -> b) -> [a] -> [b] 616parMap strat f = (`using` parList strat) . map f 617 618-- -------------------------------------------------------------------------- 619-- Strategies for lazy lists 620 621-- List-based non-compositional rolling buffer strategy, evaluating list 622-- elements to weak head normal form. 623-- Not to be exported; used in evalBuffer and for optimisation. 624evalBufferWHNF :: Int -> Strategy [a] 625evalBufferWHNF n0 xs0 = return (ret xs0 (start n0 xs0)) 626 where -- ret :: [a] -> [a] -> [a] 627 ret (x:xs) (y:ys) = y `pseq` (x : ret xs ys) 628 ret xs _ = xs 629 630 -- start :: Int -> [a] -> [a] 631 start 0 ys = ys 632 start !_n [] = [] 633 start !n (y:ys) = y `pseq` start (n-1) ys 634 635-- | 'evalBuffer' is a rolling buffer strategy combinator for (lazy) lists. 636-- 637-- 'evalBuffer' is not as compositional as the type suggests. In fact, 638-- it evaluates list elements at least to weak head normal form, 639-- disregarding a strategy argument 'r0'. 640-- 641-- > evalBuffer n r0 == evalBuffer n rseq 642-- 643evalBuffer :: Int -> Strategy a -> Strategy [a] 644evalBuffer n strat = evalBufferWHNF n . map (withStrategy strat) 645 646-- Like evalBufferWHNF but sparks the list elements when pushing them 647-- into the buffer. 648-- Not to be exported; used in parBuffer and for optimisation. 649parBufferWHNF :: Int -> Strategy [a] 650parBufferWHNF n0 xs0 = return (ret xs0 (start n0 xs0)) 651 where -- ret :: [a] -> [a] -> [a] 652 ret (x:xs) (y:ys) = y `par` (x : ret xs ys) 653 ret xs _ = xs 654 655 -- start :: Int -> [a] -> [a] 656 start 0 ys = ys 657 start !_n [] = [] 658 start !n (y:ys) = y `par` start (n-1) ys 659 660 661-- | Like 'evalBuffer' but evaluates the list elements in parallel when 662-- pushing them into the buffer. 663parBuffer :: Int -> Strategy a -> Strategy [a] 664parBuffer n strat = parBufferWHNF n . map (withStrategy strat) 665-- Alternative definition via evalBuffer (may compromise firing of RULES): 666-- parBuffer n strat = evalBuffer n (rparWith strat) 667 668-- Deforest the intermediate list in parBuffer/evalBuffer when it is 669-- unnecessary: 670 671{-# NOINLINE [1] evalBuffer #-} 672{-# NOINLINE [1] parBuffer #-} 673{-# RULES 674"evalBuffer/rseq" forall n . evalBuffer n rseq = evalBufferWHNF n 675"parBuffer/rseq" forall n . parBuffer n rseq = parBufferWHNF n 676 #-} 677 678-- -------------------------------------------------------------------------- 679-- Strategies for tuples 680 681evalTuple2 :: Strategy a -> Strategy b -> Strategy (a,b) 682evalTuple2 strat1 strat2 (x1,x2) = 683 pure (,) <*> strat1 x1 <*> strat2 x2 684 685evalTuple3 :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c) 686evalTuple3 strat1 strat2 strat3 (x1,x2,x3) = 687 pure (,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 688 689evalTuple4 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy (a,b,c,d) 690evalTuple4 strat1 strat2 strat3 strat4 (x1,x2,x3,x4) = 691 pure (,,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 <*> strat4 x4 692 693evalTuple5 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy (a,b,c,d,e) 694evalTuple5 strat1 strat2 strat3 strat4 strat5 (x1,x2,x3,x4,x5) = 695 pure (,,,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 <*> strat4 x4 <*> strat5 x5 696 697evalTuple6 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy (a,b,c,d,e,f) 698evalTuple6 strat1 strat2 strat3 strat4 strat5 strat6 (x1,x2,x3,x4,x5,x6) = 699 pure (,,,,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 <*> strat4 x4 <*> strat5 x5 <*> strat6 x6 700 701evalTuple7 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy (a,b,c,d,e,f,g) 702evalTuple7 strat1 strat2 strat3 strat4 strat5 strat6 strat7 (x1,x2,x3,x4,x5,x6,x7) = 703 pure (,,,,,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 <*> strat4 x4 <*> strat5 x5 <*> strat6 x6 <*> strat7 x7 704 705evalTuple8 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy h -> Strategy (a,b,c,d,e,f,g,h) 706evalTuple8 strat1 strat2 strat3 strat4 strat5 strat6 strat7 strat8 (x1,x2,x3,x4,x5,x6,x7,x8) = 707 pure (,,,,,,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 <*> strat4 x4 <*> strat5 x5 <*> strat6 x6 <*> strat7 x7 <*> strat8 x8 708 709evalTuple9 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy h -> Strategy i -> Strategy (a,b,c,d,e,f,g,h,i) 710evalTuple9 strat1 strat2 strat3 strat4 strat5 strat6 strat7 strat8 strat9 (x1,x2,x3,x4,x5,x6,x7,x8,x9) = 711 pure (,,,,,,,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 <*> strat4 x4 <*> strat5 x5 <*> strat6 x6 <*> strat7 x7 <*> strat8 x8 <*> strat9 x9 712 713parTuple2 :: Strategy a -> Strategy b -> Strategy (a,b) 714parTuple2 strat1 strat2 = 715 evalTuple2 (rparWith strat1) (rparWith strat2) 716 717parTuple3 :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c) 718parTuple3 strat1 strat2 strat3 = 719 evalTuple3 (rparWith strat1) (rparWith strat2) (rparWith strat3) 720 721parTuple4 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy (a,b,c,d) 722parTuple4 strat1 strat2 strat3 strat4 = 723 evalTuple4 (rparWith strat1) (rparWith strat2) (rparWith strat3) (rparWith strat4) 724 725parTuple5 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy (a,b,c,d,e) 726parTuple5 strat1 strat2 strat3 strat4 strat5 = 727 evalTuple5 (rparWith strat1) (rparWith strat2) (rparWith strat3) (rparWith strat4) (rparWith strat5) 728 729parTuple6 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy (a,b,c,d,e,f) 730parTuple6 strat1 strat2 strat3 strat4 strat5 strat6 = 731 evalTuple6 (rparWith strat1) (rparWith strat2) (rparWith strat3) (rparWith strat4) (rparWith strat5) (rparWith strat6) 732 733parTuple7 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy (a,b,c,d,e,f,g) 734parTuple7 strat1 strat2 strat3 strat4 strat5 strat6 strat7 = 735 evalTuple7 (rparWith strat1) (rparWith strat2) (rparWith strat3) (rparWith strat4) (rparWith strat5) (rparWith strat6) (rparWith strat7) 736 737parTuple8 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy h -> Strategy (a,b,c,d,e,f,g,h) 738parTuple8 strat1 strat2 strat3 strat4 strat5 strat6 strat7 strat8 = 739 evalTuple8 (rparWith strat1) (rparWith strat2) (rparWith strat3) (rparWith strat4) (rparWith strat5) (rparWith strat6) (rparWith strat7) (rparWith strat8) 740 741parTuple9 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy h -> Strategy i -> Strategy (a,b,c,d,e,f,g,h,i) 742parTuple9 strat1 strat2 strat3 strat4 strat5 strat6 strat7 strat8 strat9 = 743 evalTuple9 (rparWith strat1) (rparWith strat2) (rparWith strat3) (rparWith strat4) (rparWith strat5) (rparWith strat6) (rparWith strat7) (rparWith strat8) (rparWith strat9) 744 745-- -------------------------------------------------------------------------- 746-- Strategic function application 747 748{- 749These are very handy when writing pipeline parallelism asa sequence of 750@$@, @$|@ and @$||@'s. There is no need of naming intermediate values 751in this case. The separation of algorithm from strategy is achieved by 752allowing strategies only as second arguments to @$|@ and @$||@. 753-} 754 755-- | Sequential function application. The argument is evaluated using 756-- the given strategy before it is given to the function. 757($|) :: (a -> b) -> Strategy a -> a -> b 758f $| s = \ x -> let z = x `using` s in z `pseq` f z 759 760-- | Parallel function application. The argument is evaluated using 761-- the given strategy, in parallel with the function application. 762($||) :: (a -> b) -> Strategy a -> a -> b 763f $|| s = \ x -> let z = x `using` s in z `par` f z 764 765-- | Sequential function composition. The result of 766-- the second function is evaluated using the given strategy, 767-- and then given to the first function. 768(.|) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c) 769(.|) f s g = \ x -> let z = g x `using` s in 770 z `pseq` f z 771 772-- | Parallel function composition. The result of the second 773-- function is evaluated using the given strategy, 774-- in parallel with the application of the first function. 775(.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c) 776(.||) f s g = \ x -> let z = g x `using` s in 777 z `par` f z 778 779-- | Sequential inverse function composition, 780-- for those who read their programs from left to right. 781-- The result of the first function is evaluated using the 782-- given strategy, and then given to the second function. 783(-|) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c) 784(-|) f s g = \ x -> let z = f x `using` s in 785 z `pseq` g z 786 787-- | Parallel inverse function composition, 788-- for those who read their programs from left to right. 789-- The result of the first function is evaluated using the 790-- given strategy, in parallel with the application of the 791-- second function. 792(-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c) 793(-||) f s g = \ x -> let z = f x `using` s in 794 z `par` g z 795 796-- ----------------------------------------------------------------------------- 797-- Old/deprecated stuff 798 799{-# DEPRECATED Done "The Strategy type is now a -> Eval a, not a -> Done" #-} 800-- | DEPRECCATED: replaced by the 'Eval' monad 801type Done = () 802 803{-# DEPRECATED demanding "Use pseq or $| instead" #-} 804-- | DEPRECATED: Use 'pseq' or '$|' instead 805demanding :: a -> Done -> a 806demanding = flip pseq 807 808{-# DEPRECATED sparking "Use par or $|| instead" #-} 809-- | DEPRECATED: Use 'par' or '$||' instead 810sparking :: a -> Done -> a 811sparking = flip par 812 813{-# DEPRECATED (>|) "Use pseq or $| instead" #-} 814-- | DEPRECATED: Use 'pseq' or '$|' instead 815(>|) :: Done -> Done -> Done 816(>|) = Prelude.seq 817 818{-# DEPRECATED (>||) "Use par or $|| instead" #-} 819-- | DEPRECATED: Use 'par' or '$||' instead 820(>||) :: Done -> Done -> Done 821(>||) = par 822 823{-# DEPRECATED rwhnf "renamed to rseq" #-} 824-- | DEPRECATED: renamed to 'rseq' 825rwhnf :: Strategy a 826rwhnf = rseq 827 828{-# DEPRECATED seqTraverse "renamed to evalTraversable" #-} 829-- | DEPRECATED: renamed to 'evalTraversable' 830seqTraverse :: Traversable t => Strategy a -> Strategy (t a) 831seqTraverse = evalTraversable 832 833{-# DEPRECATED parTraverse "renamed to parTraversable" #-} 834-- | DEPRECATED: renamed to 'parTraversable' 835parTraverse :: Traversable t => Strategy a -> Strategy (t a) 836parTraverse = parTraversable 837 838{-# DEPRECATED seqList "renamed to evalList" #-} 839-- | DEPRECATED: renamed to 'evalList' 840seqList :: Strategy a -> Strategy [a] 841seqList = evalList 842 843{-# DEPRECATED seqPair "renamed to evalTuple2" #-} 844-- | DEPRECATED: renamed to 'evalTuple2' 845seqPair :: Strategy a -> Strategy b -> Strategy (a,b) 846seqPair = evalTuple2 847 848{-# DEPRECATED parPair "renamed to parTuple2" #-} 849-- | DEPRECATED: renamed to 'parTuple2' 850parPair :: Strategy a -> Strategy b -> Strategy (a,b) 851parPair = parTuple2 852 853{-# DEPRECATED seqTriple "renamed to evalTuple3" #-} 854-- | DEPRECATED: renamed to 'evalTuple3' 855seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c) 856seqTriple = evalTuple3 857 858{-# DEPRECATED parTriple "renamed to parTuple3" #-} 859-- | DEPRECATED: renamed to 'parTuple3' 860parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c) 861parTriple = parTuple3 862 863{-# DEPRECATED unEval "renamed to runEval" #-} 864-- | DEPRECATED: renamed to 'runEval' 865unEval :: Eval a -> a 866unEval = runEval 867 868{- $history #history# 869 870The strategies library has a long history. What follows is a 871summary of how the current design evolved, and is mostly of 872interest to those who are familiar with an older version, or need 873to adapt old code to use the newer API. 874 875Version 1.x 876 877 The original Strategies design is described in /Algorithm + Strategy = Parallelism/ <http://www.macs.hw.ac.uk/~dsg/gph/papers/html/Strategies/strategies.html> 878 and the code was written by 879 Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al. 880 881Version 2.x 882 883Later, during work on the shared-memory implementation of 884parallelism in GHC, we discovered that the original formulation of 885Strategies had some problems, in particular it lead to space leaks 886and difficulties expressing speculative parallelism. Details are in 887the paper /Runtime Support for Multicore Haskell/ <http://community.haskell.org/~simonmar/papers/multicore-ghc.pdf>. 888 889This module has been rewritten in version 2. The main change is to 890the 'Strategy a' type synonym, which was previously @a -> Done@ and 891is now @a -> Eval a@. This change helps to fix the space leak described 892in \"Runtime Support for Multicore Haskell\". The problem is that 893the runtime will currently retain the memory referenced by all 894sparks, until they are evaluated. Hence, we must arrange to 895evaluate all the sparks eventually, just in case they aren't 896evaluated in parallel, so that they don't cause a space leak. This 897is why we must return a \"new\" value after applying a 'Strategy', 898so that the application can evaluate each spark created by the 899'Strategy'. 900 901The simple rule is this: you /must/ use the result of applying 902a 'Strategy' if the strategy creates parallel sparks, and you 903should probably discard the the original value. If you don't 904do this, currently it may result in a space leak. In the 905future (GHC 6.14), it will probably result in lost parallelism 906instead, as we plan to change GHC so that unreferenced sparks 907are discarded rather than retained (we can't make this change 908until most code is switched over to this new version of 909Strategies, because code using the old verison of Strategies 910would be broken by the change in policy). 911 912The other changes in version 2.x are: 913 914 * Strategies can now be defined using a convenient Monad/Applicative 915 type, 'Eval'. e.g. @parList s = traverse (Par . (``using`` s))@ 916 917 * 'parList' has been generalised to 'parTraverse', which works on 918 any 'Traversable' type, and similarly 'seqList' has been generalised 919 to 'seqTraverse' 920 921 * 'parList' and 'parBuffer' have versions specialised to 'rwhnf', 922 and there are transformation rules that automatically translate 923 e.g. @parList rwnhf@ into a call to the optimised version. 924 925 * 'NFData' has been moved to @Control.DeepSeq@ in the @deepseq@ 926 package. Note that since the 'Strategy' type changed, 'rnf' 927 is no longer a 'Strategy': use 'rdeepseq' instead. 928 929Version 2.1 moved NFData into a separate package, @deepseq@. 930 931Version 2.2 changed the type of Strategy to @a -> Eval a@, and 932re-introduced the @r0@ strategy which was missing in version 2.1. 933 934Version 2.3 simplified the @Eval@ type, so that @Eval@ is now just 935the strict identity monad. This change and various other 936improvements and refactorings are thanks to Patrick Maier who 937noticed that @Eval@ didn't satisfy the monad laws, and that a 938simpler version would fix that problem. 939 940(version 2.3 was not released on Hackage). 941 942Version 3 introduced a major overhaul of the API, to match what is 943presented in the paper 944 945 /Seq no More: Better Strategies for Parallel Haskell/ 946 <http://community.haskell.org/~simonmar/papers/strategies.pdf> 947 948The major differences in the API are: 949 950 * The addition of Sequential strategies ("Control.Seq") as 951 a composable means for specifying sequential evaluation. 952 953 * Changes to the naming scheme: 'rwhnf' renamed to 'rseq', 954 'seqList' renamed to 'evalList', 'seqPair' renamed to 955 'evalTuple2', 956 957The naming scheme is now as follows: 958 959 * Basic polymorphic strategies (of type @'Strategy' a@) are called @r...@. 960 Examples: 'r0', 'rseq', 'rpar', 'rdeepseq'. 961 962 * A strategy combinator for a particular type constructor 963 or constructor class @T@ is called @evalT...@, @parT...@ or @seqT...@. 964 965 * The @seqT...@ combinators (residing in module 966 "Control.Seq") yield sequential strategies. 967 Thus, @seqT...@ combinators cannot spark, nor can the sequential 968 strategies to which they may be applied. 969 Examples: 'seqTuple2', 'seqListN', 'seqFoldable'. 970 971 * The @evalT...@ combinators do not spark themselves, yet they may 972 be applied to strategies that do spark. (They may also be applied 973 to non-sparking strategies; however, in that case the corresponding 974 @seqT...@ combinator might be a better choice.) 975 Examples: 'evalTuple2', 'evalListN', 'evalTraversable'. 976 977 * The @parT...@ combinators, which are derived from their @evalT...@ 978 counterparts, do spark. They may be applied to all strategies, 979 whether sparking or not. 980 Examples: 'parTuple2', 'parListN', 'parTraversable'. 981 982 * An exception to the type driven naming scheme are 'evalBuffer' and 983 'parBuffer', which are not named after their type constructor (lists) 984 but after their function (rolling buffer of fixed size). 985-} 986