Move user's guide to ReStructuredText
[ghc.git] / docs / users_guide / parallel.rst
1 .. _lang-parallel:
2
3 Concurrent and Parallel Haskell
4 ===============================
5
6 .. index::
7    single: parallelism
8    single: concurrency
9
10 GHC implements some major extensions to Haskell to support concurrent
11 and parallel programming. Let us first establish terminology:
12
13 -  *Parallelism* means running a Haskell program on multiple processors,
14    with the goal of improving performance. Ideally, this should be done
15    invisibly, and with no semantic changes.
16
17 -  *Concurrency* means implementing a program by using multiple
18    I/O-performing threads. While a concurrent Haskell program *can* run
19    on a parallel machine, the primary goal of using concurrency is not
20    to gain performance, but rather because that is the simplest and most
21    direct way to write the program. Since the threads perform I/O, the
22    semantics of the program is necessarily non-deterministic.
23
24 GHC supports both concurrency and parallelism.
25
26 .. _concurrent-haskell:
27
28 Concurrent Haskell
29 ------------------
30
31 Concurrent Haskell is the name given to GHC's concurrency extension. It
32 is enabled by default, so no special flags are required. The `Concurrent
33 Haskell
34 paper <https://www.haskell.org/ghc/docs/papers/concurrent-haskell.ps.gz>`__
35 is still an excellent resource, as is `Tackling the awkward
36 squad <http://research.microsoft.com/%7Esimonpj/papers/marktoberdorf/>`__.
37
38 To the programmer, Concurrent Haskell introduces no new language
39 constructs; rather, it appears simply as a library,
40 :base-ref:`Control.Concurrent <Control-Concurrent.html>`.
41 The functions exported by this library include:
42
43 -  Forking and killing threads.
44
45 -  Sleeping.
46
47 -  Synchronised mutable variables, called ``MVars``
48
49 -  Support for bound threads; see the paper `Extending the FFI with
50    concurrency <http://research.microsoft.com/%7Esimonpj/Papers/conc-ffi/index.htm>`__.
51
52 Software Transactional Memory
53 -----------------------------
54
55 GHC now supports a new way to coordinate the activities of Concurrent
56 Haskell threads, called Software Transactional Memory (STM). The `STM
57 papers <http://research.microsoft.com/%7Esimonpj/papers/stm/index.htm>`__
58 are an excellent introduction to what STM is, and how to use it.
59
60 The main library you need to use is the `stm
61 library <http://hackage.haskell.org/package/stm>`__. The main features
62 supported are these:
63
64 -  Atomic blocks.
65
66 -  Transactional variables.
67
68 -  Operations for composing transactions: ``retry``, and ``orElse``.
69
70 -  Data invariants.
71
72 All these features are described in the papers mentioned earlier.
73
74 Parallel Haskell
75 ----------------
76
77 .. index::
78    single: SMP
79
80 GHC includes support for running Haskell programs in parallel on
81 symmetric, shared-memory multi-processor (SMP). By default GHC runs
82 your program on one processor; if you want it to run in parallel you
83 must link your program with the ``-threaded``, and run it with the RTS
84 ``-N`` option; see :ref:`using-smp`). The runtime will schedule the
85 running Haskell threads among the available OS threads, running as many
86 in parallel as you specified with the ``-N`` RTS option.
87
88 Annotating pure code for parallelism
89 ------------------------------------
90
91 Ordinary single-threaded Haskell programs will not benefit from enabling
92 SMP parallelism alone: you must expose parallelism to the compiler. One
93 way to do so is forking threads using Concurrent Haskell
94 (:ref:`concurrent-haskell`), but the simplest mechanism for extracting
95 parallelism from pure code is to use the ``par`` combinator, which is
96 closely related to (and often used with) ``seq``. Both of these are
97 available from the
98 `parallel library <http://hackage.haskell.org/package/parallel>`__:
99
100 ::
101
102     infixr 0 `par`
103     infixr 1 `pseq`
104
105     par  :: a -> b -> b
106     pseq :: a -> b -> b
107
108 The expression ``(x `par` y)`` *sparks* the evaluation of ``x`` (to weak
109 head normal form) and returns ``y``. Sparks are queued for execution in
110 FIFO order, but are not executed immediately. If the runtime detects
111 that there is an idle CPU, then it may convert a spark into a real
112 thread, and run the new thread on the idle CPU. In this way the
113 available parallelism is spread amongst the real CPUs.
114
115 For example, consider the following parallel version of our old nemesis,
116 ``nfib``:
117
118 ::
119
120     import Control.Parallel
121
122     nfib :: Int -> Int
123     nfib n | n <= 1 = 1
124            | otherwise = par n1 (pseq n2 (n1 + n2 + 1))
125                          where n1 = nfib (n-1)
126                                n2 = nfib (n-2)
127
128 For values of ``n`` greater than 1, we use ``par`` to spark a thread to
129 evaluate ``nfib (n-1)``, and then we use ``pseq`` to force the parent
130 thread to evaluate ``nfib (n-2)`` before going on to add together these
131 two subexpressions. In this divide-and-conquer approach, we only spark a
132 new thread for one branch of the computation (leaving the parent to
133 evaluate the other branch). Also, we must use ``pseq`` to ensure that
134 the parent will evaluate ``n2`` *before* ``n1`` in the expression
135 ``(n1 + n2 + 1)``. It is not sufficient to reorder the expression as
136 ``(n2 + n1 + 1)``, because the compiler may not generate code to
137 evaluate the addends from left to right.
138
139 Note that we use ``pseq`` rather than ``seq``. The two are almost
140 equivalent, but differ in their runtime behaviour in a subtle way:
141 ``seq`` can evaluate its arguments in either order, but ``pseq`` is
142 required to evaluate its first argument before its second, which makes
143 it more suitable for controlling the evaluation order in conjunction
144 with ``par``.
145
146 When using ``par``, the general rule of thumb is that the sparked
147 computation should be required at a later time, but not too soon. Also,
148 the sparked computation should not be too small, otherwise the cost of
149 forking it in parallel will be too large relative to the amount of
150 parallelism gained. Getting these factors right is tricky in practice.
151
152 It is possible to glean a little information about how well ``par`` is
153 working from the runtime statistics; see :ref:`rts-options-gc`.
154
155 More sophisticated combinators for expressing parallelism are available
156 from the ``Control.Parallel.Strategies`` module in the `parallel
157 package <http://hackage.haskell.org/package/parallel>`__. This module
158 builds functionality around ``par``, expressing more elaborate patterns
159 of parallel computation, such as parallel ``map``.
160
161 .. _dph:
162
163 Data Parallel Haskell
164 ---------------------
165
166 GHC includes experimental support for Data Parallel Haskell (DPH). This
167 code is highly unstable and is only provided as a technology preview.
168 More information can be found on the corresponding
169 `DPH wiki page <http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell>`__.