Parallel Programming in F# (II.): Using PLINQ and Tasks

In this part of the Parallel Programming in F# series, we'll look at some basic examples of parallel programming in F# that are available in Parallel Programming with Microsoft .NET. This is a guide that introduces common parallel programming patterns on .NET 4.0. The guide discusses the samples in C#, but it also contains an F# translation of the source code. Since the languages are different, the F# version deserves a brief explanation.

In this article, we'll discuss some of the F# examples and we'll look at a couple of aspects that are specific for F#. In particular, we'll look at working with Parallel LINQ (both directly and using PSeq module from F# PowerPack) and working with tasks. We'll also look at an interesting example (using closures) where C# version doesn't behave as expected, but a literal translation in F# corrects the problem.

For discussion about other F# examples from Parallel Programming with Microsoft .NET, you can refer to other parts of this article series. So far, the series covers the following topics:

• Parallel Programming in F# (I.): Introducing the samples
• Parallel Programming in F# (II.): Using PLINQ and Tasks
• Parallel Programming in F# (III.): Aggregating data
• Parallel Programming in F# (IV.): Financial dashboard example

Working with Parallel LINQ

We start by looking at examples from Chapter 2, which discusses parallel loops. This is a simple pattern for parallelization. It is useful when we have a loop (such as for) where the individual iterations of the loop are independent. This means that, for example, a result of the n-th iteration does not use the result of (n-1)-th iteration. In this case, we can run multiple iterations in parallel, because the order doesn't matter and they will not affect each other. When using .NET 4.0, there are several ways to implement this pattern. The following examples (from the "ParallelForExamples.fs" file in the "BasicParallelLoops" project) demonstrate some of the implementations.

Imperative approach

The first option is useful when the body of the loop performs some imperative action such as mutating an element in an array (each iteration needs to mutate different element, so that they are independent). In this case, we can use Parallel.For or Parallel.ForEach depending on which loop we're parallelizing. The following example takes an array of inputs named source, performs some work for each input element and stores the results in a new array:

1: let result = Array.zeroCreate source.Length
2: Parallel.ForEach(source, fun i -> 
3:     result.[i] <- doWork opts i ) |> ignore
4: result

The usage looks very similar to C# thanks to the fact that F# automatically converts function values to delegates (meaning that we don't have to write new Func<_>(...). The only notable difference is that the ForEach method returns some result (which can be used to implement and detect break), so we need to explicitly drop the result using the ignore function.

Declarative approach

Another option for implementing parallel loop is to use Parallel LINQ. It provides parallel versions of most of the LINQ query operators (such as Select, Where or even GroupBy). However, to implement parallel loop, we need just the Select operator.

Parallel LINQ has been designed to nicely work with the C# 3.0 query syntax. It exposes operators as extension methods (so we need to open the System.Linq namespace in order to see them). When using Parallel LINQ from F#, we can either use the methods directly or we can use F# wrappers from the PSeq module. The following example shows the former option:

1: source.AsParallel()
2:       .AsOrdered()
3:       .Select(doWork opts)
4:       .ToArray()

The example runs AsParallel immediately followed by AsOrdered. This configures the Parallel LINQ engine to preserve ordering when processing the data, so the n-th position in the returned array will correspond to the n-th position in the input array. Without this option, the query can (sometimes) run more efficiently, but the order may change. Next, we run the Select method and we use partial function application to supply its parameter. Finally, we call ToArray to force evaluation of the query.

The second way to write the example is to use the PSeq module which is distributed together with the samples ("PSeq.fs" file) and is also available in F# PowerPack (the local version contains a few changes that will eventually appear in PowerPack too). Using this module, we can write the processing in a more idiomatic functional style. As the following example shows, it looks just like list processing using functions such as List.map (the PSeq module uses standard F# names of functions where possible):

1: source |> PSeq.ordered
2:        |> PSeq.map (doWork opts)
3:        |> PSeq.toArray

The example uses exactly the same steps as the previous version with the exception that we don't need to call AsParallel explicitly. It is called automatically when we use the first function from the PSeq module. Syntactically, the snippet uses standard F# style and is written using the pipelining operator. You'll find several other examples of parallel loops in the F# version of the sample source code. However, all examples of using Parallel LINQ are similar to those that we've just seen, so we can take a look at another topic...

Working with tasks

The second way of writing parallel programs in .NET is to use the Task type. A task represents a (small) unit of work that can either return some result (in that case, we'll use Task<'T>) or it can perform some imperative action (non-generic type Task). In this section, we'll look at a couple of basic examples of working with tasks, mainly from Chapter 3. A more complicated example that is also created using tasks can be found in part IV. We'll also see how immutability in F# makes working with tasks easier. However, let's start by a basic example that demonstrates the Task<'T> type. You can find it in "Processing.fs" file in the "ImageBlender" project. It takes two input images (source1 and source2), turns one of them to gray-scale, rotates the other one and then blends the images (as the screenshot demonstrates):

1: let toGray = Task.Factory.StartNew(fun () -> setToGray source1 layer1)
2: let rotate = Task.Factory.StartNew(fun () -> rotate source2 layer2)
3: Task.WaitAll(toGray, rotate)
4: blend layer1 layer2 blender

When working with tasks from F#, the best option is to use the Task type directly (it is also possible to write a computation builder for this, but that's a topic for another blog post). To create a new task, we use the Task.Factory property, which gives us a factory object that can be used for creating and scheduling tasks.

The StartNew method has several overloads. We're using an overload that takes a function that does not return a result (actually, the Action delegate). The functions we run draw the resulting image to layer1 and layer2 respectively. Once we start our tasks, we need to wait until both of them complete, which can be done using the Task.WaitAll method. Once the method completes, we can continue and blend the two generated images.

The Task Parallel Library (TPL) from .NET 4.0 provides many other methods for composing and working with tasks. We can wait for any of several tasks, specify a task that should be run when another task completes, create child tasks and so on. However, the F# code is relatively simple (and very similar to C#), so you can find examples of these techniques in the F# source for Parallel Programming with Microsoft .NET. Instead, I'll write about one case where F# behaves differently than C#...

Tasks and closures in C# and F#

When using tasks together with the for loop in C#, we can easily get into a situation that often causes confusion. he following example shows a snippet that creates an array of tasks and initializes the tasks in a loop. When creating the task, the loop variable i is used in the lambda function passed to the StartNew method. The variable is captured in a closure, which means that the lambda function keeps reference to it:

Task[] tasks = new Task[4];
for (int i = 0; i < 4; i++) {
    tasks[i] = Task.Factory.StartNew(() => 
        Console.WriteLine(i));
}
Task.WaitAll(tasks);

At the first sight, it would appear that the code should print 1,2,3,4, but that's not the case! The problem is that the lambda function (body of the task) does not keep the current value of the variable but a reference to the variable (allocated on a heap). The behavior of the program is non-deterministic, because we don't know when the tasks will be scheduled. In practice, the tasks typically run after the for loop completes, so it will print 4,4,4,4.

The problem is that i is a single variable that is mutated as the loop iterates. In order to fix the program in C#, we would need to declare a new variable (e.g. var temp = i) inside the body of the loop. This would declare a new variable each time the body is executed and so it will allocate new heap location (to store the value) for each iteration. Let's now look at the same example translated to F#:

1: let tasks = Array.zeroCreate 4
2: for i in 0 .. 3 do
3:     tasks.[i] <- Task.Factory.StartNew(fun () -> 
4:         Console.WriteLine(i))
5: Task.WaitAll(tasks)

If you run this version of code, it will always print 1,2,3,4 as expected. How is that possible? The reason is that F# interprets the for loop construct differently. Instead of declaring a mutable variable and changing it during the iteration, it creates a new immutable value for every iteration. This is a logical approach in F#, because mutable state is generally discouraged. As a result, the lambda function captures a reference to a value that will not be later changed.

This subtle difference between the two interpretations of the for loop can save you quite a headache when working with tasks. In fact, immutability can save you lot of troubles in general, because you can easily see which operations can be safely parallelized and which can not (this is also discussed in chapters 11 and 14 of my Real-World Functional Programming). The next snippet shows an F# example that behaves exactly as the original C# snippet, which means that it prints 4,4,4,4. As you can see we have to use reference cells. This makes the problem obvious:

1: let tasks = Array.zeroCreate 4
2: let i = ref 0 
3: while !i < 4 do
4:     tasks.[!i] <- Task.Factory.StartNew(fun () -> 
5:         Console.WriteLine(!i))
6:     i := !i + 1
7: Task.WaitAll(tasks)

If we want to capture mutable value in a closure in F#, we have to use reference cells (mutable values declared using let mutable cannot be captured). This makes the situation clearer, because reference cell is a heap allocated object that contains some mutable contents. In our example, we create a reference cell i that is modified as we iterate over the loop. The lambda function uses i, so the closure will keep a reference to the mutable heap allocated reference cell. When the task runs (after the while loop finishes), the reference cell will contain value 4.

Summary

In this article, we looked at several simpler examples from Parallel Programming with Microsoft .NET (mainly from chapters 2 and 3). We looked at several ways of implementing the "parallel loop" pattern in F#. One option is to use Parallel.For and Parallel.ForEach methods, which can be easily called directly from F#. Another option is to use (more declarative) Parallel LINQ library. The library can be either used directly (by calling extension methods) or using the PSeq module (available in F# PowerPack), which makes the API more F#-friendly.

Next, we looked at the key component from Task Parallel Library (TPL), which is a type Task that represents a unit of work. Tasks can be also easily created from F# using the Task.Factory.StartNew call (you'll find many other task-related operations in the book). As the last thing in this article, we also looked how immutability makes things easier. In particular, when creating task inside a for loop, we can easily make a mistake in C#, because the loop index variable is mutable. F# avoids this problem by treating the variable as a immutable value (newly created for every iteration).

Downloads and References

• Parallel Programming with Microsoft .NET - Book homepage at CodePlex
• F# Code Samples - Parallel Programming with Microsoft .NET