-
Notifications
You must be signed in to change notification settings - Fork 5
/
speculation.cabal
185 lines (173 loc) · 6.35 KB
/
speculation.cabal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
name: speculation
version: 1.2.0.2
license: BSD3
license-file: LICENSE
author: Edward A. Kmett
maintainer: Edward A. Kmett <ekmett@gmail.com>
stability: experimental
homepage: http://github.com/ekmett/speculation
category: Concurrency
copyright: (c) 2010 Edward A. Kmett
build-type: Custom
cabal-version: >=1.6
tested-with: GHC==6.12.1
synopsis: A framework for safe, programmable, speculative parallelism
description:
A framework for safe, programmable, speculative parallelism, loosely based on:
.
* 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:
.
@'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.
extra-source-files:
README.markdown
CHANGELOG.markdown
ISSUES.markdown
source-repository head
type: git
location: http://github.com/ekmett/speculation.git
branch: master
flag HasNumSparks
description: RTS provides GHC.Conc.numSparks
default: True
manual: False
flag tests
description: Build the tests
default: False
flag benchmarks
description: Build the benchmarks
default: False
flag optimize
description: Enable optimizations for the library and benchmarks
default: True
flag hpc
description: Use HPC for tests
default: True
library
ghc-options: -Wall
if flag(optimize)
ghc-options: -funbox-strict-fields -O2 -fspec-constr -fdicts-cheap
if flag(HasNumSparks)
cpp-options: -DHAS_NUM_SPARKS
build-depends: base >= 4.3 && < 6
else
build-depends: base >= 4 && < 4.3
build-depends:
ghc-prim >= 0.2 && < 0.4,
tag-bits >= 0.1 && < 0.2,
transformers >= 0.2.2.0 && < 0.3,
stm >= 2.1 && < 2.3
exposed-modules:
Data.Speculation
Data.Speculation.Cont
Data.Speculation.Morphism
Data.Speculation.Foldable
Data.Speculation.Traversable
Data.Speculation.List
other-modules:
Data.Speculation.Internal
executable test-speculation
main-is: Test.hs
if !flag(tests)
buildable: False
else
if flag(hpc)
ghc-options: -fhpc
x-hpc: true
ghc-options: -Wall
if flag(HasNumSparks)
cpp-options: -DHAS_NUM_SPARKS
build-depends: base >= 4.3 && < 6
else
build-depends: base >= 4 && < 4.3
build-depends:
ghc-prim >= 0.2 && < 0.4,
tag-bits >= 0.1 && < 0.2,
stm >= 2.1 && < 2.3,
transformers >= 0.2.2.0 && < 0.3,
containers >= 0.3.0 && < 0.5,
test-framework >= 0.2.4 && < 0.3,
test-framework-quickcheck >= 0.2.4 && < 0.3,
test-framework-hunit >= 0.2.4 && < 0.3,
QuickCheck >= 1.2.0.0 && < 1.3,
HUnit >= 1.2.2.1 && < 1.3
other-modules:
Data.Speculation
Data.Speculation.Cont
Data.Speculation.Morphism
Data.Speculation.Foldable
Data.Speculation.Traversable
Data.Speculation.List
Data.Speculation.Internal
executable benchmark-speculation
main-is: Benchmark.hs
if !flag(benchmarks)
buildable: False
else
ghc-options: -Wall -threaded
if flag(optimize)
ghc-options: -O2 -fspec-constr -funbox-strict-fields -fdicts-cheap
if flag(HasNumSparks)
cpp-options: -DHAS_NUM_SPARKS
build-depends: base >= 4.3 && < 6
else
build-depends: base >= 4 && < 4.3
build-depends:
ghc-prim >= 0.2 && < 0.4,
transformers >= 0.2.2.0 && < 0.3,
tag-bits >= 0.1 && < 0.2,
stm >= 2.1 && < 2.3,
containers >= 0.3.0 && < 0.5,
criterion >= 0.5 && < 0.6
other-modules:
Data.Speculation
Data.Speculation.Cont
Data.Speculation.Morphism
Data.Speculation.Foldable
Data.Speculation.Traversable
Data.Speculation.List
Data.Speculation.Internal