Overview: Parallel and Asynchronous Programming

Article
09/12/2011

Applies to: Functional Programming

Authors: Tomas Petricek and Jon Skeet

Referenced Image

Get this book in Print, PDF, ePub and Kindle at manning.com. Use code “MSDN37b” to save 37%.

Summary: This overview demonstrates how functional concepts make it easier to parallelize applications. It also demonstrates F# asynchronous workflows and interesting programming styles that can be used with their help. (7 pages)

This topic contains the following sections.

How Does Functional Programming Help?
Parallelizing Immutable Programs
Declarative Parallelism with LINQ
Writing Asynchronous Computations in F#
Message-Passing Concurrency
Summary
Additional Resources
See Also

This article is an excerpt from Real World Functional Programming: With Examples in F# and C# by Tomas Petricek with Jon Skeet from Manning Publications (ISBN 9781933988924, copyright Manning Publications 2009, all rights reserved). No part of these chapters may be reproduced, stored in a retrieval system, or transmitted in any form or by any means—electronic, electrostatic, mechanical, photocopying, recording, or otherwise—without the prior written permission of the publisher, except in the case of brief quotations embodied in critical articles or reviews.

How Does Functional Programming Help?

The fact that functional programming facilitates the writing of parallel programs may be the reason why it caught your attention. This overview explores a couple of samples demonstrating how functional programs can be easily parallelized. The first two examples use Task Parallel Library (TPL) and Parallel LINQ (PLINQ), which are new technologies for parallel programming in .NET Framework 4.0. Both of the technologies work the best with code written in a functional style. A later example looks at F# asynchronous workflows, which solve a different but related problem—how to run operations that take a long time to complete but don't consume much CPU power, such as web service calls.

First consider parallel programming—there are two problems when writing a multithreaded application using the traditional imperative style:

It’s difficult to turn the existing sequential code into parallel code because introducing threads requires modifying large portions of the codebase.
Using the shared state and locks is difficult. When using locks, you need to consider how to avoid race conditions and deadlocks but leave enough space for parallel execution.

Functional programming offers the following answers:

When using a declarative programming style, parallelism can be introduced into the existing code by replacing a few primitives that specify how to combine commands with a version that executes commands in parallel.
Thanks to immutability, it is impossible to introduce race conditions, so more code can be written in a lock-free style. It is also easy to see which parts of the program are independent, and the program can be modified to run those tasks in parallel.

These two aspects influence the application design and, as a result, make it easier to write code that executes in parallel, taking full advantage of the power of multicore machines. The simple fact that code uses immutable types doesn’t give away parallelization for free. There’s work involved, but functional programming minimizes the additional effort that needs to be put in parallelization.

Parallelizing Immutable Programs

The article Overview: Understanding What a Program Does discussed immutability and demonstrated a simple immutable C# class to represent a character in a game. This overview uses mostly C# because it is more familiar and it is good enough to demonstrate the important functional concepts.

The fact that the class is immutable means that it cannot be changed once it is created. To update the character (for example, in reaction to shooting in the game), the program creates a new instance representing the new state of the character. This makes the program easier to understand because the only thing that a method can do is to return some result.

The following snippet (repeated from the previous overview) updates two monsters in a functional game. It works with two objects, demonMonster and spiderMonster, and an object representing a gunshot. The health of monsters is updated (if they were hit) by calling HitByShooting, which returns a new state of each of the monsters:

var demonMonsterHit = 
  demonMonster.HitByShooting(gunShot); 
var spiderMonsterHit = 
  spiderMonster.HitByShooting(gunShot);

As explained in the overview referenced at the beginning of the section, the two lines of code are independent. It doesn't matter in what order they are executed because the second one doesn't rely on the result of the first one. Because the world is immutable, the first line also cannot do any operations that would affect the second one.

Not only is the order of the two calls irrelevant but the two operations can also be called in parallel. Thanks to functional programming, such situations are easy to spot—when two blocks of code don’t have a dependency between them, they can be executed in parallel. The following example shows how to do that using the TPL library:

var demonMonsterHit = Task.Factory.StartNew(() =>
  demonMonster.HitByShooting(gunShot)); 
var spiderMonsterHit = Task.Factory.StartNew(() =>
  spiderMonster.HitByShooting(gunShot));

