Shell sort, qsort recurisve, and threaded qsort.
Threaded qsort runs out of memory for creating new threads at around 600 threads.
Making the stack size smaller with NEED_STACK might be able to fix is but I couldn't work out how.
PTHREAD_THREADS_MAX is set to 16384 on this system so that is not the problem.
It relies on the fact that C++ vectors are stored in contiguous memory.
/*
* "The C++ Programming Language 3rd Ed. Bjarne Stroustrup Pg. 334"
* Copyright 2007 Timothy O'Hare
*/
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <pthread.h>
#include <memory>
using namespace std;
/*****************************************************
* template sort
*/
template<class T> void sort(vector<T>&); // declaration
void f(vector<int>& vi, vector<string>& vs)
{
time_t start = time(0);
sort(vi);
time_t taken = time(0) - start;
cout << "time taken for roll your own: " << taken << " secs" << endl;
sort(vs);
}
template<class T> void sort(vector<T>& v) // definition
// Shell sort (Knuth, Vol.13, pg.84)
{
const size_t n = v.size();
for (int gap=n/2; 0<gap; gap/=2)
for (int i=gap; i<n; i++)
for (int j=i-gap; 0<=j; j-=gap) {
//cout << "i:" << i << ", j:" << j << ", gap: " << gap << ", n:" << n << ", v[j]: " << v[j] << endl;
if (v[j+gap] < v[j])
swap(v[j], v[j+gap]);
}
}
/*****************************************************
* Log
*/
class Log {
public:
void co(string s);
static Log Instance();
ostream& operator << (ostream& os );
protected:
Log() { pthread_mutex_init(&logMutex, NULL); };
private:
static std::auto_ptr<Log> theSingleInstance;
//static Log * l;
pthread_mutex_t logMutex;
};
Log Log::Instance()
{
if (theSingleInstance.get() == 0)
theSingleInstance.reset (new Log);
return *theSingleInstance;
/*if (!l) {
l = new Log();
}
return *l;*/
}
void Log::co(string s)
{
pthread_mutex_lock(&logMutex);
cout << s;
pthread_mutex_unlock(&logMutex);
}
ostream& Log::operator << (ostream& os)
{
pthread_mutex_lock(&logMutex);
cout << os;
pthread_mutex_unlock(&logMutex);
}
/*****************************************************
* q sort
*/
template<class T> int partition(vector<T>& v, int left, int right, int pivot)
{
T pivotVal = v[pivot];
swap(v[pivot], v[right]);
int store = left;
for (int i = left; i < right; i++) {
if (v[i] < pivotVal) {
swap(v[i], v[store]);
store++;
}
}
swap(v[store], v[right]);
return store;
}
template<class T> void qsort(vector<T>& v, int left, int right)
{
if (right > left) {
int pivot = left;
int newPivot = partition(v, left, right, pivot);
//cout << "recursive newpviot: " << newPivot << ", left: " << left << ", right: " << newPivot-1 << endl;
qsort(v, left, newPivot-1);
//cout << "recursive newpviot: " << newPivot << ", left: " << newPivot+1 << ", right: " << right << endl;
qsort(v, newPivot+1, right);
}
}
/*****************************************************
* q sort threaded
*/
void prtv(string s, vector<int> &v)
{
ostringstream st;
Log log = Log::Instance();
if (v.size() > 1) {
st << s << ": size:" << v.size() << ":";
log.co(st.str());
st.str("");
for (int i = 0; i <= v.size()-2; i++) {
//cout << "v[" << i << "]:" << v[i] << ",";
st << v[i] << ",";
log.co(st.str ());
st.str("");
}
}
if (v.size() > 0) {
//cout << "v[" << v.size()-1 << "]:" << v[v.size()-1] << endl;
st << v[v.size()-1] << endl;
log.co(st.str());
st.str("");
} else {
st << s << ": size:" << v.size() << endl;
log.co(st.str());
st.str("");
}
}
int partition2(vector<int> &v, int left, int right, int pivot)
{
/*ostringstream st;
Log log = Log::Instance();
st << "End of partition: pivot: " << pivot << ", l: " << left << ", r: " << right << endl;
log.co(st.str());*/
int pivotVal = v[pivot];
swap(v[pivot], v[right]);
int store = left;
for (int i = left; i < right; i++) {
if (v[i] < pivotVal) {
swap(v[i], v[store]);
store++;
}
}
swap(v[store], v[right]);
//prtv("end of partition2", v);
return store;
}
typedef struct {
vector<int>& v;
int left;
int right;
} qs_t;
int threads;
void *qsort_threaded(void * q)
{
Log log = Log::Instance();
ostringstream s;
qs_t r1 = *(qs_t *)q;
vector<int> &v = r1.v;
int left = r1.left;
int right = r1.right;
qs_t r2 = *(qs_t *)q;
//vector<int> &v = r2.v;
//int left = r2.left;
//int right = r2.right;
//vector<int> &v = ((qs_t *)q)->v;
//int left = ((qs_t *)q)->left;
//int right = ((qs_t *)q)->right;
/*ostringstream st;
st << "begin: left " << left << ", right " << right << endl;
log.co(st.str());*/
//prtv("begin", v);
if (right > left) {
//int pivot = right/2;
int pivot = left;
int newPivot = partition2(v, left, right, pivot);
pthread_t *tid1 = NULL;
pthread_t *tid2 = NULL;
//s << "pivot:" << newPivot << ", left: " << left << ", right: " << right << endl;
//log.co(s.str());
r1.left = left;
r1.right = newPivot-1;
/*s.str("");
s << "th1: pivot:" << newPivot << ", left: " << r1.left << ", right: " << r1.right << endl;
log.co(s.str());*/
threads++;
tid1 = new pthread_t;
if (pthread_create(tid1, NULL, &qsort_threaded, (void*)&r1)) {
perror("Failed to create initial allocation thread 1:");
return (void*)-1;
}
r2.left = newPivot + 1;
r2.right = right;
/*s.str("");
s << "th2: pivot:" << newPivot << ", left: " << r2.left << ", right: " << r2.right << endl;
log.co(s.str());*/
threads++;
tid2 = new pthread_t;
if (pthread_create(tid2, NULL, &qsort_threaded, (void*)&r2)) {
perror("Failed to create initial allocation thread 2:");
return (void*)-1;
}
int i = 0;
if (tid1) {
if (0 != pthread_join(*tid1, NULL)) {
perror("pthread join tid1");
}
}
if (tid2) {
if (0 != pthread_join(*tid2, NULL)) {
perror("pthread join tid2");
}
}
} /*else {
st.str("");
st << "end: left " << left << " <= right " << right << endl;
log.co(st.str());
}*/
/* for (int j=0; j<v.size()-1; j++) {
t[j] = v[j];
}*/
return (void*)0;
}
std::auto_ptr<Log> Log::theSingleInstance;
int main(int argc, char * argv[])
{
vector<int> vi;
threads = 0;
// create a vector of random ints
int loop_cnt;
if (argc == 1)
loop_cnt = 600;
else
loop_cnt = atoi(argv[1]);
srand(time(NULL));
for( int i = 0; i < loop_cnt; i++ ) {
int num = (int) rand() % loop_cnt;
vi.push_back(num);
//cout << num << ",";
}
//cout << endl;
// copy it
vector<int> vi_builtin(vi);
vector<int> vi_qsort(vi);
vector<int> vi_qsort_threaded(vi);
// create a vector of strings
vector<string> vs;
vs.push_back("1");
vs.push_back("zerbra");
vs.push_back("towel");
vs.push_back("shovel");
vs.push_back("apple");
// built in sort
time_t start = time(0);
sort(vi_builtin.begin(), vi_builtin.end());
time_t taken = time(0) - start;
cout << "time taken for builtin: " << taken << " secs" << endl;
// qsort
start = time(0);
qsort(vi_qsort, 0, vi_qsort.size()-1);
taken = time(0) - start;
cout << "time taken for qsort: " << taken << " secs" << endl;
// qsort threaded
qs_t q = {vi_qsort_threaded, 0, vi_qsort_threaded.size()-1};
start = time(0);
qsort_threaded((void*)&q);
taken = time(0) - start;
cout << "time taken for qsort threaded: " << taken << " secs" << endl;
// shell sort
f(vi, vs);
// check if any values are different
for( int i = 0; i < vi.size(); i++ ) {
if (vi[i] != vi_builtin[i] ||
vi_qsort[i] != vi_builtin[i] ||
vi_qsort_threaded[i] != vi_builtin[i] )
cerr << "vi[i] " << vi[i] << " != " << vi_builtin[i]
<< " or vi_qsort[i] " << vi_qsort[i]
<< " or vi_qsort_threaded[i] " << vi_qsort_threaded[i] << endl;
}
// print them out
/*cout << "qsort_threaded result" << endl;
for( int i = 0; i < vi_qsort_threaded.size(); i++ ) {
cout << vi_qsort_threaded[i] << ",";
}
cout << endl;*/
cout << "thread count: " << threads << endl;
return 0;
}
The underlying infrastructure has always been a challenge. You have to buy, power, install, and manage a lot of servers. Even if you 
Well, just to remind you, Visual Studio project file is MSBuild script file and so each project can be built using "MSBuild MySuperProject.csproj" command. So most people have build script already, but they never use it outside Visual Studio, which is where you are completely to the point.
Oleg Tkachenko on November 1, 2007 03:30 AM