X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=Control%2FParallel%2FStrategies.hs;h=ce3f7b08d52d30f927fc1f6321c33549ecbe60cc;hb=f8218e0dc6d2f354f89c1b4c0cc63f61844004c1;hp=cad9aa3bf135a21231125c240b127f777653003e;hpb=7f1f4e7a695c402ddd3a1dc2cc7114e649a78ebc;p=ghc-base.git diff --git a/Control/Parallel/Strategies.hs b/Control/Parallel/Strategies.hs index cad9aa3..ce3f7b0 100644 --- a/Control/Parallel/Strategies.hs +++ b/Control/Parallel/Strategies.hs @@ -1,296 +1,61 @@ ----------------------------------------------------------------------------- --- +-- | -- Module : Control.Parallel.Strategies -- Copyright : (c) The University of Glasgow 2001 --- License : BSD-style (see the file libraries/core/LICENSE) +-- License : BSD-style (see the file libraries/base/LICENSE) -- -- Maintainer : libraries@haskell.org -- Stability : experimental -- Portability : non-portable -- --- $Id: Strategies.hs,v 1.1 2001/06/28 14:15:02 simonmar Exp $ --- -- Parallel strategy combinators -- ----------------------------------------------------------------------------- +module Control.Parallel.Strategies where -{- -Time-stamp: -$Id: Strategies.hs,v 1.1 2001/06/28 14:15:02 simonmar Exp $ - -This module defines parallel strategy combinators - - Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al. - - Based on Version VII (1/5/96) `Strategies96' of type a -> () +-- based on hslibs/concurrent/Strategies.lhs; see it for more detailed +-- code comments. Original authors: +-- +-- Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al. +-- -Author: $Author: simonmar $ -Date: $Date: 2001/06/28 14:15:02 $ -Revision: $Revision: 1.1 $ -Source: $Source: /srv/cvs/cvs.haskell.org/fptools/libraries/base/Control/Parallel/Strategies.hs,v $ -State: $State: Exp $ +#ifdef __HADDOCK__ +import Prelude +#endif -This module defines evaluation strategies for controlling the parallel -evaluation of non-strict programs. They provide a clean separation between -algorithmic and behavioural code. +import Control.Parallel as Parallel +import Data.Ix +import Data.Array +import Data.Complex +import Data.Ratio -The functions described here, and their use is documented in +-- not a terribly portable way of getting at Ratio rep. +#ifdef __GLASGOW_HASKELL__ +import GHC.Real (Ratio(..)) -- The basic defns for Ratio +#endif -"Algorithm + Strategy = Parallelism", -P.W. Trinder, K. Hammond, H-W. Loidl, S.L. Peyton Jones -In Journal of Functional Programming 8(1):23--60, January 1998. -URL: http://www.cee.hw.ac.uk/~dsg/gph/papers/ps/strategies.ps.gz +#ifdef __HUGS__ +import Hugs.Prelude(Ratio(..) ) +#endif -This module supports Haskell 1.2, Haskell 1.4 and Haskell98. -The distinction is made based on the __HASKELL1__ CPP variable. -Parts of the module could be rewritten using constructor classes. +#ifdef __NHC__ +import Ratio (Ratio(..) ) +#endif ------------------------------------------------------------------------------ -The history of the Strategies module: - -Changelog: -$Log: Strategies.hs,v $ -Revision 1.1 2001/06/28 14:15:02 simonmar -First cut of the Haskell Core Libraries -======================================= - -NOTE: it's not meant to be a working snapshot. The code is just here -to look at and so the NHC/Hugs guys can start playing around with it. - -There is no build system. For GHC, the libraries tree is intended to -be grafted onto an existing fptools/ tree, and the Makefile in -libraries/core is a quick hack for that setup. This won't work at the -moment without the other changes needed in fptools/ghc, which I -haven't committed because they'll cause breakage. However, with the -changes required these sources build a working Prelude and libraries. - -The layout mostly follows the one we agreed on, with one or two minor -changes; in particular the Data/Array layout probably isn't final -(there are several choices here). - -The document is in libraries/core/doc as promised. - -The cbits stuff is just a copy of ghc/lib/std/cbits and has -GHC-specific stuff in it. We should really separate the -compiler-specific C support from any compiler-independent C support -there might be. - -Don't pay too much attention to the portability or stability status -indicated in the header of each source file at the moment - I haven't -gone through to make sure they're all consistent and make sense. - -I'm using non-literate source outside of GHC/. Hope that's ok with -everyone. - -We need to discuss how the build system is going to work... - -Revision 1.3 2001/03/22 03:51:12 hwloidl - -*- outline -*- -Time-stamp: - -This commit covers changes in GHC to get GUM (way=mp) and GUM/GdH (way=md) -working. It is a merge of my working version of GUM, based on GHC 4.06, -with GHC 4.11. Almost all changes are in the RTS (see below). - -GUM is reasonably stable, we used the 4.06 version in large-ish programs for -recent papers. Couple of things I want to change, but nothing urgent. -GUM/GdH has just been merged and needs more testing. Hope to do that in the -next weeks. It works in our working build but needs tweaking to run. -GranSim doesn't work yet (*sigh*). Most of the code should be in, but needs -more debugging. - -ToDo: I still want to make the following minor modifications before the release -- Better wrapper skript for parallel execution [ghc/compiler/main] -- Update parallel docu: started on it but it's minimal [ghc/docs/users_guide] -- Clean up [nofib/parallel]: it's a real mess right now (*sigh*) -- Update visualisation tools (minor things only IIRC) [ghc/utils/parallel] -- Add a Klingon-English glossary - -* RTS: - -Almost all changes are restricted to ghc/rts/parallel and should not -interfere with the rest. I only comment on changes outside the parallel -dir: - -- Several changes in Schedule.c (scheduling loop; createThreads etc); - should only affect parallel code -- Added ghc/rts/hooks/ShutdownEachPEHook.c -- ghc/rts/Linker.[ch]: GUM doesn't know about Stable Names (ifdefs)!! -- StgMiscClosures.h: END_TSO_QUEUE etc now defined here (from StgMiscClosures.hc) - END_ECAF_LIST was missing a leading stg_ -- SchedAPI.h: taskStart now defined in here; it's only a wrapper around - scheduleThread now, but might use some init, shutdown later -- RtsAPI.h: I have nuked the def of rts_evalNothing - -* Compiler: - -- ghc/compiler/main/DriverState.hs - added PVM-ish flags to the parallel way - added new ways for parallel ticky profiling and distributed exec - -- ghc/compiler/main/DriverPipeline.hs - added a fct run_phase_MoveBinary which is called with way=mp after linking; - it moves the bin file into a PVM dir and produces a wrapper script for - parallel execution - maybe cleaner to add a MoveBinary phase in DriverPhases.hs but this way - it's less intrusive and MoveBinary makes probably only sense for mp anyway - -* Nofib: - -- nofib/spectral/Makefile, nofib/real/Makefile, ghc/tests/programs/Makefile: - modified to skip some tests if HWL_NOFIB_HACK is set; only tmp to record - which test prgs cause problems in my working build right now - -Revision 1.2 2000/11/18 02:13:11 hwloidl -Now provides explicit def of seq (rather than just re-exporting). -Required by the current version of the compiler. - -Revision 1.1 2000/01/14 13:34:32 hwloidl -Module for specifying (parallel) behavioural code. - -Revision 1.9 1997/10/01 00:27:19 hwloidl -Type of par and seq changed to Done -> Done -> Done with Done = () -Works for Haskell 1.2 as well as Haskell 1.4 (checks the CPP variable -__HASKELL1__ to distinguish setups). -Fixed precedences for par and seq for Haskell 1.4 (stronger than using). -New infix operators >| and >|| as aliases for par and seq as strategy -combinators. - -Revision 1.8 1997/05/20 21:13:22 hwloidl -Revised to use `demanding` and `sparking` (final JFP paper version) - -Revision 1.7 1997/04/02 21:26:21 hwloidl -Minor changes in documentation, none in the code. - - -revision 1.5 -Version VII.1; Strategies96; Type: a -> () -Minor changes to previous version. -CPP flags now separate GUM from GranSim version. -Infix declaration for `using` (important for e.g. quicksort where the old -version puts parentheses in the wrong way). -Moer instances for NFData and markStartegies (in GranSim setup only). - -revision 1.4 -Version VII; Strategies96; Type: a -> () -The type has changed again; with the old type it's not possible to describe -all the strategies we want (for example seqPair r0 rnf which should not -evaluate the first component of the pair at all). The () type acts as info -that the strategy has been applied. -The function `using` is used as inverse strategy application i.e. -on top level we usually have something like res `using` strat where ... -The markStrategy hack is included in this version: it attaches an Int value -to the currently running strategy (this can be inherited by all sub-strats) -It doesn't model the jumps between evaluating producer and consumer properly -(for that something like cost centers would be necessary). - -revision 1.3 -Version VI (V-based); Strategies95; Type: a -> a -Now uses library modules like FiniteMap with strategies in there. -CPP flags for using the same module with GUM and GranSim. -A few new strategies. - -revision 1.2 -Version V; Strategies95; Type: a -> a -The type of Strategies has changed from a -> () to a -> a -All strategies and instances of NFData have been redefined accordingly. -This branch started off after discussions between PWT, SLPJ and HWL in -mid Nov (start of development of the actual module: 10/1/96) - -revision 1.1 Initial revision ------------------------------------------------------------------------------ --- To use fakeinfo first replace all %%$ by \@ --- If you have fakeinfo makers in the file you need a slightly modified --- version of the lit-deatify script (called by lit2pgm). You get that --- version on Suns and Alphas in Glasgow by using --- \tr{lit2pgm -H "${HOME}/bin/`hw_os`"} --- in your Makefile ------------------------------------------------------------------------------ +infixl 0 `using`,`demanding`,`sparking` -- weakest precedence! ---@node Evaluation Strategies, , , ---@chapter Evaluation Strategies - ---@menu ---* Imports and infix declarations:: ---* Strategy Type and Application:: ---* Basic Strategies:: ---* Strategic Function Application:: ---* Marking a Strategy:: ---* Strategy Instances:: ---* Lolita-specific Strategies:: ---@end menu - ---@node Imports and infix declarations, Strategy Type and Application, Evaluation Strategies, Evaluation Strategies ---@section Imports and infix declarations - -> module Strategies( ->#if (__HASKELL1__>=4) -> module Strategies, -> module Parallel ->#else -> Strategies.. ->#endif -> ) where -> ->#if defined(GRAN) && !(__HASKELL1__>=4) -> import PreludeGlaST -- only needed for markStrat ->#endif ->#if (__HASKELL1__>=4) - -<> import Prelude hiding (seq) -<> import qualified Parallel - -> import Parallel - ->#else -> import Parallel renaming (par to par_from_Parallel, seq to seq_from_Parallel) ->#endif - ->#if (__HASKELL1__>=4) -> import Ix -> import Array ->#endif - ->#if defined(PAR_GRAN_LIST) -> import QSort -- tmp (only for parGranList) ->#endif - -I lifted the precedence of @par@ and @seq@ by one level to make @using@ the -combinator with the weakest precedence. -Oooops, there seems to be a bug in ghc 0.29 prohibiting another infix -declaration of @par@ and @seq@ despite renaming the imported versions. - ->#if (__HASKELL1__>=4) - -<> infixr 2 `par` -- was: 0 -<> infixr 3 `seq` -- was: 1 - ->#else -> infixr 0 `par` -- was: 0 -> infixr 1 `seq` -- was: 1 ->#endif - -> infixl 0 `using`,`demanding`,`sparking` -- weakest precedence! - -> infixr 2 >|| -- another name for par -> infixr 3 >| -- another name for seq -> infixl 6 $||, $| -- strategic function application (seq and par) -> infixl 9 .|, .||, -|, -|| -- strategic (inverse) function composition - -> strategy_version = "$Revision: 1.1 $" -> strategy_id = "$Id: Strategies.hs,v 1.1 2001/06/28 14:15:02 simonmar Exp $" +infixr 2 >|| -- another name for par +infixr 3 >| -- another name for seq +infixl 6 $||, $| -- strategic function application (seq and par) +infixl 9 .|, .||, -|, -|| -- strategic (inverse) function composition ------------------------------------------------------------------------------ - Strategy Type, Application and Semantics +-- Strategy Type, Application and Semantics ------------------------------------------------------------------------------ ---@node Strategy Type and Application, Basic Strategies, Imports and infix declarations, Evaluation Strategies ---@section Strategy Type and Application - ---@cindex Strategy - -> type Done = () -> type Strategy a = a -> Done +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. @@ -304,46 +69,23 @@ The infix fcts >| 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. +-} ---@cindex par ---@cindex seq ---@cindex >| ---@cindex >|| - ->#if (__HASKELL1__>=4) - +{- par and seq have the same types as before; >| and >|| are more specific and can only be used when composing strategies. +-} + +(>|), (>||) :: Done -> Done -> Done +{-# INLINE (>|) #-} +{-# INLINE (>||) #-} +(>|) = Prelude.seq +(>||) = Parallel.par -<> par :: Done -> Done -> Done -<> par = Parallel.par -<> seq :: a -> b -> b -- that's the real type of seq defined in Prelude -<> seq = Parallel.seq - -> (>|), (>||) :: Done -> Done -> Done -> {-# INLINE (>|) #-} -> {-# INLINE (>||) #-} -> (>|) = Prelude.seq -> (>||) = Parallel.par ->#else -> par, seq, (>|), (>||) :: Done -> Done -> Done -> par = par_from_Parallel -> seq = seq_from_Parallel -> {-# INLINE (>|) #-} -> {-# INLINE (>||) #-} -> (>|) = seq -> (>||) = par ->#endif - ---@cindex using - -> using :: a -> Strategy a -> a ->#if (__HASKELL1__>=4) -> using x s = s x `seq` x ->#else -> using x s = s x `seq_from_Parallel` x ->#endif +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 @@ -357,85 +99,56 @@ 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 +-} ---@cindex demanding ---@cindex sparking - -> demanding, sparking :: a -> Done -> a ->#if (__HASKELL1__>=4) -> demanding = flip Parallel.seq -> sparking = flip Parallel.par ->#else -> demanding = flip seq_from_Parallel -> sparking = flip par_from_Parallel ->#endif +demanding, sparking :: a -> Done -> a +demanding = flip Parallel.seq +sparking = flip Parallel.par +{- 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 - e `using` sPar x -< -<> sPar :: a -> Strategy b -<> sPar x y = x `par` () -< - e `using` sSeq x -< -<> sSeq :: a -> Strategy b -<> sSeq x y = x `seq` () +sPar is a strategy corresponding to par. i.e. x `par` e <=> e `using` sPar x +-} + +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 +-} +sSeq :: a -> Strategy b +sSeq x y = x `seq` () ----------------------------------------------------------------------------- - Basic Strategies +-- Basic Strategies ----------------------------------------------------------------------------- ---@node Basic Strategies, Strategic Function Application, Strategy Type and Application, Evaluation Strategies ---@section Basic Strategies - -r0 performs *no* evaluation on its argument. - ---@cindex r0 - -> r0 :: Strategy a -> r0 x = () - -rwhnf reduces its argument to weak head normal form. - ---@cindex rwhnf ---@cindex rnf ---@cindex NFData - ->#if defined(__HASKELL98__) -> rwhnf :: Strategy a -> rwhnf x = x `seq` () ->#elif (__HASKELL1__==4) -> rwhnf :: Eval a => Strategy a -> rwhnf x = x `seq` () ->#else -> rwhnf :: Strategy a -> rwhnf x = x `seq_from_Parallel` () ->#endif - ->#if defined(__HASKELL98__) -> class NFData a where ->#elif (__HASKELL1__>=4) -> class Eval a => NFData a where ->#else -> class NFData a where ->#endif -> -- rnf reduces its argument to (head) normal form -> rnf :: Strategy a -> -- Default method. Useful for base types. A specific method is necessay for -> -- constructed types -> rnf = rwhnf -> -> class (NFData a, Integral a) => NFDataIntegral a -> class (NFData a, Ord a) => NFDataOrd a + +-- r0 performs *no* evaluation on its argument. +r0 :: Strategy a +r0 x = () + +--rwhnf 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 + rnf :: Strategy a + -- Default method. Useful for base types. A specific method is necessay for + -- constructed types + rnf = rwhnf + +class (NFData a, Integral a) => NFDataIntegral a +class (NFData a, Ord a) => NFDataOrd a ------------------------------------------------------------------------------ - Strategic Function Application +-- Strategic Function Application ------------------------------------------------------------------------------ ---@node Strategic Function Application, Marking a Strategy, Basic Strategies, Evaluation Strategies ---@section 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 @@ -443,46 +156,37 @@ 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 @$||@. +-} ---@cindex $| ---@cindex $|| - -> ($|), ($||) :: (a -> b) -> Strategy a -> a -> b - -<> f $| s = \ x -> f x `using` \ _ -> s x `seq` () -<> f $|| s = \ x -> f x `using` \ _ -> s x `par` () +($|), ($||) :: (a -> b) -> Strategy a -> a -> b -> f $| s = \ x -> f x `demanding` s x -> f $|| s = \ x -> f x `sparking` s x +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. +-} ---@cindex .| ---@cindex .|| ---@cindex -| ---@cindex -|| - -> (.|), (.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c) -> (-|), (-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c) +(.|), (.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c) +(-|), (-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c) -> (.|) f s g = \ x -> let gx = g x -> in f gx `demanding` s gx -> (.||) f s g = \ x -> let gx = g x -> in f gx `sparking` s gx +(.|) f s g = \ x -> let gx = g x + in f gx `demanding` s gx +(.||) f s g = \ x -> let gx = g x + in f gx `sparking` s gx -> (-|) f s g = \ x -> let fx = f x -> in g fx `demanding` s fx -> (-||) f s g = \ x -> let fx = f x -> in g fx `sparking` s fx +(-|) f s g = \ x -> let fx = f x + in g fx `demanding` s fx +(-||) f s g = \ x -> let fx = f x + in g fx `sparking` s fx ------------------------------------------------------------------------------ - Marking a Strategy +-- Marking a Strategy ------------------------------------------------------------------------------ ---@node Marking a Strategy, Strategy Instances, Strategic Function Application, Evaluation Strategies ---@section Marking a Strategy +{- Marking a strategy. Actually, @markStrat@ sticks a label @n@ into the sparkname field of the @@ -492,473 +196,294 @@ all its children have the sparkname @n@ (if the static sparkname field in the @parGlobal@ annotation contains the value 1). Note, that the @SN@ field of starting the marked strategy itself contains the sparkname of the parent thread. The END event contains @n@ as sparkname. +-} ---@cindex markStrat - ->#if defined(GRAN) && !(__HASKELL1__>=4) -> markStrat :: Int -> Strategy a -> Strategy a -> markStrat n s x = unsafePerformPrimIO ( -> _casm_ ``%r = set_sparkname(CurrentTSO, %0);'' n `thenPrimIO` \ z -> -> returnPrimIO (s x)) ->#endif +#if 0 +markStrat :: Int -> Strategy a -> Strategy a +markStrat n s x = unsafePerformPrimIO ( + _casm_ ``%r = set_sparkname(CurrentTSO, %0);'' n `thenPrimIO` \ z -> + returnPrimIO (s x)) +#endif ----------------------------------------------------------------------------- - Strategy Instances and Functions +-- Strategy Instances and Functions ----------------------------------------------------------------------------- ---@node Strategy Instances, Lolita-specific Strategies, Marking a Strategy, Evaluation Strategies ---@section Strategy Instances + ----------------------------------------------------------------------------- - Tuples +-- Tuples ----------------------------------------------------------------------------- ---@menu ---* Tuples:: ---* Numbers:: ---* Characters:: ---* Booleans:: ---* Unit:: ---* Lists:: ---* Arrays:: ---@end menu - ---@node Tuples, Numbers, Strategy Instances, Strategy Instances ---@subsection Tuples +{- We currently support up to 9-tuples. If you need longer tuples you have to add the instance explicitly to your program. +-} + +instance (NFData a, NFData b) => NFData (a,b) where + rnf (x,y) = rnf x `seq` rnf y + +instance (NFData a, NFData b, NFData c) => NFData (a,b,c) where + rnf (x,y,z) = rnf x `seq` rnf y `seq` rnf z + +instance (NFData a, NFData b, NFData c, NFData d) => NFData (a,b,c,d) where + rnf (x1,x2,x3,x4) = rnf x1 `seq` + rnf x2 `seq` + rnf x3 `seq` + rnf x4 + +instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5) => + NFData (a1, a2, a3, a4, a5) where + rnf (x1, x2, x3, x4, x5) = + rnf x1 `seq` + rnf x2 `seq` + rnf x3 `seq` + rnf x4 `seq` + rnf x5 + +instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6) => + NFData (a1, a2, a3, a4, a5, a6) where + rnf (x1, x2, x3, x4, x5, x6) = + rnf x1 `seq` + rnf x2 `seq` + rnf x3 `seq` + rnf x4 `seq` + rnf x5 `seq` + rnf x6 + +instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7) => + NFData (a1, a2, a3, a4, a5, a6, a7) where + rnf (x1, x2, x3, x4, x5, x6, x7) = + rnf x1 `seq` + rnf x2 `seq` + rnf x3 `seq` + rnf x4 `seq` + rnf x5 `seq` + rnf x6 `seq` + rnf x7 + +instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8) => + NFData (a1, a2, a3, a4, a5, a6, a7, a8) where + rnf (x1, x2, x3, x4, x5, x6, x7, x8) = + rnf x1 `seq` + rnf x2 `seq` + rnf x3 `seq` + rnf x4 `seq` + rnf x5 `seq` + rnf x6 `seq` + rnf x7 `seq` + rnf x8 + +instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8, NFData a9) => + NFData (a1, a2, a3, a4, a5, a6, a7, a8, a9) where + rnf (x1, x2, x3, x4, x5, x6, x7, x8, x9) = + rnf x1 `seq` + rnf x2 `seq` + rnf x3 `seq` + rnf x4 `seq` + rnf x5 `seq` + rnf x6 `seq` + rnf x7 `seq` + rnf x8 `seq` + rnf x9 + + +seqPair :: Strategy a -> Strategy b -> Strategy (a,b) +seqPair strata stratb (x,y) = strata x `seq` stratb y + +parPair :: Strategy a -> Strategy b -> Strategy (a,b) +parPair strata stratb (x,y) = strata x `par` stratb y `par` () -> instance (NFData a, NFData b) => NFData (a,b) where -> rnf (x,y) = rnf x `seq` rnf y - -> instance (NFData a, NFData b, NFData c) => NFData (a,b,c) where -> rnf (x,y,z) = rnf x `seq` rnf y `seq` rnf z - -> instance (NFData a, NFData b, NFData c, NFData d) => NFData (a,b,c,d) where -> rnf (x1,x2,x3,x4) = rnf x1 `seq` -> rnf x2 `seq` -> rnf x3 `seq` -> rnf x4 - -> -- code automatically inserted by `hwl-insert-NFData-n-tuple' -> instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5) => -> NFData (a1, a2, a3, a4, a5) where -> rnf (x1, x2, x3, x4, x5) = -> rnf x1 `seq` -> rnf x2 `seq` -> rnf x3 `seq` -> rnf x4 `seq` -> rnf x5 - -> -- code automatically inserted by `hwl-insert-NFData-n-tuple' -> instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6) => -> NFData (a1, a2, a3, a4, a5, a6) where -> rnf (x1, x2, x3, x4, x5, x6) = -> rnf x1 `seq` -> rnf x2 `seq` -> rnf x3 `seq` -> rnf x4 `seq` -> rnf x5 `seq` -> rnf x6 - -> -- code automatically inserted by `hwl-insert-NFData-n-tuple' -> instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7) => -> NFData (a1, a2, a3, a4, a5, a6, a7) where -> rnf (x1, x2, x3, x4, x5, x6, x7) = -> rnf x1 `seq` -> rnf x2 `seq` -> rnf x3 `seq` -> rnf x4 `seq` -> rnf x5 `seq` -> rnf x6 `seq` -> rnf x7 - -> -- code automatically inserted by `hwl-insert-NFData-n-tuple' -> instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8) => -> NFData (a1, a2, a3, a4, a5, a6, a7, a8) where -> rnf (x1, x2, x3, x4, x5, x6, x7, x8) = -> rnf x1 `seq` -> rnf x2 `seq` -> rnf x3 `seq` -> rnf x4 `seq` -> rnf x5 `seq` -> rnf x6 `seq` -> rnf x7 `seq` -> rnf x8 - -> -- code automatically inserted by `hwl-insert-NFData-n-tuple' -> instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8, NFData a9) => -> NFData (a1, a2, a3, a4, a5, a6, a7, a8, a9) where -> rnf (x1, x2, x3, x4, x5, x6, x7, x8, x9) = -> rnf x1 `seq` -> rnf x2 `seq` -> rnf x3 `seq` -> rnf x4 `seq` -> rnf x5 `seq` -> rnf x6 `seq` -> rnf x7 `seq` -> rnf x8 `seq` -> rnf x9 - ---@cindex seqPair - -> seqPair :: Strategy a -> Strategy b -> Strategy (a,b) -> seqPair strata stratb (x,y) = strata x `seq` stratb y - ---@cindex parPair - -> parPair :: Strategy a -> Strategy b -> Strategy (a,b) -> parPair strata stratb (x,y) = strata x `par` stratb y `par` () - +{- 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 +-} ---@cindex seqTriple - -> 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 +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 ---@cindex parTriple - -> parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c) -> parTriple strata stratb stratc (x,y,z) = -> strata x `par` -> stratb y `par` -> stratc z `par` -> () - ------------------------------------------------------------------------------ - Numbers ------------------------------------------------------------------------------ ---@node Numbers, Characters, Tuples, Strategy Instances ---@subsection Numbers +parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c) +parTriple strata stratb stratc (x,y,z) = + strata x `par` + stratb y `par` + stratc z `par` + () +{- Weak head normal form and normal form are identical for integers, so the default rnf is sufficient. +-} +instance NFData Int +instance NFData Integer +instance NFData Float +instance NFData Double -> instance NFData Int -> instance NFData Integer -> instance NFData Float -> instance NFData Double - -> instance NFDataIntegral Int -> instance NFDataOrd Int - -Rational and complex numbers. - ->#if !(__HASKELL1__>=4) -> instance (NFData a) => NFData (Ratio a) where -> rnf (x:%y) = rnf x `seq` -> rnf y `seq` -> () - -> instance (NFData a) => NFData (Complex a) where -> rnf (x:+y) = rnf x `seq` -> rnf y `seq` -> () ->#endif +instance NFDataIntegral Int +instance NFDataOrd Int ------------------------------------------------------------------------------ - Characters ------------------------------------------------------------------------------ ---@node Characters, Booleans, Numbers, Strategy Instances ---@subsection Characters +--Rational and complex numbers. -> instance NFData Char +instance (Integral a, NFData a) => NFData (Ratio a) where + rnf (x:%y) = rnf x `seq` + rnf y `seq` + () ------------------------------------------------------------------------------ - Bools ------------------------------------------------------------------------------ ---@node Booleans, Unit, Characters, Strategy Instances ---@subsection Booleans +instance (RealFloat a, NFData a) => NFData (Complex a) where + rnf (x:+y) = rnf x `seq` + rnf y `seq` + () -> instance NFData Bool +instance NFData Char +instance NFData Bool +instance NFData () ----------------------------------------------------------------------------- - Unit ------------------------------------------------------------------------------ ---@node Unit, Lists, Booleans, Strategy Instances ---@subsection Unit - -> instance NFData () - ------------------------------------------------------------------------------ - Lists +-- Lists ---------------------------------------------------------------------------- ---@node Lists, Arrays, Unit, Strategy Instances ---@subsection Lists - -> instance NFData a => NFData [a] where -> rnf [] = () -> rnf (x:xs) = rnf x `seq` rnf xs ---@menu ---* Parallel Strategies for Lists:: ---* Sequential Strategies for Lists:: ---@end menu +instance NFData a => NFData [a] where + rnf [] = () + rnf (x:xs) = rnf x `seq` rnf xs ---------------------------------------------------------------------------- - Lists: Parallel Strategies +-- Lists: Parallel Strategies ---------------------------------------------------------------------------- ---@node Parallel Strategies for Lists, Sequential Strategies for Lists, Lists, Lists ---@subsubsection Parallel Strategies for Lists - -Applies a strategy to every element of a list in parallel - ---@cindex parList - -> 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 - ---@cindex parListN - -> 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 - ---@cindex parListNth - -> parListNth :: Int -> Strategy a -> Strategy [a] -> parListNth n strat xs -> | null rest = () -> | otherwise = strat (head rest) `par` () -> where -> rest = drop n xs - -parListChunk sequentially applies a strategy to chunks -(sub-sequences) of a list in parallel. Useful to increase grain size - ---@cindex parListChunk - -> 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' - ---@cindex parMap - -> parMap :: Strategy b -> (a -> b) -> [a] -> [b] -> 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' ---@cindex parFlatMap - -> 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 - ---@cindex parZipWith - -> parZipWith :: Strategy c -> (a -> b -> c) -> [a] -> [b] -> [c] -> parZipWith strat z as bs = -> zipWith z as bs `using` parList strat +-- | Applies a strategy to every element of a list in parallel +parList :: Strategy a -> Strategy [a] +parList strat [] = () +parList strat (x:xs) = strat x `par` (parList strat xs) + +-- | Applies a strategy to the first n elements of a list in parallel +parListN :: (Integral b) => b -> Strategy a -> Strategy [a] +parListN n strat [] = () +parListN 0 strat xs = () +parListN n strat (x:xs) = strat x `par` (parListN (n-1) strat xs) + +-- | Evaluates N elements of the spine of the argument list and applies +-- the given strategy to the Nth element (if there is one) in parallel with +-- the result. e.g. parListNth 2 [e1, e2, e3] evaluates e2 +parListNth :: Int -> Strategy a -> Strategy [a] +parListNth n strat xs + | null rest = () + | otherwise = strat (head rest) `par` () + where + rest = drop n xs + +-- | 'parListChunk' sequentially applies a strategy to chunks +-- (sub-sequences) of a list in parallel. Useful to increase 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 the given +-- strategy. +parMap :: Strategy b -> (a -> b) -> [a] -> [b] +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 the given strategy. +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 +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 ---------------------------------------------------------------------------- ---@node Sequential Strategies for Lists, , Parallel Strategies for Lists, Lists ---@subsubsection Sequential Strategies for Lists - -Sequentially applies a strategy to each element of a list - ---@cindex seqList - -> 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 - ---@cindex seqListN - -> 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 - ---@cindex seqListNth ->#if (__HASKELL1__>=4) -> seqListNth :: Int -> Strategy b -> Strategy [b] ->#else -> seqListNth :: (Integral a) => a -> Strategy b -> Strategy [b] ->#endif -> seqListNth n strat xs -> | null rest = () -> | otherwise = strat (head rest) -> where -> rest = drop n xs +-- | 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 +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 +seqListNth :: Int -> Strategy b -> Strategy [b] +seqListNth n strat xs + | null rest = () + | otherwise = strat (head rest) + where + 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 +-- semantics. +parBuffer :: Int -> Strategy a -> [a] -> [a] +parBuffer n s xs = + return xs (start n xs) + where + return (x:xs) (y:ys) = (x:return xs ys) `sparking` s y + return xs [] = xs + + start n [] = [] + start 0 ys = ys + start n (y:ys) = start (n-1) ys `sparking` s y -Parallel n-buffer function added for the revised version of the strategies -paper. @parBuffer@ supersedes the older @fringeList@. It has the same -semantics. - ---@cindex parBuffer - -> parBuffer :: Int -> Strategy a -> [a] -> [a] -> parBuffer n s xs = -> return xs (start n xs) -> where -> return (x:xs) (y:ys) = (x:return xs ys) `sparking` s y -> return xs [] = xs -> -> start n [] = [] -> start 0 ys = ys -> start n (y:ys) = start (n-1) ys `sparking` s y - -fringeList implements a `rolling buffer' of length n, i.e.applies a -strategy to the nth element of list when the head is demanded. More -precisely: +{- + 'fringeList' implements a `rolling buffer' of length n, i.e.applies a + strategy to the nth element of list when the head is demanded. More + precisely: semantics: fringeList n s = id :: [b] -> [b] dynamic behaviour: evalutates the nth element of the list when the head is demanded. -The idea is to provide a `rolling buffer' of length n. - ---@cindex fringeList - -<> fringeList :: (Integral a) => a -> Strategy b -> [b] -> [b] -<> fringeList n strat [] = [] -<> fringeList n strat (r:rs) = -<> seqListNth n strat rs `par` -<> r:fringeList n strat rs + The idea is to provide a `rolling buffer' of length n. +fringeList :: (Integral a) => a -> Strategy b -> [b] -> [b] +fringeList n strat [] = [] +fringeList n strat (r:rs) = + seqListNth n strat rs `par` + r:fringeList n strat rs +-} ------------------------------------------------------------------------------ - Arrays +-- Arrays ------------------------------------------------------------------------------ ---@node Arrays, , Lists, Strategy Instances ---@subsection Arrays +instance (Ix a, NFData a, NFData b) => NFData (Array a b) where + rnf x = rnf (bounds x) `seq` seqList rnf (elems x) `seq` () -> 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). +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. This can be done -either in sequentially or in parallel (same as with lists, really). +parArr :: (Ix b) => Strategy a -> Strategy (Array b a) +parArr s arr = parList s (elems arr) -> seqArr :: (Ix b) => Strategy a -> Strategy (Array b a) -> seqArr s arr = seqList s (elems arr) +-- Associations maybe useful even without mentioning Arrays. -> parArr :: (Ix b) => Strategy a -> Strategy (Array b a) -> parArr s arr = parList s (elems arr) - -Associations maybe useful even withou mentioning Arrays. - -See: .../lib/prelude/TyArrays.hs: data Assoc a b = a := b deriving () ->#if (__HASKELL1__<4) -> instance (NFData a, NFData b) => NFData (Assoc a b) where -> rnf (x := y) = rnf x `seq` rnf y `seq` () ->#endif +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 ------------------------------------------------------------------------------ ---@node Lolita-specific Strategies, Index, Strategy Instances, Evaluation Strategies ---@section Lolita-specific Strategies - -The following is useful in mergePenGroups - ---@cindex fstPairFstList - -> 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) - -> force :: (NFData a) => a -> a -> sforce :: (NFData a) => a -> b -> b - -Same as definition below - -<> force x = rnf x `seq` x - -> force = id $| rnf ->#if (__HASKELL1__>=4) -> sforce x y = force x `seq` y ->#else -> sforce x y = force x `seq_from_Parallel` y ->#endif - ---@node Bowing-alg specific strategies ---@section Bowing-alg specific strategies - -NB: this strategy currently needs the quicksort implementation from the hbc syslib - ->#if defined(PAR_GRAN_LIST) -> parGranList :: Strategy a -> (a -> Int) -> [a] -> Strategy [a] -> parGranList s gran_estim l_in = \ l_out -> -> parListByIdx s l_out $ -> sortedIdx gran_list (sortLe ( \ (i,_) (j,_) -> i>j) gran_list) -> where -- spark list elems of l in the order specified by (i:idxs) -> parListByIdx s l [] = () -> parListByIdx s l (i:idxs) = parListByIdx s l idxs `sparking` s (l!!i) -> -- get the index of y in the list -> idx y [] = error "idx: x not in l" -> idx y ((x,_):xs) | y==x = 0 -> | otherwise = (idx y xs)+1 -> -- the `schedule' for sparking: list of indices of sorted input list -> sortedIdx l idxs = [ idx x l | (x,_) <- idxs ] -> -- add granularity info to elems of the input list -> gran_list = map (\ l -> (gran_estim l, l)) l_in ->#endif - ---@node Index, , Lolita-specific Strategies, Evaluation Strategies ---@section Index - ---@index ---* $|:: @cindex\s-+$| ---* $||:: @cindex\s-+$|| ---* -|:: @cindex\s-+-| ---* -||:: @cindex\s-+-|| ---* .|:: @cindex\s-+.| ---* .||:: @cindex\s-+.|| ---* NFData:: @cindex\s-+NFData ---* Strategy:: @cindex\s-+Strategy ---* demanding:: @cindex\s-+demanding ---* fringeList:: @cindex\s-+fringeList ---* fstPairFstList:: @cindex\s-+fstPairFstList ---* markStrat:: @cindex\s-+markStrat ---* parBuffer:: @cindex\s-+parBuffer ---* parFlatMap:: @cindex\s-+parFlatMap ---* parList:: @cindex\s-+parList ---* parListChunk:: @cindex\s-+parListChunk ---* parListN:: @cindex\s-+parListN ---* parListNth:: @cindex\s-+parListNth ---* parMap:: @cindex\s-+parMap ---* parPair:: @cindex\s-+parPair ---* parTriple:: @cindex\s-+parTriple ---* parZipWith:: @cindex\s-+parZipWith ---* r0:: @cindex\s-+r0 ---* rnf:: @cindex\s-+rnf ---* rwhnf:: @cindex\s-+rwhnf ---* seqList:: @cindex\s-+seqList ---* seqListN:: @cindex\s-+seqListN ---* seqListNth:: @cindex\s-+seqListNth ---* seqPair:: @cindex\s-+seqPair ---* seqTriple:: @cindex\s-+seqTriple ---* sparking:: @cindex\s-+sparking ---* using:: @cindex\s-+using ---@end index + +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) + +force :: (NFData a) => a -> a +sforce :: (NFData a) => a -> b -> b + +force = id $| rnf +sforce x y = force x `seq` y