The only change is that the computation is now wrapped in a Task type from the TPL library. The snippet uses a C# lambda expression to create a delegate that is used by the Task object for execution.

The benefit of using TPL with functional programming isn’t only that it requires less code than when using, for example, threads. Functional programming also partially guarantees that the code is correct. Before doing a similar change in an imperative program, you have to carefully review the HitByShooting method (and any other method it calls) to find all places where it accesses some mutable state and add locks to protect the code that reads or modifies the shared state. In functional programming, everything is immutable so locks are not needed.

The example in this section is a form of lower-level task-based parallelism. The next section demonstrates the second approach, which benefits from the declarative programming style.

Declarative Parallelism with LINQ

The declarative programming style provides another technique for writing parallel programs. More information about declarative programming style in general can be found in Overview: Benefiting from Declarative Style. In short, when using this style, programs are composed from several primitives that specify a primitive operation or a primitive object. In LINQ, these primitives are query methods, such as Where and Select.

The declarative style makes it easy to replace the implementation of these primitives. That’s exactly what Parallel LINQ does: it replaces the standard query operators with an alternative implementation that runs in parallel. The following snippet shows a query that updates all monsters in a fictitious game and removes those that died in the last step of the game.

The snippet shows the original version and a version running in parallel. The change is extremely simple:

// Sequential single-threaded version
var updated = 
   from m in monsters
   let nm = m.PerformStep()
   where nm.IsAlive select nm;

// Parallel version running on multiple threads
var updated = 
   from m in monsters.AsParallel()
   let nm = m.PerformStep()
   where nm.IsAlive select nm;

The only change in the parallel version is the added call to the AsParallel method. This call changes the primitives that are used when running the query and makes the whole fragment run in parallel.

