Big Threading Problem

[compuKidd]

I need to do merge sort with threading but it seems to take more time with threading rather than no threading , and I have core quad!

please help

#include <iostream>
#include <fstream>
#include <windows.h>
#include <process.h>
#include <conio.h>
#include <time.h>

using namespace std;

int threadCount=0;

HANDLE ghMutex;

class mSortArg
{
public:
	int *a;
	int start;
	int end;
	int threads;

	mSortArg(int *A=NULL,int Start=0,int End=0,int Threads=0)
	{
		a=A;
		start=Start;
		end=End;
		threads=Threads;
	}
};

void merge(int a[],int s1,int e1,int s2,int e2)
{
	int s=(e1-s1+1)+(e2-s2+1);
	int *b=new int [s];
	int i1=s1;
	int i2=s2;
	int i=0;
	while(i1<=e1 && i2<=e2)
	{
		if(a[i1]<a[i2])
		{
			b[i]=a[i1];
			i1++;
		}
		else
		{
			b[i]=a[i2];
			i2++;
		}
		i++;
	}
	for(int j=i1;j<=e1;j++)
	{
		b[i]=a[j];
		i++;
	}
	for(int j=0;j<i;j++)
	{
		a[s1+j]=b[j];
	}
	delete []b;
}

void mergeSortHelp(int[],int,int,int);
unsigned __stdcall threadFunc(void *param)
{
	mSortArg *arg=(mSortArg*)param;

	mergeSortHelp(arg->a,arg->start,arg->end,arg->threads);

	WaitForSingleObject(ghMutex,INFINITE);
	threadCount--; //critical
	ReleaseMutex(ghMutex);
	_endthreadex(0);
	return 0;
}


void mergeSortHelp(int a[],int start,int end,int threads)
{
	if(start>=end)
		return;
	int mid=start+(end-start)/2;
	HANDLE th1=0;

	mSortArg *arg=NULL;
	WaitForSingleObject(ghMutex,INFINITE);
	if(threadCount<threads) // comparison is critical
	{
		threadCount++; //critical
		ReleaseMutex(ghMutex);

		arg=new mSortArg(a,start,mid,threads);
		th1=(HANDLE)_beginthreadex(NULL,0,threadFunc,arg,0,NULL);

	}
	else
	{
		ReleaseMutex(ghMutex);
		mergeSortHelp(a,start,mid,threads);
	}

	mergeSortHelp(a,mid+1,end,threads);
	WaitForSingleObject(th1,INFINITE);
	delete arg;	//shallow delete
	merge(a,start,mid,mid+1,end);
}

void mergeSort(int a[],int size,int threads)
{
	mergeSortHelp(a,0,size-1,threads);
}

int* mergeSort(char *fname,int threads,int &size)
{
	ifstream in(fname);
	in>>size;
	int *a=new int[size];
	for(int i=0;i<size;i++)
	{
		in>>a[i];
	}
	in.close();
	mergeSortHelp(a,0,size-1,threads);
	return a;
}

bool check(int a[],int s)
{
	for(int i=0;i<s-1;i++)
	{
		if(a[i]>a[i+1]) return 0;
	}
	return 1;
}
int main()
{
	ghMutex=CreateMutex(NULL,FALSE,NULL);
	ReleaseMutex(ghMutex); //just in case

	int N=100;

	clock_t t1=clock();
	int a[100]={0};
	for(int i=0;i<1000;i++)
	{
		mergeSort(a,N,0);// zero for no threading, put 1 for using only 1 thread, 2 for two threads ect...
	}
	clock_t t2=clock();
	double t=(t2-t1)/(CLOCKS_PER_SEC*1000.0);

	cerr<<t<<"s\n";
	if(check(a,N)) cerr<<"OK!\n";
	else cerr<<"oooops!!!\n";
}

any help is appreciated

[Lindley]

Unfortunately parallel sorting algorithms aren't really all that good. MergeSort is one that should be fairly parallelizable, though....

I'm suspicious of those four ReleaseMutex calls at the start of main(). First of all, I can't really see how a mutex would be necessary for a parallelized mergesort-----any parallel section should be working on disjoint data anyway. Second, releaseing a mutex before locking it is a bit strange.

This is enough to zero-initialize your array, incidentally:

int a[100]={0};

[_uj]

I need to do merge sort with threading but it seems to take more time with threading rather than no threading , and I have core quad!

Note that multithreading carries overhead so there's a threshold when the parallel algorithm starts beating the sequential one. N==100 may simply be too small. Try 1000, 10.000 or even 100.000.

[compuKidd]

Ok for sizes of 1,000->100,000 having one thread is better, but never 2 threads is better than 1 or 0 threads and never 3 is better than 2 and never 4 is better than 3 that's strange I thought threading is better than this.
if the overhead is that big why use it at all? I mean his assignment was to demonstrate that threading is better but it ended up worse

as for the mutex its just to keep the number of threads from exceeding a certain number.

any ideas how I can improve my results?

[TheCPUWizard]

<snip> that's strange I thought threading is better than this.</snip>

And what leads you to believe that the "problem" is with threading itself and not with your usage of it.

_uj brought up a critical point in dealing with threading. The overhead breaks down into three distinct domains.

1) Thread management overhead is the creation and destruction costs involved regardless of the work performed by the thread.

2) Resource contention overhead is anything that will block a thread outside of your control. For example if you are doing 100% compute bound work, and spin off more threads than there are processor units (CPU/Core/Ht), then you will likely see WORSE performance (or at least not better)

3) Synchronization overhead is anything your thread(s) are blocked explicitly waiting for another thread to complete some work so that data is available.

ANY implementation using multiple threads must address all three of these issues (ideally by emperical measurement).

[_uj]

that's strange I thought threading is better than this.

Although multithreading carries an overhead, that may not be the major problem in this case.

I suggest you set the sorting aside for a while and concentrate on getting the actual multithreading going. Let one task/thread do something simple like just looping and printing something every second or so. Then add a task/thread and make sure it runs in parallel. Then add more. You should note that each added task up to 4 (because you got a quad) increases the throughtput. You should also note that the processor utilization increases with 25% for each task (on Windows you can easily watch this using the Task Manager).

Regarding the efficiency of multithreading, using one task per thread is often called coarse-grain multitasking. A more efficient way is to use fine-grain multitasking. In this model a pool of threads are kept running all the time and some manager assigns logical tasks to be processed by idle threads. A smart manager can balance the workload very efficiently and to a great extent reduce the overhead associated with multitasking. But this is nothing you program yourself. Support for this is in the pipeline both for Java and .NET. And for native C++ you got the Intel TBB library for example.

[TheCPUWizard]

But this is nothing you program yourself. Support for this is in the pipeline both for Java and .NET. .

While you are correct that this will be "baked-in" as of .NET 4.0 (aka VS-2010), people have had an opportunity to work with it for over 6 months:
http://www.microsoft.com/downloads/d...displaylang=en

[_uj]

While you are correct that this will be "baked-in" as of .NET 4.0 (aka VS-2010), people have had an opportunity to work with it for over 6 months:
http://www.microsoft.com/downloads/d...displaylang=en

The same is true for Java. It's planned for the upcoming Java 7 but available already,

http://www.infoq.com/news/2007/07/concurrency-java-se-7

And here's TBB for C++ programmers,

http://www.threadingbuildingblocks.org/