-- 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
-- http://research.microsoft.com/pubs/118795/pldi026-vaswani.pdf
--
-- spec g f a evaluates f g while forcing
-- a, if g == a then f g is returned.
-- Otherwise f a is evaluated.
--
-- Furthermore, if the argument has already been evaluated, we avoid
-- sparking the parallel computation 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.
--
--
-- spec a f a = f $! a
--
--
-- The best-case timeline looks like:
--
--
-- [---- f g ----]
-- [----- a -----]
-- [-- spec g f a --]
--
--
-- The worst-case timeline looks like:
--
--
-- [---- f g ----]
-- [----- a -----]
-- [---- f a ----]
-- [------- spec g f a -----------]
--
--
-- Compare these to the timeline of f $! a:
--
--
-- [---- a -----]
-- [---- f a ----]
--
--
-- specSTM provides a similar time table for STM actions, but also
-- rolls back side-effects.
--
-- Changes in 0.1.0:
--
--
-- - Added Control.Concurrent.STM.Speculation with
-- specSTM, and specSTM'
--
--
-- Changes in 0.0.2:
--
--
--
-- Changes in 0.0.1:
--
--
@package speculation
@version 0.1.0
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.
--
-- Furthermore, if the argument has already been evaluated, we avoid
-- sparking the parallel computation 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.
--
--
-- spec a f a = f $! a
--
--
-- The best-case timeline looks like:
--
--
-- [---- f g ----]
-- [----- a -----]
-- [-- spec g f a --]
--
--
-- The worst-case timeline looks like:
--
--
-- [---- f g ----]
-- [----- a -----]
-- [---- f a ----]
-- [------- spec g f a -----------]
--
--
-- Compare these to the timeline of f $! a:
--
--
-- [---- a -----]
-- [---- 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
-- | Returns a guess as to whether or not a value has been evaluated. This
-- is an impure function that relies on GHC internals and will return
-- false negatives, but (hopefully) no false positives.
evaluated :: a -> Bool
-- | Given a valid estimator g, specFoldr 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.
--
--
-- specFoldr = specFoldrN 0
--
specFoldr :: (Speculative f, Eq b) => (Int -> b) -> (a -> b -> b) -> b -> f a -> b
-- | Given a valid estimator g, specFoldl 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.
--
--
-- specFoldl = specFoldlN 0
--
specFoldl :: (Speculative f, Eq b) => (Int -> b) -> (b -> a -> b) -> b -> f a -> b
class (Foldable f) => Speculative f
specFoldr1 :: (Speculative f, Eq a) => (Int -> a) -> (a -> a -> a) -> f a -> a
specFoldrN :: (Speculative f, Eq b) => Int -> (Int -> b) -> (a -> b -> b) -> b -> f a -> b
specFoldl1 :: (Speculative f, Eq a) => (Int -> a) -> (a -> a -> a) -> f a -> a
specFoldlN :: (Speculative f, Eq b) => Int -> (Int -> b) -> (b -> a -> b) -> b -> f a -> b
-- | Transform an arbitrary Foldable into a Speculative
-- container
newtype WrappedFoldable f a
WrappedFoldable :: f a -> WrappedFoldable f a
getWrappedFoldable :: WrappedFoldable f a -> f a
-- | Provides a Speculative container that doesn't actually
-- speculate.
newtype WithoutSpeculation f a
WithoutSpeculation :: f a -> WithoutSpeculation f a
getWithoutSpeculation :: WithoutSpeculation f a -> f a
instance (Functor f) => Functor (WithoutSpeculation f)
instance (Foldable f) => Foldable (WithoutSpeculation f)
instance (Traversable f) => Traversable (WithoutSpeculation f)
instance (Functor f) => Functor (WrappedFoldable f)
instance (Foldable f) => Foldable (WrappedFoldable f)
instance (Traversable f) => Traversable (WrappedFoldable f)
instance (Typeable1 f, Data (f a), Data a) => Data (WithoutSpeculation f a)
instance (Foldable f) => Speculative (WithoutSpeculation f)
instance (Typeable1 f) => Typeable1 (WithoutSpeculation f)
instance (Typeable1 f, Data (f a), Data a) => Data (WrappedFoldable f a)
instance (Typeable1 f) => Typeable1 (WrappedFoldable f)
instance (Foldable f) => Speculative (WrappedFoldable f)
instance Speculative Seq
instance Speculative IntMap
instance Speculative (Map a)
instance Speculative Set
instance (Ix i) => Speculative (Array i)
instance Speculative Maybe
instance Speculative []
module Control.Concurrent.STM.Speculation
-- | specSTM g f a evaluates f g while forcing
-- a, if g == a then f g is returned.
-- Otherwise the side-effects of the current STM transaction are rolled
-- back and f a is evaluated.
--
-- 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.
--
--
-- specSTM a f a = f $! a
--
--
-- The best-case timeline looks like:
--
--
-- [------ f g ------]
-- [------- a -------]
-- [--- specSTM g f a ---]
--
--
-- The worst-case timeline looks like:
--
--
-- [------ f g ------]
-- [------- a -------]
-- [-- rollback --]
-- [------ f a ------]
-- [------------------ spec g f a ------------------------]
--
--
-- Compare these to the timeline of f $! a:
--
--
-- [------- a -------]
-- [------ f a ------]
--
specSTM :: (Eq a) => a -> (a -> STM b) -> a -> STM b
-- | Unlike specSTM, specSTM' doesn't check if the
-- argument has already been evaluated.
specSTM' :: (Eq a) => a -> (a -> STM b) -> a -> STM b
instance Typeable Speculation
instance Show Speculation
instance Eq Speculation
instance Exception Speculation