-- 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.2.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 :: (Foldable 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 :: (Foldable f, Eq b) => (Int -> b) -> (b -> a -> b) -> b -> f a -> b
-- | specFoldr1 is to foldr1' as specFoldr is to
-- foldr'
specFoldr1 :: (Foldable f, Eq a) => (Int -> a) -> (a -> a -> a) -> f a -> a
-- | specFoldl1 is to foldl1' as specFoldl is to
-- foldl'
specFoldl1 :: (Foldable f, Eq a) => (Int -> a) -> (a -> a -> a) -> f a -> a
-- | Given a valid estimator g, specFoldrN n g f z
-- xs yields the same answer as foldr f z xs.
--
-- g m should supply an estimate of the value returned from
-- folding over the last m - n elements of the container.
specFoldrN :: (Foldable f, Eq b) => Int -> (Int -> b) -> (a -> b -> b) -> b -> f a -> b
-- | Given a valid estimator g, specFoldlN n g f z
-- xs yields the same answer as foldl f z xs.
--
-- g m should supply an estimate of the value returned from
-- folding over the first m - n elements of the container.
specFoldlN :: (Foldable f, Eq b) => Int -> (Int -> b) -> (b -> a -> b) -> b -> f a -> b
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