Threaded merge sort slower than serial implementation

Question

For school we got a task to create a multithreaded application. We chose to make a multithreaded implementation of merge sort.

We however can't manage to make it work faster than the serial implementation.

I have already tried the following:

• implementation with unlimited threads (code example 1) (was extremely slow)
• implementation with limited threads (code example 2) (4 threads max - still really slow)
• implementation using Parallel.Invoke (code example 3) (still slower)
• complex implementation also with a parallel merge function (just shamefully slow)

When I use the analyze tools in Visual Studio (Instrumentation part) I found the timings for the functions called and the threaded solution is always extremely slower than the serial implementation.

I can't see any possible reason for this.

(for example: with 5000000 numbers to sort; serial implementation: 16.717,17; parallel: 20.259,97; results with just 1 extra thread)

I tested it on both machines I own:

• Intel Core 2 Quad Q9450 @ 2.66Ghz
• Intel Core i7 Q720 @1.60Ghz

I can't for my life figure out how this is possible, shouldn't this just speed up the process?

I would be really greatefull if somebody would be able to help me out.

code example 1:

ParallelMerge pMerge = new ParallelMerge(T, p1, q1 -1, p2, q2-1, A, p3);
Thread thread = new Thread(new ThreadStart(pMerge.parallel_merge));
thread.Start();

ParallelMerge pMerge2 = new ParallelMerge(T, q1 + 1, r1, q2, r2, A, q3 + 1);
pMerge2.parallel_merge();
thread.Join();

code example 2:

if(depthRemaining > 0)
{
   ParallelMerge pMerge = new ParallelMerge(T, p1, q1 -1, p2, q2-1, A, p3);
   thread thread = new Thread(new ThreadStart(pMerge.parallel_merge));
   thread.Start();
   ParallelMerge pMerge2 = new ParallelMerge(T, q1 + 1, r1, q2, r2, A, q3 + 1);
   pMerge2.parallel_merge(); 
   thread.Join();
}
else
{
   ParallelMerge pMerge = new ParallelMerge(T, p1, q1 -1, p2, q2-1, A, p3);
   pMerge.parallel_merge(); 
   ParallelMerge pMerge2 = new ParallelMerge(T, q1 + 1, r1, q2, r2, A, q3 + 1);
   pMerge.parallel_merge(); 
}

code example 3:

if (depthRemaining > 0)
{
   Parallel.Invoke(
      () => threaded_merge_sort(getallen, p, q, depthRemaining-1));

   threaded_merge_sort(getallen, q + 1, r, 0);
}
else
{
   threaded_merge_sort(getallen, p, q, 0);
   threaded_merge_sort(getallen, q+1, r, 0);
}

Answer 1

What unit of time are you reporting in?

Starting a new thread is a 'slow' operation. Sorting/merging very short list using multi threading can be a bit slower.

If you just split the length of the number list in halve does the program run faster? if not you're code simply doesn't scale.

Answering this question without the actual code implementation is a bit hard to do.