The last two sections demonstrated two ways of parallelizing functional programs. There is one more related area where functional programming (and especially F#) helps to write more efficient and scalable code with respect to multithreading. It is important, particularly when code uses long-running I/O operations.

Writing Asynchronous Computations in F#

Long-running operations are quite frequent in contemporary software. Many applications use HTTP requests to load some data from the Internet or communicate using web services. When an application performs an operation like this, it is difficult to predict when the operation will complete and, if this is not handled properly, the application might hang.

Writing the code that performs I/O operations and doesn't block the thread is a challenge. In F#, this is largely simplified thanks to a feature called asynchronous workflows. This section shows a small example to demonstrate another area where F# works extremely well. The following C# example (synchronously) downloads the source of a web page:

// Create request and initialize HTTP connection
var req = HttpWebRequest.Create("http://manning.com");
using(var resp = req.GetResponse())
// Get stream and download the web page content
using(var stream = resp.GetResponseStream()) {
    var reader = new StreamReader(stream);
    var html = reader.ReadToEnd();
    Console.WriteLine(html);
}

The example looks fairly simple, but there are two places where the program needs to perform some HTTP communication. First, when it calls GetResponse, it needs to send a request to the server and wait for the HTTP response. Later, when it calls ReadToEnd, it needs to receive the whole page from the server.

Both of these operations could potentially take quite a long time and both of them could block the thread (and cause our application to hang). A proper implementation needs to use asynchronous .NET methods that trigger the request and call a provided code when the operation completes. Even with C# 3.0 and lambda expressions, the code begins to look quite complicated:

var req = HttpWebRequest.Create("http://manning.com");
req.BeginGetResponse(ar => {
   var rsp = req.EndGetResponse(ar);
   // TODO: Use the response to read the HTML
});

Lambda expressions make this a bit nicer because they avoid the need to write a separate method to handle the response, but the structure of the code still changes. In fact, changing a synchronous version of the code into asynchronous, often means an almost complete rewrite.

Completing the above snippet would reveal another issue. There is no BeginReadToEnd method, so this functionality would have to be implemented explicitly. The downloading would probably use a buffer. In an asynchronous version, it becomes impossible to use built-in constructs such as while loop. The implementation needs a rather complicated class encoding a state machine…

How do you solve the same problem in F#? When working with .NET libraries, the F# code is quite similar to C# (just delete semicolons and change the var keyword to let). Only a few modifications are needed to turn the synchronous version into asynchronous version:

let op = async { 
    let req = HttpWebRequest.Create("http://manning.com")
    // Run the 'GetResponse' operation asynchronously
    use! resp = req.AsyncGetResponse()
    use stream = resp.GetResponseStream()
    use reader = new StreamReader(stream)
    // Download the content asynchronously
    let! html = reader.AsyncReadToEnd()
    Console.WriteLine(html) }

// Actually execute the workflow
Async.RunSynchronously(op)

The process of turning synchronous code into asynchronous in F# is quite easy. First of all, the whole computation is wrapped into an async block. Next, all asynchronous operations in the block are changed to a corresponding asynchronous version of the method. In this case, both AsyncGetResponse and AsyncReadToEnd are already available in F# libraries. The workflow also needs to know which of the methods should be called in a nonblocking way. This is done by replacing let with let! or use with use! (which is similar, but ensures that resources are properly disposed of).

More interestingly, methods like AsyncReadToEnd are quite easy to implement because asynchronous workflows can use while loops and other basic control flow constructs. In an asynchronous workflow, let! can be used in the while loop, use declarations (to dispose of resources), or try … with blocks (to handle exceptions). It is also worth noting that asynchronous workflows aren't part of the core syntax of the F# language. It is just a very useful instance of a more general feature that allows writing nonstandard computations.

Asynchronous workflows can be used to write programs that wait for some operation without actually blocking the threads. This enables interesting models for concurrency, such as the message-passing style.

Message-Passing Concurrency

The support for asynchronous programming enables the use of message-passing concurrency in F#. The applications designed in this style consist of a large number of independent agents that perform some simple tasks. Message-passing concurrency requires a quite different application architecture but it leads to extremely scalable and reliable systems. This paradigm has been used extensively in the Erlang language.

Note

Erlang

Erlang is a language developed and heavily used by Ericsson for developing large-scale real-time systems. It can be found in much of Ericsson's telecommunication equipment. Erlang has been used commercially by Ericsson for programming the network hardware used concurrently by hundreds of users as well as by other companies.

Concurrent applications in Erlang are described using independent processes (written in a functional way) that can communicate with each other using messages. The process waits for a message and, when a message arrives, it processes it.

The following example gives a feel of message-passing concurrency in F#. It creates an agent that can receive the messages that contain integers. When it receives a message, it prints the integer to the console. After creating the agent, the sample sends it some messages to test the functionality:

// Create agent that prints numbers that it receives
let worker = MailboxProcessor.Start(fun mbox -> async {
    while true do
        // Wait for the next message and process it
        let! number = mbox.Receive()
        printfn "Processed %d" number } )

// Send 10 numbers to the agent for processing
for i in 0 .. 9 do worker.Post(i)

The agent is created using the MailboxProcessor type. The parameter to the Start method is a function that provides the body of the agent. The entire body is written as an asynchronous workflow.

The sample agent contains a while loop that runs forever (while the application is running). It asynchronously waits for the next message using mbox.Receive and, when it receives a number, it prints it and continues waiting for the next message. The fact that the body is asynchronous is very important because the agent may be blocked for quite a long time (if the application is performing another task at the time). Thanks to asynchronous workflows, agents are very lightweight and applications can consist of hundreds of thousands of agents.

Summary

This overview discussed how functional programming helps with writing parallel applications and how F# supports the asynchronous programming style. There are two ways in which the functional style makes writing multithreaded applications easier.

First, immutability provides guarantees about programs. When working with immutable data structures, independent blocks of code can be parallelized without changing the program behavior. Second, when writing code in a declarative way, it becomes easier to parallelize just by replacing a few primitives.

The overview also focused on asynchronous programming. F# provides asynchronous workflows that can be used to turn synchronous code into asynchronous. This removes the blocking of threads while waiting for the completion of a long-running operation. Asynchronous workflows also make it possible to use message-passing concurrency, which is a different but very successful paradigm for writing scalable and robust concurrent systems.

Additional Resources

The fact that functional languages simplify parallel, asynchronous, and concurrent programming is one of the reasons why they are becoming increasingly important but it isn’t the only benefit of functional languages. The next two sections cover several other benefits:

These benefits arise from the fact that functional programming is based on a different set of core principles. The focus on immutable data types and expression-based programming changes the way developers think about programs. The following articles give an overview of the functional concepts:

To download the code snippets shown in this article, go to https://code.msdn.microsoft.com/Chapter-1-Introducing-F-c967460d