In this post I will start with some time consuming algorithm, which is very simple and will move to decrease its execution time with using advantage of my two processors.

Time consuming algorithm

For example you have some complex calculations algorithm, which runs on array of dozens of elements. For simplicity let it be list of doubles like below:

      var
inputVector = new List<double>();
      for (int i = 0; i < 10000; i++)
        inputVector.Add(random.NextDouble());

All complex calculations that you do are located in class OneThreadAlgorithm. It goes through all array and gets index of the element, which is more closer to value d that you provide inside of method FindBestMatchingIndex.

  internal class OneThreadAlgorithm
  {
    public readonly List<double>
InputVector;
   
public OneThreadAlgorithm(List<double> inputVector)
    {
      InputVector = inputVector;
    }
    public int FindBestMatchingIndex(double d)
    {
      double
minDist = double.MaxValue;
      int bestInd
= -1;
      for (int i
= 0; i < InputVector.Count; i++)
      {
        var
currentDistance = DistanceProvider.GetDistance(InputVector[i],
d);
        if
(currentDistance < minDist)
        {
          minDist = currentDistance;
          bestInd = i;
 
      }
      }
 
    return bestInd;
    }
  }

If you are interested in DistanceProvider, it just returns between two double elements. Take a look on it.

  public static class
DistanceProvider
  {
    public static
double GetDistance(double val1, double
val2)
    {
     
for (int
i = 0; i < 10000; i++)i = i + 1 – 1;
      return Math.Abs(val1 – val2);
    }
  }

As you see I have some loop before returning value. It is needed to imitate hard calculations. I’m not using Thread.Sleep(), because there are some nuances, that will appear when we will move to multithreading, so I would I like to neglect them.

First change: dividing calculations to sections

As we see algorithm just loops through collection of values and finds some element. To make it going in few threads first we need to accommodate it. The intent of our accommodation is to divide calculations to sections, so we introduce following method

    public void FindBestMatchingIndexInRange(int start, int
end, double d)
    {
      double
minDist = double.MaxValue;
      int bestInd
= -1;
      for (int i
= start; i < end; i++)
      {
        var
currentDistance = DistanceProvider.GetDistance(InputVector[i],
d);
        if
(currentDistance < minDist)
        {
          minDist = currentDistance;
          bestInd = i;
 
      }
      }
      BestMatchingElements.Add(bestInd);
    }

So, what it does is the same that we had previously. Only the difference is that now we start searching for best matching indexes in range starting with index start and finishing with end, also we put result to the BestMatchingElements list. After we went through all sections we can find best matching element only in that list. See that below:

    public int FindBestMatchingIndex(double d)
    {
      double
minDist = double.MaxValue;
      int bestInd
= -1;
     
BestMatchingElements = new List<int>();
      int sectionLength = InputVector.Count /
ParallelingNumber;
      int start = 0;
      int end = sectionLength;
      for (int i = 0; i < ParallelingNumber; i++)
      {
       
FindBestMatchingIndexInRange(start, end, d);
        start = end;
   
    end += sectionLength;
        if (i == ParallelingNumber – 1) end =
InputVector.Count;
      }
      foreach (var
elementIndex in BestMatchingElements)
      {
        var currentDistance = DistanceProvider.GetDistance(InputVector[elementIndex],
d);
        if
(currentDistance < minDist)
        {
          minDist = currentDistance;
          bestInd = elementIndex;
        }
      }
      return bestInd;
 
  }

So now it works as well as before, theoretically it is a bit slower, and it does, especially when you divide array to lot of segments (number of segments we define with variable
ParallelingNumber
property).

Second modification: storing task information into one object

