multithreaded quick sort algorithm, in C? I am looking for suggestions to make it run faster. I am trying to get closer to the qsort function's time. I don't want anything too complicated, like thread pooling. Here is the code: #include #include #include #include #include #include #define SORT_THRESHOLD 40 typedef struct _sortParams { char** array; int left; int right; int* threadsLeft; // A counter to keep track of how many more threads are available to be created. pthread_mutex_t* mutex; } SortParams; static int maximumThreads; /* maximum # of threads to be used */ static void insertSort(char** array, int left, int right) { int i, j; for (i = left + 1; i <= right; i++) { char* pivot = array[i]; j = i - 1; while (j >= left && (strcmp(array[j], pivot) > 0)) { array[j + 1] = array[j]; j--; } array[j + 1] = pivot; } } /** * This function uses a mutex to atomically decrement the threadsLeft shared variable by a certain amount. * @param mutex * @param numThreadsLeft * @param amount */ void decrementThreadsLeft(pthread_mutex_t* mutex, int* numThreadsLeft, int amount) { pthread_mutex_lock(mutex); *numThreadsLeft -= amount; pthread_mutex_unlock(mutex); } /** * This function uses a mutex to atomically increment the threadsLeft shared variable by a certain amount. * @param mutex * @param numThreadsLeft * @param amount */ void incrementThreadsLeft(pthread_mutex_t* mutex, int* numThreadsLeft, int amount) { pthread_mutex_lock(mutex); *numThreadsLeft += amount; pthread_mutex_unlock(mutex); } static void quickSort(void* p) { SortParams* params = (SortParams*)p; char** array = params->array; int left = params->left; int right = params->right; int i = left, j = right; if (j - i > SORT_THRESHOLD) { int m = (i + j) >> 1; char* temp, *pivot; if (strcmp(array[i], array[m]) > 0) { temp = array[i]; array[i] = array[m]; array[m] = temp; } if (strcmp(array[m], array[j]) > 0) { temp = array[m]; array[m] = array[j]; array[j] = temp; if (strcmp(array[i], array[m]) > 0) { temp = array[i]; array[i] = array[m]; array[m] = temp; } } pivot = array[m]; for (;;) { while (strcmp(array[i], pivot) < 0) i++; while (strcmp(array[j], pivot) > 0) j--; if (i < j) { char* temp = array[i]; array[i++] = array[j]; array[j--] = temp; } else if (i == j) { i++; j--; } else break; } SortParams first, second; first = *params; first.left = left; first.right = j; second = *params; second.left = i; second.right = right; if (*params->threadsLeft > 1) { pthread_t leftThread, rightThread; //Create a thread for each partition pthread_create(&leftThread, NULL, (void* (*)(void*))quickSort, (void*)&first); pthread_create(&rightThread, NULL, (void* (*)(void*))quickSort, (void*)&second); decrementThreadsLeft(params->mutex, params->threadsLeft, 2); pthread_join(leftThread, NULL); pthread_join(rightThread, NULL); incrementThreadsLeft(params->mutex, params->threadsLeft, 2); } else { //If there are no threads available, just use recursive calls. quickSort(&first); quickSort(&second); } } else insertSort(array, i, j); } void setSortThreads(int count) { maximumThreads = count; } void sortThreaded(char** array, unsigned int count) { pthread_mutex_t mutex; int err = pthread_mutex_init(&mutex, NULL); if (err != 0) { fprintf(stderr, "Failed to initialize mutex\n"); exit(err); } int threadsLeft = maximumThreads; SortParams parameters = {array, 0, count-1, &threadsLeft, &mutex}; quickSort(¶meters); pthread_mutex_destroy(&mutex); }

multithreaded quick sort algorithm, in C? I am looking for suggestions to make it run faster. I am trying to get closer to the qsort function's time. I don't want anything too complicated, like thread pooling. Here is the code: #include #include #include #include #include #include #define SORT_THRESHOLD 40 typedef struct _sortParams { char** array; int left; int right; int* threadsLeft; // A counter to keep track of how many more threads are available to be created. pthread_mutex_t* mutex; } SortParams; static int maximumThreads; /* maximum # of threads to be used */ static void insertSort(char** array, int left, int right) { int i, j; for (i = left + 1; i <= right; i++) { char* pivot = array[i]; j = i - 1; while (j >= left && (strcmp(array[j], pivot) > 0)) { array[j + 1] = array[j]; j--; } array[j + 1] = pivot; } } /** * This function uses a mutex to atomically decrement the threadsLeft shared variable by a certain amount. * @param mutex * @param numThreadsLeft * @param amount / void decrementThreadsLeft(pthread_mutex_t mutex, int* numThreadsLeft, int amount) { pthread_mutex_lock(mutex); *numThreadsLeft -= amount; pthread_mutex_unlock(mutex); } /** * This function uses a mutex to atomically increment the threadsLeft shared variable by a certain amount. * @param mutex * @param numThreadsLeft * @param amount / void incrementThreadsLeft(pthread_mutex_t mutex, int* numThreadsLeft, int amount) { pthread_mutex_lock(mutex); numThreadsLeft += amount; pthread_mutex_unlock(mutex); } static void quickSort(void p) { SortParams* params = (SortParams*)p; char** array = params->array; int left = params->left; int right = params->right; int i = left, j = right; if (j - i > SORT_THRESHOLD) { int m = (i + j) >> 1; char* temp, pivot; if (strcmp(array[i], array[m]) > 0) { temp = array[i]; array[i] = array[m]; array[m] = temp; } if (strcmp(array[m], array[j]) > 0) { temp = array[m]; array[m] = array[j]; array[j] = temp; if (strcmp(array[i], array[m]) > 0) { temp = array[i]; array[i] = array[m]; array[m] = temp; } } pivot = array[m]; for (;;) { while (strcmp(array[i], pivot) < 0) i++; while (strcmp(array[j], pivot) > 0) j--; if (i < j) { char temp = array[i]; array[i++] = array[j]; array[j--] = temp; } else if (i == j) { i++; j--; } else break; } SortParams first, second; first = params; first.left = left; first.right = j; second = params; second.left = i; second.right = right; if (params->threadsLeft > 1) { pthread_t leftThread, rightThread; //Create a thread for each partition pthread_create(&leftThread, NULL, (void ()(void))quickSort, (void)&first); pthread_create(&rightThread, NULL, (void ()(void))quickSort, (void*)&second); decrementThreadsLeft(params->mutex, params->threadsLeft, 2); pthread_join(leftThread, NULL); pthread_join(rightThread, NULL); incrementThreadsLeft(params->mutex, params->threadsLeft, 2); } else { //If there are no threads available, just use recursive calls. quickSort(&first); quickSort(&second); } } else insertSort(array, i, j); } void setSortThreads(int count) { maximumThreads = count; } void sortThreaded(char** array, unsigned int count) { pthread_mutex_t mutex; int err = pthread_mutex_init(&mutex, NULL); if (err != 0) { fprintf(stderr, "Failed to initialize mutex\n"); exit(err); } int threadsLeft = maximumThreads; SortParams parameters = {array, 0, count-1, &threadsLeft, &mutex}; quickSort(¶meters); pthread_mutex_destroy(&mutex); }

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

