qsort_perf.c
1 /* 2 * Randomized test for qsort() routine. 3 * 4 * Includes code derived from stdlib/FreeBSD/qsort.c and the copyright header 5 * in that file applies. 6 */ 7 8 #include <sys/cdefs.h> 9 10 #include <assert.h> 11 #include <stdio.h> 12 #include <stdlib.h> 13 #include <darwintest.h> 14 #include <darwintest_utils.h> 15 16 static void qsort1(void *aa, size_t n, size_t es, 17 int (*cmp)(const void *, const void *)); 18 19 static int 20 cmp_int(const void *aa, const void *bb) 21 { 22 int a, b; 23 24 a = *(const int *)aa; 25 b = *(const int *)bb; 26 return(a - b); 27 } 28 29 #define nelm 1000000 30 31 T_DECL(qsort_perf, "qsort perf test", T_META_CHECK_LEAKS(NO)) 32 { 33 int i; 34 int arr[nelm]; 35 int save[nelm]; 36 uint64_t time_elapsed; 37 38 // ----- 25-75 ----- 39 40 int k = nelm/4; 41 for (i = 0; i < k; i++) { 42 save[i] = i; 43 } 44 for (i = k; i < nelm; i++) { 45 save[i] = i - k; 46 } 47 48 bcopy(save, arr, sizeof(arr)); 49 dt_timer_start("25-75 (qsort)"); 50 qsort(arr, nelm, sizeof(arr[0]), cmp_int); 51 time_elapsed = dt_timer_stop("25-75 (qsort)"); 52 T_LOG("25-75 (qsort): %lld ms", time_elapsed / NSEC_PER_MSEC); 53 for (i = 1; i < nelm; i++) { 54 if(arr[i - 1] > arr[i]) { 55 T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]); 56 break; 57 } 58 } 59 60 bcopy(save, arr, sizeof(arr)); 61 dt_timer_start("25-75 (Bentley)"); 62 qsort1(arr, nelm, sizeof(arr[0]), cmp_int); 63 time_elapsed = dt_timer_stop("25-75 (Bentley)"); 64 T_LOG("25-75 (Bentley): %lld ms", time_elapsed / NSEC_PER_MSEC); 65 for (i = 1; i < nelm; i++) { 66 if(arr[i - 1] > arr[i]) { 67 T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]); 68 break; 69 } 70 } 71 // ----- 50-50 ----- 72 73 k = nelm/2; 74 for (i = 0; i < k; i++) { 75 save[i] = i; 76 } 77 for (i = k; i < nelm; i++) { 78 save[i] = i - k; 79 } 80 81 bcopy(save, arr, sizeof(arr)); 82 dt_timer_start("50-50 (qsort)"); 83 qsort(arr, nelm, sizeof(arr[0]), cmp_int); 84 time_elapsed = dt_timer_stop("50-50 (qsort)"); 85 T_LOG("50-50 (qsort): %lld ms", time_elapsed / NSEC_PER_MSEC); 86 for (i = 1; i < nelm; i++) { 87 if(arr[i - 1] > arr[i]) { 88 T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]); 89 break; 90 } 91 } 92 93 bcopy(save, arr, sizeof(arr)); 94 dt_timer_start("50-50 (Bentley)"); 95 qsort1(arr, nelm, sizeof(arr[0]), cmp_int); 96 time_elapsed = dt_timer_stop("50-50 (Bentley)"); 97 T_LOG("50-50 (Bentley): %lld ms", time_elapsed / NSEC_PER_MSEC); 98 for (i = 1; i < nelm; i++) { 99 if(arr[i - 1] > arr[i]) { 100 T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]); 101 break; 102 } 103 } 104 105 // ----- median-of-3 killer ----- 106 107 k = nelm / 2; 108 for (i = 1; i <= k; i++) { 109 if(i % 2 == 1) { 110 save[i - 1] = i; 111 save[i] = k + i; 112 } 113 save[k + i - 1] = 2 * i; 114 } 115 116 bcopy(save, arr, sizeof(arr)); 117 dt_timer_start("median-of-3 killer (qsort)"); 118 qsort(arr, nelm, sizeof(arr[0]), cmp_int); 119 time_elapsed = dt_timer_stop("median-of-3 killer (qsort)"); 120 T_LOG("median-of-3 (qsort): %lld ms", time_elapsed / NSEC_PER_MSEC); 121 for (i = 1; i < nelm; i++) { 122 if(arr[i - 1] > arr[i]) { 123 T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]); 124 } 125 } 126 127 bcopy(save, arr, sizeof(arr)); 128 dt_timer_start("median-of-3 killer (Bentley)"); 129 qsort1(arr, nelm, sizeof(arr[0]), cmp_int); 130 time_elapsed = dt_timer_stop("median-of-3 killer (Bentley)"); 131 T_LOG("median-of-3 (Bentley): %lld ms", time_elapsed / NSEC_PER_MSEC); 132 for (i = 1; i < nelm; i++) { 133 if(arr[i - 1] > arr[i]) { 134 T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]); 135 } 136 } 137 138 // ----- random ----- 139 140 for (i = 0; i < nelm; i++) { 141 save[i] = random(); 142 } 143 144 bcopy(save, arr, sizeof(arr)); 145 dt_timer_start("random (qsort)"); 146 qsort(arr, nelm, sizeof(arr[0]), cmp_int); 147 time_elapsed = dt_timer_stop("random (qsort)"); 148 T_LOG("random (qsort): %lld ms", time_elapsed / NSEC_PER_MSEC); 149 for (i = 1; i < nelm; i++) { 150 if(arr[i - 1] > arr[i]) { 151 T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]); 152 } 153 } 154 155 156 bcopy(save, arr, sizeof(arr)); 157 dt_timer_start("random (Bentley)"); 158 qsort1(arr, nelm, sizeof(arr[0]), cmp_int); 159 time_elapsed = dt_timer_stop("random (Bentley)"); 160 T_LOG("random (Bentley): %lld ms", time_elapsed / NSEC_PER_MSEC); 161 for (i = 1; i < nelm; i++) { 162 if(arr[i - 1] > arr[i]) { 163 T_ASSERT_FAIL("arr[%d]=%d > arr[%d]=%d", i - 1, arr[i - 1], i, arr[i]); 164 } 165 } 166 167 T_PASS("All tests completed successfully."); 168 } 169 170 /* qsort1 -- qsort interface implemented by faster quicksort */ 171 172 #define SWAPINIT(a, es) swaptype = \ 173 (a - (char*) 0) % sizeof(long) || es % sizeof(long) ? 2 : \ 174 es == sizeof(long) ? 0 : 1; 175 #define swapcode(TYPE, parmi, parmj, n) { \ 176 long i = (n) / sizeof(TYPE); \ 177 register TYPE *pi = (TYPE *) (parmi); \ 178 register TYPE *pj = (TYPE *) (parmj); \ 179 do { \ 180 register TYPE t = *pi; \ 181 *pi++ = *pj; \ 182 *pj++ = t; \ 183 } while (--i > 0); \ 184 } 185 static void swapfunc(char *a, char *b, int n, int swaptype) 186 { if (swaptype <= 1) swapcode(long, a, b, n) 187 else swapcode(char, a, b, n) 188 } 189 #define swap(a, b) \ 190 if (swaptype == 0) { \ 191 long t = * (long *) (a); \ 192 * (long *) (a) = * (long *) (b); \ 193 * (long *) (b) = t; \ 194 } else \ 195 swapfunc(a, b, es, swaptype) 196 #define vecswap(a, b, n) if (n > 0) swapfunc(a, b, n, swaptype) 197 198 #define min(x, y) ((x)<=(y) ? (x) : (y)) 199 200 static char *med3(char *a, char *b, char *c, int (*cmp)(const void *, const void *)) 201 { 202 return cmp(a, b) < 0 ? 203 (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ) ) 204 : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ) ); 205 } 206 207 static void 208 qsort1(void *aa, size_t n, size_t es, 209 int (*cmp)(const void *, const void *)) 210 { 211 char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 212 int d, r, swaptype; 213 char *a = aa; 214 215 SWAPINIT(a, es); 216 if (n < 7) { /* Insertion sort on small arrays */ 217 for (pm = a + es; pm < a + n*es; pm += es) 218 for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es) 219 swap(pl, pl-es); 220 return; 221 } 222 pm = a + (n/2) * es; 223 if (n > 7) { 224 pl = a; 225 pn = a + (n-1) * es; 226 if (n > 40) { /* On big arrays, pseudomedian of 9 */ 227 d = (n/8) * es; 228 pl = med3(pl, pl+d, pl+2*d, cmp); 229 pm = med3(pm-d, pm, pm+d, cmp); 230 pn = med3(pn-2*d, pn-d, pn, cmp); 231 } 232 pm = med3(pl, pm, pn, cmp); /* On mid arrays, med of 3 */ 233 } 234 swap(a, pm); /* On tiny arrays, partition around middle */ 235 pa = pb = a + es; 236 pc = pd = a + (n-1)*es; 237 for (;;) { 238 while (pb <= pc && (r = cmp(pb, a)) <= 0) { 239 if (r == 0) { swap(pa, pb); pa += es; } 240 pb += es; 241 } 242 while (pb <= pc && (r = cmp(pc, a)) >= 0) { 243 if (r == 0) { swap(pc, pd); pd -= es; } 244 pc -= es; 245 } 246 if (pb > pc) break; 247 swap(pb, pc); 248 pb += es; 249 pc -= es; 250 } 251 pn = a + n*es; 252 r = min(pa-a, pb-pa); vecswap(a, pb-r, r); 253 r = min(pd-pc, pn-pd-es); vecswap(pb, pn-r, r); 254 if ((r = pb-pa) > es) qsort1(a, r/es, es, cmp); 255 if ((r = pd-pc) > es) qsort1(pn-r, r/es, es, cmp); 256 }