lvish 1.0 → 1.0.0.2
raw patch · 15 files changed
+355/−347 lines, 15 files
Files
- Control/LVish.hs +23/−10
- Control/LVish/DeepFrz.hs +32/−23
- Control/LVish/DeepFrz/Internal.hs +11/−9
- Control/LVish/Internal.hs +9/−18
- Control/LVish/SchedIdempotent.hs +39/−38
- Data/LVar/Generic.hs +8/−8
- Data/LVar/Generic/Internal.hs +11/−11
- Data/LVar/IStructure.hs +23/−25
- Data/LVar/IVar.hs +26/−20
- Data/LVar/Internal/Pure.hs +12/−40
- Data/LVar/PureMap.hs +42/−41
- Data/LVar/PureSet.hs +36/−37
- Data/LVar/SLMap.hs +34/−30
- Data/LVar/SLSet.hs +29/−29
- lvish.cabal +20/−8
Control/LVish.hs view
@@ -10,6 +10,7 @@ {-# LANGUAGE DataKinds #-} -- For 'Determinism' -- {-# LANGUAGE ConstraintKinds, KindSignatures #-} {-# LANGUAGE MagicHash #-}+{-# LANGUAGE BangPatterns #-} {-# OPTIONS_GHC -fwarn-incomplete-patterns #-} {-|@@ -17,14 +18,15 @@ The @lvish@ package provides a parallel programming model based on monotonically growing data structures. - This module provides the core scheduler and basic control flow operations. - But to do anything useful you will need to import one of the data structure modules- (@Data.LVar.*@).+ This module provides the core scheduler and basic control flow+ operations. But to do anything useful you will need to import, along+ with this module, one of the data structure modules (@Data.LVar.*@). - Here is a self-contained example that writes the same value to @num@- twice and deterministically prints @4@ instead of raising an error, as- it would if @num@ were a traditional IVar rather than an LVar. (You- will need to compile using the @-XDataKinds@ extension.)+ Here is a self-contained example. This program writes the same value+ to an @LVar@ called @num@ twice. It deterministically prints @4@+ instead of raising an error, as it would if @num@ were a traditional+ IVar rather than an LVar. (You will need to compile using the+ @-XDataKinds@ extension.) > {-# LANGUAGE DataKinds #-} > import Control.LVish -- Generic scheduler; works with any lattice.@@ -53,7 +55,7 @@ guaranteed-deterministic. Unfortunately, as of this release there is still one back-door that hasn't yet been closed. - If an adverserial user defines invalid `Eq` instances (claiming objects are equal when they're+ If an adversarial user defines invalid `Eq` instances (claiming objects are equal when they're not), or if they define a `compare` function that is not a /pure, total function/, and then they store those types within `LVar`s, then nondeterminism may leak out of a parallel `runPar` computation.@@ -160,7 +162,7 @@ withNewPool_ f = WrapPar $ L.withNewPool_ $ unWrapPar . f -- | If the input computation is quasi-deterministic (`QuasiDet`), then this may--- throw a `LVishException` non-deterministically on the thread that calls it, but if+-- throw a `LVishException` nondeterministically on the thread that calls it, but if -- it returns without exception then it always returns the same answer. -- -- If the input computation is deterministic (`Det`), then @runParIO@ will return the@@ -168,7 +170,7 @@ -- avoiding an extra `unsafePerformIO` required inside the implementation of -- `runPar`. -- --- In the future, /full/ non-determinism may be allowed as a third setting beyond+-- In the future, /full/ nondeterminism may be allowed as a third setting beyond -- `Det` and `QuasiDet`. runParIO :: (forall s . Par d s a) -> IO a runParIO (WrapPar p) = L.runParIO p @@ -262,3 +264,14 @@ (halfT,remT) = tiles `quotRem` 2 fork$ loop offset half halfT loop (offset+half) (half+rem) (halfT+remT)+++-- | A simple for loop for numeric ranges (not requiring deforestation+-- optimizations like `forM`). Inclusive start, exclusive end.+{-# INLINE for_ #-}+for_ :: Monad m => (Int, Int) -> (Int -> m ()) -> m ()+for_ (start, end) _fn | start > end = error "for_: start is greater than end"+for_ (start, end) fn = loop start+ where+ loop !i | i == end = return ()+ | otherwise = do fn i; loop (i+1)
Control/LVish/DeepFrz.hs view
@@ -8,13 +8,15 @@ {-| -Provides a way to return arbitrarily complex data-structures containing LVars-from `Par` computations.+The `DeepFrz` module rovides a way to return arbitrarily complex data+structures containing LVars from `Par` computations. -The important thing to know is that to use `runParThenFreeze` you must make sure that-all types you return from the parallel computation have `DeepFrz` instances. This-means if you introduce custom (non-LVar) datatypes, you will need to include a bit of-boilerplate to give them `DeepFrz` instances. Here is a complete example:+The important thing to know is that to use `runParThenFreeze` to run a+`Par` computation, you must make sure that all types you return from+the `Par` computation have `DeepFrz` instances. This means that, if+you wish to return a user-defined type, you will need to include a bit+of boilerplate to give it a `DeepFrz` instance. Here is a complete+example: > {-# LANGUAGE TypeFamilies #-} > import Control.LVish.DeepFrz@@ -28,7 +30,9 @@ -} --- LK: TODO: another example of a recursive FrzType would be nice.+-- TODO: a more detailed (recursive?) DeepFrz instance example might+-- be really helpful here for people who want to implement their own+-- LVar types. -- LK module Control.LVish.DeepFrz (@@ -52,30 +56,35 @@ import Control.LVish.SchedIdempotent (runPar, runParIO) -------------------------------------------------------------------------------- --- | Under normal conditions, calling a `freeze` operation makes a `Par` computation--- quasi-deterministic. However, if we freeze once all LVar operations are completed--- (after the implicit global barrier of `runPar`), then we've avoided all data--- races, and freezing is therefore safe.+-- | Under normal conditions, calling a `freeze` operation inside a+-- `Par` computation makes the `Par` computation quasi-deterministic.+-- However, if we freeze only after all LVar operations are completed+-- (after the implicit global barrier of `runPar`), then we've avoided+-- all data races, and freezing is therefore safe. Running a `Par`+-- computation with `runParThenFreeze` accomplishes this, without our+-- having to call `freeze` explicitly. -- --- For this to be possible, the type returned from the `Par` computation must be a--- member of the `DeepFrz` class. All LVar libraries should provide this instance--- already. Further, you can create additional instances for custom, pure datatypes.--- The result of a `runParThenFreeze` depends on the type-level function `FrzType`,--- whose only purpose is to toggle the `s` parameters of all IVars to the `Frzn`--- state.---+-- In order to use `runParThenFreeze`, the type returned from the+-- `Par` computation must be a member of the `DeepFrz` class. All the+-- @Data.LVar.*@ libraries should provide instances of `DeepFrz`+-- already. Further, you can create additional instances for custom,+-- pure datatypes. The result of a `runParThenFreeze` depends on the+-- type-level function `FrzType`, whose only purpose is to toggle the+-- `s` parameters of all IVars to the `Frzn` state.+-- -- Significantly, the freeze at the end of `runParThenFreeze` has /no/ runtime cost, in -- spite of the fact that it enables a /deep/ (recursive) freeze of the value returned -- by the `Par` computation. runParThenFreeze :: DeepFrz a => Par Det s a -> FrzType a runParThenFreeze (WrapPar p) = frz $ runPar p --- | This version works for non-deterministic computations as well.+-- | This version works for nondeterministic computations as well. -- --- Such computations may also do freezes internally, but this function has an--- advantage vs. doing your own freeze at the end of your computation. Namely, when--- you use `runParThenFreezeIO`, there is an implicit barrier before the final--- freeze. Further, `DeepFrz` has no runtime overhead, whereas regular freezing has a cost.+-- Of course, nondeterministic computations may also call `freeze`+-- internally, but this function has an advantage to doing your own+-- `freeze` at the end of a `runParIO`: there is an implicit barrier+-- before the final freeze. Further, `DeepFrz` has no runtime+-- overhead, whereas regular freezing has a cost. runParThenFreezeIO :: DeepFrz a => Par d s a -> IO (FrzType a) runParThenFreezeIO (WrapPar p) = do x <- runParIO p
Control/LVish/DeepFrz/Internal.hs view
@@ -3,7 +3,7 @@ {-# LANGUAGE DefaultSignatures #-} {-# LANGUAGE EmptyDataDecls #-} --- | This module is NOT Safe-Haskell, but it must be used to create+-- | This module is /not/ Safe Haskell, but it must be used to create -- new LVar types. module Control.LVish.DeepFrz.Internal (@@ -11,11 +11,13 @@ ) where --- | DeepFreezing is type-level (guaranteed O(1) time complexity)+-- | DeepFreezing is a type-level (guaranteed O(1) time complexity) -- operation. It marks an LVar and its contents (recursively) as -- frozen. DeepFreezing is not an action that can be taken directly--- by the user, however. Rather it is an optional final-step in a--- `runPar` invocation.+-- by the user, however. Rather, it is the final step in a+-- `runParThenFreeze` invocation.++-- An instance of DeepFrz is a valid return valud for `runParThenFreeze` class DeepFrz a where -- | This type function is public. It maps pre-frozen types to -- frozen ones. It should be idempotent.@@ -30,12 +32,12 @@ default frz :: a -> a frz a = a --- | An uninhabited type that signals an LVar has been frozen.--- LVars should use this inplace of their `s` parameter.+-- | An uninhabited type that signals that an LVar has been frozen.+-- LVars should use this in place of their `s` parameter. data Frzn --- | An uninhabited type that signals an LVar is not only frozen, but--- it may be traversed in whatever order its internal representation--- dictates.+-- | An uninhabited type that signals that an LVar is not only frozen,+-- but it may be traversed in whatever order its internal+-- representation dictates. data Trvrsbl
Control/LVish/Internal.hs view
@@ -1,17 +1,17 @@ {-# LANGUAGE Unsafe #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE GADTs #-}-{-# LANGUAGE BangPatterns #-} {-# LANGUAGE DataKinds #-} -- For Determinism {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE KindSignatures #-} {-| -This module is note @SafeHaskell@; as an end-user, you shouldn't ever need to import it.+This module is /not/ Safe Haskell; as an end-user, you shouldn't ever+need to import it. -It is exposed only because it is necessary for writing /new/ LVars that live in their-own, separate packages.+It is exposed only because it is necessary for implementing /new/ LVar+types that will live in their own, separate packages. -} @@ -20,14 +20,13 @@ -- * Type-safe wrappers around internal components Par(..), LVar(..), Determinism(..),+ QPar, -- * Unsafe conversions and lifting unWrapPar, unsafeRunPar, unsafeConvert, state,- liftIO,+ liftIO - -- * General utilities- for_ ) where @@ -61,6 +60,9 @@ WrapPar :: L.Par a -> Par d s a deriving (Monad, Functor, Applicative) +-- | A shorthand for quasi-deterministic `Par` computations.+type QPar = Par QuasiDet+ -- | The generic representation of LVars used by the scheduler. The -- end-user can't actually do anything with these and should not try -- to.@@ -90,14 +92,3 @@ instance MonadToss (Par d s) where toss = WrapPar L.toss---- | A simple for loop for numeric ranges (not requiring deforestation--- optimizations like `forM`). Inclusive start, exclusive end.-{-# INLINE for_ #-}-for_ :: Monad m => (Int, Int) -> (Int -> m ()) -> m ()-for_ (start, end) _fn | start > end = error "for_: start is greater than end"-for_ (start, end) fn = loop start- where- loop !i | i == end = return ()- | otherwise = do fn i; loop (i+1)-
Control/LVish/SchedIdempotent.hs view
@@ -16,27 +16,27 @@ {-# OPTIONS_GHC -Wall -fno-warn-name-shadowing -fno-warn-unused-do-bind #-} -- | This is an internal module that provides the core parallel scheduler.--- It is NOT for end-users.+-- It is /not/ for end-users. module Control.LVish.SchedIdempotent (- -- * Basic types and accessors:+ -- * Basic types and accessors LVar(), state, HandlerPool(), Par(..), ClosedPar(..), - -- * Safe, deterministic operations:+ -- * Safe, deterministic operations yield, newPool, fork, forkHP, runPar, runParIO, runParLogged, withNewPool, withNewPool_, forkWithExceptions, - -- * Quasi-deterministic operations:+ -- * Quasi-deterministic operations quiesce, quiesceAll, -- * Debug facilities logStrLn, dbgLvl, - -- * UNSAFE operations. Should be used only by experts to build new abstractions.+ -- * Unsafe operations; should be used only by experts to build new abstractions newLV, getLV, putLV, putLV_, freezeLV, freezeLVAfter, addHandler, liftIO, toss ) where@@ -96,7 +96,7 @@ {-# INLINE logStrLn_ #-} #endif --- | Print all accumulated log lines+-- | Print all accumulated log lines. printLog :: IO () printLog = do -- Clear the log when we read it:@@ -131,7 +131,7 @@ {-# NOINLINE dbgLvl #-} -- | Debugging flag shared by several modules.--- This is activated by setting the environment variable DEBUG=1..5+-- This is activated by setting the environment variable @DEBUG=1..5@. dbgLvl :: Int dbgLvl = case lookup "DEBUG" theEnv of Nothing -> defaultDbg@@ -151,20 +151,20 @@ -- | LVars are parameterized by two types: -- --- * The first, @a@, characterizes the "state" of the LVar (i.e. the lattice--- value), and should be a concurrently mutable data type. That means, in--- particular, that only a /transient snapshot/ of the lattice value can be+-- * The first, @a@, characterizes the \"state\" of the LVar (i.e., the lattice+-- element), and should be a concurrently mutable data type. That means, in+-- particular, that only a /transient snapshot/ of the state can be -- obtained in general. But the information in such a snapshot is always a -- lower bound on the current value of the LVar.------ * The second, @d@, characterizes the "delta" associated with a @putLV@--- operation (i.e. the actual change, if any, to the LVar's lattice value).+-- +-- * The second, @d@, characterizes the \"delta\" associated with a @putLV@+-- operation (i.e., the actual change, if any, to the LVar's state). -- In many cases such deltas allow far more efficient communication between -- @putLV@s and blocked @getLV@s or handlers. It is crucial, however, that -- the behavior of a @get@ or handler does not depend on the /particular/ -- choice of @putLV@ operations (and hence deltas) that moved the LVar over -- the threshold. For simple data structures, the delta may just be the--- entire LVar state, but for e.g. collection data structures, delta will+-- entire LVar state, but for, e.g., collection data structures, delta will -- generally represent a single insertion. data LVar a d = LVar { state :: a, -- the current, "global" state of the LVar@@ -189,7 +189,7 @@ = Frozen -- further changes to the state are forbidden | Active (B.Bag (Listener d)) -- bag of blocked threshold reads and handlers --- | A listener for an LVar is informed of each change to the LVar's lattice value+-- | A listener for an LVar is informed of each change to the LVar's state -- (represented as a delta) and the event of the LVar freezing. The listener is -- given access to a bag token, allowing it to remove itself from the bag of -- listeners, after unblocking a threshold read, for example. It is also given@@ -200,9 +200,9 @@ onFreeze :: B.Token (Listener d) -> SchedState -> IO () } --- | A HandlerPool contains a way to count outstanding parallel computations that+-- | A @HandlerPool@ contains a way to count outstanding parallel computations that -- are affiliated with the pool. It detects the condition where all such threads--- have completeed.+-- have completed. data HandlerPool = HandlerPool { numHandlers :: C.Counter, -- How many handler callbacks are currently -- running?@@ -260,7 +260,7 @@ -- LVar operations ------------------------------------------------------------------------------ --- | Create an LVar+-- | Create an LVar. newLV :: IO a -> Par (LVar a d) newLV init = mkPar $ \k q -> do state <- init@@ -272,7 +272,7 @@ -- | Do a threshold read on an LVar getLV :: (LVar a d) -- ^ the LVar -> (a -> Bool -> IO (Maybe b)) -- ^ already past threshold?- -> (d -> IO (Maybe b)) -- ^ does d pass the threshold?+ -> (d -> IO (Maybe b)) -- ^ does @d@ pass the threshold? -> Par b getLV lv@(LVar {state, status}) globalThresh deltaThresh = mkPar $ \k q -> do -- tradeoff: we fastpath the case where the LVar is already beyond the@@ -333,9 +333,9 @@ Nothing -> sched q --- | Update an LVar+-- | Update an LVar. putLV_ :: LVar a d -- ^ the LVar- -> (a -> Par (Maybe d, b)) -- ^ how to do the put and whether the LVar's+ -> (a -> Par (Maybe d, b)) -- ^ how to do the put, and whether the LVar's -- value changed -> Par b putLV_ LVar {state, status, name} doPut = mkPar $ \k q -> do @@ -359,8 +359,8 @@ putLV lv doPut = putLV_ lv doPut' where doPut' a = do r <- liftIO (doPut a); return (r, ()) --- | Freeze an LVar (limited nondeterminism)--- It is the data-structure implementors responsibility to expose this as qasi-deterministc.+-- | Freeze an LVar (introducing quasi-determinism).+-- It is the data structure implementor's responsibility to expose this as quasi-deterministc. freezeLV :: LVar a d -> Par () freezeLV LVar {name, status} = mkPar $ \k q -> do oldStatus <- atomicModifyIORef status $ \s -> (Frozen, s) @@ -376,7 +376,7 @@ -- Handler pool operations ------------------------------------------------------------------------------ --- | Create a handler pool+-- | Create a handler pool. newPool :: Par HandlerPool newPool = mkPar $ \k q -> do cnt <- C.new@@ -385,15 +385,15 @@ hpMsg " [dbg-lvish] Created new pool" hp exec (k hp) q --- | Convenience function. Execute a Par computation in the context of a fresh handler pool+-- | Convenience function. Execute a @Par@ computation in the context of a fresh handler pool. withNewPool :: (HandlerPool -> Par a) -> Par (a, HandlerPool) withNewPool f = do hp <- newPool a <- f hp return (a, hp) --- | Convenience function. Execute a Par computation in the context of a fresh--- handler pool, while ignoring the result of the computation+-- | Convenience function. Execute a @Par@ computation in the context of a fresh+-- handler pool, while ignoring the result of the computation. withNewPool_ :: (HandlerPool -> Par ()) -> Par HandlerPool withNewPool_ f = do hp <- newPool@@ -402,7 +402,7 @@ data DecStatus = HasDec | HasNotDec --- | Close a Par task so that it is properly registered with a handler pool+-- | Close a @Par@ task so that it is properly registered with a handler pool. closeInPool :: Maybe HandlerPool -> Par () -> IO ClosedPar closeInPool Nothing c = return $ close c $ const (ClosedPar sched) closeInPool (Just hp) c = do@@ -437,7 +437,7 @@ -- continuation that clears it from the -- handler pool --- | Add a handler to an existing pool+-- | Add a handler to an existing pool. {-# INLINE addHandler #-} addHandler :: Maybe HandlerPool -- ^ pool to enroll in, if any -> LVar a d -- ^ LVar to listen to@@ -462,7 +462,7 @@ -- launch any callbacks now exec (k ()) q --- | Block until a handler pool is quiescent +-- | Block until a handler pool is quiescent. quiesce :: HandlerPool -> Par () quiesce hp@(HandlerPool cnt bag) = mkPar $ \k q -> do hpMsg " [dbg-lvish] Begin quiescing pool, identity= " hp@@ -485,8 +485,9 @@ logStrLn_ " [dbg-lvish] Return from global barrier." exec (k ()) q --- | Freeze an LVar after a given handler quiesces--- This is quasideterministic, but it +-- | Freeze an LVar after a given handler quiesces.++-- This is quasi-deterministic. freezeLVAfter :: LVar a d -- ^ the LVar of interest -> (a -> IO (Maybe (Par ()))) -- ^ initial callback -> (d -> IO (Maybe (Par ()))) -- ^ subsequent callbacks: updates@@ -505,7 +506,7 @@ -- Par monad operations ------------------------------------------------------------------------------ --- | Fork a child thread, optionally in the context of a handler pool+-- | Fork a child thread, optionally in the context of a handler pool. forkHP :: Maybe HandlerPool -> Par () -> Par () forkHP mh child = mkPar $ \k q -> do closed <- closeInPool mh child@@ -513,11 +514,11 @@ -- hpMsg " [dbg-lvish] incremented and pushed work in forkInPool, now running cont" hp exec closed q --- | Fork a child thread+-- | Fork a child thread. fork :: Par () -> Par () fork f = forkHP Nothing f --- | Perform an IO action+-- | Perform an @IO@ action. liftIO :: IO a -> Par a liftIO io = mkPar $ \k q -> do r <- io@@ -531,7 +532,7 @@ writeIORef (Sched.prng q) g' exec (k b) q --- | Cooperatively schedule other threads+-- | Cooperatively schedule other threads. yield :: Par () yield = mkPar $ \k q -> do Sched.yieldWork q (k ())@@ -642,7 +643,7 @@ runParIO :: Par a -> IO a runParIO = runPar_internal --- | Debugging aide. Return debugging logs, in realtime order, in addition to the+-- | Debugging aid. Return debugging logs, in realtime order, in addition to the -- final result. runParLogged :: Par a -> IO ([String],a) runParLogged c =@@ -677,7 +678,7 @@ " transient cnt "++show c --- | Exceptions that walk up the fork tree of threads:+-- | Exceptions that walk up the fork tree of threads. forkWithExceptions :: (IO () -> IO ThreadId) -> String -> IO () -> IO ThreadId forkWithExceptions forkit descr action = do parent <- myThreadId
Data/LVar/Generic.hs view
@@ -3,11 +3,11 @@ {-# LANGUAGE KindSignatures #-} {-# LANGUAGE DataKinds #-} -- For Determinism --- | A generic interface providing operations that work on ALL LVars.+-- | A generic interface providing operations that work on /all/ LVars. module Data.LVar.Generic (- -- * The classes containing the generic interfaces+ -- * Classes containing the generic interfaces LVarData1(..), OrderedLVarData1(..), -- * Supporting types and utilities@@ -26,14 +26,14 @@ -------------------------------------------------------------------------------- --- |/Some LVar datatypes are stored in an /internally/ ordered way so+-- | Some LVar datatypes are stored in an /internally/ ordered way so -- that it is then possible to take /O(1)/ frozen snapshots and consume them -- inexpensively in a deterministic order.---+-- -- LVars with this additional property provide this class as well as `LVarData1`. class LVarData1 f => OrderedLVarData1 (f :: * -> * -> *) where -- | Don't just freeze the LVar, but make the full contents- -- completely available and Foldable. Guaranteed /O(1)/.+ -- completely available and `Foldable`. Guaranteed /O(1)/. snapFreeze :: f s a -> Par QuasiDet s (f Trvrsbl a) {- @@ -52,13 +52,13 @@ -- Dealing with frozen LVars. ------------------------------------------------------------------------------ --- | `Trvrsbl` is a stronger property than `Frzn` so it is always ok to \"upcast\" to+-- | `Trvrsbl` is a stronger property than `Frzn`, so it is always safe to \"upcast\" to -- the weaker version. castFrzn :: LVarData1 f => f Trvrsbl a -> f Frzn a castFrzn x = unsafeCoerceLVar x --- | LVish Par actions must commute, therefore one safe way to consume a frozen (but--- unordered) LVar, /even in another runPar session/, is to run a par computation for+-- | LVish `Par` actions must commute, therefore one safe way to consume a frozen (but+-- unordered) LVar, /even in another `runPar` session/, is to run a `Par` computation for -- each element. forFrzn :: LVarData1 f => f Frzn a -> (a -> Par d s ()) -> Par d s () forFrzn fzn fn =
Data/LVar/Generic/Internal.hs view
@@ -29,9 +29,9 @@ -- Interface for generic LVar handling ------------------------------------------------------------------------------ --- | A class representing monotonic data types that take one type--- parameter as well as an `s` parameter for session safety.---+-- | A class representing monotonic data structures that take /one/ type+-- parameter, as well as an `s` parameter for session safety.+-- -- LVars that fall into this class are typically collection types. class (F.Foldable (f Trvrsbl)) => LVarData1 (f :: * -> * -> *) -- TODO: if there is a Par class to generalize LVar Par monads, then@@ -46,9 +46,9 @@ -- | An /O(1)/ operation that atomically switches the LVar into a -- frozen state. Any threads waiting on the freeze are woken.- --- -- The frozen LVar provides a complete picture of the contents:- -- e.g. a whole set instead of one element, or the full/empty+ -- + -- The contents of a frozen LVar are fully observable:+ -- e.g., a whole set instead of one element, or the full/empty -- information for an IVar, instead of just the payload. -- -- However, note that `Frzn` LVars cannot be folded, because they may have@@ -69,7 +69,7 @@ -- version of the LVar contents with its original type: in AFoldable ls' --- | Carries a Foldable type, but you don't get to know which one.+-- | Carries a `Foldable` type, but you don't get to know which one. -- The purpose of this type is that `sortFreeze` should not have -- to impose a particular memory representation. data AFoldable a = forall f2 . F.Foldable f2 => AFoldable (f2 a)@@ -81,13 +81,13 @@ -------------------------------------------------------------------------------- {-# INLINE unsafeCoerceLVar #-}--- | A safer version of `unsafeCoerce#` for LVars only.--- Note that it needs to change the contents type, because freezing is recursive.+-- | A safer version of `unsafeCoerce#` (that is, with a slightly more constrained type) for LVars only.+-- Note, that the type of the LVar's contents must be allowed to change, because freezing is recursive. unsafeCoerceLVar :: LVarData1 f => f s1 a -> f s2 b unsafeCoerceLVar = unsafeCoerce# --- | Here we gain permission to expose the non-deterministic internal structure of an--- LVar: namely, the order in which elements occur. We pay the piper with an IO+-- | Here we gain permission to expose the nondeterministic internal structure of an+-- LVar: namely, the order in which its contents occur We pay the piper with an `IO` -- action. unsafeTraversable :: LVarData1 f => f Frzn a -> IO (f Trvrsbl a) unsafeTraversable x = return (unsafeCoerceLVar x)
Data/LVar/IStructure.hs view
@@ -11,8 +11,7 @@ {-# LANGUAGE DataKinds #-} {-# LANGUAGE InstanceSigs #-} --- | An I-Structure, aka an Array of IVars.--- This uses a boxed array.+-- | An I-Structure, also known as an array of IVars, implemented using a boxed vector. module Data.LVar.IStructure (@@ -48,8 +47,7 @@ ------------------------------------------------------------------------------ --- | An I-Structure, aka an Array of IVars.--- For now this really is a simple vector of IVars.+-- | An I-Structure, also known as an array of IVars. newtype IStructure s a = IStructure (V.Vector (IV.IVar s a)) -- unIStructure (IStructure lv) = lv@@ -57,9 +55,9 @@ instance Eq (IStructure s v) where IStructure vec1 == IStructure vec2 = vec1 == vec2 --- | An @IStructure@ can be treated as a generic container LVar. However, the+-- | An `IStructure` can be treated as a generic container LVar. However, the -- polymorphic operations are less useful than the monomorphic ones exposed by this--- module (e.g. @forEachHP@ vs. @addHandler@).+-- module (e.g., @forEachHP@ vs. @addHandler@). instance LVarData1 IStructure where freeze orig@(IStructure vec) = WrapPar$ do -- No new alloc here, just time:@@ -72,15 +70,16 @@ -- Unlike the IStructure-specific forEach, this takes only values, not indices. addHandler mh is fn = forEachHP mh is (\ _k v -> fn v) --- | The @IStructure@s in this module also have the special property that they+-- | The `IStructure`s in this module also have the special property that they -- support a freeze operation which immediately yields a `Foldable` container -- without any sorting (see `snapFreeze`). instance OrderedLVarData1 IStructure where -- No extra work here... snapFreeze is = unsafeCoerceLVar <$> G.freeze is --- | As with all LVars, after freezing, map elements can be consumed. In the case of--- this @IStructure@ implementation, it need only be `Frzn`, not `Trvrsbl`.+-- As with all LVars, after freezing, map elements can be consumed. In+-- the case of this @IStructure@ implementation, it need only be+-- `Frzn`, not `Trvrsbl`. instance F.Foldable (IStructure Frzn) where foldr fn zer (IStructure vec) = F.foldr (\ iv acc ->@@ -89,13 +88,13 @@ Just x -> fn x acc) zer vec --- | Of course, the stronger `Trvrsbl` state is still fine for folding.+-- Of course, the stronger `Trvrsbl` state is still fine for folding. instance F.Foldable (IStructure Trvrsbl) where foldr fn zer mp = F.foldr fn zer (castFrzn mp) --- | @IStructure@ values can be returned as the result of a `runParThenFreeze`.--- Hence they need a `DeepFrz` instace.--- @DeepFrz@ is just a type-coercion. No bits flipped at runtime.+-- @IStructure@ values can be returned as the result of a+-- `runParThenFreeze`. Hence they need a `DeepFrz` instance.+-- @DeepFrz@ is just a type-coercion. No bits flipped at runtime. instance DeepFrz a => DeepFrz (IStructure s a) where type FrzType (IStructure s a) = IStructure Frzn (FrzType a) frz = unsafeCoerceLVar@@ -114,22 +113,22 @@ ------------------------------------------------------------------------------ --- | Retrieve the number of slots in the I-Structure.+-- | Retrieve the number of slots in the `IStructure`. getLength :: IStructure s a -> Par d s Int getLength (IStructure vec) = return $! V.length vec --- | Physical identity, just as with IORefs.+-- Physical identity, just as with IORefs. -- instance Eq (IStructure s v) where -- IStructure lv1 == IStructure lv2 = state lv1 == state lv2 -- | Create a new, empty, monotonically growing 'IStructure' of a given size.--- All entries start off as zero, which must be BOTTOM.+-- All entries start off as zero, which must be \"bottom\". newIStructure :: Int -> Par d s (IStructure s elt) newIStructure len = fmap IStructure $ V.generateM len (\_ -> IV.new) --- | This registers handlers on each internal IVar as it is created.--- It should be more efficient than `newIStructure` followed by `forEachHP`+-- | Register handlers on each internal IVar as it is created.+-- This operation should be more efficient than `newIStructure` followed by `forEachHP`. newIStructureWithCallback :: Int -> (Int -> elt -> Par d s ()) -> Par d s (IStructure s elt) newIStructureWithCallback len fn = fmap IStructure $@@ -138,9 +137,8 @@ IV.whenFull Nothing iv (fn ix) return iv --- | /O(N)/ complexity, unfortunately. This implementation of I-Structures requires+-- | /O(N)/ complexity, unfortunately. This implementation of `IStructure`s requires -- freezing each of the individual IVars stored in the array.--- freezeIStructure :: IStructure s a -> LV.Par QuasiDet s (V.Vector (Maybe a)) freezeIStructure (IStructure vec) = do v <- V.mapM IV.freezeIVar vec@@ -148,10 +146,10 @@ {-# INLINE forEachHP #-} -- | Add an (asynchronous) callback that listens for all new elements added to--- the IStructure, optionally enrolled in a handler pool+-- the `IStructure`, optionally enrolled in a handler pool. forEachHP :: -- (Eq a) => Maybe HandlerPool -- ^ pool to enroll in, if any- -> IStructure s a -- ^ IStructure to listen to+ -> IStructure s a -- ^ `IStructure` to listen to -> (Int -> a -> Par d s ()) -- ^ callback -> Par d s () forEachHP hp (IStructure vec) callb =@@ -186,16 +184,16 @@ {-# INLINE put #-} --- | Put a single element in the array. That slot must be previously empty. (WHNF)+-- | Put a single element in the `IStructure` at a given index. That index must be previously empty. (WHNF) -- Strict in the element being put in the set. put_ :: Eq elt => IStructure s elt -> Int -> elt -> Par d s () put_ (IStructure vec) !ix !elm = IV.put_ (vec ! ix) elm --- | Put a single element in the array. This variant is deeply strict (`NFData`).+-- | Put a single element in the `IStructure` at a given index. This variant is deeply strict (`NFData`). put :: (NFData elt, Eq elt) => IStructure s elt -> Int -> elt -> Par d s () put (IStructure vec) !ix !elm = IV.put (vec ! ix) elm {-# INLINE get #-}--- | Wait for the indexed entry to contain a value and return that value.+-- | Wait for the indexed entry to contain a value, and return that value. get :: Eq elt => IStructure s elt -> Int -> Par d s elt get (IStructure vec) !ix = IV.get (vec ! ix)
Data/LVar/IVar.hs view
@@ -10,18 +10,25 @@ {-| - `IVar`s are the very simplest form of `LVar`s. They are either empty, or full, and- contain only at most a single value.+ IVars are the very simplest form of LVars. They are either empty or full, and+ contain at most a single value. - For more explanation of using IVars in Haskell, see the @monad-par@ and+ For further information on using IVars in Haskell, see the @monad-par@ and @meta-par@ packages and papers: * <http://hackage.haskell.org/package/monad-par> * <http://www.cs.indiana.edu/~rrnewton/papers/haskell2011_monad-par.pdf> + * <http://hackage.haskell.org/package/meta-par>+ * <http://www.cs.indiana.edu/~rrnewton/papers/2012-ICFP_meta-par.pdf> +Unlike the @IVar@ type provided by @monad-par@, the 'IVar' type+provided in this module permits repeated `put`s of the same value, in+keeping with the lattice-based semantics of LVars in which a `put`+takes the least upper bound of the old and new values.+ -} module Data.LVar.IVar@@ -33,7 +40,7 @@ -- * Derived IVar operations, same as in monad-par spawn, spawn_, spawnP, - -- * LVar style operations+ -- * LVar-style operations freezeIVar, fromIVar, whenFull) where @@ -60,16 +67,16 @@ -- IVars implemented on top of (the idempotent implementation of) LVars ------------------------------------------------------------------------------ --- | An `IVar` is the simplest type of `LVar`.+-- | An `IVar` is the simplest form of `LVar`. newtype IVar s a = IVar (LVar s (IORef (Maybe a)) a) -- the global data for an IVar a is a reference to Maybe a, while deltas are -- simply values of type a (taking the IVar from Nothing to Just): --- | Physical equality just as with IORefs.+-- | Physical equality, just as with `IORef`s. instance Eq (IVar s a) where (==) (IVar lv1) (IVar lv2) = state lv1 == state lv2 --- | An @IVar@ can be treated as a generic container LVar which happens to+-- | An `IVar` can be treated as a generic container LVar which happens to -- contain at most one value! Note, however, that the polymorphic operations are -- less useful than the monomorphic ones exposed by this module. instance LVarData1 IVar where @@ -79,13 +86,13 @@ return (unsafeCoerceLVar orig) addHandler = whenFull --- | DeepFrz is just a type-coercion. No bits flipped at runtime:+-- Just a type-coercion. No bits flipped at runtime. instance DeepFrz a => DeepFrz (IVar s a) where type FrzType (IVar s a) = IVar Frzn (FrzType a) frz = unsafeCoerceLVar --- | As with all other `Trvrsbl` LVars, the elements are traversable in a fixed--- order.+-- As with all other `Trvrsbl` LVars, the elements are traversable in+-- a fixed order. instance F.Foldable (IVar Trvrsbl) where foldr fn zer (IVar lv) = case unsafeDupablePerformIO$ readIORef (state lv) of@@ -109,17 +116,17 @@ newLV $ newIORef Nothing {-# INLINE get #-}--- | read the value in a @IVar@. The 'get' can only return when the+-- | Read the value in a IVar. The 'get' can only return when the -- value has been written by a prior or concurrent @put@ to the same--- @IVar@.+-- IVar. get :: IVar s a -> Par d s a get (IVar (WrapLVar iv)) = WrapPar$ getLV iv globalThresh deltaThresh where globalThresh ref _ = readIORef ref -- past threshold iff Jusbt _ deltaThresh x = return $ Just x -- always past threshold {-# INLINE put_ #-}--- | put a value into a @IVar@. Multiple 'put's to the same @IVar@--- are not allowed, and result in a runtime error. (Unless both values put happen to be @(==)@.)+-- | Put a value into an IVar. Multiple 'put's to the same IVar+-- are not allowed, and result in a runtime error, unless the values put happen to be @(==)@. -- -- This function is always at least strict up to WHNF in the element put. put_ :: Eq a => IVar s a -> a -> Par d s ()@@ -132,7 +139,7 @@ throw (LV.ConflictingPutExn$ "Multiple puts to an IVar! (obj "++show n2++" was "++show n1++")") update Nothing = (Just x, Just x) --- | The specialized freeze just for IVars. It leaves the result in a natural format (`Maybe`).+-- | A specialized freezing operation for IVars that leaves the result in a handy format (`Maybe`). freezeIVar :: IVar s a -> LV.Par QuasiDet s (Maybe a) freezeIVar (IVar (WrapLVar lv)) = WrapPar $ do freezeLV lv@@ -142,15 +149,15 @@ globalThresh ref True = fmap Just $ readIORef ref deltaThresh _ = return Nothing --- | Unpack a frozen `IVar` (as produced by a generic `freeze` operation) as a more+-- | Unpack a frozen IVar (as produced by a generic `freeze` operation) as a more -- palatable data structure. fromIVar :: IVar Frzn a -> Maybe a fromIVar (IVar lv) = unsafeDupablePerformIO $ readIORef (state lv) {-# INLINE whenFull #-}--- | Register a handler that fires when the `IVar` is filled, which, of course, only+-- | Register a handler that fires when the IVar is filled, which, of course, only -- happens once.-whenFull :: Maybe HandlerPool -> IVar s elt -> (elt -> Par d s ()) -> Par d s ()+whenFull :: Maybe HandlerPool -> IVar s a -> (a -> Par d s ()) -> Par d s () whenFull mh (IVar (WrapLVar lv)) fn = WrapPar (LI.addHandler mh lv globalCB fn') where@@ -170,12 +177,11 @@ spawn p = do r <- new; fork (p >>= put r); return r {-# INLINE spawn_ #-}--- | A version of `spawn` that uses only weak-head-normal form rather than full `NFData`.+-- | A version of `spawn` that uses only WHNF, rather than full `NFData`. spawn_ :: Eq a => Par d s a -> Par d s (IVar s a) spawn_ p = do r <- new; fork (p >>= put_ r); return r {-# INLINE spawnP #-}--- | A variant that spawnP :: (Eq a, NFData a) => a -> Par d s (IVar s a) spawnP a = spawn (return a)
Data/LVar/Internal/Pure.hs view
@@ -6,17 +6,16 @@ {-| -This is NOT a datatype for the end-user.+This is /not/ a datatype for the end-user. Rather, this module is for building /new/ LVar types in a comparatively easy way: by-putting a pure value in a mutable container, and defining a LUB operation as a pure+putting a pure value in a mutable container, and defining a @put@ operation as a pure function. -The proof-obligation for the library-writer who uses this module is that they must-guarantee that their LUB is a /true least-upper-bound/, obeying the appropriate laws-for a join-semilattice:-- * <http://en.wikipedia.org/wiki/Semilattice>+The data structure implementor who uses this module must guarantee+that their @put@ operation computes a /least upper bound/, ensuring+that the set of states that their LVar type can take on form a+join-semilattice (<http://en.wikipedia.org/wiki/Semilattice>). -} @@ -51,7 +50,7 @@ newPureLVar st = WrapPar$ fmap (PureLVar . WrapLVar) $ LI.newLV $ newIORef st --- | Wait until the Pure LVar has crossed a threshold and then unblock. (In the+-- | Wait until the pure LVar has crossed a threshold and then unblock. (In the -- semantics, this is a singleton query set.) waitPureLVar :: (JoinSemiLattice t, Eq t) => PureLVar s t -> t -> Par d s ()@@ -72,7 +71,7 @@ putter _ = return (Just new) -- | Freeze the pure LVar, returning its exact value.--- Subsequent puts will cause an error.+-- Subsequent @put@s will raise an error. freezePureLVar :: PureLVar s t -> Par QuasiDet s t freezePureLVar (PureLVar (WrapLVar lv)) = WrapPar$ do LI.freezeLV lv@@ -84,40 +83,13 @@ ------------------------------------------------------------ ---- | Physical identity, just as with IORefs.+-- | Physical identity, just as with `IORef`s. instance Eq (PureLVar s v) where PureLVar lv1 == PureLVar lv2 = state lv1 == state lv2 --- | A `PureLVar` can be treated as a generic container LVar which happens to--- contain exactly one value!- --- instance LVarData1 PureLVar where--- freeze orig@(PureLVar (WrapLVar lv)) = WrapPar$ do freezeLV lv; return (unsafeCoerceLVar orig)--- sortFreeze is = AFoldable <$> freezeSet is--- addHandler = forEachHP---- -- | The `PureLVar`s in this module also have the special property that they support an--- -- `O(1)` freeze operation which immediately yields a `Foldable` container--- -- (`snapFreeze`).--- instance OrderedLVarData1 PureLVar where--- snapFreeze is = unsafeCoerceLVar <$> freeze is---- -- | As with all LVars, after freezing, map elements can be consumed. In the case of--- -- this `PureLVar` implementation, it need only be `Frzn`, not `Trvrsbl`.--- instance F.Foldable (PureLVar Frzn) where--- foldr fn zer (PureLVar lv) =--- -- It's not changing at this point, no problem if duped:--- let set = unsafeDupablePerformIO (readIORef (state lv)) in--- F.foldr fn zer set ---- -- | Of course, the stronger `Trvrsbl` state is still fine for folding.--- instance F.Foldable (PureLVar Trvrsbl) where--- foldr fn zer mp = F.foldr fn zer (castFrzn mp)---- | `PureLVar` values can be returned as the result of a `runParThenFreeze`.--- Hence they need a `DeepFrz` instace.--- @DeepFrz@ is just a type-coercion. No bits flipped at runtime.+-- `PureLVar` values can be returned as the result of a+-- `runParThenFreeze`. Hence they need a `DeepFrz` instance.+-- @DeepFrz@ is just a type-coercion. No bits flipped at runtime. instance DeepFrz a => DeepFrz (PureLVar s a) where -- We can't be sure that someone won't put an LVar value inside a -- PureLVar! Therefore we have to apply FrzType recursively.
Data/LVar/PureMap.hs view
@@ -11,11 +11,11 @@ {-| - This module provides finite maps that only grow. It is based on the popular `Data.Map`+ This module provides finite maps that only grow. It is based on the popular "Data.Map" balanced-tree representation of maps. Thus scalability is /not/ good for this implementation. However, there are some interoperability benefits. For example, after running a parallel computation with a map result, this module can produce a- `Data.Map` in /O(1)/ without copying, which may be useful downstream.+ `Map` in /O(1)/ without copying, which may be useful downstream. -} @@ -26,18 +26,18 @@ newEmptyMap, newMap, newFromList, insert, getKey, waitValue, waitSize, modify, -- -- * Freezing results (Quasi-determinism) - freezeMap, fromIMap, -- * Iteration and callbacks forEach, forEachHP, withCallbacksThenFreeze, + -- * Quasi-deterministic operations+ freezeMap, fromIMap,+ -- * Higher-level derived operations copy, traverseMap, traverseMap_, union, - -- * Alternate versions of derived ops that expose HandlerPools they create.+ -- * Alternate versions of derived ops that expose @HandlerPool@s they create traverseMapHP, traverseMapHP_, unionHP ) where @@ -61,8 +61,6 @@ import System.IO.Unsafe (unsafePerformIO, unsafeDupablePerformIO) import System.Mem.StableName (makeStableName, hashStableName) -type QPar = Par QuasiDet -- Shorthand.- ------------------------------------------------------------------------------ -- IMaps implemented on top of LVars: ------------------------------------------------------------------------------@@ -71,7 +69,7 @@ -- `STRef`) in addition to the @a@ parameter that describes the type of elements -- in the set. -- --- Performance note: There is only ONE mutable location in this implementation. Thus+-- Performance note: There is only /one/ mutable location in this implementation. Thus -- it is not a scalable implementation. newtype IMap k s v = IMap (LVar s (IORef (M.Map k v)) (k,v)) @@ -88,25 +86,26 @@ sortFrzn (IMap lv) = AFoldable$ unsafeDupablePerformIO (readIORef (state lv)) -- | The `IMap`s in this module also have the special property that they support an--- `O(1)` freeze operation which immediately yields a `Foldable` container+-- /O(1)/ freeze operation which immediately yields a `Foldable` container -- (`snapFreeze`). instance OrderedLVarData1 (IMap k) where snapFreeze is = unsafeCoerceLVar <$> freeze is --- | As with all LVars, after freezing, map elements can be consumed. In the case of--- this `IMap` implementation, it need only be `Frzn`, not `Trvrsbl`.+-- As with all LVars, after freezing, map elements can be consumed. In+-- the case of this `IMap` implementation, it need only be `Frzn`, not+-- `Trvrsbl`. instance F.Foldable (IMap k Frzn) where foldr fn zer (IMap lv) = let set = unsafeDupablePerformIO (readIORef (state lv)) in F.foldr fn zer set --- | Of course, the stronger `Trvrsbl` state is still fine for folding.+-- Of course, the stronger `Trvrsbl` state is still fine for folding. instance F.Foldable (IMap k Trvrsbl) where foldr fn zer mp = F.foldr fn zer (castFrzn mp) --- | `IMap` values can be returned as the result of a `runParThenFreeze`.--- Hence they need a `DeepFrz` instace.--- @DeepFrz@ is just a type-coercion. No bits flipped at runtime.+-- `IMap` values can be returned as the result of a+-- `runParThenFreeze`. Hence they need a `DeepFrz` instance.+-- @DeepFrz@ is just a type-coercion. No bits flipped at runtime. instance DeepFrz a => DeepFrz (IMap k s a) where type FrzType (IMap k s a) = IMap k Frzn (FrzType a) frz = unsafeCoerceLVar@@ -140,7 +139,7 @@ -- | Register a per-element callback, then run an action in this context, and freeze -- when all (recursive) invocations of the callback are complete. Returns the final--- valueof the Map variable.+-- value of the provided action. withCallbacksThenFreeze :: forall k v b s . Eq b => IMap k s v -> (k -> v -> QPar s ()) -> QPar s b -> QPar s b withCallbacksThenFreeze (IMap (WrapLVar lv)) callback action =@@ -164,7 +163,7 @@ IV.put_ resIV res -- | Add an (asynchronous) callback that listens for all new key/value pairs added to--- the map, optionally enrolled in a handler pool+-- the map, optionally enrolled in a handler pool. forEachHP :: Maybe HandlerPool -- ^ optional pool to enroll in -> IMap k s v -- ^ Map to listen to -> (k -> v -> Par d s ()) -- ^ callback@@ -180,13 +179,13 @@ traverseWithKey_ (\ k v -> forkHP mh$ callb k v) mp -- | Add an (asynchronous) callback that listens for all new new key/value pairs added to--- the map+-- the map. forEach :: IMap k s v -> (k -> v -> Par d s ()) -> Par d s () forEach = forEachHP Nothing -- | Put a single entry into the map. Strict (WHNF) in the key and value. -- --- As with other container LVars, if an key is put multiple times, the values had+-- As with other container LVars, if a key is inserted multiple times, the values had -- better be equal @(==)@, or a multiple-put error is raised. insert :: (Ord k, Eq v) => k -> v -> IMap k s v -> Par d s () @@ -203,18 +202,18 @@ then (mp',Just (key,elm)) else (mp, Nothing) --- | IMap's containing other LVars have some additional capabilities compared to+-- | `IMap`s containing other LVars have some additional capabilities compared to -- those containing regular Haskell data. In particular, it is possible to modify -- existing entries (monotonically). Further, this `modify` function implicitly--- inserts a "bottom" element if there is no existing entry for the key.---+-- inserts a \"bottom\" element if there is no existing entry for the key.+-- -- Unfortunately, that means that this takes another computation for creating new--- "bottom" elements for the nested LVars stored inside the Map.+-- \"bottom\" elements for the nested LVars stored inside the `IMap`. modify :: forall f a b d s key . (Ord key, LVarData1 f, Show key, Ord a) => IMap key s (f s a) -> key -- ^ The key to lookup.- -> (Par d s (f s a)) -- ^ Create a new "bottom" element whenever an entry is not present.- -> (f s a -> Par d s b) -- ^ The computation to apply on the right-hand-side of the keyed entry.+ -> (Par d s (f s a)) -- ^ Create a new \"bottom\" element whenever an entry is not present.+ -> (f s a -> Par d s b) -- ^ The computation to apply on the right-hand side of the keyed entry. -> Par d s b modify (IMap lv) key newBottom fn = WrapPar $ do let ref = state lv @@ -263,7 +262,7 @@ | otherwise = return Nothing --- | Wait on the SIZE of the map, not its contents.+-- | Wait on the /size/ of the map, not its contents. waitSize :: Int -> IMap k s v -> Par d s () waitSize !sz (IMap (WrapLVar lv)) = WrapPar $ getLV lv globalThresh deltaThresh@@ -277,15 +276,17 @@ -- the threshold.a deltaThresh _ = globalThresh (L.state lv) False --- | Get the exact contents of the map Using this may cause your+-- | Get the exact contents of the map. As with any+-- quasi-deterministic operation, using `freezeSet` may cause your -- program to exhibit a limited form of nondeterminism: it will never -- return the wrong answer, but it may include synchronization bugs -- that can (nondeterministically) cause exceptions. ----- This Data.Map based LVar has the property that you can--- retrieve the full set without any IO, and without nondeterminism--- leaking. (This is because the internal order is fixed for the--- tree-based Data.Set.) +-- This "Data.Map"-based implementation has the special property that+-- you can retrieve the full set without any `IO`, and without+-- nondeterminism leaking. (This is because the internal order is+-- fixed for the tree-based representation of maps that "Data.Map"+-- uses.) freezeMap :: IMap k s v -> QPar s (M.Map k v) freezeMap (IMap (WrapLVar lv)) = WrapPar $ do freezeLV lv@@ -305,13 +306,14 @@ -- Higher level routines that could (mostly) be defined using the above interface. -------------------------------------------------------------------------------- --- | Establish monotonic map between the input and output sets. Produce a new result--- based on each element, while leaving the keys the same.+-- | Establish a monotonic map between the input and output sets.+-- Produce a new result based on each element, while leaving the keys+-- the same. traverseMap :: (Ord k, Eq b) => (k -> a -> Par d s b) -> IMap k s a -> Par d s (IMap k s b) traverseMap f s = traverseMapHP Nothing f s --- | An imperative-style, inplace version of 'traverseMap' that takes the output set+-- | An imperative-style, in-place version of 'traverseMap' that takes the output set -- as an argument. traverseMap_ :: (Ord k, Eq b) => (k -> a -> Par d s b) -> IMap k s a -> IMap k s b -> Par d s ()@@ -319,7 +321,6 @@ -- | Return a new map which will (ultimately) contain everything in either input -- map. Conflicting entries will result in a multiple put exception.--- Optionally ties the handlers to a pool. union :: (Ord k, Eq a) => IMap k s a -> IMap k s a -> Par d s (IMap k s a) union = unionHP Nothing @@ -334,7 +335,7 @@ copy :: (Ord k, Eq v) => IMap k s v -> Par d s (IMap k s v) copy = traverseMap (\ _ x -> return x) --- | Variant that optionally ties the handlers to a pool.+-- | A variant of `traverseMap` that optionally ties the handlers to a pool. traverseMapHP :: (Ord k, Eq b) => Maybe HandlerPool -> (k -> a -> Par d s b) -> IMap k s a -> Par d s (IMap k s b)@@ -343,7 +344,7 @@ traverseMapHP_ mh fn set os return os --- | Variant that optionally ties the handlers to a pool.+-- | A variant of `traverseMap_` that optionally ties the handlers to a pool. traverseMapHP_ :: (Ord k, Eq b) => Maybe HandlerPool -> (k -> a -> Par d s b) -> IMap k s a -> IMap k s b -> Par d s ()@@ -352,8 +353,9 @@ x' <- fn k x insert k x' os --- | Variant that optionally ties the handlers in the resulting set to the same--- handler pool as those in the two input sets.+-- | A variant of `union` that optionally ties the handlers in the+-- resulting set to the same handler pool as those in the two input+-- sets. unionHP :: (Ord k, Eq a) => Maybe HandlerPool -> IMap k s a -> IMap k s a -> Par d s (IMap k s a) unionHP mh m1 m2 = do@@ -367,4 +369,3 @@ unsafeName x = unsafePerformIO $ do sn <- makeStableName x return (hashStableName sn)-
Data/LVar/PureSet.hs view
@@ -13,11 +13,11 @@ {-| - This module provides sets that only grow. It is based on the popular `Data.Set`- balanced-tree representation of sets. Thus scalability is not good for this+ This module provides sets that only grow. It is based on the popular "Data.Set"+ balanced-tree representation of sets. Thus scalability is /not/ good for this implementation. However, there are some interoperability benefits. For exmaple, after running a parallel computation with a set result, this module can produce a- `Data.Set` in /O(1)/ without copying, which may be useful downstream.+ `Set` in /O(1)/ without copying, which may be useful downstream. -} @@ -39,7 +39,7 @@ copy, traverseSet, traverseSet_, union, intersection, cartesianProd, cartesianProds, - -- * Alternate versions of derived ops that expose HandlerPools they create.+ -- * Alternate versions of derived ops that expose @HandlerPool@s they create traverseSetHP, traverseSetHP_, unionHP, intersectionHP, cartesianProdHP, cartesianProdsHP ) where@@ -69,11 +69,11 @@ -- an `STRef`) in addition to the @a@ parameter that describes the type of elements -- in the set. ----- Performance note: There is only ONE mutable location in this implementation. Thus+-- Performance note: There is only /one/ mutable location in this implementation. Thus -- it is not a scalable implementation. newtype ISet s a = ISet (LVar s (IORef (S.Set a)) a) --- | Physical identity, just as with IORefs.+-- | Physical identity, just as with `IORef`s. instance Eq (ISet s v) where ISet lv1 == ISet lv2 = state lv1 == state lv2 @@ -86,27 +86,27 @@ sortFrzn (ISet lv) = AFoldable$ unsafeDupablePerformIO (readIORef (state lv)) -- | The `ISet`s in this module also have the special property that they support an--- `O(1)` freeze operation which immediately yields a `Foldable` container+-- /O(1)/ freeze operation which immediately yields a `Foldable` container -- (`snapFreeze`). instance OrderedLVarData1 ISet where snapFreeze is = unsafeCoerceLVar <$> freeze is --- | As with all LVars, after freezing, map elements can be consumed. In the case of--- this `ISet` implementation, it need only be `Frzn`, not `Trvrsbl`.+-- As with all LVars, after freezing, map elements can be consumed. In+-- the case of this `ISet` implementation, it need only be `Frzn`, not+-- `Trvrsbl`. instance F.Foldable (ISet Frzn) where foldr fn zer (ISet lv) = -- It's not changing at this point, no problem if duped: let set = unsafeDupablePerformIO (readIORef (state lv)) in F.foldr fn zer set --- | Of course, the stronger `Trvrsbl` state is still fine for folding.+-- Of course, the stronger `Trvrsbl` state is still fine for folding. instance F.Foldable (ISet Trvrsbl) where foldr fn zer mp = F.foldr fn zer (castFrzn mp) ---- | `ISet` values can be returned as the result of a `runParThenFreeze`.--- Hence they need a `DeepFrz` instace.--- @DeepFrz@ is just a type-coercion. No bits flipped at runtime.+-- `ISet` values can be returned as the result of a+-- `runParThenFreeze`. Hence they need a `DeepFrz` instance.+-- @DeepFrz@ is just a type-coercion. No bits flipped at runtime. instance DeepFrz a => DeepFrz (ISet s a) where type FrzType (ISet s a) = ISet Frzn (FrzType a) frz = unsafeCoerceLVar@@ -121,7 +121,7 @@ instance Show a => Show (ISet Trvrsbl a) where show = show . castFrzn --- | Create a new, empty, monotonically growing 'ISet'.+-- | Create a new, empty, monotonically growing set. newEmptySet :: Par d s (ISet s a) newEmptySet = newSet S.empty @@ -129,7 +129,7 @@ newSet :: S.Set a -> Par d s (ISet s a) newSet s = WrapPar$ fmap (ISet . WrapLVar) $ newLV$ newIORef s --- | Create a new 'ISet' drawing initial elements from an existing list.+-- | Create a new set drawing initial elements from an existing list. newFromList :: Ord a => [a] -> Par d s (ISet s a) newFromList ls = newSet (S.fromList ls) @@ -139,13 +139,10 @@ -- Quasi-deterministic ops: -------------------------------------------------------------------------------- --- Just a shorthand for below:-type QPar = Par QuasiDet - -- | Freeze an 'ISet' after a specified callback/handler is done running. This--- differs from withCallbacksThenFreeze by not taking an additional action to run in+-- differs from `withCallbacksThenFreeze` by not taking an additional action to run in -- the context of the handlers.---+-- -- (@'freezeSetAfter' 's' 'f' == 'withCallbacksThenFreeze' 's' 'f' 'return ()' @) freezeSetAfter :: ISet s a -> (a -> QPar s ()) -> QPar s () freezeSetAfter s f = withCallbacksThenFreeze s f (return ())@@ -175,15 +172,17 @@ res <- action -- Any additional puts here trigger the callback. IV.put_ resIV res --- | Get the exact contents of the set. Using this may cause your+-- | Get the exact contents of the set. As with any+-- quasi-deterministic operation, using `freezeSet` may cause your -- program to exhibit a limited form of nondeterminism: it will never -- return the wrong answer, but it may include synchronization bugs -- that can (nondeterministically) cause exceptions. ----- This Data.Set based LVar has the special property that you can--- retrieve the full set without any IO, and without nondeterminism--- leaking. (This is because the internal order is fixed for the--- tree-based Data.Set.)+-- This "Data.Set"-based implementation has the special property that+-- you can retrieve the full set without any `IO`, and without+-- nondeterminism leaking. (This is because the internal order is+-- fixed for the tree-based representation of sets that "Data.Set"+-- uses.) freezeSet :: ISet s a -> QPar s (S.Set a) freezeSet (ISet (WrapLVar lv)) = WrapPar $ do freezeLV lv@@ -204,7 +203,7 @@ -------------------------------------------------------------------------------- -- | Add an (asynchronous) callback that listens for all new elements added to--- the set, optionally enrolled in a handler pool+-- the set, optionally enrolled in a handler pool. forEachHP :: Maybe HandlerPool -- ^ pool to enroll in, if any -> ISet s a -- ^ Set to listen to -> (a -> Par d s ()) -- ^ callback@@ -219,7 +218,7 @@ F.foldlM (\() v -> forkHP hp $ callb v) () set -- Non-allocating traversal. -- | Add an (asynchronous) callback that listens for all new elements added to--- the set+-- the set. forEach :: ISet s a -> (a -> Par d s ()) -> Par d s () forEach = forEachHP Nothing @@ -251,7 +250,7 @@ | otherwise = return Nothing --- | Wait on the SIZE of the set, not its contents.+-- | Wait on the /size/ of the set, not its contents. waitSize :: Int -> ISet s a -> Par d s () waitSize !sz (ISet lv) = WrapPar$ getLV (unWrapLVar lv) globalThresh deltaThresh@@ -274,11 +273,11 @@ copy :: Ord a => ISet s a -> Par d s (ISet s a) copy = traverseSet return --- | Establish monotonic map between the input and output sets.+-- | Establish a monotonic map between the input and output sets. traverseSet :: Ord b => (a -> Par d s b) -> ISet s a -> Par d s (ISet s b) traverseSet f s = traverseSetHP Nothing f s --- | An imperative-style, inplace version of 'traverseSet' that takes the output set+-- | An imperative-style, in-place version of 'traverseSet' that takes the output set -- as an argument. traverseSet_ :: Ord b => (a -> Par d s b) -> ISet s a -> ISet s b -> Par d s () traverseSet_ f s o = void $ traverseSetHP_ Nothing f s o@@ -291,11 +290,11 @@ intersection :: Ord a => ISet s a -> ISet s a -> Par d s (ISet s a) intersection = intersectionHP Nothing --- | Cartesian product of two sets.+-- | Take the cartesian product of two sets. cartesianProd :: (Ord a, Ord b) => ISet s a -> ISet s b -> Par d s (ISet s (a,b)) cartesianProd s1 s2 = cartesianProdHP Nothing s1 s2 --- | Takes the cartesian product of several sets.+-- | Take the cartesian product of several sets. cartesianProds :: Ord a => [ISet s a] -> Par d s (ISet s [a]) cartesianProds ls = cartesianProdsHP Nothing ls @@ -303,7 +302,7 @@ -- Alternate versions of functions that EXPOSE the HandlerPools -------------------------------------------------------------------------------- --- | Variant that optionally ties the handlers to a pool.+-- | Variant of `traverseSet` that optionally ties the handlers to a pool. traverseSetHP :: Ord b => Maybe HandlerPool -> (a -> Par d s b) -> ISet s a -> Par d s (ISet s b) traverseSetHP mh fn set = do@@ -311,7 +310,7 @@ traverseSetHP_ mh fn set os return os --- | Variant that optionally ties the handlers to a pool.+-- | Variant of `traverseSet_` that optionally ties the handlers to a pool. traverseSetHP_ :: Ord b => Maybe HandlerPool -> (a -> Par d s b) -> ISet s a -> ISet s b -> Par d s () traverseSetHP_ mh fn set os = do@@ -319,7 +318,7 @@ x' <- fn x insert x' os --- | Variant that optionally ties the handlers in the resulting set to the same+-- | Variant of `union` that optionally ties the handlers in the resulting set to the same -- handler pool as those in the two input sets. unionHP :: Ord a => Maybe HandlerPool -> ISet s a -> ISet s a -> Par d s (ISet s a) unionHP mh s1 s2 = do@@ -328,7 +327,7 @@ forEachHP mh s2 (`insert` os) return os --- | Variant that optionally ties the handlers in the resulting set to the same+-- | Variant of `intersection` that optionally ties the handlers in the resulting set to the same -- handler pool as those in the two input sets. intersectionHP :: Ord a => Maybe HandlerPool -> ISet s a -> ISet s a -> Par d s (ISet s a) -- Can we do intersection with only the public interface? It should be monotonic.
Data/LVar/SLMap.hs view
@@ -14,12 +14,13 @@ {-| - This module provides finite maps that only grow. It is based on a concurrent-skip-list- implementation of maps.+This module provides finite maps that only grow. It is based on a+/concurrent skip list/ implementation of maps. - Note that this module provides almost the same interface as "Data.LVar.PureMap",- but this module is usually more efficient. However, it's always good to test muliple- data structures if you have a performance-critical use case.+This module is usually a more efficient alternative to+`Data.LVar.PureMap`, and provides almost the same interface. However,+it's always good to test multiple data structures if you have a+performance-critical use case. -} @@ -30,7 +31,10 @@ IMap, newEmptyMap, newMap, newFromList, insert, - getKey, waitSize, modify, freezeMap,+ getKey, waitSize, modify,++ -- * Quasi-deterministic operations+ freezeMap, -- waitValue, -- * Iteration and callbacks@@ -40,7 +44,7 @@ -- * Higher-level derived operations copy, traverseMap, traverseMap_, - -- * Alternate versions of derived ops that expose HandlerPools they create.+ -- * Alternate versions of derived ops that expose @HandlerPool@s they create traverseMapHP, traverseMapHP_, unionHP, ) where@@ -68,8 +72,6 @@ import GHC.Prim (unsafeCoerce#) import Prelude -type QPar = Par QuasiDet -- Shorthand used below.- ------------------------------------------------------------------------------ -- IMaps implemented vis SkipListMap ------------------------------------------------------------------------------@@ -111,14 +113,14 @@ SLM.foldlWithKey (\() _k v -> forkHP mh $ callb v) () slm -- | The `IMap`s in this module also have the special property that they support an--- `O(1)` freeze operation which immediately yields a `Foldable` container+-- /O(1)/ freeze operation which immediately yields a `Foldable` container -- (`snapFreeze`). instance OrderedLVarData1 (IMap k) where snapFreeze is = unsafeCoerceLVar <$> freeze is --- | `IMap` values can be returned as the result of a `runParThenFreeze`.--- Hence they need a `DeepFrz` instace.--- @DeepFrz@ is just a type-coercion. No bits flipped at runtime.+-- `IMap` values can be returned as the result of a+-- `runParThenFreeze`. Hence they need a `DeepFrz` instance.+-- @DeepFrz@ is just a type-coercion. No bits flipped at runtime. instance DeepFrz a => DeepFrz (IMap k s a) where type FrzType (IMap k s a) = IMap k Frzn (FrzType a) frz = unsafeCoerceLVar@@ -148,13 +150,13 @@ ) mp return slm --- | Create a new 'IMap' drawing initial elements from an existing list.+-- | Create a new map drawing initial elements from an existing list. newFromList :: (Ord k, Eq v) => [(k,v)] -> Par d s (IMap k s v) newFromList ls = newFromList_ ls defaultLevels --- | Create a new 'IMap' drawing initial elements from an existing list, with--- the given number of skiplist levels.+-- | Create a new map drawing initial elements from an existing list, with+-- the given number of skip list levels. newFromList_ :: Ord k => [(k,v)] -> Int -> Par d s (IMap k s v) newFromList_ ls n = do m@(IMap lv) <- newEmptyMap_ n@@ -198,7 +200,7 @@ SLM.foldlWithKey (\() k v -> forkHP mh $ callb k v) () slm -- | Add an (asynchronous) callback that listens for all new new key/value pairs added to--- the map+-- the map. forEach :: IMap k s v -> (k -> v -> Par d s ()) -> Par d s () forEach = forEachHP Nothing @@ -212,16 +214,16 @@ Added _ -> return $ Just (key, elm) Found _ -> throw$ ConflictingPutExn$ "Multiple puts to one entry in an IMap!" --- | IMap's containing other LVars have some additional capabilities compared to+-- | `IMap`s containing other LVars have some additional capabilities compared to -- those containing regular Haskell data. In particular, it is possible to modify -- existing entries (monotonically). Further, this `modify` function implicitly--- inserts a "bottom" element if there is no existing entry for the key.+-- inserts a \"bottom\" element if there is no existing entry for the key. -- modify :: forall f a b d s key . (Ord key, LVarData1 f, Show key, Ord a) => IMap key s (f s a) -> key -- ^ The key to lookup.- -> (Par d s (f s a)) -- ^ Create a new "bottom" element whenever an entry is not present.- -> (f s a -> Par d s b) -- ^ The computation to apply on the right-hand-side of the keyed entry.+ -> (Par d s (f s a)) -- ^ Create a new \"bottom\" element whenever an entry is not present.+ -> (f s a -> Par d s b) -- ^ The computation to apply on the right-hand side of the keyed entry. -> Par d s b modify (IMap (WrapLVar lv)) key newBottom fn = do act <- WrapPar $ putLV_ lv putter@@ -258,12 +260,13 @@ -- the threshold.a deltaThresh _ = globalThresh (L.state lv) False --- | Get the exact contents of the map Using this may cause your+-- | Get the exact contents of the map. As with any+-- quasi-deterministic operation, using `freezeMap` may cause your -- program to exhibit a limited form of nondeterminism: it will never -- return the wrong answer, but it may include synchronization bugs -- that can (nondeterministically) cause exceptions. ----- This is an O(1) operation that doesn't copy the in-memory representation of the+-- This is an /O(1)/ operation that doesn't copy the in-memory representation of the -- IMap. freezeMap :: Ord k => IMap k s v -> QPar s (IMap k Frzn v) -- freezeMap (IMap (WrapLVar lv)) = return (IMap (WrapLVar lv))@@ -279,13 +282,13 @@ -- Higher level routines that could (mostly) be defined using the above interface. -------------------------------------------------------------------------------- --- | Establish monotonic map between the input and output sets. Produce a new result+-- | Establish a monotonic map between the input and output map Produce a new result -- based on each element, while leaving the keys the same. traverseMap :: (Ord k, Eq b) => (k -> a -> Par d s b) -> IMap k s a -> Par d s (IMap k s b) traverseMap f s = traverseMapHP Nothing f s --- | An imperative-style, inplace version of 'traverseMap' that takes the output set+-- | An imperative-style, in-place version of 'traverseMap' that takes the output map -- as an argument. traverseMap_ :: (Ord k, Eq b) => (k -> a -> Par d s b) -> IMap k s a -> IMap k s b -> Par d s ()@@ -300,7 +303,7 @@ copy :: (Ord k, Eq v) => IMap k s v -> Par d s (IMap k s v) copy = traverseMap (\ _ x -> return x) --- | Variant that optionally ties the handlers to a pool.+-- | Variant of `traverseMap` that optionally ties the handlers to a pool. traverseMapHP :: (Ord k, Eq b) => Maybe HandlerPool -> (k -> a -> Par d s b) -> IMap k s a -> Par d s (IMap k s b)@@ -309,7 +312,7 @@ traverseMapHP_ mh fn set os return os --- | Variant that optionally ties the handlers to a pool.+-- | Variant of `traverseMap_` that optionally ties the handlers to a pool. traverseMapHP_ :: (Ord k, Eq b) => Maybe HandlerPool -> (k -> a -> Par d s b) -> IMap k s a -> IMap k s b -> Par d s ()@@ -333,8 +336,9 @@ -- Operations on frozen Maps -------------------------------------------------------------------------------- --- | As with all LVars, after freezing, map elements can be consumed. In the case of--- this `IMap` implementation, it need only be `Frzn`, not `Trvrsbl`.+-- As with all LVars, after freezing, map elements can be consumed. In+-- the case of this `IMap` implementation, it need only be `Frzn`, not+-- `Trvrsbl`. instance F.Foldable (IMap k Frzn) where -- Note: making these strict for now: foldr fn zer (IMap (WrapLVar lv)) =@@ -342,7 +346,7 @@ SLM.foldlWithKey (\ a _k v -> return (fn v a)) zer (L.state lv) --- | Of course, the stronger `Trvrsbl` state is still fine for folding.+-- Of course, the stronger `Trvrsbl` state is still fine for folding. instance F.Foldable (IMap k Trvrsbl) where foldr fn zer mp = F.foldr fn zer (castFrzn mp)
Data/LVar/SLSet.hs view
@@ -13,12 +13,13 @@ {-| - This module provides sets that only grow. It is based on a concurrent-skip-list- implementation of sets.+This module provides sets that only grow. It is based on a+/concurrent skip list/ representation of sets. - Note that this module provides almost the same interface as "Data.LVar.PureSet",- but this module is usually more efficient. However, it's always good to test muliple- data structures if you have a performance-critical use case.+This module is usually a more efficient alternative to+"Data.LVar.PureSet", and provides almost the same interface. However,+it's always good to test multiple data structures if you have a+performance-critical use case. -} @@ -40,7 +41,7 @@ copy, traverseSet, traverseSet_, union, intersection, cartesianProd, cartesianProds, - -- * Alternate versions of derived ops that expose HandlerPools they create.+ -- * Alternate versions of derived ops that expose @HandlerPool@s they create traverseSetHP, traverseSetHP_, cartesianProdHP, cartesianProdsHP ) where @@ -77,7 +78,7 @@ data ISet s a = Ord a => ISet {-# UNPACK #-}!(LVar s (SLM.SLMap a ()) a) -- TODO: Address the possible inefficiency of carrying Ord dictionaries at runtime. --- | Physical identity, just as with IORefs.+-- | Physical identity, just as with `IORef`s. instance Eq (ISet s v) where ISet slm1 == ISet slm2 = state slm1 == state slm2 @@ -93,14 +94,14 @@ -- | The `ISet`s in this module also have the special property that they support an--- `O(1)` freeze operation which immediately yields a `Foldable` container+-- /O(1)/ freeze operation which immediately yields a `Foldable` container -- (`snapFreeze`). instance OrderedLVarData1 ISet where snapFreeze is = unsafeCoerceLVar <$> freeze is --- | `ISet` values can be returned as the result of a `runParThenFreeze`.--- Hence they need a `DeepFrz` instance.--- @DeepFrz@ is just a type-coercion. No bits flipped at runtime.+-- `ISet` values can be returned as the result of a+-- `runParThenFreeze`. Hence they need a `DeepFrz` instance.+-- @DeepFrz@ is just a type-coercion. No bits flipped at runtime. instance DeepFrz a => DeepFrz (ISet s a) where type FrzType (ISet s a) = ISet Frzn (FrzType a) frz = unsafeCoerceLVar@@ -124,15 +125,16 @@ Just () -> True Nothing -> False --- | As with all LVars, after freezing, map elements can be consumed. In the case of--- this `ISet` implementation, it need only be `Frzn`, not `Trvrsbl`.+-- As with all LVars, after freezing, map elements can be consumed. In+-- the case of this `ISet` implementation, it need only be `Frzn`, not+-- `Trvrsbl`. instance F.Foldable (ISet Frzn) where foldr fn zer (ISet (WrapLVar lv)) = unsafeDupablePerformIO $ SLM.foldlWithKey (\ a k _v -> return (fn k a)) zer (L.state lv) --- | Of course, the stronger `Trvrsbl` state is still fine for folding.+-- Of course, the stronger `Trvrsbl` state is still fine for folding. instance F.Foldable (ISet Trvrsbl) where foldr fn zer mp = F.foldr fn zer (castFrzn mp) @@ -141,16 +143,16 @@ defaultLevels :: Int defaultLevels = 8 --- | Create a new, empty, monotonically growing 'ISet'.+-- | Create a new, empty, monotonically growing set. newEmptySet :: Ord a => Par d s (ISet s a) newEmptySet = newEmptySet_ defaultLevels --- | Tuning: Create a new, empty, monotonically growing 'ISet', with the given number--- of skiplist levels.+-- | Tuning: Create a new, empty, monotonically growing set, with the given number+-- of skip list levels. newEmptySet_ :: Ord a => Int -> Par d s (ISet s a) newEmptySet_ n = fmap (ISet . WrapLVar) $ WrapPar $ newLV $ SLM.newSLMap n --- | Create a new set populated with initial elements.+-- | Create a new `ISet` populated with initial elements. newSet :: Ord a => S.Set a -> Par d s (ISet s a) newSet set = fmap (ISet . WrapLVar) $ WrapPar $ newLV $ do@@ -180,10 +182,8 @@ -- Quasi-deterministic ops: -------------------------------------------------------------------------------- -type QPar = Par QuasiDet - -- | Freeze an 'ISet' after a specified callback/handler is done running. This--- differs from withCallbacksThenFreeze by not taking an additional action to run in+-- differs from `withCallbacksThenFreeze` by not taking an additional action to run in -- the context of the handlers. -- -- (@'freezeSetAfter' 's' 'f' == 'withCallbacksThenFreeze' 's' 'f' 'return ()' @)@@ -229,7 +229,7 @@ SLM.foldlWithKey (\() v () -> forkHP hp $ callb v) () slm -- | Add an (asynchronous) callback that listens for all new elements added to--- the set+-- the set. forEach :: ISet s a -> (a -> Par d s ()) -> Par d s () forEach = forEachHP Nothing @@ -252,7 +252,7 @@ deltaThresh e2 | e2 == elm = return $ Just () | otherwise = return Nothing --- | Wait on the SIZE of the set, not its contents.+-- | Wait on the /size/ of the set, not its contents. waitSize :: Int -> ISet s a -> Par d s () waitSize !sz (ISet (WrapLVar lv)) = WrapPar$ getLV lv globalThresh deltaThresh@@ -275,11 +275,11 @@ copy :: Ord a => ISet s a -> Par d s (ISet s a) copy = traverseSet return --- | Establish monotonic map between the input and output sets.+-- | Establish a monotonic map between the input and output sets. traverseSet :: Ord b => (a -> Par d s b) -> ISet s a -> Par d s (ISet s b) traverseSet f s = traverseSetHP Nothing f s --- | An imperative-style, inplace version of 'traverseSet' that takes the output set+-- | An imperative-style, in-place version of 'traverseSet' that takes the output set -- as an argument. traverseSet_ :: Ord b => (a -> Par d s b) -> ISet s a -> ISet s b -> Par d s () traverseSet_ f s o = traverseSetHP_ Nothing f s o@@ -292,11 +292,11 @@ intersection :: Ord a => ISet s a -> ISet s a -> Par d s (ISet s a) intersection = intersectionHP Nothing --- | Cartesian product of two sets.+-- | Take the cartesian product of two sets. cartesianProd :: (Ord a, Ord b) => ISet s a -> ISet s b -> Par d s (ISet s (a,b)) cartesianProd s1 s2 = cartesianProdHP Nothing s1 s2 --- | Takes the cartesian product of several sets.+-- | Take the cartesian product of several sets. cartesianProds :: Ord a => [ISet s a] -> Par d s (ISet s [a]) cartesianProds ls = cartesianProdsHP Nothing ls @@ -304,7 +304,7 @@ -- Alternate versions of functions that EXPOSE the HandlerPools -------------------------------------------------------------------------------- --- | Variant that optionally ties the handlers to a pool.+-- | Variant of `traverseSet` that optionally ties the handlers to a pool. traverseSetHP :: Ord b => Maybe HandlerPool -> (a -> Par d s b) -> ISet s a -> Par d s (ISet s b) traverseSetHP mh fn set = do@@ -312,7 +312,7 @@ traverseSetHP_ mh fn set os return os --- | Variant that optionally ties the handlers to a pool.+-- | Variant of `traverseSet_` that optionally ties the handlers to a pool. traverseSetHP_ :: Ord b => Maybe HandlerPool -> (a -> Par d s b) -> ISet s a -> ISet s b -> Par d s () traverseSetHP_ mh fn set os = do
lvish.cabal view
@@ -10,11 +10,12 @@ -- PVP summary: +-+------- breaking API changes -- | | +----- non-breaking API additions -- | | | +--- code changes with no API change-version: 1.0+version: 1.0.0.2 -- Changelog:--- 0.2 -- switch SLMap over to O(1) freeze-+-- 0.2 -- switch SLMap over to O(1) freeze+-- 1.0 -- initial public release+-- 1.0.0.2 -- minor docs polishing synopsis: Parallel scheduler, LVar data structures, and infrastructure to build more. @@ -24,10 +25,14 @@ . As a starting point, look at "Control.LVish", as well as one of these papers: .- * /LVars: lattice-based data structures for deterministic parallelism/ (<http://dl.acm.org/citation.cfm?id=2502326>).+ * FHPC 2013: /LVars: lattice-based data structures for deterministic parallelism/ (<http://dl.acm.org/citation.cfm?id=2502326>). .- * /Freeze after handling: quasi-deterministic programming with LVars/ (<http://www.cs.indiana.edu/~lkuper/papers/2013-lvish-draft.pdf>). + * POPL 2014: /Freeze after writing: quasi-deterministic programming with LVars/ (<http://www.cs.indiana.edu/~lkuper/papers/2013-lvish-draft.pdf>).+ . + If the haddocks are not building, here is a mirror:+ <http://www.cs.indiana.edu/~rrnewton/haddock/lvish/>+ license: BSD3 license-file: LICENSE author: Aaron Turon, Lindsey Kuper, Ryan Newton@@ -62,6 +67,12 @@ -------------------------------------------------------------------------------- library+ Source-repository head+ type: git+ location: https://github.com/iu-parfunc/lvars+ subdir: haskell/lvish+ tag: release-lvish-1.0.0.2+ -- Modules exported by the library. exposed-modules: ------------- End user modules ------------@@ -105,13 +116,14 @@ build-depends: base ==4.6.*, deepseq ==1.3.*, containers ==0.5.*, lattices ==1.2.*, split ==0.2.*, bytestring ==0.10.*, time ==1.4.*, rdtsc ==1.3.*, vector ==0.10.*, parallel ==3.2.*, async ==2.0.*,- atomic-primops, hashable, transformers, random, chaselev-deque, bits-atomic, missing-foreign,+ atomic-primops, hashable, transformers, random, + chaselev-deque, + bits-atomic, missing-foreign, ghc-prim -- TEMP: build-depends: HUnit, test-framework, test-framework-hunit, test-framework-th, bytestring-mmap- -- Actually -threaded won't do anything for a library, this is just a reminder:- ghc-options: -O2 -threaded -rtsopts+ ghc-options: -O2 -rtsopts if flag(abstract-par) cpp-options: -DUSE_ABSTRACT_PAR build-depends: abstract-par >=0.4