Parallele quick sort

main.c · 6.2 KiB · C Raw

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

#define INSERTION_SORT_THRESHOLD 50
#define BLOCKSIZE 256
#define min(a, b) ((a) < (b) ? (a) : (b))
#define swap(a, b)                                                             \
  {                                                                            \
    a ^= b;                                                                    \
    b ^= a;                                                                    \
    a ^= b;                                                                    \
  }

typedef struct {
  int *array;
  int left;
  int right;
  int depth;
} quicksort_args;

int max_threads;
int current_threads = 1;
pthread_mutex_t thread_lock = PTHREAD_MUTEX_INITIALIZER;

// Insertion sort for small ranges
void insert_sort(int *left, int *right) {
  for (int *pi = left + 1; pi <= right; pi++) {
    if (*pi < *left)
      swap(*pi, *left);
  }
  for (int *pi = left + 2; pi <= right; pi++) {
    int h = *pi;
    int *pj = pi - 1;
    while (h < *pj) {
      *(pj + 1) = *pj;
      pj--;
    }
    *(pj + 1) = h;
  }
}

// Median-of-three
#define sort3fast(a, b, c)                                                     \
  if (b < a) {                                                                 \
    if (c < a) {                                                               \
      if (c < b) {                                                             \
        swap(a, c);                                                            \
      } else {                                                                 \
        int h = a;                                                             \
        a = b;                                                                 \
        b = c;                                                                 \
        c = h;                                                                 \
      }                                                                        \
    } else {                                                                   \
      swap(a, b);                                                              \
    }                                                                          \
  } else {                                                                     \
    if (c < b) {                                                               \
      if (c < a) {                                                             \
        int h = c;                                                             \
        c = b;                                                                 \
        b = a;                                                                 \
        a = h;                                                                 \
      } else {                                                                 \
        swap(b, c);                                                            \
      }                                                                        \
    }                                                                          \
  }

// Hoare’s partition with median-of-three
void partition(int *left0, int *right0, int **l1, int **r1, int **l2,
               int **r2) {

int *mid = left0 + (right0 - left0) / 2;
  int piv = *mid;
  *mid = *(left0 + 1);
  sort3fast(*left0, piv, *right0);
  *(left0 + 1) = piv;

int *left = left0 + 1;
  int *right = right0;

while (1) {
    while (*++left < piv)
      ;
    while (*--right > piv)
      ;
    if (left >= right)
      break;
    swap(*left, *right);
  }

*(left0 + 1) = *right;
  *right = piv;

if (right < mid) {
    *l1 = left0;
    *r1 = right - 1;
    *l2 = right + 1;
    *r2 = right0;
  } else {
    *l1 = right + 1;
    *r1 = right0;
    *l2 = left0;
    *r2 = right - 1;
  }
}

// Recursive quicksort, parallelized
void *parallel_quicksort(void *args) {
  quicksort_args *qargs = (quicksort_args *)args;
  int *array = qargs->array;
  int left = qargs->left;
  int right = qargs->right;
  int depth = qargs->depth;

while (right - left >= INSERTION_SORT_THRESHOLD) {
    int *l, *r, *l2, *r2;
    partition(array + left, array + right, &l, &r, &l2, &r2);
    int l_idx = l - array;
    int r_idx = r - array;
    int l2_idx = l2 - array;
    int r2_idx = r2 - array;

int spawn = 0;
    pthread_t thread;
    quicksort_args *right_args = malloc(sizeof(quicksort_args));
    right_args->array = array;
    right_args->left = l2_idx;
    right_args->right = r2_idx;
    right_args->depth = depth + 1;

pthread_mutex_lock(&thread_lock);
    if (current_threads < max_threads) {
      current_threads++;
      spawn = 1;
    }
    pthread_mutex_unlock(&thread_lock);

if (spawn) {
      pthread_create(&thread, NULL, parallel_quicksort, right_args);
    } else {
      parallel_quicksort(right_args);
      free(right_args);
    }

quicksort_args left_args = {array, l_idx, r_idx, depth + 1};
    parallel_quicksort(&left_args);

if (spawn) {
      pthread_join(thread, NULL);
      pthread_mutex_lock(&thread_lock);
      current_threads--;
      pthread_mutex_unlock(&thread_lock);
      free(right_args);
    }

return NULL;
  }

// small array — do insertion sort
  insert_sort(array + left, array + right);

if (depth == 0)
    free(qargs);
  return NULL;
}

int get_named_arg(int argc, char *argv[], const char *name) {
  for (int i = 1; i < argc - 1; ++i) {
    if (strcmp(argv[i], name) == 0) {
      return atoi(argv[i + 1]);
    }
  }
  return -1;
}

int main(int argc, char **argv) {
  int power = get_named_arg(argc, argv, "--size");
  max_threads = get_named_arg(argc, argv, "--threads");

if (power < 1 || max_threads < 1) {
    fprintf(stderr, "Usage: %s --threads <num> --size <log10(size)>\n",
            argv[0]);
    return EXIT_FAILURE;
  }

int n = (int)pow(10, power);
  int *array = (int *)malloc(n * sizeof(int));
  if (!array) {
    perror("malloc");
    return EXIT_FAILURE;
  }

srand(time(NULL));
  for (int i = 0; i < n; i++)
    array[i] = rand();

quicksort_args *args = malloc(sizeof(quicksort_args));
  args->array = array;
  args->left = 0;
  args->right = n - 1;
  args->depth = 0;

parallel_quicksort(args);

free(array);
  return 0;
}

