Comparing Parallel, PLinq & Simple Execution Of CPU Bound Work in .Net
For Parallel programming in C#, there is a diversity of libraries and tools that can be used to facilitate Parallel computing.
Parallel programming is used to split up CPU bound pieces of work and divide among multiple threads. This parallel processing recipes only consider CPU-bound work. If you have naturally asynchronous operations (such as I/O bound work) that you want to execute in parallel use async-await programming concepts instead.
Consider you have a collection of data, and you want to perform the same operation on each piece of data. This operation is CPU-bound and makes take some time. For solving this kind of situation we use, divide, and conquer techniques to make different parts that can be processed independently. So that, in the end, by aggregating the results we can produce the final result.
I want to show a simple sample that compares Parallel, Plinq, and simple execution in .Net.So, I chose the pattern matching algorithm for finding matching hits for a substring pattern in a long text.
So our Algorithm is like below code in C#:
public int CountPatternMatch(string pattern, string text)
{
int M = pattern.Length;
int N = text.Length;// create lps[] that will hold the longest
// prefix suffix values for pattern
int[] lps = new int[M];
int j = 0; // index for pat[]// Preprocess the pattern (calculate lps[]
// array)
computeLPSArray(pattern, M, lps);int i = 0; // index for txt[]
int res = 0;
int next_i = 0;while (i < N)
{
if (pattern[j] == text[i])
{
j++;
i++;
}
if (j == M)
{
// When we find pattern first time,
// we iterate again to check if there
// exists more pattern
j = lps[j - 1];
res++;// We start i to check for more than once
// appearance of pattern, we will reset i
// to previous start+1
if (lps[j] != 0)
i = ++next_i;
j = 0;
}// mismatch after j matches
else if (i < N && pattern[j] != text[i])
{
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
return res;
}void computeLPSArray(string pat, int M, int[] lps)
{
// length of the previous longest prefix suffix
int len = 0;
int i = 1;
lps[0] = 0; // lps[0] is always 0// the loop calculates lps[i] for i = 1 to M-1
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
if (len != 0)
{
len = lps[len - 1];// Also, note that we do not increment
// i here
}
else // if (len == 0)
{
lps[i] = len;
i++;
}
}
}
}
In Simple execution, there is just one thread to execute the algorithm in series.
var count = patternMatching.CountPatternMatch(pattern, text);But for Parallel execution, I want to use two different methods. The first one is using the Parallel type that contains a ForEach method specifically designed for this problem.
var paragraphs = text.Split('.');
object mutex = new object();
int count = 0;
Parallel.ForEach(source: paragraphs,
localInit: () => 0,
body: (paragraph, state, localValue) => localValue + patternMatching.CountPatternMatch(pattern, paragraph),
localFinally: localValue =>
{
lock (mutex)
count += localValue;
});One thing to keep in mind is that each parallel task may run on a different thread, so any shared state must be protected. In the above code, the count variable is a shared state that all the threads add their calculated results to it.
A similar solution is parallel LINQ (PLINQ), which provides much of the same capabilities with LINQ-like syntax.
One important note about PLINQ is that it assumes it can use all the cores on the computer, but, Parallel will dynamically react to changing CPU conditions.
Most developers are familiar with LINQ syntax.PLINQ extends this syntax sot support parallel processing. So, it is an ideal choice for stream scenarios, when you have a sequence of inputs and producing a sequence of outputs.
So our code in PLINQ is :
var paragraphs = text.Split('.');
var count = paragraphs.AsParallel().
Select(paragraph => patternMatching.CountPatternMatch(pattern, paragraph))
.Sum();In our parallel code in comparison with serial code, we divided our long text to short paragraphs by dot separator. But it could be any strategy to divide your processing data into shorter independent segments.
I have executed the above code with a sample long lorem ipsum text, and I have used onlinecharttool.com to depict a comparative chart.
This code has executed in a computer with Intel Core i7 7700 CPU 3.60GHz (8 CPU) and 16 GB of DDR4 memory.
So, as you see, to some extent simple serial execution has better execution time. But, from one point on, there is an exponential difference between parallel and serial execution. So you should find this breakthrough point in your problem, then decide about the parallel solution. Because in short scales serial execution is much better than the parallel one.
Another point that must be considered is that when the data going to be larger, the Parallel class little by little getting to have better execution time.
The Parallel class is good for many scenarios, but the PLINQ code is simpler when doing aggregation or transforming one sequence to another. Keep in mind that the Parallel class is more friendly to other processes on the system than PLINQ, this is specifically an important consideration if the parallel processing is done on a server machine.
Thanks
Resources:
Concurrency in C# Cookbook Asynchronous, Parallel, and Multithreaded Programming, Second Edition, Stephen Cleary
