Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Parallel Operation Batching

Is there built-in support in the TPL (Task-Parallel-Library) for batching operations?

I was recently playing with a routine to carry out character replacement on a character array using a lookup table i.e. transliteration:

for (int i = 0; i < chars.Length; i++)
{
    char replaceChar;

    if (lookup.TryGetValue(chars[i], out replaceChar))
    {
        chars[i] = replaceChar;
    }
}

I could see that this could be trivially parallelized, so jumped in with a first stab which I knew would perform worse as the tasks were too fine-grained:

Parallel.For(0, chars.Length, i =>
{
    char replaceChar;

    if (lookup.TryGetValue(chars[i], out replaceChar))
    {
        chars[i] = replaceChar;
    }
});

I then reworked the algorithm to use batching so that the work could be chunked onto different threads in less fine-grained batches. This made use of threads as expected and I got some near linear speed up.

I'm sure that there must be built-in support for batching in the TPL. What is the syntax, and how do I use it?

const int CharBatch = 100;
int charLen = chars.Length;

Parallel.For(0, ((charLen / CharBatch) + 1), i =>
{
    int batchUpper = ((i + 1) * CharBatch);

    for (int j = i * CharBatch; j < batchUpper && j < charLen; j++)
    {
        char replaceChar;

        if (lookup.TryGetValue(chars[j], out replaceChar))
        {
            chars[j] = replaceChar;
        }
    }
});

Update

After using @Oliver's answer and replacing Parallel.For with a Parallel.ForEach and a Partitioner the code is as follows:

const int CharBatch = 100;

Parallel.ForEach(Partitioner.Create(0, chars.Length, CharBatch), range =>
{
    for (int i = range.Item1; i < range.Item2; i++)
    {
        char replaceChar;

        if (lookup.TryGetValue(chars[i], out replaceChar))
        {
            chars[i] = replaceChar;
        }
    }
});
like image 859
Tim Lloyd Avatar asked Jan 06 '11 08:01

Tim Lloyd


1 Answers

For better getting your head around you should get the Patterns for Parallel Programming: Understanding and Applying Parallel Patterns with the .NET Framework 4. It's a great source and explains the common ways on how to use the TPL.

Take a look at page 26 (Very small loop bodies). There you'll find this example:

Parallel.ForEach(Partitioner.Create(from, to), range =>
{
    for (int i = range.Item1; i < range.Item2; i++)
    {
        // ... process i
    }
});

So the missing piece you're searching is the System.Concurrent.Collections.Partitioner.

like image 191
Oliver Avatar answered Oct 05 '22 21:10

Oliver