1	#include <math.h>
2	#include <pthread.h>
3	#include <stdio.h>
4	#include <stdlib.h>
5	#include <string.h>
6	#include <time.h>
7
8	#define INSERTION_SORT_THRESHOLD 50
9	#define BLOCKSIZE 256
10	#define min(a, b) ((a) < (b) ? (a) : (b))
11	#define swap(a, b) \
12	{ \
13	a ^= b; \
14	b ^= a; \
15	a ^= b; \
16	}
17
18	typedef struct {
19	int *array;
20	int left;
21	int right;
22	int depth;
23	} quicksort_args;
24
25	int max_threads;
26	int current_threads = 1;
27	pthread_mutex_t thread_lock = PTHREAD_MUTEX_INITIALIZER;
28
29	// Insertion sort for small ranges
30	void insert_sort(int left, int right) {
31	for (int *pi = left + 1; pi <= right; pi++) {
32	if (pi < left)
33	swap(pi, left);
34	}
35	for (int *pi = left + 2; pi <= right; pi++) {
36	int h = *pi;
37	int *pj = pi - 1;
38	while (h < *pj) {
39	(pj + 1) = pj;
40	pj--;
41	}
42	*(pj + 1) = h;
43	}
44	}
45
46	// Median-of-three
47	#define sort3fast(a, b, c) \
48	if (b < a) { \
49	if (c < a) { \
50	if (c < b) { \
51	swap(a, c); \
52	} else { \
53	int h = a; \
54	a = b; \
55	b = c; \
56	c = h; \
57	} \
58	} else { \
59	swap(a, b); \
60	} \
61	} else { \
62	if (c < b) { \
63	if (c < a) { \
64	int h = c; \
65	c = b; \
66	b = a; \
67	a = h; \
68	} else { \
69	swap(b, c); \
70	} \
71	} \
72	}
73
74	// Hoare’s partition with median-of-three
75	void partition(int left0, int right0, int l1, int r1, int **l2,
76	int **r2) {
77
78	int *mid = left0 + (right0 - left0) / 2;
79	int piv = *mid;
80	mid = (left0 + 1);
81	sort3fast(left0, piv, right0);
82	*(left0 + 1) = piv;
83
84	int *left = left0 + 1;
85	int *right = right0;
86
87	while (1) {
88	while (*++left < piv)
89	;
90	while (*--right > piv)
91	;
92	if (left >= right)
93	break;
94	swap(left, right);
95	}
96
97	(left0 + 1) = right;
98	*right = piv;
99
100	if (right < mid) {
101	*l1 = left0;
102	*r1 = right - 1;
103	*l2 = right + 1;
104	*r2 = right0;
105	} else {
106	*l1 = right + 1;
107	*r1 = right0;
108	*l2 = left0;
109	*r2 = right - 1;
110	}
111	}
112
113	// Recursive quicksort, parallelized
114	void parallel_quicksort(void args) {
115	quicksort_args qargs = (quicksort_args )args;
116	int *array = qargs->array;
117	int left = qargs->left;
118	int right = qargs->right;
119	int depth = qargs->depth;
120
121	while (right - left >= INSERTION_SORT_THRESHOLD) {
122	int l, r, l2, r2;
123	partition(array + left, array + right, &l, &r, &l2, &r2);
124	int l_idx = l - array;
125	int r_idx = r - array;
126	int l2_idx = l2 - array;
127	int r2_idx = r2 - array;
128
129	int spawn = 0;
130	pthread_t thread;
131	quicksort_args *right_args = malloc(sizeof(quicksort_args));
132	right_args->array = array;
133	right_args->left = l2_idx;
134	right_args->right = r2_idx;
135	right_args->depth = depth + 1;
136
137	pthread_mutex_lock(&thread_lock);
138	if (current_threads < max_threads) {
139	current_threads++;
140	spawn = 1;
141	}
142	pthread_mutex_unlock(&thread_lock);
143
144	if (spawn) {
145	pthread_create(&thread, NULL, parallel_quicksort, right_args);
146	} else {
147	parallel_quicksort(right_args);
148	free(right_args);
149	}
150
151	quicksort_args left_args = {array, l_idx, r_idx, depth + 1};
152	parallel_quicksort(&left_args);
153
154	if (spawn) {
155	pthread_join(thread, NULL);
156	pthread_mutex_lock(&thread_lock);
157	current_threads--;
158	pthread_mutex_unlock(&thread_lock);
159	free(right_args);
160	}
161
162	return NULL;
163	}
164
165	// small array — do insertion sort
166	insert_sort(array + left, array + right);
167
168	if (depth == 0)
169	free(qargs);
170	return NULL;
171	}
172
173	int get_named_arg(int argc, char argv[], const char name) {
174	for (int i = 1; i < argc - 1; ++i) {
175	if (strcmp(argv[i], name) == 0) {
176	return atoi(argv[i + 1]);
177	}
178	}
179	return -1;
180	}
181
182	int main(int argc, char **argv) {
183	int power = get_named_arg(argc, argv, "--size");
184	max_threads = get_named_arg(argc, argv, "--threads");
185
186	if (power < 1 \|\| max_threads < 1) {
187	fprintf(stderr, "Usage: %s --threads <num> --size <log10(size)>\n",
188	argv[0]);
189	return EXIT_FAILURE;
190	}
191
192	int n = (int)pow(10, power);
193	int array = (int )malloc(n * sizeof(int));
194	if (!array) {
195	perror("malloc");
196	return EXIT_FAILURE;
197	}
198
199	srand(time(NULL));
200	for (int i = 0; i < n; i++)
201	array[i] = rand();
202
203	quicksort_args *args = malloc(sizeof(quicksort_args));
204	args->array = array;
205	args->left = 0;
206	args->right = n - 1;
207	args->depth = 0;
208
209	parallel_quicksort(args);
210
211	free(array);
212	return 0;
213	}
214