packages feed

speculation 0.5.1 → 0.6.0

raw patch · 4 files changed

+66/−42 lines, 4 files

Files

Control/Concurrent/Speculation.hs view
@@ -15,6 +15,8 @@     , specOnSTM'     , specBySTM     , specBySTM'+    -- * Throw to break out of current speculation+    , SpeculationException     -- * Determining if a closure is evaluated     , unsafeGetTagBits     , unsafeIsEvaluated@@ -23,6 +25,7 @@ import Control.Concurrent.STM import Control.Exception (Exception, throw, fromException) import Control.Parallel (par)+import Control.Monad (liftM2) import Data.Typeable (Typeable) import Data.Function (on) import Data.Bits ((.&.))@@ -133,50 +136,51 @@ -- >                   [------ f a ------]  specSTM :: Eq a => STM a -> (a -> STM b) -> a -> STM b-specSTM = specBySTM (==)+specSTM = specBySTM (returning (==)) {-# INLINE specSTM #-}  -- | Unlike 'specSTM', 'specSTM'' doesn't check if the argument has already been evaluated.  specSTM' :: Eq a => STM a -> (a -> STM b) -> a -> STM b-specSTM' = specBySTM' (==)+specSTM' = specBySTM' (returning (==)) {-# INLINE specSTM' #-}  -- | 'specSTM' using a user defined comparison function-specBySTM :: (a -> a -> Bool) -> STM a -> (a -> STM b) -> a -> STM b+specBySTM :: (a -> a -> STM Bool) -> STM a -> (a -> STM b) -> a -> STM b specBySTM cmp g f a      | unsafeIsEvaluated a = f a      | otherwise   = specBySTM' cmp g f a {-# INLINE specBySTM #-}  -- | 'specSTM'' using a user defined comparison function-specBySTM' :: (a -> a -> Bool) -> STM a -> (a -> STM b) -> a -> STM b+specBySTM' :: (a -> a -> STM Bool) -> STM a -> (a -> STM b) -> a -> STM b specBySTM' cmp g f a = a `par`      let        try = do         g' <- g         result <- f g'-        if cmp g' a+        test <- cmp g' a+        if test           then return result-          else throw Speculation+          else throw SpeculationException     in        try `catchSTM` \e -> case fromException e of-        Just Speculation -> f a -- rerun with alternative input-        _ -> throw e            -- this is a bigger problem+        Just SpeculationException -> f a -- rerun with alternative input+        _ -> throw e                     -- this is a bigger problem {-# INLINE specBySTM' #-}  -- | @'specBySTM' . 'on' (==)@-specOnSTM :: Eq c => (a -> c) -> STM a -> (a -> STM b) -> a -> STM b-specOnSTM = specBySTM . on (==)+specOnSTM :: Eq c => (a -> STM c) -> STM a -> (a -> STM b) -> a -> STM b+specOnSTM = specBySTM . on (liftM2 (==)) {-# INLINE specOnSTM #-}  -- | @'specBySTM'' . 'on' (==)@-specOnSTM' :: Eq c => (a -> c) -> STM a -> (a -> STM b) -> a -> STM b-specOnSTM' = specBySTM' . on (==)+specOnSTM' :: Eq c => (a -> STM c) -> STM a -> (a -> STM b) -> a -> STM b+specOnSTM' = specBySTM' . on (liftM2 (==)) {-# INLINE specOnSTM' #-} -data Speculation = Speculation deriving (Show,Eq,Typeable)-instance Exception Speculation+data SpeculationException = SpeculationException deriving (Show,Eq,Typeable)+instance Exception SpeculationException  -- | Used to inspect tag bits data Box a = Box a@@ -190,3 +194,7 @@ unsafeIsEvaluated :: a -> Bool unsafeIsEvaluated a = unsafeGetTagBits a /= 0 {-# INLINE unsafeIsEvaluated #-}++returning :: Monad m => (a -> b -> c) -> a -> b -> m c+returning f a b = return (f a b)+{-# INLINE returning #-}
Data/Foldable/Speculation.hs view
@@ -58,7 +58,7 @@ import Control.Applicative import Control.Monad hiding (mapM_, msum, forM_, sequence_) --- | Given a valid estimate @g@, @'fold' g f xs@ yields the same answer as @'fold' f xs@.+-- | 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. -- @@ -74,7 +74,7 @@ foldBy cmp g = foldrBy cmp g mappend mempty {-# INLINE foldBy #-} --- | Given a valid estimate @g@, @'foldMap' g f xs@ yields the same answer as @'foldMap' f xs@.+-- | 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. -- @@ -135,10 +135,10 @@ {-# INLINE foldrByM #-}  foldlSTM :: (Foldable f, Eq a) => (Int -> STM a) -> (a -> b -> STM a) -> STM a -> f b -> STM a-foldlSTM = foldlBySTM (==)+foldlSTM = foldlBySTM (returning (==)) {-# INLINE foldlSTM #-} -foldlBySTM :: Foldable f => (a -> a -> Bool) -> (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 foldlBySTM cmp g f mz = liftM extractAcc . Foldable.foldl go (liftM (Acc 0) mz)   where     go mia b = do@@ -149,10 +149,10 @@ {-# INLINE foldlBySTM #-}  foldrSTM :: (Foldable f, Eq b) => (Int -> STM b) -> (a -> b -> STM b) -> STM b -> f a -> STM b-foldrSTM = foldrBySTM (==)+foldrSTM = foldrBySTM (returning (==)) {-# INLINE foldrSTM #-} -foldrBySTM :: Foldable f => (b -> b -> Bool) -> (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 foldrBySTM cmp g f mz = liftM extractAcc . Foldable.foldr go (liftM (Acc 0) mz)   where     go a mib = do@@ -241,8 +241,8 @@ -- | 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 => (Int -> STM c) -> (a -> STM b) -> t a -> STM ()-mapSTM_ g f = foldrSTM (\n -> () <$ g n) (\a _ -> () <$ f a) (return ())+mapSTM_ :: Foldable t => STM Bool -> (Int -> STM c) -> (a -> STM b) -> t a -> STM ()+mapSTM_ chk g f = foldrBySTM (\_ _ -> chk) (\n -> () <$ g n) (\a _ -> () <$ f a) (return ()) {-# INLINE mapSTM_ #-}  mapByM_ :: (Foldable t, Monad m) => (m () -> m () -> Bool) -> (Int -> m c) -> (a -> m b) -> t a -> m ()@@ -255,8 +255,8 @@ {-# INLINE forM_#-}  -- | 'for_' is 'mapM_' with its arguments flipped.-forSTM_ :: Foldable t => (Int -> STM c) -> t a -> (a -> STM b) -> STM ()-forSTM_ g = flip (mapSTM_ g)+forSTM_ :: Foldable t => STM Bool -> (Int -> STM c) -> t a -> (a -> STM b) -> STM ()+forSTM_ chk g = flip (mapSTM_ chk g) {-# INLINE forSTM_#-}  forByM_ :: (Foldable t, Monad m) => (m () -> m () -> Bool) -> (Int -> m c) -> t a -> (a -> m b) -> m ()@@ -275,8 +275,8 @@ sequence_ = sequenceBy_ (==)  {-# INLINE sequence_ #-} -sequenceSTM_:: Foldable t => (Int -> STM a) -> t (STM b) -> STM ()-sequenceSTM_ g = foldrSTM (\n -> () <$ g n) (\a _ -> () <$ a) (return ())+sequenceSTM_:: Foldable t => STM Bool -> (Int -> STM a) -> t (STM b) -> STM ()+sequenceSTM_ chk g = foldrBySTM (\_ _ -> chk) (\n -> () <$ g n) (\a _ -> () <$ a) (return ()) {-# INLINE sequenceSTM_ #-}  sequenceBy_ :: (Foldable t, Monad m) => (m () -> m () -> Bool) -> (Int -> m b) -> t (m a) -> m ()@@ -419,3 +419,6 @@  errorEmptyStructure :: String -> a errorEmptyStructure f = error $ f ++ ": error empty structure"++returning :: Monad m => (a -> b -> c) -> a -> b -> m c+returning f a b = return (f a b)
README.markdown view
@@ -1,16 +1,19 @@ speculation =========== -This package provides speculative evaluation primitives for Haskell, very loosely based on the paper -"Safe Programmable Speculative Parallelism" by Prabhu, Ramalingam, and Vaswani. +A framework for safe, programmable, speculative parallelism, loosely based on: -<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.4622>+*  Prakash Prabhu, G. Ramalingam, and Kapil Vaswani, "*Safe Programmable Speculative Parallelism*",+   In the proceedings of Programming Language Design and Implementation (PLDI) Vol 45, Issue 6 (June 2010) pp 50-61.+   <http://research.microsoft.com/pubs/118795/pldi026-vaswani.pdf> -You can download it using 'cabal install speculation', if you have the Haskell Platform installed.+This package provides speculative function application and speculative folds. Speculative `STM` transactions take the place+of the transactional rollback machinery from the paper. -## Combinators+You can download it using `cabal install speculation`, if you have the Haskell Platform installed. -### Speculative Function Application+Speculative Function Application (Control.Concurrent.Speculation)+-----------------------------------------------------------------  Various speculative function application combinators are provided. Two fairly canonical samples are described here. @@ -44,11 +47,12 @@  #### specSTM -`specSTM` provides a similar compressed timeline for speculated STM actions, but also rolls back side-effects.+`specSTM` provides a similar compressed timeline for speculated `STM` actions, but also rolls back side-effects. -### Speculative Folds+Speculative Folds (Data.Foldable.Speculation)+--------------------------------------------- -A speculative version of Data.Foldable is provided as Data.Foldable.Speculation.+A speculative version of the combinators from `Data.Foldable` is provided as `Data.Foldable.Speculation`.      Each combinator therein takes an extra argument that is used to speculate on the value of the list. @@ -56,11 +60,11 @@      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 `Foldable.foldr' f z xs`.+Given a valid estimator `g`, `foldr g f z xs` yields the same answer as `Foldable.foldr' f z xs`.  `g n` should supply an estimate of the value returned from folding over the **last** `n` elements of the container. -As with `spec`, if the guess `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.+As with `spec`, if the guess `g n` is accurate a reasonable percentage of the time and faster to compute than the ensuing fold, then this can provide increased opportunities for parallelism.  #### foldl @@ -71,6 +75,8 @@ Contact Information ------------------- -I can be reached through the user ekmett on github, as edwardk on irc.freenode.net #haskell channel, or by email to <ekmett@gmail.com>.+Contributions and bug reports are welcome!++I can be reached through the user ekmett on github, as edwardk on irc.freenode.net #haskell channel, or by email at <ekmett@gmail.com>.  -Edward Kmett
speculation.cabal view
@@ -1,5 +1,5 @@ name:           speculation-version:        0.5.1+version:        0.6.0 license:        BSD3 license-file:   LICENSE author:         Edward A. Kmett@@ -9,10 +9,13 @@ category:       Concurrency synopsis:       A framework for safe, programmable, speculative parallelism description:- A framework for safe, programmable, speculative parallelism, loosely based on- <http://research.microsoft.com/pubs/118795/pldi026-vaswani.pdf>+ A framework for safe, programmable, speculative parallelism, loosely based on:  .- This package provides speculative function application and speculative folds. And speculative STM actions take the place+ *  Prakash Prabhu, G. Ramalingam, and Kapil Vaswani, \"/Safe Programmable Speculative Parallelism/\",+    In the proceedings of Programming Language Design and Implementation (PLDI) Vol 45, Issue 6 (June 2010) pp 50-61.+    <http://research.microsoft.com/pubs/118795/pldi026-vaswani.pdf>+ .+ 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:@@ -39,6 +42,10 @@  .  'specSTM' provides a similar time table for STM actions, but also rolls back side-effects.  . + /Changes in 0.6.0:/+ .+ * Upgraded the comparisons used by the STM combinators STM actions, so they can check for other STM side-effects.+ .  /Changes in 0.5.1:/  .   * Exposed unsafeGetTagBits and unsafeIsEvaluated