docs: make nfib compute the Fibonacci sequence [skipci]
[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.`. The functions exported by this library include:
41
42 -  Forking and killing threads.
43
44 -  Sleeping.
45
46 -  Synchronised mutable variables, called ``MVars``
47
48 -  Support for bound threads; see the paper `Extending the FFI with
49    concurrency <http://community.haskell.org/~simonmar/papers/conc-ffi.pdf>`__.
50
51 Software Transactional Memory
52 -----------------------------
53
54 GHC now supports a new way to coordinate the activities of Concurrent
55 Haskell threads, called Software Transactional Memory (STM). The `STM
56 papers <https://wiki.haskell.org/Research_papers/Parallelism_and_concurrency#Lock_free_data_structures_and_transactional_memory>`__
57 are an excellent introduction to what STM is, and how to use it.
58
59 The main library you need to use is the `stm
60 library <http://hackage.haskell.org/package/stm>`__. The main features
61 supported are these:
62
63 -  Atomic blocks.
64
65 -  Transactional variables.
66
67 -  Operations for composing transactions: ``retry``, and ``orElse``.
68
69 -  Data invariants.
70
71 All these features are described in the papers mentioned earlier.
72
73 Parallel Haskell
74 ----------------
75
76 .. index::
77    single: SMP
78
79 GHC includes support for running Haskell programs in parallel on
80 symmetric, shared-memory multi-processor (SMP). By default GHC runs
81 your program on one processor; if you want it to run in parallel you
82 must link your program with the :ghc-flag:`-threaded`, and run it with the RTS
83 :rts-flag:`-N ⟨x⟩` option; see :ref:`using-smp`). The runtime will schedule the
84 running Haskell threads among the available OS threads, running as many in
85 parallel as you specified with the :rts-flag:`-N ⟨x⟩` RTS option.
86
87 Annotating pure code for parallelism
88 ------------------------------------
89
90 Ordinary single-threaded Haskell programs will not benefit from enabling
91 SMP parallelism alone: you must expose parallelism to the compiler. One
92 way to do so is forking threads using Concurrent Haskell
93 (:ref:`concurrent-haskell`), but the simplest mechanism for extracting
94 parallelism from pure code is to use the ``par`` combinator, which is
95 closely related to (and often used with) ``seq``. Both of these are
96 available from the
97 `parallel library <http://hackage.haskell.org/package/parallel>`__:
98
99 ::
100
101     infixr 0 `par`
102     infixr 1 `pseq`
103
104     par  :: a -> b -> b
105     pseq :: a -> b -> b
106
107 The expression ``(x `par` y)`` *sparks* the evaluation of ``x`` (to weak
108 head normal form) and returns ``y``. Sparks are queued for execution in
109 FIFO order, but are not executed immediately. If the runtime detects
110 that there is an idle CPU, then it may convert a spark into a real
111 thread, and run the new thread on the idle CPU. In this way the
112 available parallelism is spread amongst the real CPUs.
113
114 For example, consider the following parallel version of our old nemesis,
115 ``nfib``:
116
117 ::
118
119     import Control.Parallel
120
121     nfib :: Int -> Int
122     nfib n | n <= 1 = 1
123            | otherwise = par n1 (pseq n2 (n1 + n2))
124                          where n1 = nfib (n-1)
125                                n2 = nfib (n-2)
126
127 For values of ``n`` greater than 1, we use ``par`` to spark a thread to
128 evaluate ``nfib (n-1)``, and then we use ``pseq`` to force the parent
129 thread to evaluate ``nfib (n-2)`` before going on to add together these
130 two subexpressions. In this divide-and-conquer approach, we only spark a
131 new thread for one branch of the computation (leaving the parent to
132 evaluate the other branch). Also, we must use ``pseq`` to ensure that
133 the parent will evaluate ``n2`` *before* ``n1`` in the expression
134 ``(n1 + n2 + 1)``. It is not sufficient to reorder the expression as
135 ``(n2 + n1 + 1)``, because the compiler may not generate code to
136 evaluate the addends from left to right.
137
138 Note that we use ``pseq`` rather than ``seq``. The two are almost
139 equivalent, but differ in their runtime behaviour in a subtle way:
140 ``seq`` can evaluate its arguments in either order, but ``pseq`` is
141 required to evaluate its first argument before its second, which makes
142 it more suitable for controlling the evaluation order in conjunction
143 with ``par``.
144
145 When using ``par``, the general rule of thumb is that the sparked
146 computation should be required at a later time, but not too soon. Also,
147 the sparked computation should not be too small, otherwise the cost of
148 forking it in parallel will be too large relative to the amount of
149 parallelism gained. Getting these factors right is tricky in practice.
150
151 It is possible to glean a little information about how well ``par`` is
152 working from the runtime statistics; see :ref:`rts-options-gc`.
153
154 More sophisticated combinators for expressing parallelism are available
155 from the ``Control.Parallel.Strategies`` module in the `parallel
156 package <http://hackage.haskell.org/package/parallel>`__. This module
157 builds functionality around ``par``, expressing more elaborate patterns
158 of parallel computation, such as parallel ``map``.