-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A framework for safe, programmable, speculative parallelism
--
-- A framework for safe, programmable, speculative parallelism, loosely
-- based on:
--
--
--
-- This package provides speculative function application and speculative
-- folds. Speculative STM transactions take the place of the
-- transactional rollback machinery from the paper.
--
-- For example:
--
-- spec g f a evaluates f g while forcing
-- a, if g == a then f g is returned,
-- otherwise f a is evaluated and returned. Furthermore, if the
-- argument has already been evaluated, we skip the f g
-- computation entirely. If a good guess at the value of a is
-- available, this is one way to induce parallelism in an otherwise
-- sequential task. However, if the guess isn't available more cheaply
-- than the actual answer, then this saves no work and if the guess is
-- wrong, you risk evaluating the function twice. Under high load, since
-- 'f g' is computed via the spark queue, the speculation will be skipped
-- and you will obtain the same answer as 'f $! a'.
--
-- The best-case timeline looks like:
--
--
-- foreground: [----- a -----]
-- foreground: [-] (check g == a)
-- spark: [----- f g -----]
-- overall: [--- spec g f a ---]
--
--
-- The worst-case timeline looks like:
--
--
-- foreground: [----- a -----]
-- foreground: [-] (check g == a)
-- foreground: [---- f a ----]
-- spark: [----- f g -----]
-- overall: [-------- spec g f a ---------]
--
--
-- Note that, if f g takes longer than a to compute, in the HEAD
-- release of GHC, f g will be collected and killed during
-- garbage collection.
--
--
-- foreground: [----- a -----]
-- foreground: [-] (check g == a)
-- foreground: [---- f a ----]
-- spark: [---- f g ----###### (#'s mark when this spark is collectable)
-- overall: [--------- spec g f a --------]
--
--
-- Under high load:
--
--
-- foreground: [----- a -----]
-- foreground: [-] (check g == a)
-- foreground: [---- f a ----]
-- overall: [-------- spec g f a ---------]
--
--
-- Compare these to the timeline of f $! a:
--
--
-- foreground: [----- a -----]
-- foreground: [---- f a ----]
-- orverall: [---------- f $! a ---------]
--
--
-- specSTM provides a similar time table for STM actions, but also
-- rolls back side-effects. The one unfortunate operational distinction
-- is that it is forced to compute a in the background thread and
-- therefore degrades slightly less gracefully under load, although we
-- mitigate this effect by only enqueuing if the number of sparks for the
-- current capability is lower than the total number of capabilities, to
-- try to avoid wasting time when all computational resources are in use.
@package speculation
@version 1.4.1
module Control.Concurrent.Speculation
-- | spec g f a evaluates f g while forcing
-- a, if g == a then f g is returned,
-- otherwise f a is evaluated and returned. Furthermore, if the
-- argument has already been evaluated or are not running on the threaded
-- runtime, we skip the f g computation entirely. If a good
-- guess at the value of a is available, this is one way to
-- induce parallelism in an otherwise sequential task. However, if the
-- guess isn't available more cheaply than the actual answer, then this
-- saves no work and if the guess is wrong, you risk evaluating the
-- function twice. Under high load or in a runtime with access to a
-- single capability, since 'f g' is computed via the spark queue, the
-- speculation will be skipped and you will obtain the same answer as 'f
-- $! a'.
--
-- The best-case timeline looks like:
--
--
-- foreground: [----- a -----]
-- foreground: [-] (check g == a)
-- spark: [----- f g -----]
-- overall: [--- spec g f a ---]
--
--
-- The worst-case timeline looks like:
--
--
-- foreground: [----- a -----]
-- foreground: [-] (check g == a)
-- foreground: [---- f a ----]
-- spark: [----- f g -----]
-- overall: [-------- spec g f a ---------]
--
--
-- Note that, if f g takes longer than a to compute, in the HEAD
-- release of GHC, f g will be collected and killed during
-- garbage collection.
--
--
-- foreground: [----- a -----]
-- foreground: [-] (check g == a)
-- foreground: [---- f a ----]
-- spark: [---- f g ----###### (#'s mark when this spark is collectable)
-- overall: [--------- spec g f a --------]
--
--
-- Under high load:
--
--
-- foreground: [----- a -----]
-- foreground: [-] (check g == a)
-- foreground: [---- f a ----]
-- overall: [-------- spec g f a ---------]
--
--
-- Compare these to the timeline of f $! a:
--
--
-- foreground: [----- a -----]
-- foreground: [---- f a ----]
-- orverall: [---------- f $! a ---------]
--
spec :: Eq a => a -> (a -> b) -> a -> b
-- | Unlike spec, this version does not check to see if the argument
-- has already been evaluated. This can save a small amount of work when
-- you know the argument will always require computation.
spec' :: Eq a => a -> (a -> b) -> a -> b
-- | spec with a user defined comparison function
specBy :: (a -> a -> Bool) -> a -> (a -> b) -> a -> b
-- | spec' with a user defined comparison function
specBy' :: (a -> a -> Bool) -> a -> (a -> b) -> a -> b
-- | spec comparing by projection onto another type
specOn :: Eq c => (a -> c) -> a -> (a -> b) -> a -> b
-- | spec' comparing by projection onto another type
specOn' :: Eq c => (a -> c) -> a -> (a -> b) -> a -> b
-- | specSTM g f a evaluates fg = do g' <- g; f
-- g', while forcing a, then if g' == a then
-- fg is returned. Otherwise the side-effects of fg are
-- rolled back and f a is evaluated. g is allowed to be
-- a monadic action, so that we can kickstart the computation of
-- a earlier. Under high load, or when we are not using the
-- parallel runtime, the speculation is avoided, to enable this to more
-- closely approximate the runtime profile of spec.
--
-- If the argument a is already evaluated, we don't bother to
-- perform f g at all.
--
-- If a good guess at the value of a is available, this is one
-- way to induce parallelism in an otherwise sequential task.
--
-- However, if the guess isn't available more cheaply than the actual
-- answer then this saves no work, and if the guess is wrong, you risk
-- evaluating the function twice.
--
-- The best-case timeline looks like:
--
--
-- foreground: [--- g >>= f ---]
-- spark: [------- a -------]
-- foreground: [-] (compare g' == a)
-- overall: [---- specSTM g f a ----]
--
--
-- The worst-case timeline looks like:
--
--
-- foreground: [---- g >>= f ----]
-- spark: [------- a -------]
-- foreground: [-] (check if g' == a)
-- foreground: [--] (rollback)
-- foreground: [------ f a ------]
-- overall: [------------ specSTM g f a ----------------]
--
--
-- Under high load, specSTM degrades less gracefully than
-- spec:
--
--
-- foreground: [---- g >>= f ----]
-- spark: [------- a -------]
-- foreground: [-] (check if g' == a)
-- foreground: [--] (rollback)
-- foreground: [------ f a ------]
-- overall: [--------------------specSTM g f a ------------------------]
--
--
-- Compare these to the timeline of f $! a:
--
--
-- foreground: [------- a -------]
-- foreground: [------ f a ------]
--
specSTM :: Eq a => STM a -> (a -> STM b) -> a -> STM b
-- | Unlike specSTM, specSTM' doesn't check if the argument
-- has already been evaluated.
specSTM' :: Eq a => STM a -> (a -> STM b) -> a -> STM b
-- |
-- specBySTM . on (==)
--
specOnSTM :: Eq c => (a -> STM c) -> STM a -> (a -> STM b) -> a -> STM b
-- |
-- specBySTM' . on (==)
--
specOnSTM' :: Eq c => (a -> STM c) -> STM a -> (a -> STM b) -> a -> STM b
-- | specSTM using a user defined comparison function
specBySTM :: (a -> a -> STM Bool) -> STM a -> (a -> STM b) -> a -> STM b
-- | specSTM' using a user defined comparison function
specBySTM' :: (a -> a -> STM Bool) -> STM a -> (a -> STM b) -> a -> STM b
-- | Versions of the combinators from the speculation package with
-- the signature rearranged to enable them to be used directly as actions
-- in the Cont and ContT monads or any other
-- Codensity-shaped monad.
module Control.Concurrent.Speculation.Class
class MonadSpec m
specByM :: MonadSpec m => (a -> a -> Bool) -> a -> a -> m a
specByM' :: MonadSpec m => (a -> a -> Bool) -> a -> a -> m a
-- | When a is unevaluated, spec g a evaluates the current
-- continuation with g while testing if g ==
-- a, if they differ, it re-evalutes the continuation with
-- a. If a was already evaluated, the continuation is
-- just directly applied to a instead.
specM :: (MonadSpec m, Eq a) => a -> a -> m a
-- | As per spec, without the check for whether or not the second
-- argument is already evaluated.
specM' :: (MonadSpec m, Eq a) => a -> a -> m a
-- | spec' with a user supplied comparison function
specOnM :: (MonadSpec m, Eq c) => (a -> c) -> a -> a -> m a
-- | spec' with a user supplied comparison function
specOnM' :: (MonadSpec m, Eq c) => (a -> c) -> a -> a -> m a
instance Monad m => MonadSpec (ContT r m)
module Control.Concurrent.Speculation.Foldable
-- | Given a valid estimator g, fold g f xs yields
-- the same answer as fold f xs.
--
-- g n should supply an estimate of the value of the monoidal
-- summation over the last n elements of the container.
--
-- If g n is accurate a reasonable percentage of the time and
-- faster to compute than the fold, then this can provide increased
-- opportunities for parallelism.
fold :: (Foldable f, Monoid m, Eq m) => (Int -> m) -> f m -> m
-- | fold using specBy
foldBy :: (Foldable f, Monoid m) => (m -> m -> Bool) -> (Int -> m) -> f m -> m
-- | Given a valid estimator g, foldMap g f xs
-- yields the same answer as foldMap f xs.
--
-- g n should supply an estimate of the value of the monoidal
-- summation over the last n elements of the container.
--
-- If g n is accurate a reasonable percentage of the time and
-- faster to compute than the fold, then this can provide increased
-- opportunities for parallelism.
foldMap :: (Foldable f, Monoid m, Eq m) => (Int -> m) -> (a -> m) -> f a -> m
-- | foldMap using specBy
foldMapBy :: (Foldable f, Monoid m) => (m -> m -> Bool) -> (Int -> m) -> (a -> m) -> f a -> m
foldr :: (Foldable f, Eq b) => (Int -> b) -> (a -> b -> b) -> b -> f a -> b
-- | Given a valid estimator g, foldr g f z xs
-- yields the same answer as foldr' f z xs.
--
-- g n should supply an estimate of the value returned from
-- folding over the last n elements of the container.
--
-- If g n is accurate a reasonable percentage of the time and
-- faster to compute than the fold, then this can provide increased
-- opportunities for parallelism.
foldrBy :: Foldable f => (b -> b -> Bool) -> (Int -> b) -> (a -> b -> b) -> b -> f a -> b
-- | Given a valid estimator g, foldl g f z xs
-- yields the same answer as foldl' f z xs.
--
-- g n should supply an estimate of the value returned from
-- folding over the first n elements of the container.
--
-- If g n is accurate a reasonable percentage of the time and
-- faster to compute than the fold, then this can provide increased
-- opportunities for parallelism.
foldl :: (Foldable f, Eq b) => (Int -> b) -> (b -> a -> b) -> b -> f a -> b
foldlBy :: Foldable f => (b -> b -> Bool) -> (Int -> b) -> (b -> a -> b) -> b -> f a -> b
foldr1 :: (Foldable f, Eq a) => (Int -> a) -> (a -> a -> a) -> f a -> a
foldr1By :: Foldable f => (a -> a -> Bool) -> (Int -> a) -> (a -> a -> a) -> f a -> a
foldl1 :: (Foldable f, Eq a) => (Int -> a) -> (a -> a -> a) -> f a -> a
foldl1By :: Foldable f => (a -> a -> Bool) -> (Int -> a) -> (a -> a -> a) -> f a -> a
foldrM :: (Foldable f, Monad m, Eq (m b)) => (Int -> m b) -> (a -> b -> m b) -> m b -> f a -> m b
foldrByM :: (Foldable f, Monad m) => (m b -> m b -> Bool) -> (Int -> m b) -> (a -> b -> m b) -> m b -> f a -> m b
foldlM :: (Foldable f, Monad m, Eq (m b)) => (Int -> m b) -> (b -> a -> m b) -> m b -> f a -> m b
foldlByM :: (Foldable f, Monad m) => (m b -> m b -> Bool) -> (Int -> m b) -> (b -> a -> m b) -> m b -> f a -> m b
foldrSTM :: (Foldable f, Eq b) => (Int -> STM b) -> (a -> b -> STM b) -> STM b -> f a -> STM b
foldrBySTM :: Foldable f => (b -> b -> STM Bool) -> (Int -> STM b) -> (a -> b -> STM b) -> STM b -> f a -> STM b
foldlSTM :: (Foldable f, Eq a) => (Int -> STM a) -> (a -> b -> STM a) -> STM a -> f b -> STM a
foldlBySTM :: Foldable f => (a -> a -> STM Bool) -> (Int -> STM a) -> (a -> b -> STM a) -> STM a -> f b -> STM a
-- | Map each element of a structure to an action, evaluate these actions
-- from left to right and ignore the results.
traverse_ :: (Foldable t, Applicative f, Eq (f ())) => (Int -> f c) -> (a -> f b) -> t a -> f ()
traverseBy_ :: (Foldable t, Applicative f) => (f () -> f () -> Bool) -> (Int -> f c) -> (a -> f b) -> t a -> f ()
-- | for_ is traverse_ with its arguments flipped.
for_ :: (Foldable t, Applicative f, Eq (f ())) => (Int -> f c) -> t a -> (a -> f b) -> f ()
forBy_ :: (Foldable t, Applicative f) => (f () -> f () -> Bool) -> (Int -> f c) -> t a -> (a -> f b) -> f ()
sequenceA_ :: (Foldable t, Applicative f, Eq (f ())) => (Int -> f b) -> t (f a) -> f ()
sequenceByA_ :: (Foldable t, Applicative f, Eq (f ())) => (f () -> f () -> Bool) -> (Int -> f b) -> t (f a) -> f ()
asum :: (Foldable t, Alternative f, Eq (f a)) => (Int -> f a) -> t (f a) -> f a
asumBy :: (Foldable t, Alternative f) => (f a -> f a -> Bool) -> (Int -> f a) -> t (f a) -> f a
-- | Map each element of the structure to a monadic action, evaluating
-- these actions from left to right and ignoring the results.
mapM_ :: (Foldable t, Monad m, Eq (m ())) => (Int -> m c) -> (a -> m b) -> t a -> m ()
mapByM_ :: (Foldable t, Monad m) => (m () -> m () -> Bool) -> (Int -> m c) -> (a -> m b) -> t a -> m ()
-- | for_ is mapM_ with its arguments flipped.
forM_ :: (Foldable t, Monad m, Eq (m ())) => (Int -> m c) -> t a -> (a -> m b) -> m ()
forByM_ :: (Foldable t, Monad m) => (m () -> m () -> Bool) -> (Int -> m c) -> t a -> (a -> m b) -> m ()
sequence_ :: (Foldable t, Monad m, Eq (m ())) => (Int -> m b) -> t (m a) -> m ()
sequenceBy_ :: (Foldable t, Monad m) => (m () -> m () -> Bool) -> (Int -> m b) -> t (m a) -> m ()
msum :: (Foldable t, MonadPlus m, Eq (m a)) => (Int -> m a) -> t (m a) -> m a
msumBy :: (Foldable t, MonadPlus m) => (m a -> m a -> Bool) -> (Int -> m a) -> t (m a) -> m a
-- | Map each element of the structure to a monadic action, evaluating
-- these actions from left to right and ignoring the results, while
-- transactional side-effects from mis-speculated actions are rolled
-- back.
mapSTM_ :: Foldable t => STM Bool -> (Int -> STM c) -> (a -> STM b) -> t a -> STM ()
-- | for_ is mapM_ with its arguments flipped.
forSTM_ :: Foldable t => STM Bool -> (Int -> STM c) -> t a -> (a -> STM b) -> STM ()
sequenceSTM_ :: Foldable t => STM Bool -> (Int -> STM a) -> t (STM b) -> STM ()
toList :: (Foldable t, Eq a) => (Int -> [a]) -> t a -> [a]
toListBy :: Foldable t => ([a] -> [a] -> Bool) -> (Int -> [a]) -> t a -> [a]
concat :: (Foldable t, Eq a) => (Int -> [a]) -> t [a] -> [a]
concatBy :: Foldable t => ([a] -> [a] -> Bool) -> (Int -> [a]) -> t [a] -> [a]
concatMap :: (Foldable t, Eq b) => (Int -> [b]) -> (a -> [b]) -> t a -> [b]
concatMapBy :: Foldable t => ([b] -> [b] -> Bool) -> (Int -> [b]) -> (a -> [b]) -> t a -> [b]
all :: Foldable t => (Int -> Bool) -> (a -> Bool) -> t a -> Bool
any :: Foldable t => (Int -> Bool) -> (a -> Bool) -> t a -> Bool
and :: Foldable t => (Int -> Bool) -> t Bool -> Bool
or :: Foldable t => (Int -> Bool) -> t Bool -> Bool
sum :: (Foldable t, Eq a, Num a) => (Int -> a) -> t a -> a
sumBy :: (Foldable t, Num a) => (a -> a -> Bool) -> (Int -> a) -> t a -> a
product :: (Foldable t, Eq a, Num a) => (Int -> a) -> t a -> a
productBy :: (Foldable t, Num a) => (a -> a -> Bool) -> (Int -> a) -> t a -> a
maximum :: (Foldable t, Ord a) => (Int -> a) -> t a -> a
maximumBy :: Foldable t => (a -> a -> Ordering) -> (Int -> a) -> t a -> a
minimum :: (Foldable t, Ord a) => (Int -> a) -> t a -> a
minimumBy :: Foldable t => (a -> a -> Ordering) -> (Int -> a) -> t a -> a
elem :: (Foldable t, Eq a) => (Int -> Bool) -> a -> t a -> Bool
elemBy :: Foldable t => (a -> a -> Bool) -> (Int -> Bool) -> a -> t a -> Bool
notElem :: (Foldable t, Eq a) => (Int -> Bool) -> a -> t a -> Bool
notElemBy :: Foldable t => (a -> a -> Bool) -> (Int -> Bool) -> a -> t a -> Bool
find :: (Foldable t, Eq a) => (Int -> Maybe a) -> (a -> Bool) -> t a -> Maybe a
findBy :: Foldable t => (Maybe a -> Maybe a -> Bool) -> (Int -> Maybe a) -> (a -> Bool) -> t a -> Maybe a
module Control.Concurrent.Speculation.Traversable
traverse :: (Traversable t, Applicative f, Eq a) => (Int -> a) -> (a -> f b) -> t a -> f (t b)
traverseBy :: (Traversable t, Applicative f) => (a -> a -> Bool) -> (Int -> a) -> (a -> f b) -> t a -> f (t b)
for :: (Traversable t, Applicative f, Eq a) => (Int -> a) -> t a -> (a -> f b) -> f (t b)
forBy :: (Traversable t, Applicative f) => (a -> a -> Bool) -> (Int -> a) -> t a -> (a -> f b) -> f (t b)
sequenceA :: (Traversable t, Applicative f, Eq (f a)) => (Int -> f a) -> t (f a) -> f (t a)
sequenceByA :: (Traversable t, Applicative f) => (f a -> f a -> Bool) -> (Int -> f a) -> t (f a) -> f (t a)
mapM :: (Traversable t, Monad m, Eq a) => (Int -> a) -> (a -> m b) -> t a -> m (t b)
mapByM :: (Traversable t, Monad m) => (a -> a -> Bool) -> (Int -> a) -> (a -> m b) -> t a -> m (t b)
sequence :: (Traversable t, Monad m, Eq (m a)) => (Int -> m a) -> t (m a) -> m (t a)
sequenceBy :: (Traversable t, Monad m) => (m a -> m a -> Bool) -> (Int -> m a) -> t (m a) -> m (t a)
forM :: (Traversable t, Monad m, Eq a) => (Int -> a) -> t a -> (a -> m b) -> m (t b)
forByM :: (Traversable t, Monad m) => (a -> a -> Bool) -> (Int -> a) -> t a -> (a -> m b) -> m (t b)
mapSTM :: (Traversable t, Eq a) => (Int -> STM a) -> (a -> STM b) -> t a -> STM (t b)
mapBySTM :: Traversable t => (a -> a -> STM Bool) -> (Int -> STM a) -> (a -> STM b) -> t a -> STM (t b)
forSTM :: (Traversable t, Eq a) => (Int -> STM a) -> t a -> (a -> STM b) -> STM (t b)
forBySTM :: Traversable t => (a -> a -> STM Bool) -> (Int -> STM a) -> t a -> (a -> STM b) -> STM (t b)
mapAccumL :: (Traversable t, Eq a) => (Int -> a) -> (a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumLBy :: Traversable t => (a -> a -> Bool) -> (Int -> a) -> (a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumR :: (Traversable t, Eq a) => (Int -> a) -> (a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumRBy :: Traversable t => (a -> a -> Bool) -> (Int -> a) -> (a -> b -> (a, c)) -> a -> t b -> (a, t c)
instance Applicative f => Applicative (AccT f)
instance Functor f => Functor (AccT f)
instance Applicative (IntAccumR s)
instance Functor (IntAccumR s)
instance Applicative (IntAccumL s)
instance Functor (IntAccumL s)
module Control.Concurrent.Speculation.List
-- | Given a valid estimator g, scan g xs converts
-- xs into a list of the prefix sums.
--
-- g n should supply an estimate of the value of the monoidal
-- summation over the first n elements of the container.
--
-- If g n is accurate a reasonable percentage of the time and
-- faster to compute than the prefix sum, then this can provide increased
-- opportunities for parallelism.
scan :: (Monoid m, Eq m) => (Int -> m) -> [m] -> [m]
-- | scan using specBy
scanBy :: Monoid m => (m -> m -> Bool) -> (Int -> m) -> [m] -> [m]
-- | Given a valid estimator g, scanMap g f xs
-- converts xs into a list of the prefix sums.
--
-- g n should supply an estimate of the value of the monoidal
-- summation over the first n elements of the container.
--
-- If g n is accurate a reasonable percentage of the time and
-- faster to compute than the scan, then this can provide increased
-- opportunities for parallelism.
--
--
-- scan = scanMap id
-- scanMap = scanMapBy (==)
--
scanMap :: (Monoid m, Eq m) => (Int -> m) -> (a -> m) -> [a] -> [m]
scanMapBy :: Monoid m => (m -> m -> Bool) -> (Int -> m) -> (a -> m) -> [a] -> [m]
-- | Given a valid estimator g, scanr g f z xs
-- yields the same answer as scanr' f z xs.
--
-- g n should supply an estimate of the value returned from
-- scanning over the last n elements of the container.
--
-- If g n is accurate a reasonable percentage of the time and
-- faster to compute than the scan, then this can provide increased
-- opportunities for parallelism.
scanr :: Eq b => (Int -> b) -> (a -> b -> b) -> b -> [a] -> [b]
scanrBy :: (b -> b -> Bool) -> (Int -> b) -> (a -> b -> b) -> b -> [a] -> [b]
scanl :: Eq b => (Int -> b) -> (b -> a -> b) -> b -> [a] -> [b]
scanlBy :: (b -> b -> Bool) -> (Int -> b) -> (b -> a -> b) -> b -> [a] -> [b]
scanr1 :: Eq a => (Int -> a) -> (a -> a -> a) -> [a] -> [a]
scanr1By :: (a -> a -> Bool) -> (Int -> a) -> (a -> a -> a) -> [a] -> [a]
scanl1 :: Eq a => (Int -> a) -> (a -> a -> a) -> [a] -> [a]
scanl1By :: (a -> a -> Bool) -> (Int -> a) -> (a -> a -> a) -> [a] -> [a]