Is there a way to optimize the following multithreaded quick sort algorithm, in C? I am looking for suggestions to make it run faster. I am trying to get closer to the qsort function's time. I don't want anything too complicated, like thread pooling. Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <pthread.h>
#include <time.h>

#define SORT_THRESHOLD 40

typedef struct _sortParams {
char** array;
int left;
int right;
int* threadsLeft; // A counter to keep track of how many more threads are available to be created.
pthread_mutex_t* mutex;
} SortParams;

static int maximumThreads; /* maximum # of threads to be used */

static void insertSort(char** array, int left, int right) {
int i, j;
for (i = left + 1; i <= right; i++) {
char* pivot = array[i];
j = i - 1;
while (j >= left && (strcmp(array[j], pivot) > 0)) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = pivot;
}
}

/**
* This function uses a mutex to atomically decrement the threadsLeft shared variable by a certain amount.
* @param mutex
* @param numThreadsLeft
* @param amount
*/
void decrementThreadsLeft(pthread_mutex_t* mutex, int* numThreadsLeft, int amount) {
pthread_mutex_lock(mutex);
*numThreadsLeft -= amount;
pthread_mutex_unlock(mutex);
}

/**
* This function uses a mutex to atomically increment the threadsLeft shared variable by a certain amount.
* @param mutex
* @param numThreadsLeft
* @param amount
*/
void incrementThreadsLeft(pthread_mutex_t* mutex, int* numThreadsLeft, int amount) {
pthread_mutex_lock(mutex);
*numThreadsLeft += amount;
pthread_mutex_unlock(mutex);
}

static void quickSort(void* p) {
SortParams* params = (SortParams*)p;
char** array = params->array;
int left = params->left;
int right = params->right;
int i = left, j = right;

if (j - i > SORT_THRESHOLD) {
int m = (i + j) >> 1;
char* temp, *pivot;

if (strcmp(array[i], array[m]) > 0) {
temp = array[i]; array[i] = array[m]; array[m] = temp;
}
if (strcmp(array[m], array[j]) > 0) {
temp = array[m]; array[m] = array[j]; array[j] = temp;
if (strcmp(array[i], array[m]) > 0) {
temp = array[i]; array[i] = array[m]; array[m] = temp;
}
}
pivot = array[m];

for (;;) {
while (strcmp(array[i], pivot) < 0) i++;
while (strcmp(array[j], pivot) > 0) j--;
if (i < j) {
char* temp = array[i];
array[i++] = array[j];
array[j--] = temp;
}
else if (i == j) {
i++; j--;
}
else break;
}

SortParams first, second;
first = *params;
first.left = left; first.right = j;
second = *params;
second.left = i; second.right = right;

if (*params->threadsLeft > 1) {
pthread_t leftThread, rightThread;

//Create a thread for each partition
pthread_create(&leftThread, NULL, (void* (*)(void*))quickSort, (void*)&first);
pthread_create(&rightThread, NULL, (void* (*)(void*))quickSort, (void*)&second);
decrementThreadsLeft(params->mutex, params->threadsLeft, 2);

pthread_join(leftThread, NULL);
pthread_join(rightThread, NULL);
incrementThreadsLeft(params->mutex, params->threadsLeft, 2);
}
else {
//If there are no threads available, just use recursive calls.
quickSort(&first);
quickSort(&second);
}
}
else insertSort(array, i, j);
}

void setSortThreads(int count) {
maximumThreads = count;
}

void sortThreaded(char** array, unsigned int count) {
pthread_mutex_t mutex;
int err = pthread_mutex_init(&mutex, NULL);
if (err != 0) {
fprintf(stderr, "Failed to initialize mutex\n");
exit(err);
}
int threadsLeft = maximumThreads;
SortParams parameters = {array, 0, count-1, &threadsLeft, &mutex};
quickSort(&parameters);
pthread_mutex_destroy(&mutex);
}

Expert Solution

Step by step

Solved in 4 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.