Like 0
Fork 0

Last active 5 months ago

mga's Avatar mga revised this gist 5 months ago. Go to revision

1 file changed, 213 insertions

main.c(file created)

@@ -0,0 +1,213 @@
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 + }
Newer Older

Powered by Opengist ⋅ Load: 98ms⋅

English