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:

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.

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

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

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:

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)

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

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.

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.

which is the same to the locking with keyword lock.

Full code base of algorithm

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.

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.