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;
}
No comments:
Post a Comment