7

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?

  • The main heuristic is either code paths that are hard work for the CPU (e.g. complex calculations on large data sets, using algorithms amenable to parallelisation - or graphics manipulations), or data queries that are executed over a network against independent sources. – Steve Jan 4 '18 at 18:40
3

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.

| improve this answer | |
  • 2
    One nitpicking detail: your first example makes use of the associatice property of addition, not of its commutative property. – Doc Brown Jan 12 '18 at 7:07
  • @DocBrown Ah yes, thank-you. I probably should have spent more time Googling (or actually reading the wiki pages), as it's been quite awhile since I've had a math class :) – svidgen Jan 15 '18 at 15:32
10

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

| improve this answer | |
  • 1
    A nitpick: a discrete task can have side effects, as long as those side effects don't affect the work that is done by other tasks. – Bart van Ingen Schenau Jan 4 '18 at 20:41
  • @BartvanIngenSchenau: True. But one of the big draws to functional programming is that its "purity" characteristics make it much easier to reason about in this parallel fashion. – Robert Harvey Jan 4 '18 at 20:50
  • True, but your post could lead to the wrong conclusion that an in-place modification of an array (such as in-place sorting) can't be split in multiple tasks because each task has a side-effect on a part of the array. – Bart van Ingen Schenau Jan 4 '18 at 22:19
  • 2
    @BartvanIngenSchenau: The code example I provided does exactly that. – Robert Harvey Jan 4 '18 at 22:23
  • Also, you can in fact have side effects affecting the work done by other tasks so long as you make sure that the shared parts that have side effects only have one thread accessing the shared part at a time. A lock/mutex is the normal way to ensure that. For example, you could have multiple tasks that all process objects in a queue. They're sharing a queue, so only one can access that queue at a time (otherwise they might grab the same object!). Yet, it's a good candidate for parallelization because all the rest of the work isn't going to interfere with each other. – Kat Jan 9 '18 at 20:17
0

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.)

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.