book

Parallel and Concurrent Programming in Haskell

by Simon Marlow

July 2013

Intermediate to advanced

322 pages

8h 43m

English

O'Reilly Media, Inc.

Read now

Unlock full access

AudienceHow to Read This BookConventions Used in This BookUsing Sample CodeSafari® Books OnlineHow to Contact UsAcknowledgments
Terminology: Parallelism and ConcurrencyTools and ResourcesSample Code
Lazy Evaluation and Weak Head Normal FormThe Eval Monad, rpar, and rseqExample: Parallelizing a Sudoku SolverDeepseq
Parameterized StrategiesA Strategy for Evaluating a List in ParallelExample: The K-Means ProblemParallelizing K-MeansPerformance and AnalysisVisualizing Spark ActivityGranularityGC’d Sparks and Speculative ParallelismParallelizing Lazy Streams with parBufferChunking StrategiesThe Identity Property
Example: Shortest Paths in a GraphPipeline ParallelismRate-Limiting the ProducerLimitations of Pipeline ParallelismExample: A Conference TimetableAdding ParallelismExample: A Parallel Type InferencerUsing Different SchedulersThe Par Monad Compared to Strategies
Arrays, Shapes, and IndicesOperations on ArraysExample: Computing Shortest PathsParallelizing the ProgramFolding and Shape-PolymorphismExample: Image RotationSummary
OverviewArrays and IndicesRunning a Simple Accelerate ComputationScalar ArraysIndexing ArraysCreating Arrays Inside AccZipping Two ArraysConstantsExample: Shortest PathsRunning on the GPUDebugging the CUDA BackendExample: A Mandelbrot Set Generator

A Simple Example: RemindersCommunication: MVarsMVar as a Simple Channel: A Logging ServiceMVar as a Container for Shared StateMVar as a Building Block: Unbounded ChannelsFairness
Exceptions in HaskellError Handling with AsyncMerging
Asynchronous ExceptionsMasking Asynchronous ExceptionsThe bracket OperationAsynchronous Exception Safety for ChannelsTimeoutsCatching Asynchronous Exceptionsmask and forkIOAsynchronous Exceptions: Discussion
Running Example: Managing WindowsBlockingBlocking Until Something ChangesMerging with STMAsync RevisitedImplementing Channels with STMMore Operations Are PossibleComposition of Blocking OperationsAsynchronous Exception SafetyAn Alternative Channel ImplementationBounded ChannelsWhat Can We Not Do with STM?PerformanceSummary
Avoiding Thread LeakageSymmetric Concurrency CombinatorsTimeouts Using raceAdding a Functor InstanceSummary: The Async API
A Trivial ServerExtending the Simple Server with StateDesign One: One Giant LockDesign Two: One Chan Per Server ThreadDesign Three: Use a Broadcast ChanDesign Four: Use STMThe ImplementationA Chat ServerArchitectureClient DataServer DataThe ServerSetting Up a New ClientRunning the ClientRecap
How to Achieve Parallelism with ConcurrencyExample: Searching for FilesSequential VersionParallel VersionPerformance and ScalingLimiting the Number of Threads with a SemaphoreThe ParIO monad
The Distributed-Process Family of PackagesDistributed Concurrency or Parallelism?A First Example: PingsProcesses and the Process MonadDefining a Message TypeThe Ping Server ProcessThe Master ProcessThe main FunctionSumming Up the Ping ExampleMulti-Node PingRunning with Multiple Nodes on One MachineRunning on Multiple MachinesTyped ChannelsMerging ChannelsHandling FailureThe Philosophy of Distributed FailureA Distributed Chat ServerData TypesSending MessagesBroadcastingDistributionTesting the ServerFailure and Adding/Removing NodesExercise: A Distributed Key-Value Store
Debugging Concurrent ProgramsInspecting the Status of a ThreadEvent Logging and ThreadScopeDetecting DeadlockTuning Concurrent (and Parallel) ProgramsThread Creation and MVar OperationsShared Concurrent Data StructuresRTS Options to TweakConcurrency and the Foreign Function InterfaceThreads and Foreign Out-CallsAsynchronous Exceptions and Foreign CallsThreads and Foreign In-Calls

Content preview from Parallel and Concurrent Programming in Haskell

Part I. Parallel Haskell

Now that processor manufacturers have largely given up trying to squeeze more performance out of individual processors and have refocused their attention on providing us with more processors instead, the biggest gains in performance are to be had by using parallel techniques in our programs so as to make use of these extra cores. Parallel Haskell is aimed at providing access to multiple processors in a natural and robust way.

You might wonder whether the compiler could automatically parallelize programs for us. After all, it should be easier to do this in a purely functional language, where the only dependencies between computations are data dependencies, which are mostly perspicuous and thus readily analyzed. However, even in a purely functional language, automatic parallelization is thwarted by an age-old problem: To make the program faster, we have to gain more from parallelism than we lose due to the overhead of adding it, and compile-time analysis cannot make good judgments in this area. An alternative approach is to use runtime profiling to find good candidates for parallelization and to feed this information back into the compiler. Even this, however, has not been terribly successful in practice.

Fully automatic parallelization is still a pipe dream. However, the parallel programming models provided by Haskell do succeed in eliminating some mundane or error-prone aspects traditionally associated with parallel programming: