How do I know if a set of code is a good candidate for parallelization?

Question

How can I tell in an application if there are parts that will benefit from using the C# Task library (I believe that is the Parallel processing library.)

Given other optimizations have been done, how do I know other than just try it? In C#, can I use Visual Studio for this analysis?

Answer 1

I'd suggest that it's about whether large chunks of work can be executed independently, in mostly-any order, without yielding different results. (Unless variations are acceptable or good.)

Three candidates I'd look for:

• Time-consuming iterations wherein processing order won't change the outcome.
• You discover DoWork() needs to happen before you need the results.
• You discover DoWork() needs to happen and you don't need results at all.

In all three cases, ensure that the impact on shared state is manageable or non-existent.

And, bear in mind that these are just candidates. You need to assess how much work needs to be done and how entangled (or non-tangled) that work is with all the other work the application could be doing. And, then you would ideally benchmark both solutions.

---

For example ...

A time-consuming iteration wherein processing order doesn't matter.

You have a massive List<Int32> data for which you need to compute the average as fast as possible. Building an average is primarily addition, which is associative. So, we can perform the addition in Task-able chunks:

avg(data[0..z]) == ( sum(data[0..n]) + sum(data[n..m]) .. sum(data[x..z]) ) / data.Count;

^{(This can actually be broken down in a more sophisticated, cluster-capable manner; but, it's an example...)}

I know that DoWork() needs to happen before you need its results.

You're rendering a document. On that document, you have N components of various types (images, formatted text blocks, graphs, etc.). To simplify it, in this scenario, each component can render itself completely independently and return a graphical component to the LayoutEngine. And, the LayoutEngine needs to wait for each component to render and return its dimensions before it can position them and feed them to the DisplayEngine ... or whatever.

I don't need the results of DoWork() at all.

Certain kinds of logging.

If you're logging application interactions to support marking efforts, for example, you might want to fire-and-forget about those logging events. If logging takes a long time or fails, you don't want to disrupt the operation or performance of the application.

Answer 2

You know code is a good candidate for parallelization when it can be broken into a set of "discrete" (i.e. independent) tasks. A discrete task is one that produces a specific result and has no side effects that compete with other tasks, i.e. a self-contained item of work.

Consider this parallel recursive quicksort algorithm:

private void QuicksortSequential<T>(T[] arr, int left, int right) 
where T : IComparable<T>
{
    if (right > left)
    {
        int pivot = Partition(arr, left, right);
        QuicksortSequential(arr, left, pivot - 1);
        QuicksortSequential(arr, pivot + 1, right);
    }
}

private void QuicksortParallelOptimised<T>(T[] arr, int left, int right) 
where T : IComparable<T>
{
    const int SEQUENTIAL_THRESHOLD = 2048;
    if (right > left)
    {
        if (right - left < SEQUENTIAL_THRESHOLD)
        {

            QuicksortSequential(arr, left, right);
        }
        else
        {
            int pivot = Partition(arr, left, right);
            Parallel.Do(
                () => QuicksortParallelOptimised(arr, left, pivot - 1),
                () => QuicksortParallelOptimised(arr, pivot + 1, right));
        }
    }
}

Notice the Parallel.Do at the bottom. This is where the parallelization takes place; it works because none of those calls to QuicksortParallelOptimised will interfere with each other.

To parallelize your own code, you should rewrite it in such a way that it can be expressed as a series of independent functions that each accept some parameters and return a Task<T>. You can then run those functions in parallel, and combine the results on completion.

Further Reading
How to: Write a Simple Parallel.ForEach Loop

Answer 3

one good indicator is: if you execute code to do something very often (for example for each file in a folder) and this particular executions are independent of each other. this is a trivial part, the pure "function-layer".

the non trivial part is the "design layer": if you want to to parallel something to speed up, you should analyze your program: which parts of your program takes the most time? maybe you can find functions which will be executed oftener than required? then you can re-design your application regarding this. (design a program with the aim to speed up your program can maybe cause less readability. here you should ponder on the value of speed and readability and yan hopefully find a compromise.)