git.iko.soy/Haskell-HSE/haskell-lectures-2024
on main help sign in
Haskell-HSE/haskell-lectures-2024/6.Multicore.md
286 lines 10 kB history raw
1# Haskell for Multicores
3[http://haskell.org/ghc GHC Haskell] comes with a large set of libraries and
4tools for building programs that exploit multicore architectures.
6[http://wiki.haskell.org/Haskell_for_multicores Haskell Wiki] attempts to
7document all our available information on exploiting such hardware with Haskell.
9Throughout, we focus on exploiting shared-memory
10[http://en.wikipedia.org/wiki/Symmetric_multiprocessing SMP systems], with aim
11of lowering absolute wall clock times. The machines we target are typical 2x to
1232x desktop multicore machine, on which vanilla GHC will run.
14## Introduction
16To get an idea of what we aim to do — reduce running times by exploiting
17more cores — here's a naive "hello, world" of parallel programs: parallel,
18naive fib. It simply tells us whether or not the SMP runtime is working:
20```haskell ignore
21import Control.Parallel
22import Control.Monad
23import Text.Printf
25cutoff = 35
27fib' :: Int -> Integer
28fib' 0 = 0
29fib' 1 = 1
30fib' n = fib' (n-1) + fib' (n-2)
32fib :: Int -> Integer
33fib n | n < cutoff = fib' n
34 | otherwise = r `par` (l `pseq` l + r)
35 where
36 l = fib (n-1)
37 r = fib (n-2)
39main = forM_ [0..45] $ \i ->
40 printf "n=%d => %d\n" i (fib i)
41```
43We compile it with the `-threaded` flag:
45```
46$ ghc -O2 -threaded --make fib.hs
47[1 of 1] Compiling Main ( fib.hs, fib.o )
48Linking fib ...
49```
51And run it with `+RTS -Nx` where `x` is the number of cores you have (or a
52slightly higher value). Here, on a quad core linux system:
54```
55./fib +RTS -N4 76.81s user 0.75s system 351% cpu 22.059 total
56```
58So we were able to use 3.5/4 of the available cpu time. And this is typical,
59most problems aren't easily scalable, and we must trade off work on more cores,
60for more overhead with communication.
62### Examples
64* [http://haskell.org/haskellwiki/Concurrency_demos/Zeta Riemann's zeta function]
66### Further reading
68* [http://haskell.org/haskellwiki/GHC/Concurrency GHC's multiprocessor guide]
69* [https://downloads.haskell.org/ghc/latest/docs/html/users_guide/using-concurrent.html#using-smp-parallelism runtime options to enable SMP parallelism]
70* [http://www.haskell.org/ghc/docs/latest/html/libraries/parallel/Control-Parallel-Strategies.html API documentation for paralell strategies]
71* [http://book.realworldhaskell.org/read/concurrent-and-multicore-programming.html Real World Haskell: Concurrent and Parallel Programming]
72* [http://haskell.org/haskellwiki/Blog_articles/Parallel Blog posts about parallelism]
74## Thread primitives
76For explicit concurrency and/or parallelism, Haskell implementations have a
77light-weight thread system that schedules logical threads on the available
78operating system threads. These light and cheap threads can be created with
79`forkIO`. (We won't discuss full OS threads which are created via `forkOS`, as
80they have significantly higher overhead and are only useful in a few situations
81like in FFIs.)
83```haskell ignore
84forkIO :: IO () -> IO ThreadId
85```
87Lets take a simple Haskell application that hashes two files and prints the
88result:
90```haskell ignore
91import Data.Digest.Pure.MD5 (md5)
92import qualified Data.ByteString.Lazy as L
93import System.Environment (getArgs)
95main = do
96 [fileA, fileB] <- getArgs
97 hashAndPrint fileA
98 hashAndPrint fileB
100hashAndPrint f = L.readFile f >>= return . md5 >>= \h -> putStrLn (f ++ ": " ++ show h)
101```
103This is a straightforward solution that hashes the files one at a time printing
104the resulting hash to the screen. What if we wanted to use more than one
105processor to hash the files in parallel?
107One solution is to start a new thread, hash in parallel, and print the answers
108as they are computed:
110```haskell ignore
111import Control.Concurrent (forkIO)
112import Data.Digest.Pure.MD5 (md5)
113import qualified Data.ByteString.Lazy as L
114import System.Environment (getArgs)
116main = do
117 [fileA,fileB] <- getArgs
118 forkIO $ hashAndPrint fileA
119 hashAndPrint fileB
121hashAndPrint f = L.readFile f >>= return . md5 >>= \h -> putStrLn (f ++ ": " ++ show h)
122```
124Now we have a rough program with great performance boost &mdash; which is
125expected given the trivially parallel computation.
127But wait! You say there is a bug? Two, actually. One is that if the main thread
128is finished hashing `fileB` first, the program will exit before the child thread
129is done with `fileA`. The second is a potential for garbled output due to two
130threads writing to stdout. Both these problems can be solved using some
131inter-thread communication - we'll pick this example up in the `MVar` section.
133### Further reading
135* [http://blog.moertel.com/articles/2004/03/13/concurrent-port-scanner-in-haskell A concurrent port scanner]
136* [http://haskell.org/haskellwiki/Research_papers/Parallelism_and_concurrency#Concurrent_Haskell Research papers on concurrency in Haskell]
137* [http://haskell.org/haskellwiki/Research_papers/Parallelism_and_concurrency#Parallel_Haskell Research papers on parallel Haskell]
139## Synchronisation with locks
141Locking mutable variables (`MVar`s) can be used to great effect not only for
142communicating values (such as the resulting string for a single function to
143print) but it is also common for programmers to use their locking features as a
144signaling mechanism.
146`MVar`s are a polymorphic mutable variables that might or might not contain a
147value at any given time. Common functions include:
149```haskell ignore
150newMVar :: a -> IO (MVar a)
151newEmptyMVar :: IO (MVar a)
152takeMVar :: MVar a -> IO a
153putMVar :: MVar a -> a -> IO ()
154isEmptyMVar :: MVar a -> IO Bool
155```
157While they are fairly self-explanitory it should be noted that `takeMVar` will
158block until the `MVar` is non-empty and `putMVar` will block until the current
159MVar is empty. Taking an MVar will leave the MVar empty when returning the value.
161In the `forkIO` example we developed a program to hash two files in parallel and
162ended with a couple small bugs because the program terminated prematurely (the
163main thread would exit when done). A second issue was that threads can conflict
164with each others use of stdout.
166Lets now generalize the example to operate on any number of files, block until
167the hashing is complete, and print all the results from just one thread so no
168stdout garbling occurs.
170```haskell ignore
171{-# LANGUAGE BangPatterns #-}
172import Data.Digest.Pure.MD5
173import qualified Data.ByteString.Lazy as L
174import System.Environment
175import Control.Concurrent
176import Control.Monad (replicateM_)
178main = do
179 files <- getArgs
180 str <- newEmptyMVar
181 mapM_ (forkIO . hashAndPrint str) files
182 printNrResults (length files) str
184printNrResults i var = replicateM_ i (takeMVar var >>= putStrLn)
186hashAndPrint str f = do
187 bs <- L.readFile f
188 let !h = show $ md5 bs
189 putMVar str (f ++ ": " ++ h)
190```
192We define a new variable, `str`, as an empty `MVar`. After the hashing, the
193result is reported with `putMVar` &mdash; remember this function blocks when the
194`MVar` is already full so no hashes are dropped on account of the mutable memory.
195Similarly, `printNrResults` uses the `takeMVar` function which will block until
196the `MVar` is full - or once the next file is done being hashed in this case.
198Note how the value is evaluated before the `putMVar` call. If the argument is an
199unevaluated thunk then `printNrResults` will have to evaluate the thunks before
200it prints the result and our efforts would have been worthless.
202Knowing the `str` `MVar` will be filled `length files` times we can let the main
203thread exit after printing the given number of results, thus terminating the
204program.
206```
207$ ghc exMVar.hs -o exMVar-threaded --make -O2 -threaded
208$ time ./exMVar-threaded +RTS -N2 -RTS 2GB 2GB 2GB 2GB
209 2GB: b8f1f1faa6dda5426abffb3a7811c1fb
210 2GB: b8f1f1faa6dda5426abffb3a7811c1fb
211 2GB: b8f1f1faa6dda5426abffb3a7811c1fb
212 2GB: b8f1f1faa6dda5426abffb3a7811c1fb
214 real 0m40.524s
216$ time ./exMVar-threaded +RTS -N1 -RTS 2GB 2GB 2GB 2GB
217 2GB: b8f1f1faa6dda5426abffb3a7811c1fb
218 2GB: b8f1f1faa6dda5426abffb3a7811c1fb
219 2GB: b8f1f1faa6dda5426abffb3a7811c1fb
220 2GB: b8f1f1faa6dda5426abffb3a7811c1fb
222 real 1m8.170s
223```
225## Message passing channels
227For streaming data it is hard to beat the performance of channels. After
228declaring a channel (`newChan`), you can pipe data between threads
229(`writeChan`, `readChan`) and tee data to separate readers (`dupChan`). The
230flexibility of channels makes them useful for a wide range of communications.
232Continuing with our hashing example, let's say the names of the files needing
233hashed are coming available, or need streaming for other reasons. We can fork a
234set of worker threads and feed them the filenames through a channel. For
235consistency, the program has also been modified to communicate the result from
236worker to printer via a channel.
238```haskell ignore
239{-# LANGUAGE BangPatterns #-}
240import Data.Digest.Pure.MD5
241import qualified Data.ByteString.Lazy as L
242import System.Environment
243import Control.Concurrent
244import Control.Concurrent.Chan
245import Control.Monad (forever, forM_, replicateM_)
247nrWorkers = 2
249main = do
250 files <- getArgs
251 str <- newChan
252 fileChan <- newChan
253 forM_ [1..nrWorkers] (\_ -> forkIO $ worker str fileChan)
254 forM_ files (writeChan fileChan)
255 printNrResults (length files) str
257printNrResults i var = replicateM_ i (readChan var >>= putStrLn)
259worker :: Chan String -> Chan String -> IO ()
260worker str fileChan = forever (readChan fileChan >>= hashAndPrint str)
262hashAndPrint str f = do
263 bs <- L.readFile f
264 let !h = show $ md5 bs
265 writeChan str (f ++ ": " ++ h)
266```
268Notice that this has advantages: results are available incrementally, and the
269performance has improved with the number of parallel hash operations matching
270the number of cores.
272### Examples
274* [http://haskell.org/haskellwiki/Implement_a_chat_server Implementing a chat server]
275* [http://haskell.org/haskellwiki/Concurrency_demos/Two_reader_threads Two reader threads]
277## To be discussed next
279* Lock-free synchronisation &mdash; STM
280* Asynchronous exceptions
282## Further reading
284* Parallelism strategies &mdash; [http://hackage.haskell.org/package/parallel Control.Parallel]
285* [http://haskell.org/haskellwiki/GHC/Data_Parallel_Haskell Data Parallel Arrays]
286* Non-blocking foreign calls in concurrent threads