Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 83 lines (50 sloc) 3.219 kb
b66020e Edward Kmett README
authored
1 speculation
2 ===========
3
806cb96 Edward Kmett README
authored
4 A framework for safe, programmable, speculative parallelism, loosely based on:
b66020e Edward Kmett README
authored
5
806cb96 Edward Kmett README
authored
6 * Prakash Prabhu, G. Ramalingam, and Kapil Vaswani, "*Safe Programmable Speculative Parallelism*",
7 In the proceedings of Programming Language Design and Implementation (PLDI) Vol 45, Issue 6 (June 2010) pp 50-61.
8 <http://research.microsoft.com/pubs/118795/pldi026-vaswani.pdf>
b66020e Edward Kmett README
authored
9
d4c1dba Edward Kmett version 0.6.0 - STM based comparison operators
authored
10 This package provides speculative function application and speculative folds. Speculative `STM` transactions take the place
806cb96 Edward Kmett README
authored
11 of the transactional rollback machinery from the paper.
e44dff2 Edward Kmett markdown cleanup
authored
12
d4c1dba Edward Kmett version 0.6.0 - STM based comparison operators
authored
13 You can download it using `cabal install speculation`, if you have the Haskell Platform installed.
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
14
c482c60 Edward Kmett documentation cleanup
authored
15 Speculative Function Application (Control.Concurrent.Speculation)
16 -----------------------------------------------------------------
b66020e Edward Kmett README
authored
17
135d6c3 Edward Kmett Preliminary Codensity STM
authored
18 Various speculative function application combinators are provided. Two fairly canonical samples are described here.
19
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
20 #### spec
b66020e Edward Kmett README
authored
21
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
22 spec :: Eq a => a -> (a -> b) -> a -> b
b66020e Edward Kmett README
authored
23
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
24 `spec g f a` evaluates `f g` while forcing `a`, if `g == a` then `f g` is returned. Otherwise `f a` is evaluated.
b66020e Edward Kmett README
authored
25
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
26 Furthermore, if the argument has already been evaluated, we avoid sparking the parallel computation at all.
b66020e Edward Kmett README
authored
27
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
28 If `g` is a good guess at the value of `a`, this is one way to induce parallelism in an otherwise sequential task.
b66020e Edward Kmett README
authored
29
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
30 However, if `g` isn\'t available more cheaply than `a`, then this saves no work, and if `g` is wrong, you risk evaluating the function twice.
31 spec a f a = f $! a
7b5ecec Edward Kmett 1.3 release candidate
authored
32
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
33 The best-case timeline looks like:
34 [---- f g ----]
35 [----- a -----]
36 [-- spec g f a --]
b66020e Edward Kmett README
authored
37
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
38 The worst-case timeline looks like:
39 [---- f g ----]
40 [----- a -----]
41 [---- f a ----]
42 [------- spec g f a -----------]
7b5ecec Edward Kmett 1.3 release candidate
authored
43
3d12f57 Edward Kmett markdown cleanup
authored
44 Compare these to the timeline of `f $! a`:
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
45 [---- a -----]
46 [---- f a ----]
b66020e Edward Kmett README
authored
47
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
48 #### specSTM
b66020e Edward Kmett README
authored
49
d4c1dba Edward Kmett version 0.6.0 - STM based comparison operators
authored
50 `specSTM` provides a similar compressed timeline for speculated `STM` actions, but also rolls back side-effects.
b66020e Edward Kmett README
authored
51
c482c60 Edward Kmett documentation cleanup
authored
52 Speculative Folds (Data.Foldable.Speculation)
53 ---------------------------------------------
b66020e Edward Kmett README
authored
54
d4c1dba Edward Kmett version 0.6.0 - STM based comparison operators
authored
55 A speculative version of the combinators from `Data.Foldable` is provided as `Data.Foldable.Speculation`.
7b5ecec Edward Kmett 1.3 release candidate
authored
56
135d6c3 Edward Kmett Preliminary Codensity STM
authored
57 Each combinator therein takes an extra argument that is used to speculate on the value of the list.
b66020e Edward Kmett README
authored
58
135d6c3 Edward Kmett Preliminary Codensity STM
authored
59 #### foldr
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
60
135d6c3 Edward Kmett Preliminary Codensity STM
authored
61 foldr :: (Foldable f, Eq b) => (Int -> b) -> (a -> b -> b) -> b -> f a -> b
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
62
d4c1dba Edward Kmett version 0.6.0 - STM based comparison operators
authored
63 Given a valid estimator `g`, `foldr g f z xs` yields the same answer as `Foldable.foldr' f z xs`.
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
64
153b4c1 Edward Kmett markdown cleanup
authored
65 `g n` should supply an estimate of the value returned from folding over the **last** `n` elements of the container.
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
66
d4c1dba Edward Kmett version 0.6.0 - STM based comparison operators
authored
67 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.
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
68
135d6c3 Edward Kmett Preliminary Codensity STM
authored
69 #### foldl
70
71 foldl :: (Foldable f, Eq b) => (Int -> b) -> (b -> a -> b) -> b -> f a -> b
72
153b4c1 Edward Kmett markdown cleanup
authored
73 `foldl` works similarly to `Foldable.foldl'`, except that `g n` should provide an estimate for the **first** `n` elements.
135d6c3 Edward Kmett Preliminary Codensity STM
authored
74
e44dff2 Edward Kmett markdown cleanup
authored
75 Contact Information
135d6c3 Edward Kmett Preliminary Codensity STM
authored
76 -------------------
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
77
c482c60 Edward Kmett documentation cleanup
authored
78 Contributions and bug reports are welcome!
79
80 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>.
4378fc4 Edward Kmett added specOn and specBy, and separated out Data.Foldable.Speculation
authored
81
135d6c3 Edward Kmett Preliminary Codensity STM
authored
82 -Edward Kmett
Something went wrong with that request. Please try again.