When we use multithreading we schedule method which represents public delegate void WaitCallback (Object state). So to accomplish this we create new class FindBestInRangeRequest and use it as an object that passes to changed method:

    public void FindBestMatchingIndexInRange(object bestInRangeRequest)

    {
      var request = (FindBestInRangeRequest)bestInRangeRequest;
      double minDist = double.MaxValue;
 
    int bestInd = -1;
      for (int i
= request.Start; i < request.End; i++)
   
  {

That new class FindBestInRangeRequest encapsulates Start, End, D and other values needed to schedule a threading task. See that class:

    internal class FindBestInRangeRequest
    {
      public int Start { get;
private set;
}
      public
int End { get;
private set;
}
      public
double D { get;
private set;
}
      public
ManualResetEvent Done { get; private
set; }
      public
FindBestInRangeRequest(int start, int end, double
d, ManualResetEvent
done)
      {
     
  Start = start;
        End = end;
        D = d;
       
Done = done;
      }
    }

As you see we are also passing the ManualResetEvent
object, which has method Set(), with using it we can identify that task execution has finished.

Third modification: Using ThreadPool

We can allocate threads manually, but that operation is very expensive, so it is strongly recommended to use ThreadPool.
So here is how we do use ThreadPool to call FindBestMatchingIndexInRange.

        var
bestInRangeRequest = new FindBestInRangeRequest(start,
end, d, DoneEvents[i]);
        ThreadPool.QueueUserWorkItem(FindBestMatchingIndexInRange,
bestInRangeRequest);

after we have scheduled all ranges we should ensure that all threads has synchronized. We could do this using

      WaitHandle.WaitAll(DoneEvents);

 method.
Another interesting thing is that saving into BestMatchingElements is not safe, so we use to unsure safe adding.

      Monitor.Enter(BestMatchingElements);
      BestMatchingElements.Add(bestInd);
      Monitor.Exit(BestMatchingElements);

which is the same to the locking with keyword lock.

Full code base of algorithm

  internal class MultiThreadAlgorithm
  {
    public int ParallelingNumber { get; private set; }
    private List<int>
BestMatchingElements { get; set; }
    private ManualResetEvent[] DoneEvents { get;
set; }
   
public readonly
List<double> InputVector;
    public
MultiThreadAlgorithm(List<double> inputVector, int parallelingNumber)
    {
      InputVector = inputVector;
      ParallelingNumber = parallelingNumber;
      DoneEvents = new
ManualResetEvent[ParallelingNumber];
    }
    public int FindBestMatchingIndex(double d)
    {
      double
minDist = double.MaxValue;
      int bestInd
= -1;
      BestMatchingElements = new List<int>();
     
for (int
i = 0; i < ParallelingNumber; i++)
      {
        DoneEvents[i] = new
ManualResetEvent(false);
      }
      int sectionLength = InputVector.Count /
ParallelingNumber;
      int start = 0;
      int end = sectionLength;
      for (int i = 0; i < ParallelingNumber; i++)
      {
        var bestInRangeRequest = new FindBestInRangeRequest(start,
end, d, DoneEvents[i]);
        ThreadPool.QueueUserWorkItem(FindBestMatchingIndexInRange,
bestInRangeRequest);
        start = end;
        end +=
sectionLength;
        if (i == ParallelingNumber – 1) end = InputVector.Count;
      }
      WaitHandle.WaitAll(DoneEvents);
      foreach (var elementIndex in
BestMatchingElements)
      {
        var
currentDistance = DistanceProvider.GetDistance(InputVector[elementIndex],
d);
        if
(currentDistance < minDist)
        {
          minDist = currentDistance;
          bestInd = elementIndex;
        }
      }
      return bestInd;
 
  }
    public void
FindBestMatchingIndexInRange(object
bestInRangeRequest)
    {
      var request
= (FindBestInRangeRequest)bestInRangeRequest;
      double
minDist = double.MaxValue;
      int bestInd
= -1;
      for (int i
= request.Start; i < request.End; i++)
   
  {
        var
currentDistance = DistanceProvider.GetDistance(InputVector[i],
request.D);
        if (currentDistance < minDist)
        {
          minDist =
currentDistance;
          bestInd = i;
        }
      }
      Monitor.Enter(BestMatchingElements);
      BestMatchingElements.Add(bestInd);
      Monitor.Exit(BestMatchingElements);
     
request.Done.Set();
    }
    internal class
FindBestInRangeRequest
    {
      public int
Start { get; private set; }
      public int End { get;
private set;
}
      public
double D { get;
private set;
}
      public
ManualResetEvent Done { get; private
set; }
      public
FindBestInRangeRequest(int start, int end, double
d, ManualResetEvent
done)
      {
     
  Start = start;
        End = end;
        D = d;
       
Done = done;
      }
    }
  }

Do you see how our class is cumbersome. So that is why do we call multithreading to be complex and not an easy to implement.

Does this pay off?
Of course, it does. I wrote this example, because I’ve been working on another, a bit more complex thing, but generally I did the same.

Here is output of execution of three variants of algorithm: simple, division to sections, multithreading.

One thread result = 9841. TIME: 0H:0M:2S:583ms
One thread with sections result = 9841. TIME: 0H:0M:2S:917ms
Multi threads result = 9841. TIME: 0H:0M:1S:939ms
Press any key to continue . . .

As could bee seen, multithreading variant is much-much faster. It could be even faster if I had more than two processors on my machine.

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInEmail this to someone